Efficient Neighborhood Evaluations for the Vehicle Routing Problem with Multiple Time Windows

Maaike Hoogeboom (), Wout Dullaert (), David Lai () and Daniele Vigo ()
Additional contact information
Maaike Hoogeboom: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands
Wout Dullaert: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands
David Lai: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands
Daniele Vigo: Department of Supply Chain Analytics, Vrije Universiteit Amsterdam, 1081 HV Amsterdam, Netherlands; Department of Electrical, Electronic and Information Engineering “Guglielmo Marconi,” University of Bologna, 40136 Bologna, Italy

Transportation Science, 2020, vol. 54, issue 2, 400-416

Abstract: In the vehicle routing problem with multiple time windows (VRPMTW), a single time window must be selected for each customer from the multiple time windows provided. Compared with classical vehicle routing problems with only a single time window per customer, multiple time windows increase the complexity of the routing problem. To minimize the duration of any given route, we present an exact polynomial time algorithm to efficiently determine the optimal start time for servicing each customer. The proposed algorithm has a reduced worst-case and average complexity than existing exact algorithms. Furthermore, the proposed exact algorithm can be used to efficiently evaluate neighborhood operations during a local search resulting in significant acceleration. To examine the benefits of exact neighborhood evaluations and to solve the VRPMTW, the proposed algorithm is embedded in a simple metaheuristic framework generating numerous new best known solutions at competitive computation times.

Keywords: vehicle routing; multiple time windows; metaheuristics (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (6)

Downloads: (external link)
https://doi.org/10.1287/trsc.2019.0912 (application/pdf)

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:inm:ortrsc:v:54:y:2020:i:2:p:400-416

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().