Department of Computer Science News
CS Colloquium 3/9/2012 "Modeling and Computation for Large-scale Air Traffic Flow Optimization"Posted Feb. 29, 2012
Modeling and Computation for Large-scale Air Traffic Flow Optimization
Dr. Dengfeng Sun
3:45 P.M - 5:00 P.M., March 9th 2012, 228 MSB
Abstract: Optimizing the nationwide air traffic flow is intrinsically challenging due to the size of the problem. This talk will present a solution which speeds up the optimization process. The nationwide air traffic is modeled using a Link Transmission Model, to which a dual decomposition method is applied to optimize the traffic. In this large-scale problem, a master problem and approximately 10,000 independent subproblems are formulated and these problems are solvable using personal computers; in particular, the subproblems can be solved in parallel using standard parallel computing techniques. In this talk, a parallel computing framework is also presented for the air traffic flow optimization problem. The master problem is solved on a server, and a client cluster is deployed to solve the subproblems such that the most computationally intensive part of the optimization can be executed in parallel. The sever and the clients communicate via TCP/UDP. An adaptive job allocation method is developed to balance the workload among each client, resulting in a maximized utilization of the computing resource.
Experimental results show that, compared to an early single process solution, this parallel computing framework considerably increases the computational efficiency. The runtime of a 2-hour nationwide air traffic flow optimization is reduced from two hours to six minutes with a 9-client cluster.
Bio: Dengfeng Sun received a bachelor's degree in precision instruments and mechanology from China's Tsinghua University, a master's degree in industrial and systems engineering from the Ohio State University, and a PhD degree in civil engineering from the University of California - Berkeley. Dr. Sun's research areas include control and optimization, with an emphasis on applications in air traffic flow management, dynamic airspace configuration, and studies for the Next Generation Air Transportation System(NextGen). His research is sponsored by the National Science Foundation, the National Aeronautics and Space Administration, and the Federal Aviation Administration.