Truck-drone collaborative routing with flexible cross-truck operations and slot constraints

Truck-drone collaborative routing faces critical operational bottlenecks in realistic logistics scenarios due to strict return constraints and limited physical recovery slots. We address these challenges by proposing a novel Mixed-Integer Linear Programming model for the Flexible Assignment Vehicle Routing Problem with Drones and Slot Constraints (FA-VRPDSC). By decoupling drones from specific launch vehicles, the model enables flexible cross-truck operations and dynamic task assignments across the entire fleet under strict slot capacity limits. To efficiently solve this complex combinatorial problem, we develop a tailored Memetic Algorithm with Adaptive Large Neighborhood Perturbation (MA-ALNP). The algorithm leverages a dual-chain representation to jointly encode routing sequences and collaboration states. To navigate the tightly coupled temporal and spatial constraints, we integrate specialized repair operators and an adaptive destroy-and-repair shaking mechanism that effectively prevents premature convergence. Computational results confirm the algorithm’s exact optimality on small instances and its structural superiority on large-scale benchmarks, significantly outperforming advanced heuristics in minimizing total makespan. Our sensitivity analysis ultimately highlights that extended drone endurance is pivotal for activating flexible cross-truck docking and maximizing fleet coordination.