An improved large neighborhood search algorithm for solving dynamic pickup and delivery problems

The large-scale dynamic pickup and delivery problem (DPDP), characterized by a vast number of orders, complex constraints, and the uncertainties introduced by its dynamic nature, poses significant challenges to existing vehicle routing algorithms. Although current methods each have their own merits, they still exhibit limitations when addressing large-scale DPDPs. To overcome these challenges, this paper introduces an improved large neighborhood search (I-LNS) algorithm for solving large-scale DPDPs. The algorithm consists of two key components: initial solution construction and adaptive large neighborhood search. In each optimization step, the initial solution for the current stage is generated using the cheapest insertion (CI) algorithm, and the best solution from the previous stage is retrieved. The algorithm then searches using six specially designed destruction operators and three repair operators tailored for large-scale DPDPs, with operator weights adaptively adjusted based on the quality of the new solutions. To validate the effectiveness of the proposed method, extensive experiments were conducted using the Huawei benchmark problem, comparing it against five contemporary algorithms. The experimental results demonstrate that the I-LNS algorithm significantly outperforms the competing algorithms in solving large-scale DPDPs. Furthermore, additional validation experiments further confirm the effectiveness of the proposed approach.