Uso da técnica de busca em vizinhança de grande porte para a programação da escala de motoristas de ônibus urbano
DOI:
https://doi.org/10.14295/transportes.v18i2.422Abstract
Resumo: Este artigo apresenta uma nova abordagem para a resolução do Problema de Programação de Tripulações no Sistema de Transporte Público (PPT). O modelo se baseia na metaheurística GRASP cuja busca local é realizada pelo método da Busca em Vizinhança de Grande Porte, conhecida na literatura como Very Large-Scale Neighborhood Search. O grande diferencial da aplicação desta técnica de busca para o PPT é que, além de incorporar os movimentos de realocação e troca de tarefas, realizados tradicionalmente, ela também permite considerar trocas do tipo 3-optimal, 4-optimal, até o limite de n-optimal, para uma solução com n tripulações. A implementação da heurística proposta foi testada com dados de problemas reais de uma empresa que opera em Belo Horizonte, e os resultados foram comparados com as soluções adotadas pela empresa. Desta forma foi possível observar que o modelo apresentado neste trabalho produziu soluções mais econômicas do que aquelas praticadas pela empresa.
Abstract: This paper presents a new approach to solve the Crew Scheduling Problem (CSP) for public mass transport system. The proposed model is based on the GRASP metaheuristic framework, where the local search is performed by the Very Large-Scale Neighborhood (VLSN) search technique. The great differential of this search technique applied to the CSP is that, in addition to task reassigning and swapping movements, adopted in previous work, it also allows considering 3-optimal, 4-optimal, up to n-optimal task movements, for a solution with n crews, yielding to improved solutions. The proposed heuristic was tested with data from real problems of a bus company operating in the city of Belo Horizonte, and the results compared to the manual solution adopted by the company. Thus it was observed that the model presented in this work have produced more economical solutions than those used by the company.Downloads
Downloads
Published
How to Cite
Issue
Section
License
Authors who submit papers for publication by TRANSPORTES agree to the following terms:
- Authors retain copyright and grant TRANSPORTES the right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors may enter into separate, additional contractual arrangements for the non-exclusive distribution of this journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in TRANSPORTES.
- Authors are allowed and encouraged to post their work online (e.g., in institutional repositories or on their website) after publication of the article. Authors are encouraged to use links to TRANSPORTES (e.g., DOIs or direct links) when posting the article online, as TRANSPORTES is freely available to all readers.
- Authors have secured all necessary clearances and written permissions to published the work and grant copyright under the terms of this agreement. Furthermore, the authors assume full responsibility for any copyright infringements related to the article, exonerating ANPET and TRANSPORTES of any responsibility regarding copyright infringement.
- Authors assume full responsibility for the contents of the article submitted for review, including all necessary clearances for divulgation of data and results, exonerating ANPET and TRANSPORTES of any responsibility regarding to this aspect.
