Worst-Case Analysis for Split Delivery Vehicle Routing Problems

Claudia Archetti (), Martin W. P. Savelsbergh () and M. Grazia Speranza ()
Additional contact information
Claudia Archetti: Department of Quantitative Methods, University of Brescia, C. da S. Chiara 50, 25122 Brescia, Italy
Martin W. P. Savelsbergh: School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, Georgia 30332-0205
M. Grazia Speranza: Department of Quantitative Methods, University of Brescia, C. da S. Chiara 50, 25122 Brescia, Italy

Transportation Science, 2006, vol. 40, issue 2, 226-234

Abstract: 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.

Keywords: vehicle routing; split deliveries; worst-case analysis (search for similar items in EconPapers)
Date: 2006
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (36)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.1050.0117 (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:40:y:2006:i:2:p:226-234

Access Statistics for this article

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