Vehicle–Drone Routing Problem with Heterogeneous Time-Sensitive Tasks and en Route Synchronization: A Hybrid Adaptive Large Neighborhood Search

Full abstract

Read the full abstract

Vehicle–drone cooperative systems leverage the ground transport capacity of vehicles and the aerial mobility of drones to markedly boost operational efficiency in time-sensitive missions. However, existing studies generally rely on predefined launch and recovery locations and provide limited consideration of how heterogeneous task requirements and time-dependent values interact with vehicle–drone synchronization. This paper focuses on the vehicle–drone cooperative routing problem that integrates heterogeneous tasks, time-varying rewards, and en route launch–recovery synchronization. Tasks fall into three categories by platform compatibility, with their rewards following distinct time-decay functions that decrease as completion is delayed. Vehicles travel along ground routes, while drones can be launched from and recovered by moving vehicles. To maximize the total system reward, we formulate the problem as a mixed-integer nonlinear programming model. We develop a hybrid adaptive large neighborhood search (HALNS). Computational experiments compare HALNS with benchmark algorithms and examine the effects of key operational parameters. The results show that HALNS consistently achieves higher total rewards across the tested instances and highlight the benefits of flexible en route synchronization in improving temporal coordination, facilitating timely task completion, and mitigating delay-induced reward loss. Sensitivity analyses further reveal how drone endurance, battery replacement time, and travel speed affect system performance.