A study of different metaheuristics to solve the urban transit crew scheduling problem.
No Thumbnail Available
Date
2014
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Este artigo explora diferentes métodos de busca associados à metaheurística Iterated Local Search (ILS) para resolver o Problema de Programação de Tripulações de um Sistema de Transporte Público. Os resultados obtidos com o ILS foram comparados com um trabalho prévio, dos mesmos autores, que utilizou a metaheurísica Variable Neighborhood Search (VNS). Inicialmente ambas as metaheurísticas foram implementadas utilizando como procedimento de busca o método clássico First Improvement, realizando realocação e troca “guiada” das tarefas das tripulações. Esta realocação/troca guiada substitui a componente randômica dos métodos clássicos por uma busca da melhor posição para a inserção das tarefas. Posteriormente, foi utilizada a técnica denominada Very Large-scale Neighborhood Search (VLNS) como procedimento de busca nas respectivas metaheurísticas. Esta técnica produz um número muito maior de vizinhos do que vizinhanças 2-opt, pois ela permite a realocação de tarefas entre uma série de diferentes tripulações. Ambas as versões das metaheurísticas foram aplicadas a um conjunto de dados reais de uma empresa que opera em Belo Horizonte, produzindo programações mais econômicas do que aquelas adotadas pela empresa. Os resultados são apresentados e discutidos neste trabalho.
Description
Keywords
Crew scheduling problem, Metaheuristics, Variable neighborhood search, Iterated local search
Citation
SILVA, G. P.; REIS, A. F. da S. A study of different metaheuristics to solve the urban transit crew scheduling problem. Journal of Transport Literature, v. 8, n. 4, p. 227-251, out. 2014. Disponível em: <http://www.scielo.br/pdf/jtl/v8n4/v8n4a10.pdf>. Acesso em: 27 out. 2015.