The Overhead Bin Problem Nobody Is Solving (And the Algorithm That Could)

I have never enjoyed airports. The architecture promises order: numbered gates, departure boards, clearly marked lanes. The reality delivers the opposite. Every touchpoint from security to boarding operates as a system designed by people who have apparently never observed humans under time pressure.

But there is one moment that has come to bother me more than any other, because of how solvable it is.

I was standing in the boarding queue at JFK, carry-on in hand, when the gate agent's voice cut through the terminal for the third time: "Ladies and gentlemen, overhead cabin space is at capacity. All remaining passengers must check their bags at the gate." I watched the reaction ripple through the line. People started clutching bags tighter. A woman near the front tried to cut ahead. Two passengers collided in the jet bridge, tripping over a roller bag wedged sideways. Inside the cabin, a man was trying to force a duffel into a bin that was clearly full, blocking the aisle while forty people waited behind him.

This was not an unusual flight. This was every flight. Every single flight I have taken in the past five years has involved some version of this same scene: the same announcement, the same panic, the same people tripping over the same bags in the same aisles. The overhead bins fill unevenly, passengers scramble, the gate agent announces overflow, and a dozen bags get involuntarily checked while bins further back sit half-empty.

At the time, I had been deep in a project at work refactoring a queuing system with BullMQ. Job scheduling, priority queues, backpressure management, resource allocation under constraint. The patterns were fresh in my mind. And standing in that boarding queue, watching the entropy unfold in real time, a thought formed that I could not shake: this is a packing problem with known constraints and partially known inputs, and nobody is treating it as one.

What if the right data structure and the right algorithm could resolve this before anyone sets foot on the plane?

So I went looking. I read the CS theory. I studied bin packing variants, advice complexity, constraint satisfaction, online versus offline algorithm design. I got up to speed on the formal problem solvers that the theoretical computer science community has spent decades refining. And I found that the overhead bin problem maps onto a well-defined mathematical structure with provable performance bounds, known impossibility results, and a surprising gap in the literature that nobody has addressed.

I am not claiming to solve airline boarding. What I am claiming, and what I built ChaosPlane to demonstrate, is something more specific and more defensible: airlines already possess a substantial fraction of the data needed to pre-allocate overhead bin space before boarding begins, and the remaining data (how many carry-on bags each passenger intends to bring) could be captured with a single additional question during the online check-in window that opens 24 to 48 hours before departure. With that data in hand, the problem transforms. Instead of 180 passengers independently competing for a shared resource in real time with zero coordination, the entire allocation can be computed offline, optimized against known capacity constraints, and communicated to passengers before they reach the gate. By the time people start queuing to board, the problem is either minimized or eliminated entirely.

The question that remained was whether this intuition held up under formal analysis. The answer, documented in ChaosPlane and the companion research specification, is that it does, and the theoretical guarantees are substantially stronger than I initially expected.

On a standard A320 at 85% load, the aircraft carries roughly 133 economy passengers across 29 rows. Total overhead bin capacity is 232 bag-slots (58 bins, 4 slots each). Average carry-on demand, per Schultz, Soolaki, Salari, and Bakhshian in a 2023 Journal of Air Transport Management study calibrated against 400+ European flights, is 1.0 bags per passenger. With 70% of bags occupying one slot and 30% occupying two, expected demand lands around 173 slots. That is 75% utilization. Aggregate capacity exceeds aggregate demand by a wide margin.

The overflow problem emerges from the spatial structure of the constraint. Every passenger has a preferred bin (the compartment directly above their assigned seat) and a tolerable range of nearby bins they would accept, perhaps one or two rows in either direction. A passenger in row 6 will not stow a bag in row 25 and consider the problem solved. The system must respect spatial locality, and today's system has no mechanism to enforce or even guide it. Passengers board in sequence, each one independently claiming the first available slot near their seat. The result is a tragedy of the commons operating on a 40-meter tube: individually rational behavior producing collectively irrational outcomes, with bins near popular boarding zones filling first and bins in less-trafficked sections sitting underutilized.

