Paper Info
Title
A Bus Driver Scheduling Problem: a new mathematical model and a GRASP approximate solution
Abstract
This paper addresses the problem of determining the best scheduling for Bus Drivers, a $\mathcal{NP}$ -hard problem consisting of finding the minimum number of drivers to cover a set of Pieces-Of-Work (POWs) subject to a variety of rules and regulations that must be enforced such as spreadover and working time. This problem is known in literature as Crew Scheduling Problem and, in particular in public transportation, it is designated as Bus Driver Scheduling Problem. We propose a new mathematical formulation of a Bus Driver Scheduling Problem under special constraints imposed by Italian transportation rules. Unfortunately, this model can only be usefully applied to small or medium size problem instances. For large instances, a Greedy Randomized Adaptive Search Procedure (GRASP) is proposed. Results are reported for a set of real-word problems and comparison is made with an exact method. Moreover, we report a comparison of the computational results obtained with our GRASP procedure with the results obtained by Huisman et al. (Transp. Sci. 39(4):491---502, 2005).
Year
DOI
Venue
2011
10.1007/s10732-010-9141-3
Journal of Heuristics
Keywords
Field
DocType
Crew and Bus Driver Scheduling Problem,Transportation,Meta-heuristics,GRASP
Mathematical optimization,GRASP,Job shop scheduling,Fair-share scheduling,Computer science,Crew scheduling,Nurse scheduling problem,Greedy randomized adaptive search procedure,Dynamic priority scheduling,Metaheuristic
Journal
Volume
Issue
ISSN
16
3
1381-1231
Citations 
PageRank 
References 
12
0.61
13
Authors
3
Name
Order
Citations
PageRank
Renato De Leone111817.54
Paola Festa228725.32
Emilia Marchitto3181.37