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

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.

Keywords:

• Public transit
• driver rostering
• cyclic rosters
• days off scheduling
• duty assignment
• integer programming
• matheuristic

Acknowledgements

We are thankful to Charles Fleurent and Marc Gendron from GIRO Inc. for introducing this problem to us, providing the data, and discussing our progress throughout the project. We gratefully acknowledge the financial support provided by GIRO Inc. and the Natural Sciences and Engineering Research Council of Canada under the grant RDCPJ 4634633-14.

Notes

1 To always return a nonnegative value, we define the modulo function as follows: $a\hspace{1em}\mathrm{mod}n=a-n\lfloor \frac{a}{n}\rfloor .$