A Constraint Relaxation Co-Evolutionary Algorithm for the Two-Echelon Vehicle Routing Problem With Load-Dependent Drones

The growing adoption of drones in last-mile logistics has raised urgent demands for controlling energy consumption costs while ensuring delivery efficiency. To address this, we formulate the Two-Echelon Vehicle Routing Problem with Load-dependent Drones (2E-VRPLD) within a depot-satellite-customer framework, which reflects realistic logistics conditions where drones experience continuously changing payloads as they pick up and deliver parcels. These load fluctuations cause discrete shifts in power consumption, making their actual flight endurance highly uncertain under a fixed energy budget and thereby significantly increasing the complexity of planning feasible routes and minimizing overall transportation costs. To solve this complex VRP variant, we develop a novel Constraint Relaxation Co-evolutionary Algorithm (CRCEA) that integrates a customer-satellite matching mechanism to minimize drone endurance redundancy and a minimal impact assessment strategy for route segment merging. Experiments show that CRCEA attains nearly negligible optimality gaps relative to Gurobi on small-scale instances, significantly outperforms seven representative heuristics on large-scale instances, and consistently delivers superior solutions in real-world delivery scenarios from leading express carriers JD and SF Express in Changsha, China. Furthermore, ablation studies identify key factors affecting algorithmic performance, and sensitivity analyses illustrate how drone performance parameters influence the efficiency of solving the 2E-VRPLD. This work provides a robust theoretical and practical approach for solving the two-echelon pickup-and-delivery routing problem with load-dependent drones, offering important insights for advancing smart logistics and improving enterprise operational efficiency.