首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Total unimodularity and decomposition method for large-scale air traffic cell transmission model
Institution: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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号