Safe routing of multiple aircraft flows in the presence of time-varying weather data

The expected growth of air traffic over the course of the twenty-first century strongly suggests a need for new approaches to air traffic management that are more flexible in the face of both traffic volume and weather. One approach to increasing the capacity of the national airspace is to improve the ability of existing routes to be adjusted in the presence of hazardous weather. In this paper, we describe the algorithms that make up a system we have implemented, the Flow-Based Route Planner (FBRP), to compute multiple flows of aircraft to be routed across a specified region of airspace, e.g., a sector or the transitional airspace in the vicinity of an airport. The FBRP allows for a variety of constraints on the computed routes that permit a user to approximate the desired behavior of real aircraft, including avoidance of changing hazardous weather patterns, turn and curvature constraints, and the horizontal separation standard. The algorithm searches for optimal routes satisfying the constraints using a search within a discrete network that models the geometry of the airspace. The novelty of the system is its ability to handle a variety of constraints and to efficiently route multiple flows of aircraft in dynamic weather scenarios. We describe here some of the algorithmic details of the FBRP system and report on initial experimentation with the system. In a companion paper [KPPM], the FBRP is used to conduct a suite of experiments and a comparison of methods for synthesizing weather-avoidance routes in the transition airspace.