The US NationalAirspace System is currentlyoperating 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 measuringthe 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 airtraffic personnel.