An Effective Matheuristic Approach for Robust Bus Driver Rostering with Uncertain Daily Working Hours

The bus driver rostering problem (BDRP) is a significant problem in public transportation that aims at assigning drivers to bus routes over a given time period while reducing system costs as well as inconveniences. In this work, a mixed-integer linear mathematical model is presented for the problem with the objective of minimizing the total assignment and driver dissatisfaction costs. Uncertainty is considered for the maximum daily working hours of drivers, which appears on the right-hand side of a block of constraints. A set of scenarios regarding the uncertain parameters and robust optimization are considered. A matheuristic approach is proposed consisting of a hybridization of particle swarm optimization (PSO), simulated annealing (SA) and mathematical programming of sub-problems based on the concept of partial optimization metaheuristic under special intensification conditions (POPMUSIC). It is shown that the proposed matheuristic is an effective approach for solving the BDRP by examining its performance on a set of benchmark instances.