Integrated and sequential solution methods for the cyclic bus driver rostering problem

Safae Er-Rbib, Guy Desaulniers, Issmail El Hallaoui and Abderrahman Bani

Journal of the Operational Research Society, 2021, vol. 72, issue 4, 764-779

Abstract: Given a set of duties (sequences of activities to be accomplished by a bus driver on a specific day) to be operated over a cyclic one-week horizon and groups of drivers with similar characteristics, the cyclic bus driver rostering problem (CBDRP) consists of building driver schedules that cover every duty exactly once, can cycle from one week to the next in the same driver group, and satisfy a set of labor law and collective agreement rules. The objective aims at balancing as much as possible the workload between the drivers. In this paper, we first propose an integrated mixed-integer linear programming model for the CBDRP that assigns simultaneously days off and duties to bus drivers. This model turns out to be very hard to solve to optimality without providing an initial solution. Based on this model, we introduce a new two-step matheuristic that can compute high-quality solutions. Using such a solution as an input to a commercial solver, the integrated model can be solved much more rapidly. Our computational results obtained on real-world CBDRP instances involving up to 333 drivers and 1509 duties show that these initial solutions are optimal in most cases and, consequently, that the proposed matheuristic is very efficient by itself.

Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2019.1700187 (text/html)
Access to full text is restricted to subscribers.

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:taf:tjorxx:v:72:y:2021:i:4:p:764-779

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2019.1700187

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().