An exact algorithm for the period routing problem

Roberto Baldacci; Enrico Bartolini; Aristide Mingozzi; Andrea Valletta

doi:10.1287/opre.1100.0875

An exact algorithm for the period routing problem

Roberto Baldacci^*, Enrico Bartolini, Aristide Mingozzi, Andrea Valletta

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

66 Citations (Scopus)

Abstract

This paper presents an exact algorithm for solving strategic and tactical multiperiod vehicle routing problems that can be modeled as period vehicle routing problems (PVRPs). The PVRP is defined on a time horizon of several days and consists of assigning appropriate combinations of delivery to customers and designing a set of delivery routes for every day of the planning period. The objective is to service all customers assigned to each day minimizing the overall routing cost. This paper describes an integer programming formulation of the PVRP that is used to derive different lower bounds and an exact solution method. Computational results on test instances from the literature and on new sets of test instances show the effectiveness of the proposed method.

Original language	English
Pages (from-to)	228-241
Number of pages	14
Journal	Operations Research
Volume	59
Issue number	1
DOIs	https://doi.org/10.1287/opre.1100.0875
Publication status	Published - Jan 2011
Externally published	Yes

Keywords

Dual ascent
Dynamic programming
Period vehicle routing
Set partitioning

Access to Document

10.1287/opre.1100.0875

Cite this

@article{9dc6b779a5df4251bd30250062c662e5,

title = "An exact algorithm for the period routing problem",

abstract = "This paper presents an exact algorithm for solving strategic and tactical multiperiod vehicle routing problems that can be modeled as period vehicle routing problems (PVRPs). The PVRP is defined on a time horizon of several days and consists of assigning appropriate combinations of delivery to customers and designing a set of delivery routes for every day of the planning period. The objective is to service all customers assigned to each day minimizing the overall routing cost. This paper describes an integer programming formulation of the PVRP that is used to derive different lower bounds and an exact solution method. Computational results on test instances from the literature and on new sets of test instances show the effectiveness of the proposed method.",

keywords = "Dual ascent, Dynamic programming, Period vehicle routing, Set partitioning",

author = "Roberto Baldacci and Enrico Bartolini and Aristide Mingozzi and Andrea Valletta",

year = "2011",

month = jan,

doi = "10.1287/opre.1100.0875",

language = "English",

volume = "59",

pages = "228--241",

journal = "Operations Research",

issn = "0030-364X",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "1",

}

TY - JOUR

T1 - An exact algorithm for the period routing problem

AU - Baldacci, Roberto

AU - Bartolini, Enrico

AU - Mingozzi, Aristide

AU - Valletta, Andrea

PY - 2011/1

Y1 - 2011/1

N2 - This paper presents an exact algorithm for solving strategic and tactical multiperiod vehicle routing problems that can be modeled as period vehicle routing problems (PVRPs). The PVRP is defined on a time horizon of several days and consists of assigning appropriate combinations of delivery to customers and designing a set of delivery routes for every day of the planning period. The objective is to service all customers assigned to each day minimizing the overall routing cost. This paper describes an integer programming formulation of the PVRP that is used to derive different lower bounds and an exact solution method. Computational results on test instances from the literature and on new sets of test instances show the effectiveness of the proposed method.

AB - This paper presents an exact algorithm for solving strategic and tactical multiperiod vehicle routing problems that can be modeled as period vehicle routing problems (PVRPs). The PVRP is defined on a time horizon of several days and consists of assigning appropriate combinations of delivery to customers and designing a set of delivery routes for every day of the planning period. The objective is to service all customers assigned to each day minimizing the overall routing cost. This paper describes an integer programming formulation of the PVRP that is used to derive different lower bounds and an exact solution method. Computational results on test instances from the literature and on new sets of test instances show the effectiveness of the proposed method.

KW - Dual ascent

KW - Dynamic programming

KW - Period vehicle routing

KW - Set partitioning

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

U2 - 10.1287/opre.1100.0875

DO - 10.1287/opre.1100.0875

M3 - Article

AN - SCOPUS:79952925170

SN - 0030-364X

VL - 59

SP - 228

EP - 241

JO - Operations Research

JF - Operations Research

IS - 1

ER -

An exact algorithm for the period routing problem

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this