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.


  • English

Media Info

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

Subject/Index Terms

Filing Info

  • Accession Number: 01155767
  • Record Type: Publication
  • Report/Paper Numbers: 10-1476
  • Files: BTRIS, TRIS, TRB
  • Created Date: Jan 25 2010 10:39AM