A BRANCH AND BOUND ALGORITHM FOR THE MULTIPLE DEPOT VEHICLE SCHEDULING PROBLEM

This article describes analyses carried out to solve the scheduling problem for freight vehicles assigned to various different depots. The vehicle scheduling problem concerns the assigning of a set of time-tabled trips to vehicles so as to minimize a given cost function. We consider the np-hard multiple depot case in which, in addition, one has to assign vehicles to depots. Different lower bounds based on assignment relaxation and on connectivity constraints are presented and combined in an effective bounding procedure. A strong dominance procedure derived from new dominance criteria is also described. A branch and bound algorithm is finally proposed. Computational results are given.

• Corporate Authors:

  John Wiley & Sons, Incorporated

  111 River Street
  Hoboken, NJ  United States  07030-6000
• Authors:
  • Carpaneto, G
  • Dell'amico, M
  • Fishetti, M
  • Toth, P
• Publication Date: 1989-8

Language

• English

Media Info

• Pagination: p. 531-548
• Serial:
  • NETWORKS
  • Volume: 19
  • Issue Number: 5

Subject/Index Terms

• TRT Terms: Calculation; Costs; Freight transportation; Mathematical analysis; Methodology; Minimization; Operations research; Timetables; Travel
• Uncontrolled Terms: Minimum
• ITRD Terms: 6471: Analysis (math); 6464: Calculation; 224: Cost; 741: Goods traffic; 698: Journey; 9102: Method; 9046: Minimum; 9055: Operational research; 1186: Timetable
• Subject Areas: Finance; Freight Transportation;

Filing Info

• Accession Number: 00498640
• Record Type: Publication
• Source Agency: Transport and Road Research Laboratory (TRRL)
• Files: ITRD, TRIS
• Created Date: Sep 30 1990 12:00AM