Preliminary Results from Application of TFMP Optimization Model to NAS Weather Impact Cases

Bertsimas and Stock-Patterson [1998] described a mixed-integer programming (MIP) model that addresses the traffic flow management problem (TFMP) in the presence of weather induced capacity constraints. The National Airspace System (NAS) is characterized as a set of airports interconnected via en route sectors. Each airport and en route sector is assigned time varying aircraft capacities. Individual flights are modeled as traversals of sectors forming paths between pairs of origin and destination airports. The model specifies the valid paths, along with minimum sector traversal times, so that aircraft speed is accounted for. The model solution yields not only the optimal cost (in terms of minimal in-flight and ground delays) but also the "flight plan" for each flight -- takeoff and landing times, and arrival times at each sector along its path. Using 1990's state-of-the-art MIP solvers and hardware, Bertsimas and Stock-Patterson showed that TFMP problems of significant size (six major airports, with three thousand flights over a sixteen-hour period) could be solved optimally using only a few minutes of computation time.

The Bertsimas-Stock-Patterson model assumes only a single route from origin to destination. Using suggestions from 1998 paper, we have have implemented a variant of this model which allows for an arbitrary finite number of routes between airport pairs. The 1998 paper used simulated flight data as model inputs. We have applied the new model to a number of severe weather cases which affected the NAS in 2004 and 2005. In each case, sector capacities were determined from recorded weather data, the NAS network topology was derived from ETMS and FAA GIS databases, and flight schedule information was obtained from the ASPM database. In this paper, we show how the new model can be used as a post-event analysis tool to evaluate flight scheduling and routing in the NAS under various weather conditions. For flights in the CIWS domain, we compare the model-generated solution, to the actual flight data for each event under various optimality assumptions. We also consider the effects of modifications to the NAS sector and route structures on overall scheduling performance.

Bertsimas -Stock-Patterson [1998] TFMP model is based on the assumption that future airspace capacity is known with certainty. We have recently commenced efforts to extend the formulation to the more realistic situation where future airspace capacity is uncertain, owing for example to imperfect thunderstorm forecasts. The new extensions are based on the concept of robust discrete optimization, introduced in Bertsimas and Sim [2003]. The paper concludes with a discussion of robust discrete optimization, showing how the technique can be used to construct a real-time scheduling tool.