Optimal Sequential Backward Flow Saturation for cell transmission model

The cell transmission model for air traffic flow was built by Sun and Bayen. The problem of managing the flow under sector capacity constraints was formulated as an integer programming problem. However, the corresponding relaxed linear programming in their work failed to give the integer solution for the aircraft count, which is not applicable in practice. In this paper we propose the Optimal Sequential Backward Flow Saturation paradigm to find the optimal integer solution. Firstly we introduce the Backward Flow Saturation on a single path. Secondly the Sequential Backward Flow Saturation is developed to solve a M-path problem given a certain path sequence. Then we show that the path sequence is critical and the Sequential Backward Flow Saturation under an arbitrary path sequence can not guarantee the optimal solution. Finally inspired by the Branch and Bound technique (B&B), we design a decision tree searching to provide the Sequential Backward Flow Saturation the optimal path sequence. The final algorithm Optimal Sequential Backward Flow Saturation Algorithm is proved to give the optimal integer solution.