Preference-based and cyclic bus driver rostering problem with fixed days off
Document Type
Journal Article
Publication Date
2021
Subject Area
mode - bus, planning - methods, ridership - drivers
Keywords
Duty assignment, Driver rostering, Driver preferences, Mixed-integer programming, Public transit
Abstract
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.
Rights
Permission to publish the abstract has been given by SpringerLink, copyright remains with them.
Recommended Citation
Er-Rbib, S., Desaulniers, G., Elhallaoui, I., & Munroe, P. (2021). Preference-based and cyclic bus driver rostering problem with fixed days off. Public Transport, Vol. 13, pp. 251–286.
