The Aircraft Boarding Problem …

                                The Aircraft Boarding Problem
                    Menkes H. L. van den Briel, J. Rene Villalobos, Gary L. Hogg
                              Department of Industrial Engineering
                                     Arizona State University
                                      Tempe, AZ 85287-5906

                                                      Abstract
By minimizing boarding time, commercial airlines can improve their on-time performance and increase their
aircraft/crew utilization and thereby increase profitability. Herein, we present preliminary results from combining IP
and a simulation model that suggest that structured group boarding can result in boarding time reductions.

Keywords: Integer Programming, Nonlinear Assignment Problems, Airlines, Aircraft Boarding

1. Introduction
When boarding a commercial aircraft, the passengers are usually assigned to groups that determine the order that
passengers board. The aircraft-boarding problem can be described as how to assign passengers to these boarding
groups such that the total boarding time is minimized. A reduction in total boarding time can result in significant
benefits for the airline industry. Boarding time is one of the significant elements of airplane turnaround time; i.e. the
time between flights that an airplane spends on the ground. Airplanes produce revenues while flying; thus it is
important that turnaround time be minimized. Turnaround time includes, airplane servicing, cargo handling,
deplaning, and boarding. For many airlines, boarding is the bottleneck element in the process. Thus, reductions in
boarding time result in revenue increases and/or cost reductions while potentially increasing passenger satis faction.
The practice of most commercial airlines has been to board passengers in groups formed by assigning passengers
sitting in contiguous rows to the same group. These groups are usually ordered from the back to the front of the
aircraft (back-to-front approach), with special groups (usually first class and special needs passengers) boarding the
aircraft before general boarding. The logic behind this boarding procedure is that the congestion of the aircraft aisle
will be minimized by freeing the journey of the passengers to the back of the aircraft from aisle obstacles. However,
it remains an open question whether this policy actually minimizes the total boarding time. An obvious problem
with the back-to-front approach is that the congestion created in a reduced area of the aisle among passengers of the
same group results in impediments for these passengers to stow their carry -on luggage and to reach their assigned
seat in an expedient manner. This observation leads to the conjecture that a different boarding approach, where the
groups are composed of passengers more dispersed throughout the aircraft, might actually perform better, than the
current back-to-front approach. Previous researchers have already explored this conjecture using simulation.
In a study by Marelli, Mattocks, and Merry [2] different boarding strategies and different airplane interior
configurations were tested on a Boeing 757 airplane using the Passenger Enplane/Deplane Simulation (PEDS)
developed by the authors. This study showed that by boarding "outside-in," i.e. window-seats first, followed by
middle seats and aisle seats last, boarding time could be decreased by as much as 17 minutes. The company "Shuttle
by United" was one of the first companies to start using this outside-in strategy. While it was reported that the
method was implemented with a good degree of success [3], the method was later discontinued and replaced by the
current approach: first class first, followed by premier class, and the rest of the passengers boarding using the back-
to-front approach.
Van Landeghem and Beuselinck [4] also used simulation to study numerous boarding strategies. Their study showed
that the fastest boarding method consisted of passengers boarding individually according to their seat and row
number. In addition, they also showed that by boarding by "half-row," i.e. splitting up of rows into two groups,
significant boarding time reductions could be achieved.
Regarding the techniques used to analyze the aircraft -boarding problem, it seems that simulation has been the tool of
choice. We are unaware of the use of any formal analytical, optimization model for this problem. Herein, we present
an integer programming formulation of the aircraft-boarding problem. The problem is formulated as a nonlinear
assignment problem where our objective is to minimize the total expected boarding time. We use the concept of
"boarding interferences" as a surrogate measure of boarding time. We define a boarding interference as being an
event where a passenger blocks the free flow of another passenger moving from the boarding gate to their seat. If
one could board an aircraft without any passenger interference, improvements could be made only by changing other
elements of the boarding process. Hence, we presume that there is equivalence between minimizing the total number
of interferences and the total boarding time. In this paper, we present the development of the analytical model first,
and then we build a simulation model of the aircraft-boarding procedure for an Airbus 320 (A320) airplane. We
then perform a cross-validation between the analytical and simulation models. Finally, we use the simulation model
to explore different aircraft-boarding scenarios.

