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

Maaike Hoogeboom, Wout Dullaert, David Lai, Daniele Vigoa

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

3 Citaten (Scopus)

Samenvatting

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.

Originele taal-2Engels
Pagina's (van-tot)400-416
Aantal pagina's17
TijdschriftTransportation Science
Volume54
Nummer van het tijdschrift2
DOI's
StatusGepubliceerd - 2020
Extern gepubliceerdJa

Vingerafdruk

Duik in de onderzoeksthema's van 'Efficient neighborhood evaluations for the vehicle routing problem with multiple time windows'. Samen vormen ze een unieke vingerafdruk.

Citeer dit