Waiting Strategies for Dynamic Vehicle Routing

Dynamic vehicle routing with previously unknown customer requests arriving over time has become increasingly important as new technologies such as global positioning systems (GPS) allow the assignment of new requests to vehicles in real time. This paper studied a dynamic vehicle routing problem (VRP) where a single new customer arrives at a uniformly chosen random location after the vehicles have left the depot. The problem of choosing an appropriate waiting strategy that would maximize the probability for being able to insert the new customer into an otherwise fixed tour was then examined. The paper shows that the problem of finding an optimal waiting strategy is NP-complete no matter whether the time of arrival is known or unknown.

  • Availability:
  • Authors:
    • Branke, Jyrgen
    • Middendorf, Martin
    • Noeth, Guntram
    • Dessouky, Maged
  • Publication Date: 2005-8


  • English

Media Info

  • Media Type: Print
  • Features: Appendices; Figures; References; Tables;
  • Pagination: pp 298-312
  • Serial:

Subject/Index Terms

Filing Info

  • Accession Number: 01004164
  • Record Type: Publication
  • Files: TRIS, ATRI
  • Created Date: Sep 2 2005 3:16PM