Adaptive Grid-Based Multi-Objective Evolutionary Optimization for Coordinated Truck–Drone Routing with Backhauls

Abstract

The Coordinated Truck-Drone Routing with Time Windows and Backhauls poses a complex challenge in collaborative logistics, requiring tight coordination between ground vehicles and drones under stringent operational constraints. Unlike traditional back-haul routing models that impose a strict priority between linehaul deliveries and backhaul pickups, this paper adopts an improved backhaul paradigm that allows pickups and deliveries to be interleaved along a route. Moreover, drones operate under limited endurance and can be launched and recovered by vehicles to serve selected customers, enabling flexible cooperation while preserving synchronization. We formulate this setting as a bi-objective problem that minimizes total cost and waiting time, and develop a Mixed-Integer Linear Programming model to optimally solve small-scale instances for benchmarking. For larger instances, this paper proposes the Constraint-Integrated Adaptive Grid-based Evolutionary Algorithm (CIAGEA) that integrates adaptive Pareto grid adjustment, adaptive local search, and a diversity mechanism to balance convergence and diversity while preserving feasibility. Extensive experiments on benchmark instances show that CIAGEA consistently outperforms state-of-the-art algorithms in terms of Hypervolume and Inverted Generational Distance, achieving particularly strong gains on large-scale problems and producing solutions close to optimal on small instances.