An Evolutionary Multi-Objective Optimization Framework for Bi-level Problems

Genetic algorithms (GA) are stochastic optimization methods inspired by the evolutionist theory on the origin of species and natural selection. They are able to achieve good exploration of the solution space and accurate convergence toward the global optimal solution. GAs are highly modular and easily adaptable to specific real-world problems which makes them one of the most efficient available numerical optimization methods. This work presents an optimization framework based on the Multi-Objective Genetic Algorithm for Structured Inputs (MOGASI) which combines modules and operators with specialized routines aimed at achieving enhanced performance on specific types of problems. MOGASI has dedicated methods for handling various types of data structures present in an optimization problem as well as a pre-processing phase aimed at restricting the problem domain and reducing problem complexity. It has been extensively tested against a set of benchmarks well-known in literature and compared to a selection of state-of-the-art GAs. Furthermore, the algorithm framework was extended and adapted to be applied to Bi-level Programming Problems (BPP). These are hierarchical optimization problems where the optimal solution of the bottom-level constitutes part of the top-level constraints. One of the most promising methods for handling BPPs with metaheuristics is the so-called "nested" approach. A framework extension is performed to support this kind of approach. This strategy and its effectiveness are shown on two real-world BPPs, both falling in the category of pricing problems. The first application is the Network Pricing Problem (NPP) that concerns the setting of road network tolls by an authority that tries to maximize its profit whereas users traveling on the network try to minimize their costs. A set of instances is generated to compare the optimization results of an exact solver with the MOGASI bi-level nested approach and identify the problem sizes where the latter performs best. The second application is the Peak-load Pricing (PLP) Problem. The PLP problem is aimed at investigating the possibilities for mitigating European air traffic congestion. The PLP problem is reformulated as a multi-objective BPP and solved with the MOGASI nested approach. The target is to modulate charges imposed on airspace users so as to redistribute air traffic at the European level. A large scale instance based on real air traffic data on the entire European airspace is solved. Results show that significant improvements in traffic distribution in terms of both schedule displacement and air space sector load can be achieved through this simple, en-route charge modulation scheme.