Novas heurísticas para o problema de escalonamento de atripulações

• Ano de defesa: 2005
• Autor(a) principal: Geraldo Regis Mauri
• Orientador(a): Luiz Antonio Nogueira Lorena
• Banca de defesa: Marcone Jamilson Freitas Souza, Edson Luis França Senne
• Tipo de documento: Dissertação
• Tipo de acesso: Acesso aberto
• Idioma: por
• Instituição de defesa: Instituto Nacional de Pesquisas Espaciais (INPE)
• Programa de Pós-Graduação: Programa de Pós-Graduação do INPE em Computação Aplicada
• País: BR
• Resumo em Inglês: The crew scheduling problem consists in attributing to the crews the job of driving vehicles, in such a way that trips of dierent lines assisted by a company are executed with the smallest possible cost. This process is of fundamental importance in planning the operations for the public transportation sector and belongs to a class of dicult problems. Several methods have been applied to this problem presenting dierent results. This work reviews some of them presented in the literature, and presents a hybrid methodology, not yet explored, named ATP/PL, to solve such problem, searching varied solutions for problems considering real characteristics. The ATP/PL is based in a Column Generation technique and implemented through Population Training Algorithm with Linear Programming interaction. Besides, the obtained solutions are compared against solutions obtained by the Simulated Annealing metaheuristic, that had presented good results for real problems in previous works.
• Link de acesso: http://urlib.net/sid.inpe.br/mtc-m16@80/2006/06.23.12.07

O problema de escalonamento de tripulações consiste na atribuição da tarefa de condução dos veículos às tripulações, de tal forma que todas as viagens realizadas por uma empresa sejam executadas com o menor custo possível. Esse processo é uma etapa de fundamental importância no planejamento das operações para uma empresa do setor de transporte coletivo e pertence à classe de problemas de difícil solução. Vários métodos tem sido aplicados para resolver tal problema, mostrando resultados bem variados. Este trabalho faz uma revisão de alguns trabalhos correlatos encontrados na literatura, e apresenta uma metodologia híbrida, ainda não explorada, denominada ATP/PL, para resolver tal problema, com o objetivo de alcançar soluções variadas para problemas que considerem características de problemas reais. A ATP/PL é baseada na técnica de Geração de Colunas e é implementada através da interação entre o Algoritmo de Treinamento Populacional com a Programação Linear. Além disso, as soluções obtidas por tal metodologia são comparadas com soluções obtidas pela Metaheurística Simulated Annealing, que por sua vez apresentou excelentes resultados para problemas reais em trabalhos anteriores.