A real-time schedule method for Aircraft Landing Scheduling problem based on Cellular Automation

The Aircraft Landing Scheduling (ALS) problem has been a complex and challenging problem in air traffic control for a long time. In practice, it can be formulated as a constrained optimization problem that needs to be solved in real-time. Although quite a few optimization techniques, e. g., linear programming-based approaches and evolutionary algorithms, have been shown to be good solver of ALS problems with small number of aircrafts, their relatively high computational cost prohibits their applications in the real world. In this paper, we propose a cellular automata optimization (CAO) approach to the ALS problem. The CAO approach solves the ALS problem in two major steps. First, a good aircraft landing sequence is obtained by simulating the aircraft landing process using a CA model. Then, the exact landing time of each aircraft is determined by a simple yet effective local search procedure. Experimental study on 13 data sets in the OR-Library was conducted to compare the CAO approach and several popular approaches in the literature. It was observed that the CAO method managed to attain high quality solutions on most of the test problem. More importantly, the computational time (in CPU seconds) of CAO method is extremely short. In most cases, satisfactory solutions can be obtained by the CAO approach within 4 s, which perfectly fulfills the requirement of the real-world air traffic control system. (C) 2011 Elsevier B.V. All rights reserved.