IMPACS--A BUS CREW SCHEDULING SYSTEM USING A SET COVERING FORMULA

A computerized bus crew scheduling system, known as IMPACS, that uses a set covering formulation is described. The crew scheduling problem is converted into a set covering problem by generating a very large set of possible duties, each of which is associated with a cost. Each duty is assigned to one of six classes corresponding to scheduling periods and durations. The covering problem is solved by relaxing the constraints that the values of the variables should be integer. The resulting linear programming problem is then solved and, unless the solution is already integer, an integer solution is found using a branch-and-bound algorithm. Heuristic improvement routines have also been developed. IMPACS has been tested and implemented by London Buses Limited, Greater Manchester Transport, and Cleveland Transit, and has been commissioned by Strathclyde Passenger Transport Executive.

• Corporate Authors:

  University of Leeds

  School of Geography, Woodhouse Lane
  Leeds, West Yorkshire  England  LS2 9JT
• Authors:
  • Smith, B M
  • Wren, A
• Publication Date: 1986-8

Media Info

• Pagination: 19 p.

Subject/Index Terms

• TRT Terms: Algorithms; Bus drivers; Information processing; Linear programming; Scheduling
• Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; Public Transportation; I72: Traffic and Transport Planning;

Filing Info

• Accession Number: 00477098
• Record Type: Publication
• Source Agency: National Technical Information Service
• Report/Paper Numbers: LU/DCS-R-210
• Files: TRIS
• Created Date: Nov 30 1988 12:00AM