Please use this identifier to cite or link to this item: http://www.repositorio.ufop.br/handle/123456789/5750
Title: A study of different metaheuristics to solve the urban transit crew scheduling problem.
Other Titles: Um estudo de diferentes metaheurísticas para resolver o problema de programação de tripulações do sistema de transporte público.
Authors: Silva, Gustavo Peixoto
Reis, Allexandre Fortes da Silva
Keywords: Crew scheduling problem
Metaheuristics
Variable neighborhood search
Iterated local search
Issue Date: 2014
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.
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. _____________________________________________________________________________________________
ABSTRACT: This paper explores different local search methods associated with the metaheuristic Iterated Local Search (ILS) to solve the Crew Scheduling Problem (CSP) of a Public Transportation System. The results from ILS were compared to those obtained in a previous work from the same authors that used the Variable Neighborhood Search (VNS). Initially, both metaheuristics were implemented using, as local search, the classical First Improvement Method, performing “guided” reallocation and exchange of crew tasks. The guided reallocation/exchange replaces random components from the classical method by searching the best position to insert the task. Further, the Very Large-scale Neighborhood Search (VLNS) technique was used as a local search procedure in the metaheuristics. This technique has substantially more neighbors than the 2-opt neighborhoods, since it performs a chain exchange of tasks from different crews. Both versions of metaheuristics were applied to a set of real data from a company operating in the city of Belo Horizonte, producing more economical schedules than those adopted by the company. The results are presented and discussed in this work.
URI: http://www.repositorio.ufop.br/handle/123456789/5750
ISSN: 22381031
metadata.dc.rights.license: Autorização concedida ao Repositório Institucional da UFOP pelo Journal of Transport Literature em 11/05/2015 para depositar uma cópia eletrônica dos artigos publicados por esse periódico em que ao menos um dos autores é aluno ou professor da UFOP.
Appears in Collections:DECOM - Artigos publicados em periódicos

Files in This Item:
File Description SizeFormat 
ARTIGO_StudyDifferentMetaheuristics.pdf1,3 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.