An Evolutionary Multi-Objective Optimization Framework for bi-level problems

Stefano Costanzo

CHALLENGE - Many real-world problems (related to management, economic planning and engineering) involve a hierarchical relationship between two decision levels. This poses several challenges, including randomness, two-level decision making and conflicting objectives. A promising method for handling these problems is the Bi-level Programming. Bi-level Programming Problems (BPPs) are hierarchical optimization problems where an optimal solution at the lower level is used as a constraint at the upper level. This work introduces an optimization framework based on the proprietary Multi-Objective Genetic Algorithm for Structured Inputs (MOGASI) which was extended and adapted to two real-world BPPs related to pricing systems.

SOLUTION - The first application is the Network Pricing Problem (NPP). An authority sets road network tolls and tries to maximize its profit, whereas users traveling on the network try to minimize their costs. The optimization results obtained with an exact solver on one hand and the MOGASI bi-level nested approach on the other hand are compared. The aim was to identify the problem dimensions where the MOGASI approach performs best. The second application is the Peak-load Pricing (PLP) Problem. The aim was to investigate the possibility to mitigate the European air traffic congestion. The PLP problem has been reformulated as a multi-objective BPP and solved with the MOGASI nested approach based on real air traffic data. The idea was to modulate charges imposed on airspace users and in this way re-distribute air traffic. Results show significant improvements in air traffic distribution in terms of both flight timetable observation and airspace sector load on a large scale instance.

BENEFITS - The main contribution of this study is the application of special-purpose genetic algorithm and the adaptation of its behavior to the problem characteristics. In future work heavy testing of the specialized components of MOGASI will be performed using selected problems. The number of these components will be expanded to include a wider variety of structures that the algorithm can handle. The performance of this approach will also be studied in detail on mixed-integer and combinatorial problems. Finally, MOGASI will be considered for inclusion in the modeFRONTIER algorithm portfolio.