Why Are PlanesSOChaotic?

Every passenger declares their bag count at check-in. Airlines have all the data they need to predict bin overflow, pre-allocate space, and eliminate gate-check chaos. They just aren't using the best algorithms to do it.

scroll

The Problem

133 passengers, 52 overhead bins (208 total slots), zero coordination. Watch what happens when bags are placed first-come, first-served with no data and no plan.

cockpit
1
A
B
C
D
E
F
2
A
B
C
D
E
F
3
A
B
C
D
E
F
4
A
B
C
D
E
F
5
A
B
C
D
E
F
6
A
B
C
D
E
F
7
A
B
C
D
E
F
8
A
B
C
D
E
F
9
A
B
C
D
E
F
10
A
B
C
D
E
F
11
A
B
C
D
E
F
12
A
B
C
D
E
F
13
A
B
C
D
E
F
14
A
B
C
D
E
F
15
A
B
C
D
E
F
16
A
B
C
D
E
F
17
A
B
C
D
E
F
18
A
B
C
D
E
F
19
A
B
C
D
E
F
20
A
B
C
D
E
F
21
A
B
C
D
E
F
22
A
B
C
D
E
F
23
A
B
C
D
E
F
24
A
B
C
D
E
F
25
A
B
C
D
E
F
26
A
B
C
D
E
F
27
A
B
C
D
E
F
28
A
B
C
D
E
F
29
A
B
C
D
E
F
tail

0

Gate-checked bags

overflow from full bins

0.0%

Overflow rate

overflow / total bags

0.00

Mean displacement

rows from preferred bin

0

Displaced bags

placed outside preferred bin

Progress: 0 / 133

idle

The Data Structure

Every passenger already declares their bags at check-in. This is the composite data structure that turns that data into a conflict-minimized boarding plan: a segment tree for O(log B) bin queries, a priority queue for boarding order, and a capacity ledger for overflow prediction.

Check-In Counter

Checked in: 0 / 133

Step or play to begin check-in

idle

No segment tree data available. Initialize the simulation to view the tree.

Segment tree over bin capacities: O(log B) queries find the nearest valid bin. Internal nodes store max remaining capacity in subtree.

Priority queue is empty. Check in passengers to populate the queue.

Min-heap priority queue: key = (boardingGroup << 16) + checkinSequence. Boarding group order with FIFO within groups.

Capacity Ledger

0%utilization

0 / 208 slots committed

Checked in
0
Remaining
133
Alert level
green

Capacity ledger tracks committed vs. projected slots. When projectedOverflow first exceeds 0, the airline knows hours before boarding that bins will overflow.

No allocations yet. Check in passengers to see bin assignments.

The Algorithm

Four interval-constrained bin packing strategies, each run 3 times on independently generated 133-passenger manifests. All algorithms within each run process the identical dataset (common random numbers) so differences reflect algorithmic choice alone.

key insight

The check-in allocation algorithm converts an online problem (passengers arrive one at a time with no advance info) into an offline problem (all data known at check-in before boarding begins). This is not standard bin packing: it is Interval-Constrained Bin Packing on a Line (ICBPL), where each bag is restricted to a contiguous subset of bins determined by seat location. The problem is NP-hard (Dawande et al. 2000), but the segment tree makes practical allocation O(N log B), effectively instant for any aircraft. Airlines already have the data. They just process it too late.

The Check-In Notification System

Real-time passenger communication transforms bin allocation from a gate-time scramble into a check-in-time certainty.

Check-In (online)

Bag Declaration

System Allocates Bin Slot

Gate Arrival (bin shown on pass)

Boarding (direct to assigned bin)

Check-in notification

ChaosPlane Airlines

How many carry-on bags?

Selected: 1 bag

Gate display board

Flight UA 1234 — Overhead Bin Status

0%allocated208slots leftGroup 1now boarding
Low
Medium
High
Full

Enhanced boarding pass

CP

ChaosPlane

UA 1234

Passenger

Jane Smith

Seat

14A

Group

3

Bin

NO BIN INFO

Current boarding passes have no bin information. IATA BCBP standard v7 (2021) has no field for carry-on bin assignment. One additional field eliminates all searching.

key insight

Airlines already send notifications during check-in (seat assignments, upgrade offers, gate changes). Adding bin allocation is zero additional infrastructure -- it is a software update, not a hardware purchase. The $750K-per-aircraft retrofit for larger bins is unnecessary if you allocate existing space intelligently.

The Impact

Industry data and simulation results quantifying the value of algorithmic bin allocation versus the status quo.

$7.27B

Annual U.S. checked bag fees

U.S. DOT Bureau of Transportation Statistics, 2024

68%

Boarding time increase from hand luggage

Schultz 2018

>$50M/yr

Savings from 1-min boarding reduction

Jaehn and Neumann 2015 (per major carrier)

$2M-$10M

Software system development + deployment

vs. $750K-$1M per aircraft hardware retrofit

Before vs. after comparison

Run the simulation to see comparison data

Overflow reduction hierarchy

Average gate-checked bags (lower is better)

Measured from 3 independent runs per algorithm. Reduction percentages are relative to Local First Fit (the online baseline).

Run the simulation to see overflow data

cost-benefit

Even if the software system captures only 30% of the benefit of a hardware upgrade, its ROI is orders of magnitude higher. The two approaches are also complementary: bigger bins increase total capacity, algorithmic allocation reduces waste of existing capacity.