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

Worst-Case Analysis for Split Delivery Vehicle Routing Problems

Department of Quantitative Methods, University of Brescia, C. da S. Chiara 50, 25122 Brescia, Italy
School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
Department of Quantitative Methods, University of Brescia, C. da S. Chiara 50, 25122 Brescia, Italy
archetti{at}eco.unibs.it
mwps{at}isye.gatech.edu
speranza{at}eco.unibs.it

In the vehicle routing problem (VRP) the objective is to construct a minimum cost set of routes serving all customers where the demand of each customer is less than or equal to the vehicle capacity and where each customer is visited once. In the split delivery vehicle routing problem (SDVRP) the restriction that each customer is visited once is removed. We show that the cost savings that can be realized by allowing split deliveries is at most 50%. We also study the variant of the VRP in which the demand of a customer may be larger than the vehicle capacity, but where each customer has to be visited a minimum number of times. We show that the cost savings that can be realized by allowing more than the minimum number of required visits is again at most 50%. Furthermore, we analyze the performance of simple heuristics that handle customers with demands larger than the vehicle capacity by employing full load out-and-back trips to these customers until the demands become less than or equal to the vehicle capacity. Finally, we investigate situations in which demands are discrete and vehicle capacities are small.

Key Words: vehicle routing; split deliveries; worst-case analysis
History: Received: September 2004; revised: December 2004; accepted: January 2005.

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]

				J. W. Ohlmann, M. J. Fry, and B. W. Thomas Route Design for Lean Production Systems Transportation Science, August 1, 2008; 42(3): 352 - 370. [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]

				M. Nowak, O. Ergun, and C. C. White III Pickup and Delivery with Split Loads Transportation Science, February 1, 2008; 42(1): 32 - 43. [Abstract] [PDF]