Title

Precedence Constrained Pickup and Delivery with Split Loads

Document Type

Article

Publication Date

1-20-2012

Publication Title

International Journal of Logistics Research and Applications

Volume

15

Issue

1

Pages

1-14

Abstract

A split load is a load having size no greater than the capacity of a single vehicle that is delivered using more than a single vehicle. The use of split loads can reduce the total transportation cost and the number of vehicles serving a set of loads. Several studies have shown the benefit of split loads as applied to the split delivery vehicle routing problem (SDVRP) and the pickup and delivery problem with split loads (PDPSL). While most research on the application of split loads to vehicle routing has revolved around heuristic methods, in this paper an exact solution method is used on a constrained version of the PDPSL. All origins to be visited must be served before any destination that is to be visited on each route, which we refer to as the precedence constrained-PDPSL (PC-PDPSL). Through this constraint, several structural characteristics that result from the SDVRP are shown to also hold for the PC-PDPSL. In particular, we develop a dynamic programming formulation of the PC-PDPSL and show that the state and action spaces of this problem are finite. We use the well-known A* ‘best-first’ search algorithm from artificial intelligence to find an exact solution to a wide range of data sets. Computational experiments support findings developed using heuristic methods for the PDPSL, showing that splitting loads can reduce costs and that there is a relationship between average load size and cost savings.

Comments

This is an Author's Accepted Manuscript of an article published in Maciek Nowak , Mike Hewitt & Chelsea C. White III (2012): Precedence constrained pickup and delivery with split loads, International Journal of Logistics Research and Applications, 15:1, 1-14. © 2012, Taylor & Francis, available online at: http://dx.doi.org/10.1080/13675567.2012.660476

Creative Commons License

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

This document is currently not available here.

Share

COinS