Flight Scheduling in the Airspace

This paper addresses an important problem in the aircraft traffic management caused by the rapid growth of air traffic. The air route traffic control center has to deal with different plans of airlines in which they specify a requested entry time of their aircraft to the airspace. Each flight has to be assigned to a track and a level in order to ensure the Federal Aviation Administration (FAA) safety standards. When two flights are assigned to the same track and level, a minimum separation time has to be ensured. If this condition could not be satisfied, one of the flight will be delayed. This solution is undesirable for many reasons such as missing the connecting flight, decrease in the passengers' satisfaction, etc. The problem of track-level scheduling can be defined as follows. Given a set of flights, each flight has to be assigned to one track and one level. To ensure the separation time between two flights assigned to the same track and level, it is possible to delay the requested departure time of a flight. The objective is to minimize the overall flight delay. To deal with this problem, we propose a mixed integer programming formulation to find a flight plan that minimizes the objective function, while ensuring the FAA safety standards. In particular, this model considers an aircraft-dependent separation time: the separation time depends on the type of the aircraft assigned to the same track and level. However, some problems are too large to be solved in a reasonable time with the proposed model using a commercial solver. In this study, we developed a scatter search (SS) to deal with larger instances. SS is an evolutionary heuristic and the feature to be a problem-independent structure. This metaheuristic has been efficiently applied to a variety of optimization problems. Initially, SS starts with a set of solutions (reference set) that is constantly updated through two procedures (solution generation and combination) in the aim to produce high-quality solutions. In order to assess the quality of the exact method and the scatter search, we carried out an experimental study on a set of instances that are generated from a real case data. This includes small (80 to 120 flights), medium (200 to 220 flights), and large (400 to 420 flights) instances. The mathematical model has been solved using CPLEX 12.6 and the scatter search has been coded using C language under Microsoft Visual Studio v12 environment. The tests were conducted under a Windows 7 machine with an Intel Core i7 and 8 GB of RAM. The model was tested on each instance with 1 hour time limit. The results show that no instances have been solved to optimality. For small instances, the model and the scatter search provide comparable results; however, for medium and large instances, scatter search gives the best results.qscienc