Solving Vehicle Routing Problems with Stochastic and Correlated Travel Times and Makespan Objectives

In this paper, the authors examine a vehicle routing problem with a makespan objective incorporating both stochastic and correlated travel times, which is usually not considered in routing problems. As an alternative to simulation, the authors develop an approach based on extreme-value theory to estimate the expected makespan (and standard deviation) and show how this approach can be embedded within an existing routing heuristic. The authors present results that demonstrate the impact of different correlation patterns and levels of correlation on route planning using real-world motivated instances. Depending on the particular objective, cost savings of up to 13.76% can be obtained by considering correlation.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01765558
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Jan 22 2021 3:11PM