Distributed Flight Routing and Scheduling for Air Traffic Flow Management

Air traffic flow management (ATFM) is an important component in an air traffic control system and has significant effects on the safety and efficiency of air transportation. In this paper, we propose a distributed ATFM strategy to minimize the airport departure and arrival schedule deviations. The scheduling problem is formulated based on an en-route air traffic system model consisting of air routes, waypoints, and airports. A cell transmission flow dynamic model is adopted to describe the system dynamics under safety related constraints, such as the capacities of air routes and airports, and the aircraft speed limits. Our ATFM problem is formulated as an integer quadratic programming problem. To overcome the computational complexity associated with this problem, we first solve a relaxed quadratic programming problem by a distributed approach based on Lagrangian relaxation. Then a heuristic forward-backward propagation algorithm is proposed to obtain the final integer solution. Experimental results demonstrate the effectiveness of the proposed scheduling strategy.