The pickup and delivery problem with transshipments: Critical review of two existing models and a new formulation

The pickup and delivery problem with transshipments (PDP-T) is generalized from the classical pickup and delivery problem (PDP) by allowing the transfer of requests between vehicles. After considering the time window constraints, the PDP-T is further generalized to the pickup and delivery problem with time windows and transshipments (PDPTW-T). In this paper, we review two state-of-the-art models for the PDP-T and PDPTW-T. We point out the possible issues existing in the models and provide our revisions. In addition, we develop a new mixed-integer linear programming formulation to solve the PDP-T and PDPTW-T. The performance of the proposed model is evaluated by solving 340 generated PDP-T instances and 360 open-access PDPTW-T instances. Computational results show that the proposed model outper-forms the existing models in terms of solution quality and computing time. PTP-T instances with up to 25 requests and 2 transfer stations are solved to optimality by using the proposed model. As a compar-ison, the best-known benchmarks in the literature are instances with 5 requests and 1 transfer station. In addition, the computing time is significantly reduced. In our experiments, the average computational time for solving PDP-T is reduced by 96%. For PDPTW-T instances, the solvable scale is increased from 3 requests and 4 transfer stations to 5 requests and 4 transfer stations. The average computing time is reduced by 40%.(c) 2022 Elsevier B.V. All rights reserved.

Automated summary

The paper investigates the pickup and delivery problem with transshipments, which is further extended to incorporate time windows and transshipments. Two existing models are reviewed and revised, and a new solution is developed. Experimental results demonstrate that the proposed approach outperforms existing models in terms of solution quality and computing time.