A Three-Phase Heuristic for Optimizing Truck-Drone Collaborative Delivery

Truck-drone collaborative delivery has attracted increasing attention as an effective means to enhance flexibility and efficiency in complex distribution systems. However, the resulting Vehicle Routing Problem with Drones (VRPD) is NP-hard, and existing heuristics often struggle to balance solution quality and computational efficiency, especially in large-scale and multi-trip settings. To address these challenges, this paper proposes a Structure-Guided Adaptive Large Neighborhood Search (S-ALNS) framework for truck-drone collaborative routing. The proposed approach explicitly exploits problem-specific structural characteristics through a three-phase solution process. First, balanced initial truck routes are constructed using customer clustering. Second, a structured split-based heuristic reallocates suitable customers from truck routes to a drone service. Third, the solution is further refined within an improved ALNS framework, where a structure-guided repair mechanism based on dynamic programming is introduced to efficiently handle batch customer insertions under coupled capacity and feasibility constraints. Extensive computational experiments on instances of varying scales show that S-ALNS consistently produces near-optimal solutions for small-scale instances used for validation. For medium- and large-scale instances, S-ALNS significantly outperforms classical heuristics, including simulated annealing and a standard ALNS baseline, in terms of solution quality while maintaining competitive in computational efficiency. These results demonstrate the effectiveness of incorporating the problem structure into Adaptive Large Neighborhood Searches for complex truck-drone routing problems.