A cumulative service state representation for the pickup and delivery problem with transfers

The pickup and delivery problem with transfers is a challenging version of the vehicle routing problem. In order to tackle this problem, we add a time dimension to physical transportation networks to not only track the location of vehicles at any time but also impose parcels’ pickup/delivery time windows, synchronization time points, and precedence constraints to the problem. We also add another dimension, described as the “cumulative service state” to the constructed space-time network to track the service status of parcels at any time. The constructed network not only handles real-life transportation networks but also is well-suited for connecting microscopic cumulative service states to macroscopic cumulative flow count diagrams. We develop a continuous time approximation approach using cumulative arrival, departure, and on-board count diagrams to effectively assess the performance of the system and dynamically constrict the search space. To handle a large-scale set of parcels, we develop the traditional cluster-first, route-second approach. We reach optimality for the clusters derived from the original set of parcels. We also propose an integer programming model to improve the vehicles’ efficiency. We perform extensive numerical experiments over the standard data set used by Ropke and Pisinger (2006) and real-world large-scale data set proposed by Cainiao Network (with about 10,000 delivery orders) to examine the computational efficiency of our developed algorithm.