A variable neighborhood search for optimal scheduling and routing of take-off and landing aircraft

This paper deals with the development of meta-heuristic algorithms for the real-time traffic management problem of scheduling and routing landing and take-off operations at busy terminal control areas. The objective is to reduce the traffic controller workload and to limit airport congestion via intelligent traffic control decisions. We formulate this problem as a mixed integer linear program and solve it via a tabu search algorithm and variable neighborhood search algorithms. The development of metaheuristics is motivated by the fact that the problem is strongly NP-hard and heuristic algorithms are typically adopted in practice to compute good quality solutions in a short computation time. The algorithmic framework starts from a good initial solution for the aircraft scheduling problem with pre-defined routes, obtained via a truncated branch-and-bound algorithm. A metaheuristic is then applied to improve the solution by changing the routing of some aircraft. The neighbourhood of a solution is characterized by the number of aircraft to be re-routed. Computational experiments are performed on two Italian airports and various sources of disturbance. The variable neighborhood search algorithms outperform the tabu search algorithm within a small computation time.