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

Desrochers, Martin; Soumis, François

Transp. Sci. 23, No. 1, 1-13 (1989).

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.

MSC:

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

Keywords:

urban transit crew scheduling; mass transit organizations; minimal cost bus driver schedules; set covering; shortest path; resource constraints