An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows

D. Cattaruzza, N. Absi, D. Feillet, D. Vigo

Abstract

The Multi-Commodity Multi-Trip Vehicle Routing Problem with Time Windows calls for the determination of a routing planning to serve a set of customers that require products belonging to incompatible commodities. Two commodities are incompatible if they cannot be transported together into the same vehicle. Vehicles are allowed to perform several trips during the working day. The objective is to minimize the number of used vehicles. We propose an Iterated Local Search that outperforms the previous algorithm designed for the problem. Moreover, we conduct an analysis on the benefit that can be obtained introducing the multi-trip aspect at the fleet dimensioning level. Results on classical VRPTW instances show that, in some cases, the fleet can be halved. © 2014 Elsevier Ltd. All rights reserved.
Original languageEnglish
Pages (from-to)257-267
Number of pages11
JournalComputers and Operations Research
Volume51
Issue numberNovember
Early online date20 Jun 2014
DOIs
StatePublished - 2014

Cite this

Cattaruzza, D.; Absi, N.; Feillet, D.; Vigo, D. / An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows.

In: Computers and Operations Research, Vol. 51, No. November, 2014, p. 257-267.

Research output: Scientific - peer-reviewArticle

@article{3bc61f9a20b64fdd8a04162b89b5bea1,
title = "An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows",
abstract = "The Multi-Commodity Multi-Trip Vehicle Routing Problem with Time Windows calls for the determination of a routing planning to serve a set of customers that require products belonging to incompatible commodities. Two commodities are incompatible if they cannot be transported together into the same vehicle. Vehicles are allowed to perform several trips during the working day. The objective is to minimize the number of used vehicles. We propose an Iterated Local Search that outperforms the previous algorithm designed for the problem. Moreover, we conduct an analysis on the benefit that can be obtained introducing the multi-trip aspect at the fleet dimensioning level. Results on classical VRPTW instances show that, in some cases, the fleet can be halved. © 2014 Elsevier Ltd. All rights reserved.",
author = "D. Cattaruzza and N. Absi and D. Feillet and D. Vigo",
year = "2014",
doi = "10.1016/j.cor.2014.06.006",
volume = "51",
pages = "257--267",
journal = "Computers and Operations Research",
issn = "0305-0548",
publisher = "Elsevier Limited",
number = "November",

}

An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows. / Cattaruzza, D.; Absi, N.; Feillet, D.; Vigo, D.

In: Computers and Operations Research, Vol. 51, No. November, 2014, p. 257-267.

Research output: Scientific - peer-reviewArticle

TY - JOUR

T1 - An iterated local search for the multi-commodity multi-trip vehicle routing problem with time windows

AU - Cattaruzza,D.

AU - Absi,N.

AU - Feillet,D.

AU - Vigo,D.

PY - 2014

Y1 - 2014

N2 - The Multi-Commodity Multi-Trip Vehicle Routing Problem with Time Windows calls for the determination of a routing planning to serve a set of customers that require products belonging to incompatible commodities. Two commodities are incompatible if they cannot be transported together into the same vehicle. Vehicles are allowed to perform several trips during the working day. The objective is to minimize the number of used vehicles. We propose an Iterated Local Search that outperforms the previous algorithm designed for the problem. Moreover, we conduct an analysis on the benefit that can be obtained introducing the multi-trip aspect at the fleet dimensioning level. Results on classical VRPTW instances show that, in some cases, the fleet can be halved. © 2014 Elsevier Ltd. All rights reserved.

AB - The Multi-Commodity Multi-Trip Vehicle Routing Problem with Time Windows calls for the determination of a routing planning to serve a set of customers that require products belonging to incompatible commodities. Two commodities are incompatible if they cannot be transported together into the same vehicle. Vehicles are allowed to perform several trips during the working day. The objective is to minimize the number of used vehicles. We propose an Iterated Local Search that outperforms the previous algorithm designed for the problem. Moreover, we conduct an analysis on the benefit that can be obtained introducing the multi-trip aspect at the fleet dimensioning level. Results on classical VRPTW instances show that, in some cases, the fleet can be halved. © 2014 Elsevier Ltd. All rights reserved.

U2 - 10.1016/j.cor.2014.06.006

DO - 10.1016/j.cor.2014.06.006

M3 - Article

VL - 51

SP - 257

EP - 267

JO - Computers and Operations Research

T2 - Computers and Operations Research

JF - Computers and Operations Research

SN - 0305-0548

IS - November

ER -