Modular Multi-Objective Genetic Algorithm for Large Scale Bi-level Problems.

Peak-load pricing (PLP), a two-tariff pricing scheme commonly used in public transport and utilities, is tested on the European Air Traffic Management (ATM) system as a means for reducing airspace congestion. In particular, a centralised approach to PLP (CPLP) where a Central Planner (CP) sets en-route charges on the network is presented. CPLP consists of two phases: in the first phase congested airspace sectors and their peak and off-peak hours are identified; in the second phase the CP assesses and sets en-route charges in order to reduce the overall shift on the network, where shift is intended as the difference between the actual and the scheduled flight departure times. Such charges should guarantee that Air Navigation Service Providers (ANSPs) are able to recover their operational costs while inducing the Airspace Users (AUs) to route their traffic in such way that the network is able to sustain it. The interaction between CP and AUs is modelled as a Stackelberg game and formulated by means of bilevel linear programming. A Genetic Algorithm is used to solve the CPLP model based on a dataset obtained from historical data for an entire day of traffic on the entire European airspace (approximately 30,000 flights). GAs are very popular stochastic optimization methods and are particularly suitable for solving multi-objective problems and finding reasonably good trade-off solutions. Results show that significant improvements in traffic distribution in terms of both shift and sector load can be achieved through this simple en-route charges modulation scheme. We model the relationship between the CP and the AUs as a Stackelberg game where the leader (CP) has a comprehensive knowledge on the entire system and makes his decision first, to which the follower(s) (AUs) must react. The Stackelberg equilibrium is obtained by means of an optimisation problem formulated as a bilevel linear programming model where the CP sets one peak and one off-peak en-route charge and the AUs choose the route among the available alternatives.