Air Corridor Planning for Urban Drone Delivery: Complexity Analysis and Comparison via Multi-Commodity Network Flow and Graph Search

Xinyu He, Lishuai Li, Yanfang Mo, Zhankun Sun and S. Joe Qin

Transportation Research Part E: Logistics and Transportation Review, 2025, vol. 193, issue C

Abstract: Urban drone delivery, a rapidly evolving sector, holds the potential to enhance accessibility, address last-mile delivery issues, and alleviate ground traffic congestion in cities. Effective Unmanned Aircraft System Traffic Management (UTM) is essential to scale drone delivery. A critical aspect of UTM involves planning a city-wide network with spatially-separated air corridors (air routes). Most existing works have focused on routing problems or air traffic management. Compared to these problems, the air corridor planning problem requires much higher spatial and temporal resolutions and presents computational challenges due to the scale, complexity, and density of urban airspace, along with the coupling issues of multi-path planning. Therefore, we conducted this research to understand the complexity and computational resources required to optimally solve the air corridor planning problem. In this paper, we use a minimum-cost Multi-Commodity Network Flow (MCNF) model, a mathematical model, to model the problem and demonstrate the complexity of air corridor planning through the complexity of MCNF. We then apply Gurobi’s and GLPK’s integer programming (IP) solvers to find optimal solutions. Additionally, we present two existing multi-path graph search algorithms, the Sequential Route Network Planning (SRP) algorithm and the Distributed Route Network Planning (DRP) algorithm, to address this corridor planning problem. Numerical experiments conducted at various scales and settings using IP solvers and graph search algorithms indicate that finding an optimal solution requires significant computational resources and yields only a slight improvement in optimality compared to graph search algorithms. Thus, air corridor planning is complex both theoretically and numerically, and graph search algorithms can provide a feasible solution with good enough optimality for corridor planning in real-world scenarios. Moreover, the multi-path graph search algorithms can easily incorporate side constraints that are known to be impossible to solve with polynomial algorithms, making it more practical for real-world applications. Finally, we demonstrate the application of SRP and DRP in real-world 3D urban scenarios.

Keywords: Unmanned aircraft system traffic management (UTM); Drone delivery; Multi-path planning; Network flow theory; Graph search (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S1366554524004502
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:transe:v:193:y:2025:i:c:s1366554524004502

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/journaldescription.cws_home/600244/bibliographic
http://www.elsevier. ... 600244/bibliographic

DOI: 10.1016/j.tre.2024.103859

Access Statistics for this article

Transportation Research Part E: Logistics and Transportation Review is currently edited by W. Talley

More articles in Transportation Research Part E: Logistics and Transportation Review from Elsevier
Bibliographic data for series maintained by Catherine Liu ().