Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery

Nicola Bianchessi; Giovanni Righini

doi:10.1016/j.cor.2005.03.014

Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery

Nicola Bianchessi
, Giovanni Righini^*

^*Corresponding author for this work

Research output: Contribution to Journal › Article › Academic › peer-review

Abstract

The vehicle routing problem with simultaneous pick-up and delivery is the problem of optimally integrating goods distribution and waste collection, when no precedence constraints are imposed on the order in which the operations must be performed. The purpose of this paper is to present heuristic algorithms to solve this problem approximately in a small amount of computing time. We present and compare constructive algorithms, local search algorithms and tabu search algorithms, reporting on our computational experience with all of them. In particular we address the issue of applying the tabu search paradigm to algorithms based on complex and variable neighborhoods. For this purpose we combine arc-exchange-based and node-exchange-based neighborhoods, employing different and interacting tabu lists. All the algorithms presented in this paper are applicable to problems in which each customer may have either a pick-up demand or a delivery demand as well as to problems in which each customer may require both kinds of operation.

Original language	English
Pages (from-to)	578-594
Number of pages	17
Journal	Computers and Operations Research
Volume	34
Issue number	2
DOIs	https://doi.org/10.1016/j.cor.2005.03.014
Publication status	Published - 1 Feb 2007

Funding

We are grateful to Marco Trubian for his invaluable suggestions and to Jan Dethloff for providing us the input data of his tests. The detailed comments of two anonymous referees helped us considerably at improving both the content and the presentation of the paper. We also acknowledge the kind support of ACSU–Associazione Cremasca Studi Universitari to the Operations Research Laboratory at the Department of Information Technologies of the University of Milano, where this research was done.

Keywords

Distribution logistics
Heuristics
Vehicle routing

Access to Document

10.1016/j.cor.2005.03.014

Persistent URL (handle)

Persistent link

Cite this

@article{de43818b409e4489b942da400badf5bc,

title = "Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery",

abstract = "The vehicle routing problem with simultaneous pick-up and delivery is the problem of optimally integrating goods distribution and waste collection, when no precedence constraints are imposed on the order in which the operations must be performed. The purpose of this paper is to present heuristic algorithms to solve this problem approximately in a small amount of computing time. We present and compare constructive algorithms, local search algorithms and tabu search algorithms, reporting on our computational experience with all of them. In particular we address the issue of applying the tabu search paradigm to algorithms based on complex and variable neighborhoods. For this purpose we combine arc-exchange-based and node-exchange-based neighborhoods, employing different and interacting tabu lists. All the algorithms presented in this paper are applicable to problems in which each customer may have either a pick-up demand or a delivery demand as well as to problems in which each customer may require both kinds of operation.",

keywords = "Distribution logistics, Heuristics, Vehicle routing",

author = "Nicola Bianchessi and Giovanni Righini",

year = "2007",

month = feb,

day = "1",

doi = "10.1016/j.cor.2005.03.014",

language = "English",

volume = "34",

pages = "578--594",

journal = "Computers and Operations Research",

issn = "0305-0548",

publisher = "Elsevier Ltd",

number = "2",

}

TY - JOUR

T1 - Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery

AU - Bianchessi, Nicola

AU - Righini, Giovanni

PY - 2007/2/1

Y1 - 2007/2/1

N2 - The vehicle routing problem with simultaneous pick-up and delivery is the problem of optimally integrating goods distribution and waste collection, when no precedence constraints are imposed on the order in which the operations must be performed. The purpose of this paper is to present heuristic algorithms to solve this problem approximately in a small amount of computing time. We present and compare constructive algorithms, local search algorithms and tabu search algorithms, reporting on our computational experience with all of them. In particular we address the issue of applying the tabu search paradigm to algorithms based on complex and variable neighborhoods. For this purpose we combine arc-exchange-based and node-exchange-based neighborhoods, employing different and interacting tabu lists. All the algorithms presented in this paper are applicable to problems in which each customer may have either a pick-up demand or a delivery demand as well as to problems in which each customer may require both kinds of operation.

AB - The vehicle routing problem with simultaneous pick-up and delivery is the problem of optimally integrating goods distribution and waste collection, when no precedence constraints are imposed on the order in which the operations must be performed. The purpose of this paper is to present heuristic algorithms to solve this problem approximately in a small amount of computing time. We present and compare constructive algorithms, local search algorithms and tabu search algorithms, reporting on our computational experience with all of them. In particular we address the issue of applying the tabu search paradigm to algorithms based on complex and variable neighborhoods. For this purpose we combine arc-exchange-based and node-exchange-based neighborhoods, employing different and interacting tabu lists. All the algorithms presented in this paper are applicable to problems in which each customer may have either a pick-up demand or a delivery demand as well as to problems in which each customer may require both kinds of operation.

KW - Distribution logistics

KW - Heuristics

KW - Vehicle routing

UR - https://www.scopus.com/pages/publications/33746950313

UR - https://www.scopus.com/pages/publications/33746950313#tab=citedBy

U2 - 10.1016/j.cor.2005.03.014

DO - 10.1016/j.cor.2005.03.014

M3 - Article

AN - SCOPUS:33746950313

SN - 0305-0548

VL - 34

SP - 578

EP - 594

JO - Computers and Operations Research

JF - Computers and Operations Research

IS - 2

ER -

Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery

Abstract

Funding

Keywords

Access to Document

Persistent URL (handle)

Other files and links

Fingerprint

Cite this