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

作     者：Er-Rbib, Safae Desaulniers, Guy Elhallaoui, Issmail Munroe, Patrick 

作者机构：Gerad Montreal PQ Canada Polytech Montreal Montreal PQ Canada 

出 版 物：《PUBLIC TRANSPORT》 (公共运输)

年 卷 期：2021年第13卷第2期

页      面：251-286页

核心收录：

学科分类：08[工学] 0823[工学-交通运输工程] 

基　　金：Natural Sciences and Engineering Research Council of Canada [2017-05683] 

主　　题：Duty assignment Driver rostering Driver preferences Mixed-integer programming Public transit 

摘      要：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.