Variable neighborhood search for the stochastic and dynamic vehicle routing problem

Briseida Sarasola, Karl Franz Dörner, Verena Schmid, Enrique Alba

Publications: Contribution to journalArticlePeer Reviewed

Abstract

In this paper, the authors consider the vehicle routing problem (VRP) with stochastic demand and/or dynamic requests. The classical VRP consists of determining a set of routes starting and ending at a depot that provide service to a set of customers. Stochastic demands are only revealed when the vehicle arrives at the customer location; dynamic requests mean that new orders from previously unknown customers can be received and scheduled over time. The variable neighborhood search algorithm (VNS) proposed in this study can be extended by sampling for stochastic scenarios and adapted for the dynamic setting. We use standard sets of benchmark instances to evaluate our algorithms. When applying sampling based VNS, on average we were able to improve results obtained by a classical VNS by 4.39 %. Individual instances could be improved by up to 8.12 %. In addition, the proposed VNS framework matches 32 out of 40 best known solutions and provides one new best solution. In the dynamic case, VNS improves on existing results and provides new best solutions for 7 out of 21 instances. Finally, this study offers results for stochastic and dynamic scenarios. Our experiments show that the sampling based dynamic VNS provides better results when the demand deviation is small, and reduces the excess route duration by 45–90 %.
Original languageEnglish
Pages (from-to)425–461
Number of pages37
JournalAnnals of Operations Research
Volume236
Issue number2
Early online date14 Aug 2015
DOIs
Publication statusPublished - Jan 2016

Austrian Fields of Science 2012

  • 101015 Operations research
  • 502017 Logistics

Keywords

  • Variable neighborhood search
  • Vehicle routing problem
  • Dynamic requests
  • Stochastic demands
  • TRAVEL
  • TABU SEARCH
  • ALGORITHM
  • DEMANDS
  • DEPOT
  • CUSTOMERS
  • DISPATCHING PROBLEM
  • CONSTRAINTS
  • TIME WINDOWS
  • VNS

Fingerprint

Dive into the research topics of 'Variable neighborhood search for the stochastic and dynamic vehicle routing problem'. Together they form a unique fingerprint.

Cite this