Complexity and Reducibility of the Skip Delivery Problem

C. Archetti (), R. Mansini () and M. G. Speranza ()
Additional contact information
C. Archetti: Department of Quantitative Methods, University of Brescia, C.da S. Chiara 50, I-25122 Brescia, Italy
R. Mansini: Department of Electronics for Automation, University of Brescia, via Branze 38, I-25123 Brescia, Italy
M. G. Speranza: Department of Quantitative Methods, University of Brescia, C.da S. Chiara 50, I-25122 Brescia, Italy

Transportation Science, 2005, vol. 39, issue 2, 182-187

Abstract: In the skip delivery problem (SDP), a fleet of vehicles must deliver skips to a set of customers. Each vehicle has a maximum capacity of two skips, and has to start and end its tour at a central depot. The demand of each customer can be greater than the capacity of the vehicles. The objective is to minimize the cost of the total distance traveled by the vehicles to serve all the customers. We show that the SDP is solvable in polynomial time, while its generalization to the case where all vehicles have a capacity greater than two, known as the split delivery vehicle routing problem (SDVRP), is shown to be NP-hard, even under restricted conditions on the costs. We also show that, if the costs are symmetrical and satisfy the triangle inequality, the SDP is reducible in polynomial time to a problem of possibly smaller size, where each customer has unitary demand. This property allows a remarkable simplification of the problem.

Keywords: vehicle routing; skip delivery problem; split delivery; triangle inequality; computational complexity (search for similar items in EconPapers)
Date: 2005
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (9)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1030.0084 (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:39:y:2005:i:2:p:182-187

Access Statistics for this article

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