A column generation approach for the driver scheduling problem with staff cars

Shyam S. G. Perumal (), Jesper Larsen (), Richard M. Lusby (), Morten Riis () and Tue R. L. Christensen ()
Additional contact information
Shyam S. G. Perumal: Technical University of Denmark
Jesper Larsen: Technical University of Denmark
Richard M. Lusby: Technical University of Denmark
Morten Riis: QAMPO ApS
Tue R. L. Christensen: QAMPO ApS

Public Transport, 2022, vol. 14, issue 3, No 7, 705-738

Abstract: Abstract Given a set of timetabled bus trips, transport companies are faced with the challenge of finding a feasible driver schedule that covers all trips and abides by various labor union regulations. The regulations are primarily concerned with providing sufficient breaks for the drivers during the day. Practical limitations in the city network enforce drivers to travel by cars between bus stops to have breaks. Transport companies have a limited number of cars, known as staff cars, which have to be returned to their respective depots at the end of the day. The simultaneous scheduling of drivers and staff cars for the drivers is known as the driver scheduling problem with staff cars (DSPSC). It is estimated that the DSPSC accounts for 60% of a bus company’s operational expense, and this paper proposes a column generation approach that attempts to minimize operational expense. The column-generation framework iterates between a master problem, a subproblem for generating driver variables and a subproblem for generating staff car variables. The subproblem related to the drivers is formulated as a resource constrained shortest path problem, which is solved by a dynamic programming approach. Several heuristic branching strategies are explored to find integer solutions. The proposed methodology is tested on eight real-life instances from seven Northern European bus companies. A comparison with a state-of-the-art mixed integer programming (MIP) solver and an adaptive large neighborhood search (ALNS) heuristic indicate that the column generation approach provides improved solutions for six instances and the average improvement is 1.45%.

Keywords: Transportation; Driver scheduling problem; Column generation; Heuristics (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s12469-021-00279-9 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:pubtra:v:14:y:2022:i:3:d:10.1007_s12469-021-00279-9

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12469

DOI: 10.1007/s12469-021-00279-9

Access Statistics for this article

Public Transport is currently edited by Stefan Voß

More articles in Public Transport from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().