The US National Airspace System is currently operating at a level close to its maximum potential. The limitation comes from the workload demand on the air traffic controllers. Currently, the air traffic flow management is based on the flight path requests by the airline operators, whereas the minimum separation assurance between flights is handled strategically by air traffic control personnel. In this paper, we propose a scalable framework that allows path planning for a large number of unmanned aerial vehicles (UAVs) taking into account the deadline and weather constraints. Our proposed solution has a polynomial-time computational complexity that is also verified by measuring the runtime for typical workloads. We further demonstrate that the proposed framework is able to route 80% of the workloads while not exceeding the sector capacity constraints, even under dynamic weather conditions. Due to low computational complexity, our framework is suitable for a fleet of UAVs where decentralizing the routing process limits the workload demand on the air traffic personnel.


Computer Science


National Science Foundation, Grant CCF-1725755

Keywords and Phrases

Air traffic; conflict avoidance; routing; simulation; unmanned aircraft

International Standard Serial Number (ISSN)


Document Type

Article - Journal

Document Version

Final Version

File Type





© 2023 Institute of Electrical and Electronics Engineers, All rights reserved.

Publication Date

01 Aug 2022