2. Interference model
The minimization of total boarding time by assigning passengers to boarding groups is the goal of the aircraft-
boarding problem. However, explicitly including time related parameters in an analytical model increases the
complexity of the model representation and solution. Thus we resorted to a surrogate metric for time, the number of
expected passenger interferences under a particular assignment strategy. We model the aircraft-boarding problem as
a binary integer program with minimization of the total number of interferences as its objective function. We call
this model the "interference model." We make the assumption, without a formal argument, that the minimization of
interferences is equivalent to the minimization of total boarding time. In the interference model, we seek a grouping
of passengers that will minimize the total number of expected interferences. An assumption of the model is that
every passenger has been pre-assigned to a particular seat of the aircraft. A detailed discussion of interferences and
the model development follows.

2.1 Types of interference
We define two types of interferences, seat interference and aisle interference. Seat interference occurs when a
window or middle seat passenger boards later than the middle and/or aisle seat passenger that sits on the same side
and same row of the aircraft. For example, assume a passenger is seated in seat 7C (aisle seat in row 7). When the
passenger with seat 7B (middle seat in 7) boards the aircraft, passenger 7C must get out of their seat to allow
passenger 7B access. There may be an even longer delay when passenger 7A (window seat in row 7) arrives and
passengers 7B and 7C are already seated. Note that putting window-seat passengers in the groups boarding first
would minimize this type of interference.
By aisle interference, we mean the situation when a passenger boarding the aircraft has to wait for the passenger in
front of them to take their seat and to stow their luggage before proceeding to their seat, located further back in the
aircraft. Aisle interferences involve two passengers; we refer to the "first" passenger as the passenger right ahead of
the "second" passenger although they do not necessarily have to board as the first and second passengers in the
boarding process. Aisle interference can occur within one group, or between two consecutive groups. Note that we
assume passengers do not try to pass other passengers in the aisle of the aircraft.

2.2 Formulation of the aircraft-boarding problem
Consider an airplane having only one aisle with three seats on each side of the aisle (typical of Airbus 319 and 320,
and the Boeing 737 and 757). Let N = {1, 2, 3, ..., n} represent the set of rows and M = {A, B, C, D, E, F} represent
the set of seat positions in the aircraft. In addition, let the seats on the left side of the aisle be represented by L = {A,
B, C} and those on the right side by R = {D, E, F}, thus A and F are window seats, B and E are middle seats, and C
and D are aisle seats. Given a row number i  N and a seat position j  M, all seat locations in the aircraft can be
uniquely identified and represented by the pair (i, j) just as in a normal aircraft, such as in seat (7, C).
By assigning seats to groups (with a fixed seat assignment, this is similar to assigning passengers to groups) we are
able to form groups of different sizes and composition. For the defined boarding problem, we want to assign each
seat (i, j) to a boarding group k, with k  G, with G = {1, 2, 3, ..., g}, where g is the total number of groups used in
boarding the aircraft. Let the decision variable xijk = 1 if seat (i, j) is assigned to group k and xijk = 0 otherwise, for all
i  N, j  M, k  G.
The complete formulation of the aircraft -boarding problem is presented below. In this formulation, the equation
numbers alongside the model serve to clarify the purpose of each set of expressions. In the objective function, we
have different penalties for each type of interference. Seat interferences have penalties represented by  s and aisle
interferences by  a . The penalties associated with the different types of interferences, capture their relative
contribution to the total delay of the boarding procedure. These penalties are explained in detail in the next section.

Minimize: z = 1
                              s
                                   x
                                  i N   k G
                                              iAk   x iBk x iCk + 1 
                                                                  s

                                                                         i N
                                                                                 x
                                                                                 k G
                                                                                       iFk   x iEk x iDk +                                (1a)

s 
2           x           iAk
                              x iBk x iCl +  s 
                                             3               x         iAk
                                                                             x iBl x iCk +  s 
                                                                                            4           x           iAl
                                                                                                                          x iBk x iCk +   (1b)
   i N   k ,l G :k