Air-ground collaborative routing problem for parcel deliveries under soft time windows

Rapid growth in e-commerce is putting unprecedented pressure on urban logistics to reduce costs, emissions, and delivery times. Leveraging complementary strengths of ground vehicles and drones, this study investigates an Electric Vehicle and Drone Routing Problem with soft Time Windows (EVRPD-TW) for parcel deliveries. Specifically, the system consists of multiple Electric Unmanned Ground Vehicles (E-UGVs), each capable of deploying a drone at one node to serve a customer and retrieving it at another. Therefore, customers may be served by either E-UGVs or drones, depending on energy-endurance constraints. The objective is to minimize the total cost, including the travel cost, vehicle activation fees, and penalties for early or late deliveries beyond time windows. To solve the proposed problem, we design a two-level Hybrid Genetic Algorithm with Dynamic Iteration (HGA-DI). The HGA-DI adopts a permutation chromosome that encodes the sequence of customer visits for each E-UGV, and explores the space of ground routes by classical genetic operators. Moreover, the HGA-DI is integrated with a dynamic iteration method that optimizes drone launches for every candidate route, guaranteeing solution feasibility. We evaluate the proposed problem in a real-world scenario in Shenzhen, China. The HGA-DI can achieve the optimal solutions on small instances over thirty times faster than Gurobi. Compared to vehicle-only delivery, the E-UGVs and drones collaborative system can better meet the time windows and reduce the total cost by 1.2%. Sensitivity analyses reveal that the total cost is most sensitive to the relative per-kilometer travel cost of E-UGVs and drones, followed by time-window penalty rates and drone endurance. These findings demonstrate the economic and environmental benefits of applying air-ground collaborations and offer practical insights for implementing the proposed system in urban logistics.