Variable neighborhood search for the stochastic and dynamic vehicle routing problem

Briseida Sarasola (), Karl Doerner (), Verena Schmid () and Enrique Alba ()

Annals of Operations Research, 2016, vol. 236, issue 2, 425-461

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 %. Copyright Springer Science+Business Media New York 2016

Keywords: Variable neighborhood search; Vehicle routing problem; Dynamic requests; Stochastic demands (search for similar items in EconPapers)
Date: 2016
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10479-015-1949-7 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:236:y:2016:i:2:p:425-461:10.1007/s10479-015-1949-7

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-015-1949-7

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().