Efficient neighborhood evaluations for the Vehicle Routing Problem with Multiple Time Windows

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
JournalTransportation Science
DOIs
Publication statusAccepted/In press - 6 Jan 2020

Fingerprint

Vehicle routing
evaluation
customer
time
Polynomials

Keywords

  • vehicle routing
  • multiple time windows
  • metaheuristics

Cite this

@article{525491006ffe45fb978f6e58725980dc,
title = "Efficient neighborhood evaluations for the Vehicle Routing Problem with Multiple Time Windows",
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",
author = "Maaike Hoogeboom and Wout Dullaert and David Lai and D. Vigo",
year = "2020",
month = "1",
day = "6",
doi = "10.1287/trsc.2019.0912",
language = "English",
journal = "Transportation Science",
issn = "0041-1655",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",

}

TY - JOUR

T1 - Efficient neighborhood evaluations for the Vehicle Routing Problem with Multiple Time Windows

AU - Hoogeboom, Maaike

AU - Dullaert, Wout

AU - Lai, David

AU - Vigo, D.

PY - 2020/1/6

Y1 - 2020/1/6

N2 - 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.

AB - 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.

KW - vehicle routing

KW - multiple time windows

KW - metaheuristics

U2 - 10.1287/trsc.2019.0912

DO - 10.1287/trsc.2019.0912

M3 - Article

JO - Transportation Science

JF - Transportation Science

SN - 0041-1655

ER -