CREW-OPT: CREW SCHEDULING BY COLUMN GENERATION. FROM THE BOOK COMPUTER-AIDED TRANSIT SCHEDULING

The urban transit crew scheduling problem arises in mass transit corporations who have to create minimal cost bus driver schedules 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 i.e., a given bus trip. In previous solution methods, a subset of the feasible workdays was created and a heuristic solution using only these workdays was found by solving the resulting 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 as a shortest path problem with resource constraints and proposes new feasible workdays to improve the actual solution of the set covering problem. The approach was tested successfully on real-life problems.

• Availability:
  • Find a library where document is available. Order URL: http://worldcat.org/isbn/038719441X
• Supplemental Notes:
  • Proceedings of the Fourth International Workshop on Computer-Aided Scheduling of Public Transport, Hamburg, July 28-31, 1987.
• Corporate Authors:

  Springer Verlag

  175 5th Avenue
  New York, NY  United States  10010
• Authors:
  • DESROCHERS, M
  • Soumis, F
• Publication Date: 1988

Media Info

• Features: References;
• Pagination: p. 83-90
• Monograph Title: Computer-Aided Transit Scheduling. Proceedings of the Fourth International Workshop on Computer-Aided Scheduling of Public Transport, Hamburg, Germany, July 28-31, 1987

Subject/Index Terms

• TRT Terms: Bus drivers; Buses; Computers; Mathematical models; Scheduling
• Uncontrolled Terms: Computer aided scheduling
• Subject Areas: Operations and Traffic Management; Public Transportation;

Filing Info

• Accession Number: 00484141
• Record Type: Publication
• ISBN: 038719441X
• Files: TRIS
• Created Date: May 31 1989 12:00AM