Optimization Online


Minimizing Airplane Boarding Time

Felix J.L. Willamowski(willamowski***at***or.rwth-aachen.de)
Andreas M. Tillmann(a.tillmann***at***tu-braunschweig.de)

Abstract: The time it takes passengers to board an airplane is known to directly influence the turn-around time of the aircraft and thus bears a significant cost-saving potential for airlines. Although minimizing boarding time therefore is the most important goal from an economic perspective, previous efforts to design efficient boarding strategies apparently never tackled this task directly. In this paper, we first prove strong NP-hardness of the problem. While this generally justifies the development of inexact solution methods, we demonstrate that all commonly discussed boarding strategies may in fact give solutions that are far from optimal. We complement these theoretical findings by a simple time-aware boarding strategy with guaranteed approximation quality (under very reasonable assumptions) as well as mixed-integer programming formulations. Numerical experiments with structured random data show that for several airplane cabin layouts, provably high-quality or even optimal solutions can be obtained within reasonable time in practice.

Keywords: Airplane Boarding, Complexity, Optimization

Category 1: Applications -- OR and Management Sciences

Category 2: Combinatorial Optimization

Citation: @techreport{repORt:2019-56, author = {F.J.L. Willamowski and A.M. Tillmann}, title = {Minimizing Airplane Boarding Time}, institution = {Lehrstuhl f\"{u}r Operations Research, RWTH Aachen University}, year = {2019}, type = {repORt}, number = {2019--56}, month = {Nov} }

Download: [PDF]

Entry Submitted: 11/04/2019
Entry Accepted: 11/05/2019
Entry Last Modified: 11/04/2019

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society