Queuing Theory and Markov Chains in Airplane Boarding: An Econometric Approach

Tags: #Operations Research

Introduction

The idea for this blog originated on an 1 hour long boarding process on my last trip. The process of boarding an airplane appears deceptively simple; yet, it exhibits surprisingly high delays compared to boarding other forms of transportation such as buses or trains. This document aims to provide a mathematically rigorous explanation of why the boarding process is so inefficient. We build a model that captures both stochastic delays (due to bag stowing, seating interference, etc.) and systematic constraints imposed by the boarding procedure.

In what follows, we leverage the tools of queuing theory and Markov chain analysis to derive insights into the dynamics of airplane boarding. We also discuss several potential improvements to the boarding process and provide theoretical justification for their efficiencies.

Problem Statement

The Boarding Process Overview

In typical airline operations for economy-class passengers, boarding is performed using a Back-to-Front (B2F) procedure. In this method, passengers enter in a single file, with the following major sources of delay:

  1. Seat Interference (Seat Shuffle): When a passenger finds their seat, they may block the aisle while storing their carry-on bag or waiting for a neighboring passenger to move.
  2. Carry-on Luggage: The time required to stow luggage in overhead compartments can cause substantial delay for passengers behind them.
  3. Boarding Grouping: First-class and business-class passengers often board prior to economy, further complicating the flow of passengers.

These elements collectively result in an unexpectedly long boarding time.

Mathematical Modeling of the Boarding Process

Total Boarding Time

Let the total boarding time $( T )$ be modeled as: $$[ T = \sum_{i=1}^{N} t_i + \sum_{j=1}^{M} d_j, ]$$ where:

  • $( N )$ is the total number of passengers.
  • $( t_i )$ is the intrinsic time required for passenger $( i )$ to find and occupy their seat.
  • $( M )$ represents the number of interference events (e.g., waiting for a neighboring passenger or bag stowing), with $( d_j )$ being the delay caused by the $( j )$-th event.

If we assume $( t_i )$ and $( d_j )$ are random variables with means $(\mu_t)$ and $(\mu_d)$, respectively, then the expected total boarding time is: $$[ \mathbb{E}[T] = N \mu_t + M \mu_d. ]$$

Queuing Model Perspective

The boarding process can be seen as a single-server queue where the “server” is the aisle. Each passenger must wait until the preceding passenger completes their boarding operation. Under this view, if the service time (boarding and seating) is $( S )$ and the arrival process is sequential, then the delay induced by a single passenger is propagated to all those behind them.

Markov Chain Model of Boarding Dynamics

Formulating the Markov Chain

We now propose a discrete-time Markov chain to model the progression of boarding. Define the state space as: $$[ \mathcal{S} = {0, 1, 2, \dots, N}, ]$$ where state $( k )$ represents that $( k )$ passengers have successfully taken their seats.

The system transitions from state $( k )$ to state $( k+1 )$ when the next passenger completes the boarding operation. However, delays due to interference events (such as the “seat shuffle” or bag stowing) can be modeled as self-transitions where the system remains in state $( k )$ for one or more time steps.

Let $( P_{ij} )$ be the transition probability from state $( i )$ to $( j )$. The structure of the transition probabilities is as follows:

  • $( P_{k,k+1} = p )$ represents the probability that the $( (k+1) )$-th passenger completes the boarding process in the next time step.
  • $( P_{k,k} = 1 - p )$ represents the probability that the system experiences a delay at state $( k )$.

Thus, the transition matrix $( P )$ has the following form for $( 0 \leq k < N )$: $$[ P_{k,k+1} = p, \quad P_{k,k} = 1 - p, \quad \text{and} \quad P_{N,N} = 1. ]$$

Expected Time to Absorption

The state $( N )$ is absorbing (i.e., all passengers are seated). The expected number of steps $( E_k )$ to reach state $( N )$ starting from state $( k )$ satisfies the recurrence: $$[ E_k = 1 + p,E_{k+1} + (1-p),E_k, \quad 0 \leq k < N, ]$$ which simplifies to: $$[ E_k = \frac{1}{p} + E_{k+1}. ]$$ By recursively solving this equation with the boundary condition $( E_N = 0 )$, we obtain: $$[ E_0 = \frac{N}{p}. ]$$ This result indicates that the expected total boarding time (in units corresponding to the time step) is inversely proportional to the probability $( p )$ that a boarding action completes without interference.

Theoretical Analysis and Proofs

Theorem: Delay Propagation in a Sequential Queue

Theorem. Under the assumption that each boarding event (without interference) occurs independently with probability $( p )$, the expected boarding time $( \mathbb{E}[T] )$ for $( N )$ passengers is given by $$[ \mathbb{E}[T] = \frac{N}{p}. ]$$

