Using computational intelligence for large scale air route networks design

Due to the rapid development of air transportation, Air Route Networks (ARNs) need to be carefully designed to improve both efficiency and safety of air traffic service. The Crossing Waypoints Location Problem (CWLP) plays a crucial role in the design of an ARN. This paper investigates this problem in the context of designing the national ARN of China. Instead of adopting the single-objective formulation established in previous research, we propose to formulate CWLP as a bi-objective optimization problem. An algorithm named Memetic Algorithm with Pull-Push operator (MAPP) is proposed to tackle it. MAPP employs the Pull-Push operator, which is specifically designed for CWLP, for local search and the Comprehensive Learning Particle Swarm Optimizer for global search. Empirical studies using real data of the current national ARN of China showed that MAPP outperformed an existing approach to CWLP as well as three well-known Multi-Objective Evolutionary Algorithms (MOEAs). Moreover, MAPP not only managed to reduce the cost of the current ARN, but also improved the airspace safety. Hence, it has been implemented as a module in the software that is currently used for ARN planning in China. The data used in our experimental studies have been made available online and can be used as a benchmark problem for research on both ARN design and evolutionary multi-objective optimization.