A study of different metaheuristics to solve the urban transit crew scheduling problem
Um estudo de diferentes metaheurísticas para resolver o problema de programação de tripulações do sistema de transporte público
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.
- Record URL:
-
Availability:
- Find a library where document is available. Order URL: http://worldcat.org/issn/22381031
-
Supplemental Notes:
- Abstract used with permission of the Brazilian Transportation Planning Society (BTPS)
-
Authors:
- Silva, Gustavo Peixoto
- Reis, Allexandre Fortes da Silva
- Publication Date: 2014-10
Language
- English
- Portuguese
Media Info
- Media Type: Digital/other
- Features: Figures; References; Tables;
- Pagination: pp 227-251
-
Serial:
- Journal of Transport Literature
- Volume: 8
- Issue Number: 4
- Publisher: Brazilian Transport Planning Society
- ISSN: 2238-1031
- Serial URL: http://www.scielo.br/scielo.php?script=sci_serial&pid=2238-1031&lng=en&nrm=iso
Subject/Index Terms
- TRT Terms: Heuristic methods; Neighborhoods; Personnel; Scheduling; Urban transit
- Geographic Terms: Belo Horizonte (Brazil)
- Subject Areas: Operations and Traffic Management; Public Transportation; I70: Traffic and Transport;
Filing Info
- Accession Number: 01531625
- Record Type: Publication
- Files: TRIS
- Created Date: Jul 25 2014 4:16PM