THE MULTIPLE-VEHICLE ROUTING PROBLEM

In this paper, a branch and bound optimizing procedure is presented for finding the routes which minimize travel time for several vehicles to serve customers from a central depot. The branches are formed by successively eliminating infeasibilities (such as partial routes) which do not connect to the depot or routes which exceed constraints on the vehicles. The lower bounds are determined by solving assignment problems without regard to feasibility. A good initial upper bound is determined by using a heuristic. The method requires more computing time than for the m-salesman traveling salesman problem; and some suggestions are made for reducing this time. (A) /TRRL/

• Corporate Authors:

  University of British Columbia, Vancouver

  Faculty of Commerce
  Vancouver, British Columbia  Canada 
• Authors:
  • O'NEIL, B F
  • Whybark, D C
• Publication Date: 1975

Language

• English

Media Info

• Features: Figures; References;
• Pagination: p. 153-163
• Serial:
  • LOGISTICS AND TRANSPORTATION REVIEW
  • Volume: 11
  • Issue Number: 2

Subject/Index Terms

• TRT Terms: Digital computers; Heuristic methods; Itinerary; Mathematical models; Networks; Optimization; Routing; Traffic assignment; Travel time; Trip length
• Uncontrolled Terms: Optimum; Transportation networks
• ITRD Terms: 8673: Digital computer; 699: Itinerary; 697: Journey time; 6473: Mathematical model; 679: Traffic assignment
• Subject Areas: Highways; Operations and Traffic Management; I71: Traffic Theory;

Filing Info

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