An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping

Andreas Stenger, Daniele Vigo, Steffen Enz, Michael Schwind

Research output: Contribution to JournalArticleAcademicpeer-review

Abstract

In this paper, we investigate a routing problem arising in the last-mile delivery of small packages. The problem, called Multi-Depot Vehicle Routing Problem with Private fleet and Common carriers (MDVRPPC), is an extension of the Multi-Depot Vehicle Routing Problem (MDVRP) where customers can either be served by the private fleet based at self-owned depots or by common carriers, i.e., subcontractors. We develop an effective Variable Neighborhood Search algorithm based on the use of cyclic-exchange neighborhoods that incorporates an adaptive mechanism to bias the random shaking step. The approach is successfully used to solve MDVRPPC as well as closely related problems, such as the MDVRP and the single-depot VRP with Private fleet and Common carriers (VRPPC), obtaining high quality solutions within short computing time. Our extensive testing on these problems shows the positive impact of the adaptive mechanism with respect to a standard VNS algorithm.
LanguageEnglish
Pages64-80
Number of pages17
JournalTransportation Science
Volume47
Issue number1
DOIs
Publication statusPublished - 1 Feb 2013

Fingerprint

Vehicle routing
shipping
Freight transportation
common carrier
subcontractor
Testing
customer
trend

Keywords

  • Heuristics
  • Small package shipping
  • Subcontracting
  • Variable neighborhood search
  • Vehicle routing

Cite this

@article{eb65db1675fa43f2b029d8b8031d5f9f,
title = "An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping",
abstract = "In this paper, we investigate a routing problem arising in the last-mile delivery of small packages. The problem, called Multi-Depot Vehicle Routing Problem with Private fleet and Common carriers (MDVRPPC), is an extension of the Multi-Depot Vehicle Routing Problem (MDVRP) where customers can either be served by the private fleet based at self-owned depots or by common carriers, i.e., subcontractors. We develop an effective Variable Neighborhood Search algorithm based on the use of cyclic-exchange neighborhoods that incorporates an adaptive mechanism to bias the random shaking step. The approach is successfully used to solve MDVRPPC as well as closely related problems, such as the MDVRP and the single-depot VRP with Private fleet and Common carriers (VRPPC), obtaining high quality solutions within short computing time. Our extensive testing on these problems shows the positive impact of the adaptive mechanism with respect to a standard VNS algorithm.",
keywords = "Heuristics, Small package shipping, Subcontracting, Variable neighborhood search, Vehicle routing",
author = "Andreas Stenger and Daniele Vigo and Steffen Enz and Michael Schwind",
year = "2013",
month = "2",
day = "1",
doi = "10.1287/trsc.1110.0396",
language = "English",
volume = "47",
pages = "64--80",
journal = "Transportation Science",
issn = "0041-1655",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "1",

}

An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping. / Stenger, Andreas; Vigo, Daniele; Enz, Steffen; Schwind, Michael.

In: Transportation Science, Vol. 47, No. 1, 01.02.2013, p. 64-80.

Research output: Contribution to JournalArticleAcademicpeer-review

TY - JOUR

T1 - An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping

AU - Stenger, Andreas

AU - Vigo, Daniele

AU - Enz, Steffen

AU - Schwind, Michael

PY - 2013/2/1

Y1 - 2013/2/1

N2 - In this paper, we investigate a routing problem arising in the last-mile delivery of small packages. The problem, called Multi-Depot Vehicle Routing Problem with Private fleet and Common carriers (MDVRPPC), is an extension of the Multi-Depot Vehicle Routing Problem (MDVRP) where customers can either be served by the private fleet based at self-owned depots or by common carriers, i.e., subcontractors. We develop an effective Variable Neighborhood Search algorithm based on the use of cyclic-exchange neighborhoods that incorporates an adaptive mechanism to bias the random shaking step. The approach is successfully used to solve MDVRPPC as well as closely related problems, such as the MDVRP and the single-depot VRP with Private fleet and Common carriers (VRPPC), obtaining high quality solutions within short computing time. Our extensive testing on these problems shows the positive impact of the adaptive mechanism with respect to a standard VNS algorithm.

AB - In this paper, we investigate a routing problem arising in the last-mile delivery of small packages. The problem, called Multi-Depot Vehicle Routing Problem with Private fleet and Common carriers (MDVRPPC), is an extension of the Multi-Depot Vehicle Routing Problem (MDVRP) where customers can either be served by the private fleet based at self-owned depots or by common carriers, i.e., subcontractors. We develop an effective Variable Neighborhood Search algorithm based on the use of cyclic-exchange neighborhoods that incorporates an adaptive mechanism to bias the random shaking step. The approach is successfully used to solve MDVRPPC as well as closely related problems, such as the MDVRP and the single-depot VRP with Private fleet and Common carriers (VRPPC), obtaining high quality solutions within short computing time. Our extensive testing on these problems shows the positive impact of the adaptive mechanism with respect to a standard VNS algorithm.

KW - Heuristics

KW - Small package shipping

KW - Subcontracting

KW - Variable neighborhood search

KW - Vehicle routing

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

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

U2 - 10.1287/trsc.1110.0396

DO - 10.1287/trsc.1110.0396

M3 - Article

VL - 47

SP - 64

EP - 80

JO - Transportation Science

T2 - Transportation Science

JF - Transportation Science

SN - 0041-1655

IS - 1

ER -