Skip to main content

Research Repository

Advanced Search

Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm

Constantino, Ademir Aparecido; de Mendonca, Candido F.X.; de Araujo, Silvio Alexandre; Landa-Silva, Dario; Calvi, Rogerio; dos Santos, Allainclair Flausino

Authors

Ademir Aparecido Constantino

Candido F.X. de Mendonca

Silvio Alexandre de Araujo

Rogerio Calvi

Allainclair Flausino dos Santos



Abstract

The bus driver scheduling problem (BDSP) under study consists in finding a set of duties that covers the bus schedule from a Brazilian public transportation bus company with the objective of minimizing the total cost. A deterministic 2-phase heuristic algorithm is proposed using multiple assignment problems that arise from a model based on a weighted multipartite graph. In the first phase, the algorithm constructs an initial feasible solution by solving a number of assignment problems. In the second phase, the algorithm attempts to improve the solution by two different procedures. One procedure takes the whole set of duties and divides them in a set of partial duties which are recombined. The other procedure seeks to improve single long duties by eliminating the overtime time and inserting it into another duty. Computational tests are performed using large-scale real-world data with more than 2,300 tasks and random instances extracted from real data. Three different objective functions are analyzed. The overall results indicate that the proposed approach is competitive to solve large BDSP.

Journal Article Type Article
Publication Date May 28, 2017
Journal Journal of Universal Computer Science
Print ISSN 0948-695X
Electronic ISSN 0948-6968
Publisher Graz University of Technology, Institut für Informationssysteme und Computer Medien
Peer Reviewed Peer Reviewed
Volume 23
Issue 5
APA6 Citation Constantino, A. A., de Mendonca, C. F., de Araujo, S. A., Landa-Silva, D., Calvi, R., & dos Santos, A. F. (2017). Solving a large real-world bus driver scheduling problem with a multi-assignment based heuristic algorithm. Journal of Universal Computer Science, 23(5),
Keywords bus driver scheduling, crew management, heuristic, large real-world instances, transportation
Publisher URL http://www.jucs.org/jucs_23_5/solving_a_large_real
Copyright Statement Copyright information regarding this work can be found at the following address: http://eprints.nottingh.../end_user_agreement.pdf

Files

dls_jucs2017.pdf (209 Kb)
PDF

Copyright Statement
Copyright information regarding this work can be found at the following address: http://eprints.nottingham.ac.uk/end_user_agreement.pdf





You might also like



Downloadable Citations

;