Route Minimization Heuristic for the Vehicle Routing Problem with Multiple Pauses

Alexey Khmelev ()
Additional contact information
Alexey Khmelev: Novosibirsk State University

A chapter in Operations Research Proceedings 2015, 2017, pp 265-271 from Springer

Abstract: Abstract In this work we introduce the vehicle routing problem with multiple pauses, where the fleet is heterogeneous in terms of capacity and drivers availability. Each shift has a time interval when the driver is available and a set of breaks that needs to be scheduled in the route during this shift. The objective is to minimize the number of vehicles and the travel distance. To tackle large instances, we develop a three-phase local search algorithm taking multiple breaks into account by introducing an ejection pool and randomized variable neighborhood descent as local improvement procedure. For effective break scheduling, we develop a special dynamic programming routine. Computational experiments are done on the data set provided by a delivery company situated in Novosibirsk, Russia. The instances contain 1000 customers and 30 vehicles. Experiments show effectiveness of our algorithm. It substantially reduces the fleet and travel distance.

Keywords: Time Window; Travel Distance; Vehicle Route Problem; Vehicle Rout Problem With Time Window; Variable Neighborhood Descent (search for similar items in EconPapers)
Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

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:oprchp:978-3-319-42902-1_36

Ordering information: This item can be ordered from
http://www.springer.com/9783319429021

DOI: 10.1007/978-3-319-42902-1_36

Access Statistics for this chapter

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