A column generation approach to the urban transit crew scheduling problem. (English) Zbl 0668.90043

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.


90B35 Deterministic scheduling theory in operations research
90C10 Integer programming
65K05 Numerical mathematical programming methods
90C09 Boolean programming
90C05 Linear programming
90C27 Combinatorial optimization
90C90 Applications of mathematical programming
Full Text: DOI