Valid Inequalities for the Fleet Size and Mix Vehicle Routing Problem with Fixed Costs

Roberto Baldacci, Maria Battarra, Daniele Vigo

Research output: Contribution to journalArticle

18 Citations (Scopus)

Abstract

In the well-known vehicle routing problem (VRP), a set of identical vehicles located 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 mixed fleet of vehicles, characterized by different capacities and costs, is available for distribution activities. The problem is known as fleet size and mix VRP with fixed costs FSMF and has several practical applications. In this article, we present a new mixed integer programming formulation for FSMF based on a two-commodity network flow approach. New valid inequalities are proposed to strengthen the linear programming relaxation of the mathematical formulation. The effectiveness of the proposed cuts is extensively tested on benchmark instances.

LanguageEnglish
Pages178-189
JournalNetworks
Volume54
Issue number4
DOIs
StatusPublished - 2009

Fingerprint

Vehicle routing
Costs
Integer programming
Linear programming

Cite this

Valid Inequalities for the Fleet Size and Mix Vehicle Routing Problem with Fixed Costs. / Baldacci, Roberto; Battarra, Maria; Vigo, Daniele.

In: Networks, Vol. 54, No. 4, 2009, p. 178-189.

Research output: Contribution to journalArticle

Baldacci, Roberto ; Battarra, Maria ; Vigo, Daniele. / Valid Inequalities for the Fleet Size and Mix Vehicle Routing Problem with Fixed Costs. In: Networks. 2009 ; Vol. 54, No. 4. pp. 178-189.
@article{a0616c1c83d04584b85596a55de868d9,
title = "Valid Inequalities for the Fleet Size and Mix Vehicle Routing Problem with Fixed Costs",
abstract = "In the well-known vehicle routing problem (VRP), a set of identical vehicles located 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 mixed fleet of vehicles, characterized by different capacities and costs, is available for distribution activities. The problem is known as fleet size and mix VRP with fixed costs FSMF and has several practical applications. In this article, we present a new mixed integer programming formulation for FSMF based on a two-commodity network flow approach. New valid inequalities are proposed to strengthen the linear programming relaxation of the mathematical formulation. The effectiveness of the proposed cuts is extensively tested on benchmark instances.",
author = "Roberto Baldacci and Maria Battarra and Daniele Vigo",
year = "2009",
doi = "10.1002/net.v54:4",
language = "English",
volume = "54",
pages = "178--189",
journal = "Networks",
issn = "0028-3045",
publisher = "Wiley-Liss Inc.",
number = "4",

}

TY - JOUR

T1 - Valid Inequalities for the Fleet Size and Mix Vehicle Routing Problem with Fixed Costs

AU - Baldacci, Roberto

AU - Battarra, Maria

AU - Vigo, Daniele

PY - 2009

Y1 - 2009

N2 - In the well-known vehicle routing problem (VRP), a set of identical vehicles located 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 mixed fleet of vehicles, characterized by different capacities and costs, is available for distribution activities. The problem is known as fleet size and mix VRP with fixed costs FSMF and has several practical applications. In this article, we present a new mixed integer programming formulation for FSMF based on a two-commodity network flow approach. New valid inequalities are proposed to strengthen the linear programming relaxation of the mathematical formulation. The effectiveness of the proposed cuts is extensively tested on benchmark instances.

AB - In the well-known vehicle routing problem (VRP), a set of identical vehicles located 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 mixed fleet of vehicles, characterized by different capacities and costs, is available for distribution activities. The problem is known as fleet size and mix VRP with fixed costs FSMF and has several practical applications. In this article, we present a new mixed integer programming formulation for FSMF based on a two-commodity network flow approach. New valid inequalities are proposed to strengthen the linear programming relaxation of the mathematical formulation. The effectiveness of the proposed cuts is extensively tested on benchmark instances.

U2 - 10.1002/net.v54:4

DO - 10.1002/net.v54:4

M3 - Article

VL - 54

SP - 178

EP - 189

JO - Networks

T2 - Networks

JF - Networks

SN - 0028-3045

IS - 4

ER -