Optimisation

Complex networks for airline route management

Airline companies need to organize and manage their route networks in cost-efficient and reliable ways in order to cope with increasing customer demands and market changes. In collaboration with Xiaobing Hu, we have applied complex network concepts and techniques to model airline route networks and we develop an efficient genetic algorithm to optimize airline route networks in terms of properties that play a crucial role in making these networks cost-efficient and reliable.

The resulting algorithm is used to improve the topology of airline route networks in terms of operating costs and robustness.

Hu, X., and Di Paolo, E. A., (2007). A genetic algorithm based on complex networks theory for the management of airline route networks. In Proceedings of NICSO2007, Workshop on Nature Inspired Cooperative Strategies for Optimization, Acireale, Sicily (Italy), November8-10 2007. Studies in Computational Intelligence series, Springer-Verlag.

Novel genetic algorithm for gate-assignment problem

As a major issue in air traffic control operations, the gate assignment problem (GAP)at airport terminals aims to assign aircraft to terminal gates to meet operational requirements while minimizing both inconveniences to passengers and operating costs of airports and airlines. The term gate is used to designate not only the facility through which passengers pass to board or leave an aircraft but also the parking positions used for servicing a single aircraft. These station operations usually account for a smaller part of the overall cost of an airlines operations than the flight operations themselves. However, they can have a major impact on the efficiency with which the flight schedules are maintained and on the level of passenger satisfaction with the service.

We apply a genetic algorithm to the solution of the multi-objective GAP (focusing on passenger walking distance, baggage transport distance, and aircraft waiting time on the apron). The relative positions between aircraft rather than their absolute positions in the queues to gates are used to construct chromosomes in a novel encoding scheme, and a new uniform crossover operator, free of feasibility problems, is then proposed and studied.

Hu, X., and Di Paolo, E. A. (2008). An efficient genetic algorithm with uniform crossover for the multi-objective airport gate assignment problem, in K. C. Tan, C. K. Goh and Y. S. Ong (eds) Multi-Objective Memetic Algorithms, Springer-Verlag, pp. 71 – 90.

Hu, X., and Di Paolo, E. A. (2008). Genetic algorithms for the airport gate assignment problem: Linkage, representation and uniform crossover in Y.P. Chen and M.H. Lim (eds) Linkage in Evolutionary Computation, Springer-Verlag, pp 361 – 388.

Hu, X. and Di Paolo, E. A., (2007) An efficient genetic algorithm with uniform crossover for the multi-objective airport gate assignment problem, in 2007 IEEE Congress on Evolutionary Computation, CEC 2007, Singapore, September 25-28, 2007.

Hu, X-B, and Di Paolo, E., (2009). A ripple-spreading genetic algorithm for the airport gate assignment problem. IEEE Congress on Evolutionary Computation, CEC, 2009, Trondheim, Norway, 18-21 May, 2009.

Optimizing aircraft arrival sequencing and scheduling

Aircraft arrival sequencing and scheduling is a major issue in the daily air traffic control operations. We have applied genetic algorithms to tackle this problem in multi-runway systems. Most existing GAs for aircraft sequencing are confronted with feasibility and efficiency problems in the design of their evolutionary operators, particularly the crossover. Our new GA uses the sequencing relations between aircraft to encode solutions genetically. This makes it possible to design a highly efficient uniform crossover operator, which is hardly applicable to those GAs designed directly based on the order of aircraft in arrival queues. The main benefit from the proposed uniform crossover operator is the effectiveness and efficiency in identifying, inheriting and protecting common sub-traffic-sequences without sacrificing the capability of diversifying chromosomes. By adopting the strategy of receding horizon control, the reported GA exhibits a good potential of real-time implementation.

Hu, X., and Di Paolo, E. A. (2009) An efficient genetic algorithm with uniform crossover for air traffic control. Computers and Operations Research, 36: 245 – 259.

Hu, X., and Di Paolo, E. A. (2008) Binary representation based genetic algorithm for aircraft arrival sequencing and scheduling. IEEE Transactions on Intelligent Transportation Systems, 9, 301-310.