Precedence constrained pickup and delivery with split loads

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.