Groupe d’études et de recherche en analyse des décisions

G-87-32

A Column Generation Approach to the Urban Transit Crew Scheduling Problem

et

The urban transit crew scheduling problem arises in mass transit corporations who have to create minimal cost bus driver schedule respecting both the collective agreement and the bus schedule. This problem is often modeled as a set covering problem where each column represents a driver's workday and each row represents a task. In previous solution methods, a set covering problem including only a subset of the feasible workdays was created and a heuristic solution using only these workdays was found by solving this set covering problem. We propose a column generation approach to solve the transit crew scheduling problem. The column generation approach decomposes the problem in two parts. The set covering problem chooses a schedule from already known feasible workdays. The subproblem is modeled using 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 tested successfully on real-life problems.

, 18 pages