Adaptive large multiple neighborhood search for the truck-drone-collection station collaborative delivery problem

To address the shortcomings of rural traditional truck logistics services, such as high distribution costs and low distribution efficiency, we propose a novel truck-drone-collection station collaborative delivery problem (TDCS-CDP). The integer programming model of truck-drone-collection station collaborative delivery is constructed, considering the rural road conditions and the geographical distribution of customers. Decisions are made to determine the routes for the truck and drone, as well as the locations and customer assignments for collection stations, drone launch and recovery nodes. The objective of the TDCS-CDP is to minimize the costs associated with truck-drone travel and collection station operations. To solve this complex problem, we propose an adaptive large multiple neighborhood search (ALMNS) algorithm that explores the solution space using multiple destruction-repair operators and neighborhood operators designed based on the problem structure. At the same time, the iteration period is segmented, and the weight information of the operators in each period is adjusted dynamically, which effectively prevents the algorithm from falling into local optimization. Finally, we conducted extensive computational experiments on a set of instances based on existing benchmarks. Out of 75 instances, ALMNS and Gurobi find 14 and 19 optimal solutions within a given time. However, the average computation time of ALMNS is about 2.76 % of Gurobi. The state-of-the-art algorithm obtains 29 best solutions out of 75 instances, while ALMNS achieves 75 best solutions in less computation time.