Abstract:
The time it takes passengers to board an airplane is a known bottleneck of the turn-around time of aircraft and thus bears a significant cost-saving potential for airlines. Although minimizing boarding time therefore is the most important economic goal, previous efforts to design efficient boarding strategies apparently never tackled this task directly. We first rigorously define the problem and prove its NP-hardness even for very simple airplane cabin layouts. Although the theoretical intractability generally justifies the development of inexact heuristic solution methods, we show that all common boarding strategies may in fact give solutions that are far from optimal. We then discuss an exact mixed-integer programming (MIP) formulation, a simple time-aware boarding strategy with guaranteed approximation quality (under reasonable assumptions) as well as a local improvement heuristic for the airplane boarding problem. Our numerical experiments with realistic simulation data show that for several airplane cabin layouts, provably high-quality or even optimal solutions can be obtained within reasonable time in practice by means of our approximation scheme and MIP approach. We also empirically assess the sensitivity of boarding strategies with respect to disruptions of the prescribed boarding sequences -- we identify robustness against such disruptions as a bottleneck for further improvements, and conclude with some initial results on corresponding robust optimization approaches.
(Based on joint work with Felix Willamowski (RWTH Aachen)).
Bereits ab 16:45 Uhr gibt es für alle Interessierten die Möglichkeit zu einem Gespräch bei Kaffee und Tee im Sitzungszimmer (R206).
Olaf Ippisch
Veranstalter: Institut für Mathematik, Erzstraße 1, 38678 Clausthal-Zellerfeld