Document Type

Article

Publication Date

11-2009

Publication Title

European Journal of Operational Research

Volume

198

Issue

1

Abstract

Splitting loads such that the delivery of certain loads is completed in multiple trips rather than one trip has show to have benefit for both the classic Vehicle Routing Problem and the Pickup and Delivery Problem. However, the magnitude of the benefit may be affected by various problem characteristics. In this paper, we characterize those real world environments in which split loads are most likely to be beneficial. Based on practitioner interest, we determine how the benefit is affected by the mean load size and variance, number of origins relative to the number of destinations, the percentage of origin-destination pairs with a load requiring service and the clustering of origin and destination locations. We find that the magnitude of benefit: is greatest for load sizes just over one half vehicle capacity as these loads can not be combined without splitting, while they are the easiest to combine on a vehicle with splitting; increases as the number of loads sharing an origin or destination increases because there are more potential load combinations to split at each stop; and increases as the average distance from an origin to a destination increases because splitting loads reduces the trips from origins to destinations.

Comments

Author Posting © Elsevier, 2008. This is the author's version of the work. It is posted here by permission of Elsevier for personal use, not for redistribution. The definitive version was published in European Journal of Operational Research, Volume 198, Issue 1, November 2009. http://dx.doi.org/10.1016/j.ejor.2008.09.041

Creative Commons License

Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 3.0 License.