Truck–Drone Cooperative Delivery Problem Based on Two-Stage Algorithm
Abstract
To address contactless delivery and fully account for customers’ expected delivery time preferences, this paper presents a mixed-integer programming model for minimizing truck–drone cooperative delivery costs. The model takes truck stopping points, truck routes, drone routes, and customer service time windows as decision variables and minimizes the sum of truck operating costs, drone operating costs, and time-window penalty costs as the objective. Based on the characteristics of the model, a two-stage algorithm is designed. In Stage 1, an improved K-Means clustering method partitions customers into sub-regions, with each cluster centroid serving simultaneously as a temporary truck stop and a drone launch point. In Stage 2, a variable neighborhood simulated annealing (SAVN) algorithm jointly optimizes truck and drone cooperative delivery routes to achieve minimum delivery cost. The correctness and effectiveness of the model and algorithm are verified by benchmarking against an exact solver and two traditional heuristic algorithms. A real-world case study in Chongqing, China, further shows that the two-stage algorithm achieves moderate cost savings and substantial solution-time reduction compared with simultaneous truck–drone route generation.