Collaborative Routing of a Single Truck and Multiple Drones with Soft Time Windows and Parcel Exposure-Time Constraints

Abstract

The growth of e-commerce, on-demand retailing, and cold-chain distribution has intensified the need for efficient and sustainable last-mile delivery. This study formulates a single-truck, multi-drone collaborative routing problem with soft time windows, payload/endurance limits, and parcel exposure-time constraints. A mixed-integer linear programming model minimizes fixed, transportation, waiting, tardiness, and route-based carbon-tax costs, and an improved adaptive large neighborhood search (IALNS) integrates adaptive operator selection, simulated annealing, tabu memory, large-scale reconstruction, and final intensification. Experiments on adapted Solomon instances compare IALNS with Gurobi, classical adaptive large neighborhood search (ALNS), and a genetic algorithm (GA). Under the tested settings, Gurobi proves optimality for five of the 12 small instances, and IALNS matches all five proven optima. Across 240 matched-seed comparisons on 24 common instances, IALNS reduces cost by 8.56% versus classical ALNS and 18.16% versus GA on average. Under the stricter U(0.1, 0.3) h exposure regime used in the coverage-sensitivity experiment, expanding the exposure-constrained share from 0 to 0.5 raises the best-found cost by 1.91%, 3.94%, and 9.12% for clustered (C), random (R), and mixed random–clustered (RC) instances, respectively. Under the adopted route-emission factors, adding the first drone reduces transportation emissions by 19.58–55.73% across the three representative 50-customer cases. These benchmark-specific results support geography- and exposure-aware fleet and routing decisions.