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

v. 25 n. 1 (2017)

Seção

Artigos

Licença

Ao submeter um manuscrito para publicação neste periódico, todos os seus autores concordam, antecipada e irrestritamente, com os seguintes termos:

  1. Os autores mantém os direitos autorais e concedem à Revista TRANSPORTES o direito de primeira publicação do manuscrito, sem nenhum ônus financeiro, e abrem mão de qualquer outra remuneração pela sua publicação pela ANPET.
  2. Ao ser submetido à Revista TRANSPORTES, o manuscrito fica automaticamente licenciado sob a Licença Creative Commons Attribution, que permite o compartilhamento do trabalho com reconhecimento da autoria e da publicação inicial neste periódico.
  3. Os autores têm autorização para assumir contratos adicionais separadamente, para distribuição não exclusiva da versão do trabalho publicada neste periódico (ex.: publicar em repositório institucional ou como capítulo de livro), com reconhecimento da publicação inicial nesta revista, desde que tal contrato não implique num endosso do conteúdo do manuscrito ou do novo veículo pela ANPET.
  4. Os autores têm permissão e são estimulados a publicar e distribuir seu trabalho online (ex.: em repositórios institucionais ou na sua página pessoal) depois de concluído o processo editorial. Como a Revista TRANSPORTES é de acesso livre, os autores são estimulados a usar links para o site da Revista TRANSPORTES nesses casos.
  5. Os autores garantem ter obtido a devida autorização dos seus empregadores para a transferência dos direitos nos termos deste acordo, caso esses empregadores possuam algum direito autoral sobre o manuscrito. Além disso, os autores assumem toda e qualquer responsabilidade sobre possíveis infrações ao direito autoral desses empregadores, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.
  6. Os autores assumem toda responsabilidade sobre o conteúdo do trabalho, incluindo as devidas e necessárias autorizações para divulgação de dados coletados e resultados obtidos, isentando a ANPET e a Revista TRANSPORTES de toda e qualquer responsabilidade neste sentido.