Routing a heterogeneous fleet of vehicles

Roberto Baldacci, Maria Battarra, Daniele Vigo

Research output: Contribution to journalReview article

95 Citations (Scopus)

Abstract

In the well-known Vehicle Routing Problem (VRP) a set of identical vehicles, based at a central depot, is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. An important variant of the VRP arises when a fleet of vehicles characterized by different capacities and costs is available for distribution activities. The problem is known as the Mixed Fleet VRP or as the Heterogeneous Fleet VRP. This chapter gives an overview of approaches from the literature to solve heterogeneous VRPs. In particular, we classify the different variants described in the literature and, as no exact algorithm has been presented for any variants of heterogeneous VRP, we review the lower bounds and the heuristic algorithms proposed. Computational results, comparing the performance of the different heuristic algorithms on benchmark instances, are also discussed.

LanguageEnglish
Pages3-27
Number of pages25
JournalOperations Research/ Computer Science Interfaces Series
Volume43
DOIs
StatusPublished - 1 Dec 2008

Keywords

  • Heterogeneous vehicle routing problem

ASJC Scopus subject areas

  • Computer Science(all)
  • Management Science and Operations Research

Cite this

Routing a heterogeneous fleet of vehicles. / Baldacci, Roberto; Battarra, Maria; Vigo, Daniele.

In: Operations Research/ Computer Science Interfaces Series, Vol. 43, 01.12.2008, p. 3-27.

Research output: Contribution to journalReview article

@article{1d398c4455744f18a0c147acd1842142,
title = "Routing a heterogeneous fleet of vehicles",
abstract = "In the well-known Vehicle Routing Problem (VRP) a set of identical vehicles, based at a central depot, is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. An important variant of the VRP arises when a fleet of vehicles characterized by different capacities and costs is available for distribution activities. The problem is known as the Mixed Fleet VRP or as the Heterogeneous Fleet VRP. This chapter gives an overview of approaches from the literature to solve heterogeneous VRPs. In particular, we classify the different variants described in the literature and, as no exact algorithm has been presented for any variants of heterogeneous VRP, we review the lower bounds and the heuristic algorithms proposed. Computational results, comparing the performance of the different heuristic algorithms on benchmark instances, are also discussed.",
keywords = "Heterogeneous vehicle routing problem",
author = "Roberto Baldacci and Maria Battarra and Daniele Vigo",
year = "2008",
month = "12",
day = "1",
doi = "10.1007/978-0-387-77778-8_1",
language = "English",
volume = "43",
pages = "3--27",
journal = "Operations Research/ Computer Science Interfaces Series",
issn = "1387-666X",
publisher = "Springer Verlag",

}

TY - JOUR

T1 - Routing a heterogeneous fleet of vehicles

AU - Baldacci, Roberto

AU - Battarra, Maria

AU - Vigo, Daniele

PY - 2008/12/1

Y1 - 2008/12/1

N2 - In the well-known Vehicle Routing Problem (VRP) a set of identical vehicles, based at a central depot, is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. An important variant of the VRP arises when a fleet of vehicles characterized by different capacities and costs is available for distribution activities. The problem is known as the Mixed Fleet VRP or as the Heterogeneous Fleet VRP. This chapter gives an overview of approaches from the literature to solve heterogeneous VRPs. In particular, we classify the different variants described in the literature and, as no exact algorithm has been presented for any variants of heterogeneous VRP, we review the lower bounds and the heuristic algorithms proposed. Computational results, comparing the performance of the different heuristic algorithms on benchmark instances, are also discussed.

AB - In the well-known Vehicle Routing Problem (VRP) a set of identical vehicles, based at a central depot, is to be optimally routed to supply customers with known demands subject to vehicle capacity constraints. An important variant of the VRP arises when a fleet of vehicles characterized by different capacities and costs is available for distribution activities. The problem is known as the Mixed Fleet VRP or as the Heterogeneous Fleet VRP. This chapter gives an overview of approaches from the literature to solve heterogeneous VRPs. In particular, we classify the different variants described in the literature and, as no exact algorithm has been presented for any variants of heterogeneous VRP, we review the lower bounds and the heuristic algorithms proposed. Computational results, comparing the performance of the different heuristic algorithms on benchmark instances, are also discussed.

KW - Heterogeneous vehicle routing problem

UR - http://www.scopus.com/inward/record.url?scp=84888619233&partnerID=8YFLogxK

U2 - 10.1007/978-0-387-77778-8_1

DO - 10.1007/978-0-387-77778-8_1

M3 - Review article

VL - 43

SP - 3

EP - 27

JO - Operations Research/ Computer Science Interfaces Series

T2 - Operations Research/ Computer Science Interfaces Series

JF - Operations Research/ Computer Science Interfaces Series

SN - 1387-666X

ER -