Genetic Algorithm + Neural Network: Boarding Efficiency Beats Steffen Method by 9.6%

A Well-Studied Old Problem: How to Board Faster

Airplane boarding may seem simple, but it's a classic combinatorial optimization challenge. Every time a passenger pauses in the aisle to stow luggage or find their seat, the entire boarding process slows down. For airlines, reducing boarding time means higher aircraft turnaround rates and lower operating costs—every minute a plane sits on the ground is money lost.

According to aviation industry data, every additional minute a narrow-body aircraft (like a Boeing 737 or Airbus A320) spends on the ground costs approximately $30 to $150, depending on airport parking fees, crew labor costs, APU fuel consumption, and other factors. American aviation consulting firms estimate that if a major airline could shorten each boarding process by even one minute, the annual savings could reach tens of millions of dollars. This is why airlines have long invested resources in studying boarding strategies—though they often end up compromising on suboptimal but manageable approaches like "zone boarding" due to passenger experience concerns and implementation complexity.

Over the years, researchers have proposed various boarding strategies. The most famous is the Steffen Method. Developed by physicist Jason Steffen in 2008 through optimization algorithms, its core idea is to have passengers board in a specific interleaved order that maximizes the number of people simultaneously stowing luggage, thereby reducing aisle congestion.

Specifically, the Steffen Method works as follows: passengers board in window-middle-aisle order, while also using an alternating pattern within each column. For example, all even-row window seat passengers board first, then odd-row window seat passengers, and so on. The elegance of this design is that when multiple passengers enter the cabin simultaneously, their seats are spaced far enough apart that they can stow luggage in overhead bins at different rows without interfering with each other. Jason Steffen himself is a particle physicist who worked at Fermilab. He arrived at this conclusion using Monte Carlo optimization methods and validated the approach's efficiency in a 2012 television experiment with real passengers and a real aircraft.

In multiple experiments and televised tests, the Steffen Method has been proven significantly superior to common strategies like "back-to-front" or "random boarding," establishing it as the academic gold standard for efficiency.

Precisely because the Steffen Method has long been considered "near-optimal," a recent achievement by a Reddit developer is particularly noteworthy.

"Evolving" a Better Boarding Order with Genetic Algorithms

According to the developer's Reddit post, they used a Genetic Algorithm (GA) combined with a Multilayer Perceptron (MLP) to optimize the boarding problem, ultimately achieving results 9.6% faster than the Steffen Method in simulation.

The reasoning behind this approach is worth breaking down:

Genetic Algorithm: Strategy Search Through Simulated Natural Selection

Genetic algorithms are a class of optimization algorithms inspired by biological evolution. They encode each possible boarding order as an "individual" (chromosome) and filter for better-performing solutions through selection, crossover, and mutation operations across generations of "reproduction." The fitness function is typically set as total boarding time—the shorter the time, the more "fit" the individual, and the greater its chance of passing its "genes" to the next generation.

Each of these three core operations has specific technical meaning: Selection picks superior individuals from the current population as "parents" based on fitness, with common methods including roulette wheel selection and tournament selection. Crossover recombines gene segments from two parent individuals to generate offspring—for permutation encoding problems, order crossover (OX) or partially matched crossover (PMX) is typically used to avoid duplicate elements. Mutation randomly alters certain gene positions in an individual with low probability, such as swapping two position values, to maintain population diversity and avoid local optima. For boarding problems as a permutation optimization scenario, the encoding itself is a challenge—each passenger can only appear once, making standard binary encoding inapplicable and requiring permutation encoding with specialized crossover operators.

The search space for boarding orders is astronomically large: for an aircraft with over a hundred seats, the possible permutations are astronomical (e.g., 180 seats yield 180! permutations, approximately 10^325), making exhaustive search completely infeasible. The advantage of genetic algorithms lies precisely in their ability to efficiently converge on high-quality solutions within such vast spaces without exploring every possibility.

Multilayer Perceptron: Providing Decision-Making Capability

A pure genetic algorithm searches for a fixed boarding sequence, but by introducing an MLP, the author essentially lets a neural network participate in decision-making—the network outputs boarding priorities based on passenger features like seat position and luggage, while the genetic algorithm optimizes the network's parameters.

