25 Apr 2016
A Simple Discrete-time Model
In this series of posts, I will be describing a simple simulation model of passengers boarding an airplane. This is a situation which most of us have experienced first-hand, and as the airlines keep putting more and smaller seats in the planes the experience becomes increasingly unpleasant from a passenger standpoint. From the airlines' standpoint, however, the ability to herd passengers into and out of their planes has direct economic consequences, as the more time a plane spends on the ground, the less money it is making for the airline. When considered over the thousands of flights an airline runs per year, the savings of even a few minutes of gate time can result in significant cost savings.
One apporach to optimizing the boarding process would be to use either real or mocked up aircraft cabins and either actual passengers or surrogates, and to test the strategies 'live'. One could see this being an expensive proposition. another more economical option is computer modeling.
The model presented here is an extremely simplified one that ignores many of the messy realities of people trying to get their luggage and themselves loaded on board. The key assumptions underlying this model are:
Passengers enter the plane from a boarding queue that determines their order of entry.
Other then thier seating information, passengers are identical
Passengers move at uniform speed down the aisle in one direction only (towards the rear of the plane).
Passengers waiting in the aisle 'block' passengers behind them.
The time required to 'seat' from the aisle is dependent on the number of people already seated between the aisle and the passenger's target seat. Moving into a window seat will take longer if people are already in the middle and aisle seats.
Time is modeled in discrete fashion, where a small time-step (e.g. 0.2s) is used to advance the simulation. The model's state is represented by three main items:
Boarding Queue - This is an ordered list of passenger records which contains the passenger seating information. As passengers are transferred from the boarding queue to the aisle, they are assigned a sequential boarding order which is carried through the model to the seating array.
Aisle - The Aisle consists of a series of 'slots' holding passenger information, and also state information. Each aisle slot is handled as an independent state machine which interacts with previous and succeeding aisle slots, as well as the seating array. In this model two aisle 'slots' are provided per seating row, so that two passengers can be accomodated in the aisle for every row of seats.
Seating Array - The seating array is a passive array into which passengers are deposited. Seats are either empty or occupied, with an optional code that is used to indicate boarding queue order.
Each aisle slot is implemented as a state machine with 5 states as shown below. There are five major states and a timer used for realizing delays - this creates a number of substates. The first state is EMPTY, in which the aisle slot is unoccupied. If the previous aisle slot is in state ADVANCING, the the current aisle slot can move to JUST_FILLED. Once in this state, the next state can be either SEATING (if the passenger row matches the aisle row) or WAITING_TO_ADVANCE if the passenger must move on. In both cases, the timer is loaded with a value corresponding either to the seating time or the advance time. When the timer expires, the state machine moves to the EMPTY state (in the case of SEATING) or ADVANCING, in the case of WAITING_TO_ADVANCE. The state machine will remain in the ADVANCING state until the following aisle slot enters an EMPTY state so it can accept a passenger. Passenger information is also transferred between the aisle slot state machines at this time.
The aisle slot state machines communicate with their previous and sucesisve neighbors, as well as the seating array. Not all aisle slots have a provision to intercat with the seating array, as shown below. Aisle slot '0' has a simplified state machine that allows it to interact with the boarding queue as an input instead of a prior state machine.
The simulation implementation includes an animated view of the cabin status. In addition to its entertainment value, the animation is also useful as an aid to debigging the model and code. In the cabin view shown below, passengers in the aisle are represented by black ovals (entering from the left) while the seat array is indicated by squares - white for empty and green for occupied. In additon, the boarding order is indicated in each occupied seat.
Part II of this blog will discuss differences in boarding strategies.