Groupe d’études et de recherche en analyse des décisions

G-2020-69

Preference-based and cyclic bus driver rostering problem with fixed days off

, , et

Given a set of predefined duties and groups of drivers, the duty assignment problem with group-based driver preferences (DAPGDP) aims at building rosters that cover all the duties over a predetermined cyclic horizon while respecting a set of rules (hard constraints), balancing the workload between the drivers and satisfying as much as possible the driver preferences (soft constraints). In this paper, we first model the DAPGDP as a mixed-integer linear program that minimizes the number of preference violations while maintaining the workload balance of the solutions within a certain margin relative to the optimal one. Since this model is hard to solve for large instances, we propose two new matheuristics. The first one restricts the search space by preassigning duties to rosters based on an optimal solution to the duty assignment problem with fixed days off. The second algorithm makes use of a set partitioning problem to decompose rosters consisting of a large number of positions into subrosters of smaller sizes. In a series of computational experiments conducted on real-world instances, we show that these matheuristics can be used to produce high-quality solutions for large instances of the DAPGDP (i.e., with up to 333 drivers and 1509 duties) within relatively short computational times.

, 30 pages