Comparison of Two Algorithms for Stochastic Time-Dependent Vehicle-Routing Problem

Vehicle-routing problems (VRP) have been studied in depth. Many variants of the problem exist, most of them trying to find a set of routes with the shortest distance possible for a fleet of vehicles. This paper combines two important variants, the stochastic VRP and the time-dependent VRP, to form and define the Stochastic Time-Dependent VRP. Two algorithms for solving the stochastic time-depended VRP are compared, an efficient heuristic that is a new variant of the well-known saving algorithm, and a genetic algorithm. Both algorithms incorporate simulation that enables an estimate of each route’s probability of being the quickest. The two algorithms yield results that are at most 10% off the optimal solutions (when possible to compare), yet are very different in their running times. Such results are similar to the performance of the saving algorithm when compared to the capacitated vehicle-routing problem.

• Corporate Authors:

  Transportation Research Board

  500 Fifth Street, NW
  Washington, DC  United States  20001
• Authors:
  • Nahum, Oren E
  • Hadas, Yuval
• Conference:
  • Transportation Research Board 89th Annual Meeting
  • Location: Washington DC, United States
  • Date: 2010-1-10 to 2010-1-14
• Date: 2010

Language

• English

Media Info

• Media Type: DVD
• Features: References; Tables;
• Pagination: 18p
• Monograph Title: TRB 89th Annual Meeting Compendium of Papers DVD

Subject/Index Terms

• TRT Terms: Freight traffic; Genetic algorithms; Heuristic methods; Optimization; Routing; Stochastic processes
• Subject Areas: Data and Information Technology; Freight Transportation;

Filing Info

• Accession Number: 01155767
• Record Type: Publication
• Report/Paper Numbers: 10-1476
• Files: BTRIS, TRIS, TRB
• Created Date: Apr 30 2010 8:35AM