A column generation based heuristic for a bus driver rostering problem

Abstract

The Bus Driver Rostering Problem (BDRP) aims at determining optimal work-schedules for the drivers of a bus company, covering all work duties, respecting the Labor Law and the regulation, while minimizing company costs. A new decomposition model for the BDRP was recently proposed and the problem was addressed by a metaheuristic combining column generation and an evolutionary algorithm. This paper proposes a new heuristic, which is integrated in the column generation, allowing for the generation of complete or partial rosters at each iteration, instead of generating single individual work-schedules. The new heuristic uses the dual solution of the restricted master problem to guide the order by which duties are assigned to drivers. The knowledge about the problem was used to propose a variation procedure which changes the order by which a new driver is selected for the assignment of a new duty. Sequential and random selection methods are proposed. The inclusion of the rotation process results in the generation of rosters with better distribution of work among drivers and also affects the column generation performance. Computational tests assess the proposed heuristic ability to generate good quality rosters and the impact of the distinct variation procedures is discussed.