Improving Lower Bound for Aircraft Routing Optimization. An Application of Lagrange Relaxation

Abstract

Aircraft routing is a complicated optimization problem which can be modelled as a form of resource-constrained integer multi-commodity network flow problem. When optimizing this problem, a good lower bound is useful to assess the quality of feasible solutions and for determining convergence of the solution algorithm. The technique currently used to calculate lower bounds is very fast, but does several relaxations on top of each other, which might yield a quite weak lower bound. This fact raises the question if it could be possible to develop an efficient method to strengthen the lower bound. This master thesis examines an alternative method of calculating a lower bound by performing Lagrange relaxation with respect to only one constraint group, which theoretically would lead to a stronger lower bound. Subgradient optimization with Polyak step size is used to solve the Lagrangian dual problem. Tests are performed, both with realistic implementations and with idealistic parameters, to investigate the potential of Lagrange relaxation, and solving the Lagrange dual problem with subgradient optimization. Lastly the results are compared with an linear programmingbased relaxation of the original problem. The Lagrange relaxation shows promise as the idealized tests resulted in a significant improvement of the lower bound for most of the studied test cases. However, the realistic implementations of subgradient optimization did not perform consistently well for all the test cases; this indicates that improvements of the implementations are required for this method of solving the Lagrange dual problem to be usable in practice.