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

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.