A Column Generation Approach to the Urban Transit Crew Scheduling Problem

The urban transit crew scheduling problem arises in mass transit organizations which have to create minimal cost bus driver schedules respecting both the collective agreement with labor unions and the bus schedule. We propose a column generation approach to solve the transit crew scheduling problem. The column generation approach decomposes the problem into two parts. The set covering problem chooses a schedule from already known feasible workdays. The second subproblem is a shortest path problem with resource constraints and is used to propose new feasible workdays to improve the current solution of the set covering problem. The approach has been successfully tested on real-life problems.