AN INTEGER PROGRAMMING APPROACH TO THE VEHICLE SCHEDULING PROBLEM

This paper describes an integer programming formulation of the vehicle scheduling problem and illustrates how such a formulation can be extended to incorporate restrictions on work load, coverage and service that occur in real world vehicle scheduling problems. The integer programme is solved using the revised simplex method additional constraints being introduced to retain integrality during convergence. The feasible region of this integer programme is initially restricted so that only routes constructed through sets of radially contiguous locations are considered. The effect of relaxing these over-constraints is explored. The method is demonstrated on fifteen problems ranging in size from 21 to 100 locations and the results generally show an improvement on previously published results. This is particularly true of the larger problems. This method compares favourably with other methods in computational efficiency. /Author/TRRL/

• Corporate Authors:

  Pergamon Press, Incorporated

  Maxwell House, Fairview Park
  Elmsford, NY  United States  10523
• Authors:
  • Foster, B A
  • Ryan, D M
• Publication Date: 1976

Language

• English

Media Info

• Features: Figures; References; Tables;
• Pagination: p. 367-384
• Serial:
  • Operational Research Quarterly /UK/
  • Volume: 27
  • Issue Number: 2,I

Subject/Index Terms

• TRT Terms: Computer programming; Constraints; Level of service; Routes; Scheduling; Vehicles
• Uncontrolled Terms: Programming
• ITRD Terms: 1057: Air transport network; 6473: Mathematical model; 1054: Network (traffic); 9055: Operational research; 143: Planning; 9072: Selection; 1186: Timetable
• Subject Areas: Highways; Planning and Forecasting; Vehicles and Equipment;

Filing Info

• Accession Number: 00147651
• Record Type: Publication
• Source Agency: Transport and Road Research Laboratory (TRRL)
• Report/Paper Numbers: Analytic
• Files: ITRD, TRIS
• Created Date: Jun 22 1977 12:00AM