Traffic flow management (TFM) of the National Airspace System (NAS) endeavors to deliver flights from their origins to their destinations while minimizing delays and respecting all capacities. There are several models for solving this problem. Some models aggregate flights into flows and others consider controls for individual flights. Typically, the latter set of models is computationally difficult to solve for large-scale, high-fidelity scenarios. One of the more heavily studied aircraft-level models presented by Bertsimas and Stock-Patterson (BSP) has runtime concerns that should not be overlooked, but it neatly describes the issues associated with TFM (respecting capacities of airspace resources and the schedules of individual aircraft).

The BSP model has special structure that allows for solving by decomposition into smaller problems. This well-known, provably optimal approach to solving largescale linear programs is called Dantzig-Wolfe (DW) decomposition. To speed the process of assigning delays to flights, DW decomposition is applied to the BSP model. The subproblems for this decomposition are solved in parallel via independent computation threads. Each subproblem represents the plan for one particular flight. This results in the generation of thousands of subproblems.

When this massively parallel approach is compared with a traditional, non-decomposed approach in terms of solution quality and runtime, the results are dramatic. While many others in various application domains have used DW, there is no clear example for such a high level of parallelism as is accomplished here. By using DW, the computational barrier to implementing a huge-scale, high-fidelity, aircraft-level model may be lowered to the point that future decision support tools may make use of the model with commercial-off-the-shelf software and hardware.

As a result of this research, a software package for solving any properly decomposed linear programming problem was developed at NASA Ames. Other non-aviation research projects have already leveraged the computational capabilities of this software. This software has been released open source and may be downloaded from: http://sourceforge.net/projects/dwsolver/ .

This work was done by Joseph Rios of Ames Research Center. NASA invites companies to inquire about partnering opportunities. Contact the Ames Technology Partnerships Office at 1-855-627-2249 or This email address is being protected from spambots. You need JavaScript enabled to view it.. Refer to ARC-16432-1.


NASA Tech Briefs Magazine

This article first appeared in the November, 2014 issue of NASA Tech Briefs Magazine.

Read more articles from this issue here.

Read more articles from the archives here.