This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Citing Articles Citing Articles via HighWire Citing Articles via Google Scholar Google Scholar Articles by Archetti, C. Articles by Speranza, M. G. Search for Related Content

Complexity and Reducibility of the Skip Delivery Problem

Department of Quantitative Methods, University of Brescia, C.da S. Chiara 50, I-25122 Brescia, Italy
Department of Electronics for Automation, University of Brescia, via Branze 38, I-25123 Brescia, Italy
Department of Quantitative Methods, University of Brescia, C.da S. Chiara 50, I-25122 Brescia, Italy
archetti{at}eco.unibs.it
rmansini{at}ing.unibs.it
speranza{at}eco.unibs.it

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.

Key Words: vehicle routing; skip delivery problem; split delivery; triangle inequality; computational complexity
History: Received: November 2001; revised: February 2003; accepted: February 2003.

This article has been cited by other articles:

				A. Ceselli, G. Righini, and M. Salani A Column Generation Algorithm for a Rich Vehicle-Routing Problem Transportation Science, February 1, 2009; 43(1): 56 - 69. [Abstract] [PDF]

				C. Archetti, M. G. Speranza, and M. W. P. Savelsbergh An Optimization-Based Heuristic for the Split Delivery Vehicle Routing Problem Transportation Science, February 1, 2008; 42(1): 22 - 31. [Abstract] [PDF]

				C. Archetti, M. W. P. Savelsbergh, and M. G. Speranza Worst-Case Analysis for Split Delivery Vehicle Routing Problems Transportation Science, May 1, 2006; 40(2): 226 - 234. [Abstract] [PDF]