Task Planning of Multiple Unmanned Aerial Vehicles Based on Minimum Cost and Maximum Flow

With the rapid development of UAV technology, UAV delivery has gained attention for its potential to reduce labor costs. However, limitations in load capacity and energy restrict UAVs' distribution capabilities. This paper proposes a cooperative delivery scheme combining traditional trucks and UAVs to extend UAV coverage and improve delivery completion rates. For densely distributed depots in wide-area regions, we develop algorithms for task allocation and path planning in a truck-independent UAV system. Specifically, a minimum-cost, maximum-flow model is constructed to obtain sub-paths covering all delivery tasks, and resource tree-based algorithms are used to construct global paths for UAVs and trucks. Simulation results show that our algorithms reduce total energy consumption by 11.53% and 9.15% under different task points, which suggests that our proposed method can significantly enhance delivery efficiency, offering a promising solution for future logistics operations.