An Adaptive Variable Neighborhood Search Algorithm for a Vehicle Routing Problem Arising in Small Package Shipping

Andreas Stenger (), Daniele Vigo (), Steffen Enz () and Michael Schwind ()
Additional contact information
Andreas Stenger: IT-based Logistics, Institute of Information Systems, Goethe University, 60323 Frankfurt, Germany
Daniele Vigo: Dipartimento di Elettronica, Informatica e Sistemica, University of Bologna, 40136 Bologna, Italy
Steffen Enz: IT-based Logistics, Institute of Information Systems, Goethe University, 60323 Frankfurt, Germany
Michael Schwind: IT-based Logistics, Institute of Information Systems, Goethe University, 60323 Frankfurt, Germany

Transportation Science, 2013, vol. 47, issue 1, 64-80

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: vehicle routing; heuristics; small package shipping; subcontracting; variable neighborhood search (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (41)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1110.0396 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:47:y:2013:i:1:p:64-80

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().