Split delivery routing

Moshe Dror and Pierre Trudeau

Naval Research Logistics (NRL), 1990, vol. 37, issue 3, 383-402

Abstract: This article examines a relaxed version of the generic vehicle routing problem. In this version, a delivery to a demand point can be split between any number of vehicles. In spite of this relaxation the problem remains computationally hard. Since only small instances of the vehicle routing problem are known to be solved using exact methods, the vehicle route construction for this problem version is approached using heuristic rules. The main contribution of this article to the existing body of literature on vehicle routing issues in (a) is presenting a new vehicle routing problem amenable to practical applications, and (b) demonstrating the potential for cost savings over similar “traditional” vehicle routing when implementing the model and solutions presented here. The solution scheme allowing for split deliveries is compared with a solution in which no split deliveries are allowed. The comparison is conducted on six sets of 30 problems each for problems of size 75, 115, and 150 demand points (all together 540 problems). For very small demands (up to 10% of vehicle's capacity) no significant difference in solutions is evident for both solution schemes. For the other five problem sets for which point demand exceeds 10% of vehicle's capacity, very significant cost savings are realized when allowing split deliveries. The savings are significant both in the total distance and the number of vehicles required. The vehicles' routes constructed by our procedure tend to cover cohesive geographical zones and retain some properties of optimal solutions.

Date: 1990
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (26)

Downloads: (external link)
https://doi.org/10.1002/nav.3800370304

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:wly:navres:v:37:y:1990:i:3:p:383-402

Access Statistics for this article

More articles in Naval Research Logistics (NRL) from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().