Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows

Maaike Hoogeboom, Wout Dullaert, David Lai, Daniele Vigoa

Research output: Contribution to JournalArticleAcademicpeer-review

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.

Original languageEnglish
Pages (from-to)400-416
Number of pages17
JournalTransportation Science
Volume54
Issue number2
Early online date6 Jan 2020
DOIs
Publication statusPublished - Mar 2020

Keywords

  • Metaheuristics
  • Multiple time windows
  • Vehicle routing

Fingerprint Dive into the research topics of 'Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows'. Together they form a unique fingerprint.

Cite this