Improving Lower Bound for Aircraft Routing Optimization. An Application of Lagrange Relaxation
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Complex adaptive systems (MPCAS), MSc
Publicerad
2023
Författare
Hult , Karin
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
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.
Beskrivning
Ämne/nyckelord
Aircraft routing, Lagrange relaxation, non-smooth optimization, subgra dient optimization, Polyak step size, network flow, lower bounds.