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

Safae Er-Rbib (), Guy Desaulniers (), Issmail Elhallaoui () and Patrick Munroe ()
Additional contact information
Safae Er-Rbib: GERAD & Polytechnique de Montréal
Guy Desaulniers: GERAD & Polytechnique de Montréal
Issmail Elhallaoui: GERAD & Polytechnique de Montréal
Patrick Munroe: GERAD & Polytechnique de Montréal

Public Transport, 2021, vol. 13, issue 2, No 1, 286 pages

Abstract: 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.

Keywords: Duty assignment; Driver rostering; Driver preferences; Mixed-integer programming; Public transit (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://link.springer.com/10.1007/s12469-021-00268-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:pubtra:v:13:y:2021:i:2:d:10.1007_s12469-021-00268-y

Ordering information: This journal article can be ordered from
https://www.springer ... search/journal/12469

DOI: 10.1007/s12469-021-00268-y

Access Statistics for this article

Public Transport is currently edited by Stefan Voß

More articles in Public Transport from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().