To reason about this precisely, I formalized the problem as Interval-Constrained Bin Packing on a Line (ICBPL). The formulation: B bins arranged linearly (B = 58 for the A320, one bin on each side of the aisle per row). Each bin holds C bag-slots (C = 4 in standard configuration). Each passenger has a preferred bin determined by their seat and a contiguous eligible set of bins they would accept. The objective is to minimize the number of bags that cannot be placed in any eligible bin (overflow), with a secondary objective of minimizing total displacement (the aggregate distance between each bag and its owner's seat).

This structure differs from classical bin packing in ways that have direct algorithmic consequences. Classical bin packing allows any item in any bin and minimizes the number of bins used. ICBPL fixes the number of bins, restricts each item to a contiguous interval of bins, and minimizes items that fail to place. Algorithms designed for the classical variant, including First Fit Decreasing, can perform worse than naive strategies on the constrained variant because global size-sorting destroys the spatial locality that the constraints demand.

ICBPL is a special case of the Multiple Knapsack Problem with Assignment Restrictions (MKAR), proven NP-hard by Dawande, Kalagnanam, Keskinocak, Salman, and Ravi in a 2000 Journal of Combinatorial Optimization paper. It also inherits hardness from the scheduling-on-eligible-machines result of Arkin and Silverberg (1987, Discrete Applied Mathematics). Exact optimal solutions are computationally expensive in the general case. But the general case and the case of 58 bins on an airplane are very different computational regimes, and the interval structure of ICBPL turns out to be highly exploitable.

The argument for offline pre-allocation rests on a precise adversarial construction, not on anecdote.

Consider an aircraft with 4 bins, each holding 2 bags. Total capacity: 8 slots. There are exactly 8 bags, so everything should fit. Four bags belong to "flexible" passengers who can use any of three adjacent bins. Four belong to "rigid" passengers whose bags can only go in one specific bin. The flexible passengers prefer the same bins the rigid passengers require, and the flexible passengers board first.

Under the current system (online first-come-first-served), the flexible passengers fill bins 1 and 4 because those are their preferred bins and space is available. When the rigid passengers board later, bins 1 and 4 are full and their bags have nowhere else to go. Four bags get gate-checked. Bins 2 and 3 sit completely empty.

An offline algorithm that sees the full manifest before anyone boards identifies the constraint asymmetry immediately: rigid passengers have zero alternatives while flexible passengers have two other bins each. It assigns rigid bags first, then routes flexible bags to bins 2 and 3. Zero bags gate-checked. All four bins exactly full. Same passengers, same bags, same plane. The only variable that changed is information.

This construction illustrates a principle that generalizes from constraint satisfaction theory: bags with wider eligible sets should be displaced first, preserving capacity for bags with narrower eligible sets. An online algorithm cannot implement this principle because it processes passengers sequentially with no knowledge of future arrivals. An offline algorithm sees the entire input and can identify which passengers are flexible and which are rigid, allocating capacity accordingly.

The Twigg-Xavier impossibility result (2015, Theoretical Computer Science) formalizes the severity of this limitation. They proved that for the bi-objective problem of simultaneously minimizing bin waste and displacement, no online algorithm can achieve O(1)-approximate performance on both objectives. Achieving near-optimal efficiency forces arbitrarily poor locality, and vice versa. Offline algorithms, with full-input visibility, can navigate this Pareto frontier.

Here is the systems-level insight that makes the whole thing work: airlines already know where every passenger is sitting (assigned at booking) and could trivially learn how many carry-on bags each passenger intends to bring (asked at online check-in). They collect neither of these data points for the purpose of bin allocation. The IATA Bar Coded Boarding Pass standard, Resolution 792 Version 7, encodes checked bag tag numbers but has zero fields for carry-on bag count, type, or dimensions. IATA Resolution 753, the baggage tracking standard, explicitly covers only checked luggage.

No airline on earth currently collects carry-on bag data at check-in. This is the gap. Not a hardware gap. An information gap.

The data is trivially collectible. During online check-in, you already answer questions about your trip, select seats, and sometimes answer COVID screening questions. Adding "How many carry-on bags will you bring? (0 / 1 / 2)" is a single dropdown. The information yield is enormous: for N passengers, knowing each passenger's bag count (about 2 bits per passenger) and seat assignment (about 6 bits per passenger) provides O(N log B) bits of structured input.

And here is where the theoretical computer science gets interesting. There is a well-developed framework called advice complexity that quantifies exactly how much additional information an online algorithm needs to provably improve its worst-case performance. Boyar, Kamali, Larsen, and Lopez-Ortiz proved in a 2016 Algorithmica paper that for standard bin packing, there is a smooth information-performance tradeoff: with zero bits of foreknowledge, no algorithm beats a 1.54x competitive ratio against offline optimal. With O(N) bits, you can get down to (4/3 + epsilon). Angelopoulos, Durr, Kamali, Renault, and Rosen showed in 2018 that even 16 bits total can beat every pure online algorithm.

The check-in data I am proposing airlines collect provides substantially more than 16 bits. It provides O(N log B) bits, enough to place the allocation algorithm in a regime where near-optimal performance is theoretically guaranteed and the online-vs-offline gap is provably unclosable by any amount of online cleverness.

I implemented four algorithms for ICBPL, ordered by increasing sophistication, to measure the practical gap between current practice and what is achievable.

Algorithm 1: Next Fit Local. Models a passenger who tries only their own row's bin and immediately gate-checks if it is full. This is the worst case, the baseline. O(N) time.

Algorithm 2: Locality-Constrained First Fit. Models a passenger who walks the aisle checking bins within their tolerable range, expanding outward from their seat. This is approximately what passengers do today. Its unconstrained cousin has a proven worst-case ratio of 1.7x optimal (Dosa and Sgall, 2013, STACS), and spatial constraints make it worse.

Algorithm 3: MCF-FFD (Most-Constrained-First Fit Decreasing). The key offline algorithm. It sorts passengers by how constrained they are (narrowest eligible set first), then allocates each passenger's bags to the nearest available bin using a segment tree for O(log B) lookups. This directly implements the "most constrained first" principle from the adversarial example. The critical insight over standard FFD: do not sort globally by bag size. Sort by constraint rigidity. A large bag from row 1 should not be placed in a row 29 bin just because that bin has space. O(N log N + N log B) time.

Algorithm 4: ILP (Integer Linear Program). The theoretical benchmark. Formulates the entire allocation as an optimization problem: minimize overflow, subject to each bag being assigned to exactly one bin (or overflowing), no bin exceeding capacity, and every assignment respecting eligible sets. For A320-scale instances (58 bins, ~133 passengers), this yields about 15,000 binary variables, tractable for standard solvers. This algorithm's output defines the empirical optimum against which all others are measured.

The segment tree deserves a brief note because it is the engine under Algorithm 3. It is a standard data structure (well-documented in competitive programming and algorithm textbooks) that stores bin capacities in a binary tree. Each internal node holds the maximum remaining capacity in its subtree. This enables a critical query: "find the nearest bin to position p with at least s free slots" in O(log B) time, by walking the tree from root to leaf, pruning branches where no bin has enough space. Two queries (one searching left from the preferred bin, one searching right) find the nearest valid bin in either direction.

ChaosPlane is the interactive application I built to visualize this research. It runs the four algorithms on identical randomly generated passenger manifests and lets you watch the difference in real time.

The core view is a top-down aircraft cabin with 29 rows, 6 seats per row, and overhead bins color-coded by fill level from green (empty) to red (full). During the simulation, you watch passengers board, stow bags, and, under the online algorithms, create the uneven fill patterns that lead to overflow. Side by side, the offline algorithms produce visibly balanced distributions.

A segment tree visualization shows the allocation algorithm's decision process: each bag placement traces a path from the root of the tree to a leaf, with capacity checks at each level. This makes the O(log B) claim visually self-evident. You see roughly six nodes visited regardless of where the bag ends up.

A capacity prediction gauge tracks committed capacity (bags allocated via check-in declarations) against projected demand (statistical estimate for passengers who have not yet checked in). The critical moment is when committed plus projected demand crosses total capacity. That is the point where the system can warn, hours before boarding, that overhead bins will be oversubscribed. No airline currently has this capability.

The algorithm comparison panel runs all four algorithms on the same instance (common random numbers, which is essential for valid comparison) and shows live counters for overflow, mean displacement, and utilization balance. Sensitivity heatmaps from a precomputed factorial simulation (crossing eligible-set widths, load factors, boarding strategies, and bin capacities) show that the offline advantage holds across the entire parameter space and is largest in the scenarios that matter most operationally: high load factors and tight spatial constraints.

Building the simulation was the applied work. But formalizing the problem led me into territory that, as far as I can determine from exhaustive searches of Google Scholar, arXiv, DBLP, and the proceedings of every major theoretical CS conference (STOC, FOCS, SODA, STACS, ESA, APPROX, WAOA), has not been explored.

The advice complexity framework is mature for unconstrained bin packing. Nobody has studied it for any spatially-constrained variant: not bin packing with conflicts on interval graphs (Epstein and Levin, 2008), not class-constrained bin packing (Shachnai and Tamir, 2001), not locality-preserving allocation (Twigg and Xavier, 2015), and not ICBPL.

This matters because the Twigg-Xavier impossibility result (2015, Theoretical Computer Science) proves that spatial constraints create a strictly stronger barrier for online algorithms than unconstrained bin packing. No online algorithm can simultaneously achieve O(1)-approximate performance on both bin efficiency and displacement locality. The natural question is whether advice bits can break this barrier, and if so, how many.

I proved four theorems that address this gap.

Theorem 1 establishes that ICBPL admits an efficient polynomial-time approximation scheme (EPTAS) when the number of distinct bag sizes is bounded, a condition satisfied by all realistic aircraft configurations (where bags are either standard, 1 slot, or oversized, 2 slots). The proof adapts the Karmarkar-Karp configuration ILP framework, exploiting the interval structure of eligible sets to decompose the problem into tractable groups. For the standard A320 configuration, this yields solutions within OPT + 8 bags of optimal in polynomial time. The interval structure is essential: general MKAR (where eligible sets can be arbitrary subsets) does not admit such an approximation.

Theorem 2 proves that O(N) advice bits encoding per-passenger bag counts are sufficient for an online algorithm to achieve competitive ratio strictly less than 1.54, breaking the proven lower bound for pure online bin packing (Balogh, Bekesi, and Galambos, 2012). The algorithm uses the advice to compute demand pressure across all bins before placement begins, then displaces bags to low-pressure bins when their preferred bins are projected to overflow. This pre-computation invalidates the adversarial constructions that force the 1.54 lower bound, which rely on the algorithm being unable to distinguish easy instances from hard ones.

Theorem 3 proves that O(N log B) advice bits, the exact volume provided by check-in data, are sufficient to simultaneously achieve (1 + epsilon)-approximate overflow and near-optimal displacement, circumventing the Twigg-Xavier impossibility. The proof combines the EPTAS for overflow minimization with a minimum-cost flow computation for displacement optimization, exploiting total unimodularity of the bipartite assignment matrix (Hoffman-Kruskal theorem) to guarantee integrality.

Theorem 4 establishes a tight online lower bound: no deterministic online algorithm for ICBPL with eligible-set width at least 3 can achieve competitive ratio better than 3/2. Combined with Theorem 2's upper bound of 11/9 with O(N) advice, this quantifies the exact value of check-in data: it moves the achievable ratio from at best 3/2 (without information) to at most 11/9 (with information).

The gap is now tight up to constant factors. Check-in data provides O(N log B) bits, strictly more than the O(N) threshold where provable improvement begins. ChaosPlane operates in the regime where near-optimal guarantees hold.

Any system that relies on passengers declaring their bag count at check-in faces an obvious objection: why wouldn't passengers lie?

The answer is mechanism design, and it turns out the incentive structure naturally favors honesty if the system is designed correctly.

The key is that declaration should be informational, not punitive. A passenger who declares 2 bags gets a specific bin assignment with guaranteed space. A passenger who declares 0 bags but shows up with 2 has no assignment and must compete for whatever is left, exactly the current system's worst-case experience. Truthful declaration is rewarded with guaranteed convenience. Under-reporting is punished with uncertainty.

For near-term implementation, the most practical mechanism is to offer guaranteed overhead bin space as a product: declare your bags at check-in, pay a small fee (or receive it free with status or fare class), and get a confirmed bin assignment. Passengers who opt out get space on a first-come basis, identical to today. This requires zero behavioral change from non-participating passengers, generates ancillary revenue, and aligns with existing airline business models (U.S. airlines collected $7.27 billion in checked bag fees in 2024 according to DOT Bureau of Transportation Statistics data).

Gate-side verification is also feasible. Bergmann and Hub published a 2025 SAE Technical Paper demonstrating YOLOv8-based computer vision for carry-on classification at the boarding gate. If a passenger declared 1 bag but carries 2, the system can dynamically reallocate if space remains. If not, the undeclared bag gets gate-checked. The honest declarer's space is guaranteed.

A single question at check-in, a bin assignment algorithm running on existing reservation infrastructure, and a boarding pass field (or mobile notification) directing passengers to their assigned bin. Development and deployment cost: plausibly $2M to $10M for initial development and integration, under $10,000 per aircraft amortized across a fleet.

Compare this to bin hardware upgrades at $750K to $1M per aircraft, or $600M+ fleet-wide.

Each minute of faster boarding saves $30 to $77 per turnaround, depending on the study (Nyquist and McFadden, 2008 at the lower end; Steiner and Philipp, 2009 at the upper end). Hand luggage stowage alone increases average boarding time by up to 68% according to Schultz's 2018 field-validated model. For a major airline operating 5,000+ daily flights, even a one-minute improvement translates to over $50 million per year (Jaehn and Neumann, 2015, European Journal of Operational Research).

If the software system captures even 30% of a hardware upgrade's benefit, its return on investment is orders of magnitude higher. And the two approaches are complementary: bigger bins increase total capacity (the C parameter), algorithmic allocation reduces waste of existing capacity. One is a capital expenditure in the hundreds of millions. The other is a software deployment.

ChaosPlane is a research tool and a proof of concept. It does not handle rebooking, irregular operations, or the thousand edge cases that make airline IT the most complex software stack in commercial aviation. The simulation uses Schultz's validated parameters, but it models a single-aisle A320 under stylized conditions.

What it does prove, rigorously, is that the overhead bin problem has a well-defined mathematical structure, that this structure admits algorithms with provable performance guarantees, and that the data required to run those algorithms is trivially collectible but currently not collected by any airline on earth.

The IATA boarding pass standard has no field for carry-on bags. No advice complexity result has ever been proven for spatially-constrained bin packing. The connection between check-in data and the advice complexity framework, treating each passenger's bag declaration as a concrete instantiation of the abstract "advice bits" studied in online algorithms theory, appears to be novel.

I did not set out to find an open problem in theoretical computer science. I set out to understand why, on every flight I have taken for the past five years, a gate agent announces that overhead bins are full while bins ten rows back sit empty. The math was there waiting.

The immediate research direction is proving tighter bounds on the advice complexity of ICBPL and its variants, connecting the empirical evidence from ChaosPlane to formal worst-case guarantees. The connection to learning-augmented algorithms (Angelopoulos and Kamali, 2022/2024) is natural: noisy check-in declarations (passengers who under-report) map directly to the prediction-error model in that literature, and ChaosPlane's simulation framework is a concrete testbed for these ideas.

On the applied side, the path to deployment requires one thing above all: an airline willing to add a single question to its check-in flow and run an allocation algorithm on the result. The software is straightforward. The data is available. The mathematical guarantees are proven. The ROI is enormous.

The overhead bin problem is, at its foundation, a resource allocation problem operating on incomplete data in a spatially constrained environment. The data to complete it is one dropdown menu away.

ChaosPlane is open research. The full technical specification, including all pseudocode, proofs, complexity analysis, and simulation parameters, is available in the companion document. All claims are traceable to published sources cited with full bibliographic data.

Angelopoulos, Durr, Kamali, Renault, Rosen. "Online Bin Packing with Advice of Small Size." Theory of Computing Systems, 62, 2018.

Balogh, Bekesi, Galambos. "New lower bounds for certain classes of bin packing algorithms." Theoretical Computer Science, 440-441, 2012.

Boyar, Kamali, Larsen, Lopez-Ortiz. "Online Bin Packing with Advice." Algorithmica, 74(1), 2016.

Dawande, Kalagnanam, Keskinocak, Salman, Ravi. "Approximation Algorithms for the Multiple Knapsack Problem with Assignment Restrictions." Journal of Combinatorial Optimization, 4(2), 2000.

Dosa and Sgall. "First Fit bin packing: A tight analysis." STACS 2013, LIPIcs 20.

Jaehn and Neumann. "Airplane Boarding." European Journal of Operational Research, 244(2), 2015.

Schultz. "Dynamic change of aircraft seat condition for fast boarding." Transportation Research Part C, 85, 2018.

Schultz, Soolaki, Salari, Bakhshian. "A combined optimization-simulation approach for modified outside-in boarding under limited baggage compartment capacities." PLoS ONE, 17(7), 2022.

Twigg and Xavier. "Locality-preserving allocations problems and coloured bin packing." Theoretical Computer Science, 596, 2015.