Proof.
Consider the boarding process as a discrete-time Markov chain with the state $( k )$ representing the number of seated passengers. The process transitions to state $( k+1 )$ with probability $( p )$ in each time step. Let $( E_k )$ be the expected time to absorption (state $( N )$) starting from state $( k )$. Then, for $( k < N )$: $$[ E_k = 1 + p,E_{k+1} + (1-p),E_k. ]$$ Rearranging the terms, we have: $$[ p,E_k = 1 + p,E_{k+1} \quad \Rightarrow \quad E_k = \frac{1}{p} + E_{k+1}. ]$$ With the boundary condition $( E_N = 0 )$, a telescoping sum yields: $$[ E_0 = \frac{1}{p} + \frac{1}{p} + \dots + \frac{1}{p} = \frac{N}{p}. ]$$ Thus, the expected boarding time is $( \mathbb{E}[T] = \frac{N}{p} )$, which proves the theorem.
$(\square)$

Proposed Improvements to the Boarding Process

Method 1: Random Boarding

Concept:
Allow passengers to board in a random order, thereby decoupling spatial correlations and reducing clustered delays.

Mathematical Justification:
Let $( \tau_i )$ be the delay incurred by the $(i)$-th passenger due to interference (e.g., bag stowing, seat shuffling). In the Back-to-Front (B2F) method, delays are sequentially correlated, meaning that a delay from one passenger propagates to those behind. This can be modeled by assuming that delays in B2F have a positive covariance: $$[ \text{Var}(T_{B2F}) = \sum_{i=1}^{N} \text{Var}(\tau_i) + 2\sum_{i<j} \text{Cov}(\tau_i, \tau_j), ]$$ where the covariance terms contribute significantly to the overall variability and hence the likelihood of compounded delays.

In contrast, under random boarding, assume that each $( \tau_i )$ is an independent and identically distributed (i.i.d.) random variable with mean $(\mu)$ and variance $(\sigma^2)$. Then, the expected total delay is: $$[ \mathbb{E}[T_{\text{random}}] = \sum_{i=1}^{N} \mathbb{E}[\tau_i] = N\mu, ]$$ and the total variance is minimized to: $$[ \text{Var}(T_{\text{random}}) = N\sigma^2. ]$$ The elimination of positive covariance terms in random boarding reduces the probability of extreme delays, thereby yielding a more efficient boarding process from a statistical perspective.

Method 2: Window-to-Aisle Boarding

Concept:
Segment the boarding process into three distinct phases:

  1. Passengers with window seats board first.
  2. Followed by those with middle seats.
  3. Finally, passengers with aisle seats board last.

This method minimizes the interference where a seated passenger must stand to allow access to an adjacent seat.

Mathematical Justification:
Assume that in the traditional B2F method, the effective probability that a passenger completes boarding without interference is ( p ), leading to an expected boarding time modeled by the Markov chain result: $$[ \mathbb{E}[T_{B2F}] = \frac{N}{p}. ]$$

Under the Window-to-Aisle method, we partition the boarding process into three phases with different interference probabilities:

  • $( p_w )$ for window seats,
  • $( p_m )$ for middle seats, and
  • $( p_a )$ for aisle seats, with $( p_w > p_m > p_a )$ (interpreting a higher $( p )$ as a lower chance of interference).

Let $( N_w )$, $( N_m )$, and $( N_a )$ denote the number of passengers in each boarding group, such that $( N = N_w + N_m + N_a )$. The expected boarding time for each group can be approximated by: $$[ \mathbb{E}[T_{w}] = \frac{N_w}{p_w}, \quad \mathbb{E}[T_{m}] = \frac{N_m}{p_m}, \quad \mathbb{E}[T_{a}] = \frac{N_a}{p_a}. ]$$ Thus, the overall expected boarding time becomes: $$[ \mathbb{E}[T_{W-A}] \approx \frac{N_w}{p_w} + \frac{N_m}{p_m} + \frac{N_a}{p_a}. ]$$

By segregating the boarding order, the likelihood of sequential interference events is reduced. In particular, passengers who are most likely to cause delays (typically those seated at the aisle) board last, which mathematically translates into a higher effective $( p )$ for the earlier groups. Consequently, the overall expected boarding time $(\mathbb{E}[T_{W-A}])$ is reduced compared to the B2F approach, and the variance in boarding times is also diminished, leading to a more predictable process.

These rigorous mathematical justifications quantify the benefits of alternative boarding methods by comparing both the expected delays and their variances, offering a robust framework to evaluate improvements in boarding efficiency.

Conclusion

We have presented a mathematical treatment of the airplane boarding process by:

  • Modeling the total boarding time as the sum of individual seating times and interference delays.
  • Formulating the boarding process as a discrete-time Markov chain and deriving the expected boarding time.
  • Proving that under simplified assumptions, the expected boarding time is $( \frac{N}{p} )$.
  • Analyzing the benefits of alternative boarding methods, such as random boarding and window-to-aisle boarding, through the lens of queuing theory and Markov processes.

This rigorous approach not only explains the inefficiencies inherent in the current system but also provides a quantitative framework for evaluating potential improvements. Further research could involve more detailed stochastic modeling, incorporating heterogeneous passenger behaviors and dynamic aisle-blocking events, to better reflect real-world boarding conditions.