Total unimodularity and decomposition method for large-scale air traffic cell transmission model |
| |
Affiliation: | 1. Department of Civil and Environmental Engineering, The Hong Kong Polytechnic University, Kowloon, Hong Kong;2. The Hong Kong Polytechnic University Shenzhen Research Institute, Shenzhen, Guangdong, China;3. Excellence Center in Infrastructure Technology and Transportation Engineering, Department of Civil Engineering, School of Engineering, Chiang Mai University, 50200, Thailand;1. School of Civil and Environmental Engineering, Georgia Institute of Technology, Atlanta, 30318, United States;2. H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, 30318, United States;3. School of Transportation, Southeast University, Nanjing, 211189, China;1. Department of Civil and Environmental Engineering, Carnegie Mellon University, Pittsburgh, PA 15213, United States;2. Heinz College, Carnegie Mellon University, Pittsburgh, PA 15213 United States |
| |
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. |
| |
Keywords: | Air traffic flow management Cell transmission model Total unimodularity Large-scale transportation network |
本文献已被 ScienceDirect 等数据库收录! |
|