Aplicação de um algoritmo genético ao problema de rodízio de tripulações do sistema de transporte público urbano

Autores

  • Leandro do Carmo Martins Programa da Pós-Graduação Departamento de Computação
  • Gustavo Peixoto Silva Departamento de Computação Universidade Federal de Ouro Preto http://orcid.org/0000-0002-9158-2370

DOI:

https://doi.org/10.14295/transportes.v25i1.1074

Palavras-chave:

Problema de rodízio de tripulações, Programação de tripulações, Algoritmos genéticos.

Resumo

Este trabalho aborda a resolução do Problema de Rodízio de Tripulações (PRT) de empresas do sistema de trans-porte público. O PRT consiste em atribuir uma sequência de jornadas de trabalho aos tripulantes de uma empresa para um dado horizonte de planejamento, com o intuito de minimizar seus custos totais. O custo fixo é dado pelo número de tripulações necessárias para realizar todas as jornadas e os custos variáveis correspondem ao total de horas extras ou ociosas, acumuladas por cada tripulação no período. Na resolução deste problema, são consideradas tanto as restrições operacionais quanto as restrições trabalhistas de uma dada empresa. Neste trabalho, o PRT foi resolvido em duas etapas: a primeira consiste em atribuir os dias de folga, minimizando o número de tripulações. A segunda etapa consiste em alocar as jornadas a serem realizadas, minimizando as horas extras e ociosas no período. As duas etapas foram resolvidas utilizando um Algoritmo Genético ainda não aplicado em casos brasileiros. O algoritmo foi desenvolvido para resolver um caso real e seus resultados foram comparados com a solução exata de um modelo de Programação Linear Inteira, mostrando ser competitivo.

Downloads

Não há dados estatísticos.

Biografia do Autor

Leandro do Carmo Martins, Programa da Pós-Graduação Departamento de Computação

Formado em Ciências da Computação, atualmente está fazendo mestrado no Programa de Pós-Graduação em Ciências da Computação do Departamento de Computação da Universidade Federal de Ouro Preto.

Gustavo Peixoto Silva, Departamento de Computação Universidade Federal de Ouro Preto

Professor Associado 3 do Departamento de Computação da Universidade Federal de Ouro Preto. Fez mestrado em Matemática Aplicada e Computacional na UNICAMP, doutorado em Engenharia de Transportes na POLI/USP com estágio "sandwich" na Universidade de Leeds, Reino Unido e pós-doutorado no Departamento de Engenharia de Transportes da POLI/USP.

Referências

Ahuja, R. K., Magnanti, T. L. e Orlin, J. B. (1993) Network Flows: Theory, Algorithms, and Applications. Prentice Hall, New Jersey.

Bianco, L., BieIli, M., Mingozzi, A., Ricciardelli, S. e Spadoni, M. (1992) A heuristic procedure for the crew rostering problem, European Journal of Operations Research, 58(2), p. 272–283.

DOI:10.1016/0377-2217(92)90213-S

Boas, M. G. V. e Silva, G. P. (2014) Modelos de Programação Inteira para o Problema de Rodízio de Tripulações de Ônibus Urbano. Anais do XLVI Simpósio Brasileiro de Pesquisa Operacional, p. 1-12.

Caprara, A., Monaci, M. e Toth, P. (2003) Models and algorithms for a staff scheduling problem, Mathematical Programming, 98(1–3), p. 445–476.

DOI:10.1007/s10107-003-0413-7

Carraresi, P. e Gallo, G. (1984) A multi-level bottleneck assignment approach to the bus drivers rostering problem, European Journal of Operational Research, 16(2), p. 163–173.

DOI:10.1016/0377-2217(84)90071-7

Ernst, A. T.; Jiang, H.; Krishnamoorthy, M. e Sier, D. (2004) Staff scheduling and rostering: A review of applications, methods and models, European Journal of Operational Research, 153, p. 3–27.

DOI:10.1016/S0377-2217(03)00095-X

Goldberg, D. E. (1989) Genetic Algorithms in Search, Optimization and Machine Learning. Addison-Wesley, Berkeley.

Holland, J. H. (1975) Adaptation in Natural and Artificial Systems. University of Michigan Press.

Kruskal, W. H.. e Wallis, W. A. (1952) Use of ranks in the one criterium variance analysis, Journal of American Statistical Association, 47(260), p. 583-621.

DOI:10.1080/01621459.1952.10483441

Leite, P. V. S. (2012) Resolução do Problema de Rodízio de Tripulações Usando um Modelo de Fluxo em Redes. Trabalho de Conclusão de Curso, Departamento de Engenharia de Controle e Automação, Universidade Federal de Ouro Preto.

Mayrink, V. T. M. e Silva, G. P. (2013) Otimização do rodízio de tripulações do sistema de transporte público, Journal of Transport Literature, 7(3), p. 192–213.

DOI:10.1590/S2238-10312013000300009

Silva, G. P. e Prates, R. F. C. (2014) Otimização da Escala Mensal de Motoristas de Ônibus Urbano Utilizando a Metaheurística Variable Neighborhood Search, TRANSPORTES, 22(1), p. 31–43.

DOI:10.14295/transportes.v22i1.698

Talbi, E. G. (2009) Metaheuristics: from design to implementation. John Wiley & Sons.

Toffolo, T. A., Souza, M. J. F. e Silva, G. P. (2005) Resolução do Problema de Rodízio de Tripulações de Ônibus Urbano via Simulated Annealing e Iterated Local Search, Anais do XIX Congresso de pesquisa e Ensino em Transportes, ANPET, 2, p. 657–668.

Whitley, D. (1994) A Genetic Algorithm Tutorial, Computer Science Department, Colorado State University, Fort Collins, CO 80523.

DOI:10.1007/BF00175354

Downloads

Publicado

01-03-2017

Como Citar

Martins, L. do C., & Silva, G. P. (2017). Aplicação de um algoritmo genético ao problema de rodízio de tripulações do sistema de transporte público urbano. TRANSPORTES, 25(1), 31–40. https://doi.org/10.14295/transportes.v25i1.1074

Edição

Seção

Artigos