Fleet assignment
Which aircraft type should fly each flight, when every aircraft that lands has to take off again from the same airport, and the airline only has so many of each.
A bigger aircraft spills fewer passengers but costs more, and there are only so many of each type. Below, 30 flights at a hub are solved as an integer program in your browser and compared with a greedy rule. Companion to NP 101, chapter 05 and OR 101, chapters 04 and 05. The schedule, costs, fares and demand are illustrative.
Loading the schedule and the solver…
1. The day as a time-space network
Each airport is a row and time runs left to right from 03:00, where the count line sits. A flight is an arc from its departure to its arrival, and the dotted tail is the turn, after which the aircraft can leave again. While aircraft wait at an airport they travel along a ground arc. Once a plan is chosen, each airport splits into one lane per aircraft type: the numbers on the ground arcs count the aircraft on the ground, and the aircraft that cross the count line are the fleet the plan needs. Click a flight to change its demand.
Scroll sideways to see the whole day.
2. What each flight costs on each aircraft
Flying a flight with a type costs its operating cost, the type's cost per block hour times the block time, plus the spill cost: the average fare times the passengers expected above the seat count, who go to another airline. This is the leg-fleet cost cik of OR 101's model, and every commercial judgment in fleet assignment sits in it.
One flight on each type
What it means for this flight
Selected in section 1 or the table belowEvery flight on every type
Cost per flight. Bold: the cheapest type for that flight on its own. Click a row to select it.3. The optimum against the greedy rule
The optimum solves the whole day at once. The greedy rule goes down the flights from the busiest to the quietest and gives each the largest type that still leaves a flyable plan for the rest: without that check it would soon break the balance, with an aircraft due to leave an airport it never reached. A second rule gives each flight its own cheapest type instead, still busiest first. Change the fleet below, or a flight's demand above, and both are solved again.
The fleet
Edit any number; set "available" to 0 to leave a type outWhere the money goes
Cost per dayHow each plan uses the fleet
Flights, block hours and aircraft by type4. On 1,000 days of actual demand
Both plans are chosen on expected spill. On the day, each flight's demand is one draw from its forecast, and spill is whatever exceeds the seats. Here the two plans fly the same 1,000 simulated days: the average realised cost should match the expected cost of section 3, and the gap between the plans varies from day to day.
Greedy minus optimum, day by day
How it works
Background
A bigger aircraft carries the passengers a smaller one would turn away, but it costs more to fly. Flight by flight the choice is easy. Across a day it isn't: the aircraft that flies a busy morning departure is then away until it comes back, and there are only a few of each type. The day of 30 flights between a hub and four spokes is drawn as a time-space network and solved as an integer program in your browser, with the HiGHS solver: every flight gets exactly one type, aircraft are balanced at every airport at every moment, no type is used more than the airline has, and the total of operating cost and expected spill is as low as possible. The optimum is then compared with a greedy rule that gives the largest aircraft to the busiest flights.
The schedule and the fleet
One day of 30 flights between a hub (H) and four spokes, A to D, with block times of 1, 1.5, 2 and 2.5 hours and average fares of $150, $190, $220 and $250 (all in fleetassign.json). Three spokes keep an aircraft overnight for an early flight to the hub, and the hub sends one back to each of them late in the evening. The fleet has up to three types: a 76-seat regional jet at $3,900 per block hour with a 30-minute turn, a 150-seat narrowbody at $7,200 with 40 minutes, and a 190-seat narrowbody at $8,600 with 45 minutes. The two narrowbodies are those of NP 101 and OR 101: on the 2.5-hour leg to D they cost $18,000 and $21,500 to fly, the operating costs of OR 101's worked example. Every number here is illustrative; real costs per block hour vary a lot between airlines and include or leave out different items (ownership, crew, maintenance, fuel).
Demand
Each flight's unconstrained demand is normal with mean μi and spread σi. The mean is the spoke's size (85, 120, 135 and 150 passengers for A to D) times a time-of-day factor (1.2 before 09:00, 0.95 to noon, 0.8 to 15:00, 1.1 to 19:00, 0.9 after) times a lognormal noise with a 12% spread, times the demand level (1, 1.2 on a peak day, 0.8 on a quiet day); the spread is 20% of the mean. The noise comes from a seeded generator (mulberry32), so the page opens on the same demand every time, and "New demand draw" changes the seed. With the opening seed, the 07:45 flight from the hub to D is set to OR 101's example: 160 ± 30 passengers.
The cost of a flight on a type
For flight i with block time bi and average fare r̄i, and type k with Qk seats and cost hk per block hour:
cik = hk bi + (1 − ρ) r̄i E[(Di − Qk)+], with E[(D − Q)+] = σ φ(z) + (μ − Q)(1 − Φ(z)), z = (Q − μ) / σ,
where φ and Φ are the standard normal density and distribution, and ρ is the share of spilled passengers recaptured on another of the airline's flights (0 by default, as in the courses). With 160 ± 30 passengers and a $250 fare, the expected spill is 17.6 passengers on 150 seats and 2.5 on 190, so the two types cost $22,407 and $22,125 on that leg: OR 101's numbers. Spill is valued at the average fare and nothing else changes with the type: no catering or fees per passenger, no extra revenue from cargo.
The time-space network
Each type has its own network, because turn times differ. At each airport, every departure is a node at its departure time, and every arrival is a node at the time the aircraft is ready again, arrival plus turn; events at the same airport and minute share a node, and an aircraft that is ready at 07:45 can leave at 07:45. Ground arcs join consecutive nodes at an airport, and the last one of the day wraps round to the first, because tomorrow repeats today. Time is counted from the count line at 03:00, when no flight is in the air, so the aircraft a type needs are those on the wrap-around ground arcs.
The integer program
With xik = 1 if flight i is flown by type k, yg ≥ 0 the number of aircraft of type k on ground arc g, and Sk the aircraft available, the fleet assignment model of Hane et al. (1995), as written in OR 101, chapter 05, is:
minimise Σi Σk cik xik
subject to Σk xik = 1 for every flight i (cover),
Σi arriving at n xik + yn− − Σi leaving n xik − yn+ = 0 for every type k and node n of its network (balance),
Σg crossing the count line yg + Σi in the air at the count line xik ≤ Sk for every type k (count),
xik ∈ {0, 1}, yg ≥ 0 and whole,
where yn− and yn+ are the ground arcs entering and leaving node n. With the three-type fleet that is 90 flight-type variables, 137 ground-arc variables and 170 constraints. The page writes the model in CPLEX LP format and solves it with highs-js 1.15.3, the HiGHS solver compiled to WebAssembly and loaded from jsDelivr, by branch and bound with cuts. It also solves the LP relaxation, with 0 ≤ xik ≤ 1 and y fractional, to show how close it comes: often it is already whole, the near-network structure that OR 101, chapter 04 describes, and when it isn't, the gap is small.
The ground counts drawn in section 1 are those of the fewest aircraft that can fly the chosen plan: at each airport, the running total of arrivals minus departures of a type, plus the number parked across the count line that keeps it from going below zero. Aircraft the plan doesn't need are left out of the picture.
The greedy rules
Both rules sort the flights by mean demand, busiest first. "Largest on the busiest" gives each flight the largest type that still leaves a flyable plan; "cheapest flight by flight" gives it the type with the lowest cik that still does. "Still flyable" is checked by solving the same integer program with the choices made so far fixed and no objective, so a rule never paints itself into a corner. Without that check, both rules would usually produce a plan that can't be flown. Neither is what planners do: they are there to show what solving the day as a whole is worth.
Simulated days
For section 4, each day draws every flight's demand from its normal forecast (floored at zero), and each plan pays its operating cost plus the fare (less recapture) for every passenger above the seats. The draws are seeded (mulberry32), and both plans see the same days. With the opening settings, the average over 1,000 days lands within 0.1% of the expected cost of each plan, which checks the spill formula.
Checking the numbers
scripts/fleetassign/check.mjs runs the engine embedded in this page (between the fam-engine markers) in Node with the same HiGHS build, for both fleets and all three demand levels, and checks every plan: each flight covered once, aircraft balanced, counts within the fleet, OR 101's example leg costs, and the greedy plans never below the optimum. The optima were also reproduced, to the cent, by a separate model built from the same inputs with SciPy's milp and the spill integrated numerically.
Sources
- Hane, C. A., Barnhart, C., Johnson, E. L., Marsten, R. E., Nemhauser, G. L. and Sigismondi, G. (1995), "The fleet assignment problem: solving a large-scale integer program", Mathematical Programming 70(2), 211–232. The model used here: a multicommodity flow on a time-expanded network with side constraints.
- Abara, J. (1989), "Applying integer linear programming to the fleet assignment problem", Interfaces 19(4), 20–28. The first integer programming formulation assigning several fleets at once, at American Airlines.
- Subramanian, R., Scheff, R. P., Quillinan, J. D., Wiper, D. S. and Marsten, R. E. (1994), "Coldstart: fleet assignment at Delta Air Lines", Interfaces 24(1), 104–120. About 2,500 daily domestic legs and 450 aircraft from 10 fleets; the model was expected to save Delta $300 million over three years.
- Barnhart, C., Kniker, T. S. and Lohatepanont, M. (2002), "Itinerary-based airline fleet assignment", Transportation Science 36(2), 199–217. Spill and recapture by itinerary rather than by leg.
- Huangfu, Q. and Hall, J. A. J. (2018), "Parallelizing the dual revised simplex method", Mathematical Programming Computation 10(1), 119–142: the paper behind HiGHS, run here through highs-js (MIT licence).
- Charts drawn with D3 7.9.0.
Limitations
- Spill is counted leg by leg. A connecting passenger spilled from a small first leg is also lost on the second, and some spilled passengers would take another of the airline's flights; the recapture slider is a single average for that. The itinerary-based model of Barnhart, Kniker and Lohatepanont (2002) handles both, and the demand unconstraining page looks at spill and recapture on one flight.
- Demand is a forecast with a normal spread, fixed before the day. Airlines refine the assignment as bookings come in, swapping types that share a cockpit, which is worth more than a perfect plan that can't be changed (NP 101, chapter 05).
- Aircraft cost only per block hour. There is no ownership or leasing cost per aircraft per day, so the model is happy to use every aircraft it has; nor are there landing fees by weight, crew rules, gate limits or noise curfews.
- One day, repeated. Real fleeting covers a week with different days, and the next steps, routing each tail through maintenance and building crew pairings (OR 101, chapters 06 to 08), can make a cheap assignment impossible to fly.
- The schedule is fixed. Retiming a flight by a few minutes can free an aircraft for a better assignment; integrated schedule design and fleeting models choose both.
This is a personal project and isn't affiliated with any airline.