Highlights An integer program is formulated to minimize the total travel time in the airspace. The relaxed linear program is proved to provide the integral and optimal solution. The simplex-based decomposition is proved to preserve the total unimodularity.
Abstract In an earlier work, Sun and Bayen built a Large-Capacity Cell Transmission Model for air traffic flow management. They formulated an integer programming problem of minimizing the total travel time of flights in the National Airspace System of the United States subject to sector capacity constraints. The integer program was relaxed to a linear program for computational efficiency. In this paper the authors formulate the optimization problem in a standard linear programming form. We analyze the total unimodular property of the constraint matrix, and prove that the linear programming relaxation generates an optimal integral solution for the original integer program. It is guaranteed to be optimal and integral if solved by a simplex related method. In order to speed up the computation, we apply the Dantzig–Wolfe Decomposition algorithm, which is shown to preserve the total unimodularity of the constraint matrix. Finally, we evaluate the performances of Sun and Bayen’s relaxation solved by the interior point method and our decomposition algorithm with large-scale air traffic data.
Total unimodularity and decomposition method for large-scale air traffic cell transmission model
Transportation Research Part B: Methodological ; 53 ; 1-16
2013-03-18
16 pages
Aufsatz (Zeitschrift)
Elektronische Ressource
Englisch
Total unimodularity and decomposition method for large-scale air traffic cell transmission model
Online Contents | 2013
|CUR decomposition for compression and compressed sensing of large-scale traffic data
DSpace@MIT | 2013
|Multicommodity Eulerian-Lagrangian Large-Capacity Cell Transmission Model for En Route Traffic
Online Contents | 2008
|A Temporal Domain Decomposition Algorithmic Scheme for Large-Scale Dynamic Traffic Assignment
DOAJ | 2012
|