Airport Gate Assignment
Assignment Problem · Hungarian Algorithm O(n³)
An airport operations centre assigns 6 arriving flights to 6 terminal gates, minimizing total passenger walking distance for connections. At major airports, poor gate assignment adds 5–8 minutes per connection, costing airlines €500–€2,000 per missed connection.
The Problem
Airport Operations · Gate Assignment
Every flight bank at a hub airport triggers a combinatorial puzzle: which gate should each arriving aircraft use? The objective is to minimize the total weighted walking distance for connecting passengers. Each flight carries passengers transferring to other flights in the bank, and the walking distance between any two gates varies from 50 m (adjacent gates) to over 800 m (cross-terminal).
This is the Linear Assignment Problem (LAP) — a square cost matrix where 6 flights must be assigned to 6 gates, one-to-one. The cost cij of assigning flight i to gate j equals the sum of walking distances weighted by passenger counts for all connections involving flight i when parked at gate j. Additional compatibility constraints ensure wide-body aircraft are only assigned to gates with jet bridges that accommodate their fuselage width.
| OR Concept | Airport Mapping |
|---|
subject to
Σj xij = 1 ∀ i // each flight assigned to exactly one gate
Σi xij = 1 ∀ j // each gate assigned to exactly one flight
xij ∈ {0, 1} // binary assignment decision
xij = 0 // if gate j incompatible with flight i (narrow/wide body)
Where cij is the total weighted walking distance when flight i is assigned to gate j, computed from the connection passenger matrix and the gate-to-gate distance matrix.
See full Assignment Problem theoryTry It Yourself
Assign flights to gates and compare algorithms
Gate Assignment Optimizer
6 Flights · 6 GatesReady. Select a scenario and click Solve.
| Algorithm | Total Cost | vs Random | Time |
|---|
The Algorithms
From random baseline to polynomial-time exact solution
Random Assignment
O(n) | No optimality guaranteeRandomly permute the gate indices and assign each flight to the next available gate. This serves as a baseline to quantify the value of optimization. In practice, random assignment at a 6-gate bank typically produces walking costs 40–80% higher than optimal, translating to thousands of extra passenger-minutes per day.
Greedy (Cheapest Gate First)
O(n²) | Good but not optimalSort all flight-gate pairs by ascending cost. Iterate through the sorted list: assign a flight to a gate if neither the flight nor the gate has been assigned yet. Greedy typically achieves within 5–15% of optimal for well-distributed cost matrices, but can perform poorly when multiple flights compete for the same low-cost gate.
Hungarian Algorithm (Kuhn-Munkres)
O(n³) | Guaranteed optimalThe Hungarian algorithm finds the minimum-cost perfect matching in a bipartite graph. It works by maintaining dual variables (potentials) for rows and columns, then iteratively finding augmenting paths along zero-reduced-cost edges. For the 6×6 gate assignment, it runs in microseconds and guarantees the globally optimal assignment.
Originally published by Harold Kuhn in 1955 (based on earlier work by Hungarian mathematicians König and Egerváry), and refined by James Munkres in 1957, this algorithm remains the gold standard for balanced assignment problems in airline operations.
Real-World Complexity
Why airport gate assignment goes beyond a simple cost matrix
Beyond the Assignment Matrix
- Aircraft compatibility — Wide-body aircraft (B777, A350) require specific gates with appropriate jet bridge configurations; narrow-body gates cannot accommodate them
- Temporal overlap — Real schedules have flights arriving and departing throughout the day; gate assignment becomes a scheduling problem with time windows and turnaround buffers
- Towing costs — When gates are scarce, aircraft may be towed to remote stands between flights, adding operational cost and delay risk
- Airline preferences — Airlines lease gate zones within terminals; cross-airline gate swaps require inter-airline coordination and contractual agreements
- Disruption recovery — Weather delays, mechanical issues, and diversions force real-time gate reassignment, often cascading across the entire terminal
Key References
Foundational works in assignment and airport operations
- (1955). “The Hungarian method for the assignment problem.” Naval Research Logistics, 2(1-2), 83–97. DOI: 10.1002/nav.3800020109
- (1957). “Algorithms for the assignment and transportation problems.” SIAM Journal, 5(1), 32–38. DOI: 10.1137/0105003
- (2005). “The over-constrained airport gate assignment problem.” Computers & Operations Research, 32(7), 1867–1880. DOI: 10.1016/j.cor.2003.12.007
- (2007). “Flight gate scheduling: State-of-the-art and recent developments.” Omega, 35(3), 326–334. DOI: 10.1016/j.omega.2005.07.001
- (1990). “A conceptual solution to the aircraft gate assignment problem using 0,1 linear programming.” Computers & Industrial Engineering, 19(1-4), 280–284. DOI: 10.1016/0360-8352(90)90121-2
Need to optimize your airport operations?
From gate assignment to crew scheduling and disruption recovery, mathematical modeling can transform hub efficiency. Let’s discuss how Operations Research can work for your organization.