Mixed-Integer Programming Solution to Zone-Based Air Traffic Management Problem

The study presented in this research discusses the Air Traffic Flow Management Problem by introducing alternative routing options for aircrafts in a constrained 3-dimensional capacitated airspace. The airspace is divided into a set of capacitated 3-dimensional sectors in order to depict the concept of a free flight situation in which the pilots have more autonomy. This study aims to minimize the total arrival time of all aircrafts to their final destinations while upholding timing and routing constraints and most importantly regarding the capacity constraints through which mid-air collision is avoided and safety is ensured. In order to achieve such a goal, a non-time indexed mixed integer programming model has been developed. Solving the model provides us with a comprehensive flight schedule consisting of the sequence of sectors each flight has to take and the exact departure and arrival times from/to each sector while the capacity constraints defined for all sectors ensure flight safety and collision avoidance at all times. This model takes multiple airports into consideration and despite the complexity of the problem and its NP-hard nature, is able to be solved for a number of flights on a personal computer using CPLEX. Furthermore, three different solution strategies are introduced in this research in order to tackle real-life size instances. First, we investigated the computational complexity of the problem by considering all flights in the system. Next, a sequential solution methodology is proposed. In the sequential solution method, first the problem is solved for a subset of flights. Next, new set of flights from remaining flight list according to their departure time are added to the airspace by considering the en-route flight plans of previously solved flight sets. The addition of new flights continued until an en-route flight plan for all flights is determined. Obviously the sequential solution method cannot guarantee optimality, yet the problem for large instance can be solved. Finally, an iterative conflict resolution methodology is proposed. In this method, first we relax some of the constraints so large instances can be solved. Next, flights that conflict with the actual constraint are identified and problem is solved to satisfy only these flights. The iteration is continued until no unresolved conflict is left. Performance of each solution methodology is demonstrated through various case studies