A Column Generation Approach to the Urban Transit Crew Scheduling Problem

Martin Desrochers and François Soumis
Additional contact information
Martin Desrochers: GERAD, École des H.E.C., 5255, avenue Decelles, Montréal, Québec, Canada, H3T 1V6
François Soumis: GERAD, École Polytechnique, P.O. Box 6129, Stn. A, Montréal, Québec, Canada, H3C 3A7

Transportation Science, 1989, vol. 23, issue 1, 1-13

Abstract: 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.

Date: 1989
References: Add references at CitEc
Citations: View citations in EconPapers (69)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.23.1.1 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:23:y:1989:i:1:p:1-13

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().