A Lightweight Memetic Adaptive Genetic Algorithm with Drone Insertion for Truck–Drone Collaborative Routing

Abstract

Truck–drone collaborative delivery combines the carrying capacity and operational reliability of a ground vehicle with the point-to-point mobility of an unmanned aerial vehicle. This paper studies an adjacent-sortie variant of the single-truck single-drone routing problem on Euclidean instances, where the objective is to minimize the synchronized completion time. For a fixed customer permutation, feasible drone insertions are selected by a dynamic-programming decoder under endurance and non-conflict constraints. On this basis, a Memetic Adaptive Genetic Algorithm with Drone Insertion, denoted by MAGA-DI, is developed. The algorithm uses randomized nearest-neighbor initialization, adaptive mutation, and decoder-aware local search. In the local search phase, swap, insertion, and segment-reversal moves are evaluated by the same drone insertion decoder used for final solution evaluation, so local improvement is guided by synchronized truck–drone makespan rather than by truck-only distance. On five instances per size and ten independent runs per stochastic method, MAGA-DI reduces the mean makespan of the adaptive GA baseline AGA-DI by 3.35 percent, 5.11 percent, and 4.86 percent for 20-, 50-, and 100-customer instances, respectively. The added local search increases runtime, but the average runtime remains below three seconds for 100-customer instances in the tested setting.