task 2

Task 2 consists in the development of solution methods to address in acceptable time the multi-objective optimization model of Task 1. MILP models can be solved by using either exact methods or approximate methods. The exact methods guarantee an optimal solution, however sometimes they can lead to impracticable computational times as instance size increases. They will thus be applied, first, to small and mid-size airports where exact methods are hypothesized to be tractable in realistic settings. However, it is highly unlikely that exact methods can be used to handle the largest airports worldwide. In this case, we will need to resort to approximate methods, such as hybrid meta-heuristics.

The application of exact methods can be made through sophisticate commercial software packages, such as XPRESS, CPLEX or Gurobi. These packages implement advanced branch-and-cut algorithms, which can be coupled with decomposition techniques in the case of large instances of difficult models. Tailored solution algorithms will be developed to enhance the computational performance of the model, and enable it to be solved exactly at the largest airports possible. Typical techniques that will be investigated include valid inequalities (to make the feasible solution of the mixed-integer programming model closer to its linear relaxation), and decomposition algorithms that rely on special structures of the data matrices, allowing to solve several smaller problems rather than a unique problem.

If the largest instances cannot be solved to (provable) exact optimality, then it will be necessary to resort to approximate methods. In particular, we will experiment with hybrid metaheuristic algorithms. These algorithms combine metaheuristic components both of the local search type (such as simulated annealing, tabu search, iterated local search, variable neighborhood search or greedy randomized adaptive search procedure) and of the population search type (such as genetic algorithms and particle swarm) with other optimization techniques such as constrained, dynamic or mathematical programming. The motivation behind hybrid metaheuristics is the exploitation of the complementarities of different resolution strategies. The choice of combinations of complementary algorithms is crucial mostly for hard optimization problems and requires expertise in different areas of optimization. Through extensive algorithm developments and computational experiments, we expect to show that approximate methods can result in at least close-to-optimal outcomes in small and mid-size instances where solutions can be obtained from both exact and approximate methods. Once such validation will be performed, the approximate solution algorithms will then be applied to solve larger instances where exact solution algorithms cannot provide solutions in reasonable computational times.