Complexity and reducibility of the skip delivery problem

Complexity and reducibility of the skip delivery problem

0.00 Avg rating0 Votes
Article ID: iaor2006830
Country: United States
Volume: 39
Issue: 2
Start Page Number: 182
End Page Number: 187
Publication Date: May 2005
Journal: Transportation Science
Authors: , ,
Keywords: transportation: road, computational analysis
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.

Reviews

Required fields are marked *. Your email address will not be published.