The Multilayer Perceptron (MLP) is the most classic feedforward neural network architecture, consisting of an input layer, one or more hidden layers, and an output layer, with full connections between layers. In this project, the MLP serves as a "policy function": it takes passenger features as input (such as row number, column number, whether carrying large luggage, etc.) and outputs a priority score. All passengers are then sorted by score to determine the boarding order.

This "neuroevolution" approach gives the strategy stronger generalization and adaptability, rather than simply memorizing a fixed sequence. Neuroevolution refers to using evolutionary algorithms instead of gradient descent to optimize neural network weights or architecture. The advantage of this approach is that it doesn't require a differentiable loss function—boarding time, being discrete, simulation-derived, and difficult to differentiate, is perfectly suited for this method. The famous NEAT algorithm (NeuroEvolution of Augmenting Topologies) is a classic representative of this field, and OpenAI's 2017 research also demonstrated that evolutionary strategies can rival gradient methods in reinforcement learning tasks.

What Does a 9.6% Improvement Mean?

The author admitted they "didn't originally expect to beat the Steffen Method," but the evolved strategy ultimately achieved a 9.6% speedup. This number is by no means trivial from an engineering perspective.

Taking a typical 25-minute boarding process as an example, a 9.6% improvement means saving approximately 2.4 minutes. Scaled up to a major airline operating thousands of flights daily, the cumulative ground time savings could translate into significant economic value and higher on-time rates.

Interestingly, the author mentioned that the simulation included a constraint: passengers cannot cross between seats (no crossing between seats), and this constraint equally applied to the random baseline. This point is crucial—in reality, passengers indeed cannot teleport through each other. Including such physical constraints makes the simulation closer to real-world scenarios and gives the 9.6% result more credibility.

Insights and Limitations of a "Vibecoded" Project

The author described the entire project as "basically vibecoded"—completed through intuition and experimental, relatively casual coding rather than a rigorous academic process. This reflects a current trend driven by the proliferation of AI tools: individual developers, leveraging readily available algorithm frameworks and AI-assisted programming, can make meaningful explorations on classic optimization problems.

However, we should view this result rationally:

• Simulation ≠ Reality: The 9.6% improvement comes from the author's self-built simulation environment, where parameter settings (luggage stowing time, passenger movement speed, constraints, etc.) directly affect results. Different simulation assumptions may lead to different conclusions. Boarding simulations typically require setting multiple key parameters: passenger movement speed in the aisle (usually assumed as one row per time step), luggage stowing time distribution (often normal or uniform distribution, typically 5-25 seconds), seat interference time (delay when seated passengers need to stand to let inner-seat passengers through), and passenger compliance rate. Small changes in these parameters can significantly alter the relative ranking between different strategies.
• Lack of Peer Review: As a personal project shared on Reddit, it has not undergone rigorous academic reproduction and verification. The Steffen Method itself is optimal under specific model assumptions, and comparing the two requires a consistent baseline to be fair.
• Questionable Real-World Feasibility: While the Steffen Method is theoretically excellent, it's difficult to implement in practice because it requires passengers to board in a strict, complex order. Academic research shows that when passenger compliance drops below 70%, nearly all carefully designed boarding strategies degrade to near-random boarding effectiveness. Any newly evolved strategy that's more complex than Steffen will face the same "passenger non-compliance" implementation challenge. This is why most airlines still use simple zone boarding or random boarding today.

Conclusion: Another Example of AI Optimizing Classic Problems

Regardless of the final verdict, this project is a vivid case study demonstrating the potential of evolutionary computation + neural networks in combinatorial optimization problems. It reminds us that even classic methods studied for years and considered "near-optimal" may still have room for improvement when faced with new algorithmic tools.

For developers looking to get started with optimization algorithms, the boarding problem is an excellent practice scenario: the problem definition is clear, there are recognized benchmarks to compare against, and results are intuitive and easy to understand. The proliferation of AI-assisted programming is lowering the barrier to such explorations. Perhaps the next benchmark-breaking solution will come from a hobbyist's weekend project.