Simulation - Airplane Boarding Part III - EdsCave

1 May 2016

In part I of this blog, we showed a simple simulation that modeled the airplane boarding process, and in part II we showed how this simulation model could be used to compare different boarding strategies.  In this final installment we will examine a method for automatically designing effective boarding strategies.

While it is possible to manually design a series of boarding strategies and to compare their effectiveness through simulation, as we did in the last installment, it is also possible to automate the design process.  In this case, the computer does the work of figuring out what the 'best' strategy should be. One method for doing this uses a technique known as an Evolutionary Algorithm, or EA.

EA's are used to find optimal configurations for complex systems, and are particularly useful in cases where the system's behavior is difficult to analyze or is difficutl to cast into a form where other more traditional techniques such as linear programming can be used.  In an EA, the system configuration is encoded into a representation called a chromosome, which is essentailly just a list of numbers in which the values and order describe key features of the system of interest.  In the case of our 6-zone boarding strategy, the chromosome's encoding is pretty straightforward - a list of the seats in each of the six boarding zones. This is effectively six sub-lists corresponding to the seats within each boarding zone.

Organization of Boarding Strategy 'Chromosome'

One of the key features of an EA is that it works with not a single a single chromosome, but uses a population of different chromosomes. The intent is to mimic some of the features of natural evolution, specifically natural selection and mutation. when you use an EA to solve a problem, you are selectively breeding a solution to meet some desired characteristics, much as you might breed plants or animals.

An EA Requires a Population of Chromosomes with varying 'Fitness' Levels

To start off, an EA requires that an initial population be selected. This initial population is typically chosen to have random characteristics. In the case of this boarding problem we will build the initial population with differing 'random' boarding assignments.  For this problem we will use a population comprising 50 member chromosomes.

After an initial population has been selected, the EA progresses by repetitively performing a series of steps. Each cycle through these steps results in a new generation of population. These steps are:

1) Evaluation - In this step, the 'fitness' of each member of the population is determined. In the case of our boarding problem, fitness is defined by boarding time, with shorter boarding times being considered higher fitness levels.

2) Selection - The population is ranked from high to low levels of fitness, and the least fit chromosomes are removed.

3) Reproduction - The chromosomes that survived the selection process are then copied, and some or all of the copies are 'mutated' so that they are slightly different from their parents.

These three steps are then repeated until the process ceases to provide significant improvements to the population's fitness level.

While the overall EA process is applicable to a wide range of optimization problems, the details needed to sucessfully  adapt the EA technique to a given problem may vary greatly.  For the boarding problem, since the boarding time is dependent on the actual seating order that occurs within each zone, so just simulating the order specified in the chromosome may not provide a particularly representative of how the boarding order performs over all conditions. To get a more accurate measurement of quality requires randomly shuffling the seats within each zone and performing multiple runs (in this case 25) to obtain an average boarding time over possible variations.

Evaluating the 'Fitness' of a Chromosome requires multiple simulations with intra-zone shuffling of seating order

Another detail that is specific to this problem is that of how to 'mutate' a chromosome.  A mutation for this problem is implemented by swapping seats between different boarding zones. Additionally, between 0 and 10 mutations can occur when a chromosome reproduces - this helps both speed up the evolution process and helps keep the population from becoming too homogenous.

To 'Mutate' a Chomosome Requires Exchanging Seats Between Different Boarding Zones

For this problem we ran the EA for 2000 generations. Below you can see a chart showing the both the fitness of the entire population (blue), and the fitness of the most fit member (red) over the different generations.  Note that since better 'fitness' is defined as shorter boarding times, these lines go down over time. The improvement starts out fast from the initial random state, and tends toward better with suceeding generations. One reason the trend is not monotonic (continually decreasing) is that there is some uncertainty in fitness measurement.   This uncertainty comes from the shuffle-and-average process described above. If we were to use a larger number of samples, for example 100 or 1000, this uncertainty would be reduced - but the trade-off would be vastly increased computer run-times.  This problem took ~2 hours to run on a desktop computer.

Convergence of the Average Population Fitness and that its Best Individual Chromosome

The final result of the above process is the 6-zone boarding zone order shown below, with an average boarding time of 645 seconds. This is a little better than the 6-zone outside-to-inside strategy shown in the last installment (680 seconds average boarding time).  While the improvement is not very great, only about 5% better, the important thing is that employing an EA to discover it did not require any kind of profound knowledge or thought. The main requirements for using an EA to 'solve' a problem is that we can represent or encode potential solutions as chromosomes, and that we have a way of evaluating how good those solutions are relative to one another.  This becomes especially important as the problem becomes more complex and less suceptible to solution through either analysis or insight. For example, if the aircraft had more than one aisle (like in a 747) or a non-uniform seating plan, we could still use an EA to find a good boarding strategy as long as we could still build an effective simulation model.

Best Evolved Boarding Strategy 2000 generations - 645 Seconds Average Boarding Time

One frequent characteristic of 'evolved' solutions is that they may not appear to make much sense. This is certainly the case here, as the solution appears pretty 'random'.  Buried in it, however, are some islands of order.  For example, the final boarding zone (6-violet) is laid out very similarly to that of the 6-zone outside-to-inside scheme. Also, the first boarding zone (1-red) is skewed to the rear of the cabin - something that also makes sense.  The other zones, however appear to be randomly distributed. This is one of the intellactual trade-offs that come with using EAs to solve problems - you  often trade the understandability of a solution for the performance.