A study of different metaheuristics to solve the urban transit crew scheduling problem.

Simple item page
dc.contributor.authorSilva, Gustavo Peixoto
dc.contributor.authorReis, Allexandre Fortes da Silva
dc.date.accessioned2015-11-12T18:38:00Z
dc.date.available2015-11-12T18:38:00Z
dc.date.issued2014
dc.description.abstractEste 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.pt_BR
dc.description.abstractenThis 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.
dc.description.abstractenhttp://dx.doi.org/10.1590/2238-1031.jtl.v8n4a9
dc.identifier.citationSILVA, 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.pt_BR
dc.identifier.issn2238-1031
dc.identifier.urihttp://www.repositorio.ufop.br/handle/123456789/5750
dc.language.isopt_BRpt_BR
dc.rights.licenseAutorizaçã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.pt_BR
dc.subjectCrew scheduling problempt_BR
dc.subjectMetaheuristicspt_BR
dc.subjectVariable neighborhood searchpt_BR
dc.subjectIterated local searchpt_BR
dc.titleA study of different metaheuristics to solve the urban transit crew scheduling problem.pt_BR
dc.title.alternativeUm estudo de diferentes metaheurísticas para resolver o problema de programação de tripulações do sistema de transporte público.pt_BR
dc.typeArtigo publicado em periodicopt_BR
Files
Original bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
ARTIGO_StudyDifferentMetaheuristics.pdf
Size:
1.27 MB
Format:
Adobe Portable Document Format
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
2.57 KB
Format:
Item-specific license agreed upon to submission
Description:
Download
Collections
DECOM - Artigos publicados em periódicos