A beginner's guide to operations research in airlines, covering the models behind fleets, crews, schedules and prices.
Operations research (OR) is the discipline of turning a decision into a mathematical model and letting an algorithm find the best answer. Airlines are one of its oldest and heaviest users: almost every plan an airline publishes, from which aircraft flies which flight to which pilot sits in which seat, has been through an optimization model at some point. This page is my attempt to explain the main models in the same spirit as RM 101, Loyalty 101 and NP 101, with one difference: here the math is the subject, so I write the models out properly. Every model is introduced in plain language first, so you can skip the formulas and still follow. It describes the industry in general, not how any particular airline does things, and every number in the examples is made up for illustration.
An airline is a machine with an absurd number of moving parts that all have to line up. A single flight needs an aircraft of the right type, at the right airport, with enough hours left before its next maintenance check; two pilots qualified on that type who are legal to work that day; a cabin crew of the right size; a gate, a slot, fuel and a catering load. Multiply that by a few thousand flights a day and every decision starts to depend on every other one. Humans are good at spotting what a plan should look like. They are not good at choosing the best of the billions of plans that satisfy every rule. That is the job of OR.
The stakes are large because the costs are large. Crew is typically one of an airline's biggest cost lines, usually second only to fuel, and aircraft ownership is not far behind. A crew schedule that is one percent more efficient, or a fleet plan that puts the right-sized aircraft on a few dozen more flights, is worth tens of millions a year at a large carrier. Very few other analytical functions can point at a number like that.
OR was born in Britain during the Second World War, when teams of scientists were asked to help the military use radar, convoys and bombers more effectively. After the war the methods moved into industry. George Dantzig published the simplex method for linear programming in 1947, and it quickly became the workhorse of the field.
Airlines took to it early. In 1961 a group of airline OR practitioners formed AGIFORS, the Airline Group of the International Federation of Operational Research Societies, which still meets every year. American Airlines built one of the largest in-house OR groups of any company, and its crew-pairing optimizer, TRIP, was reported to save more than $20 million a year by the early 1990s. The models in this page have been refined for sixty years, and they remain some of the largest optimization problems solved routinely anywhere in industry.
Because the full problem is far too big to solve in one piece, airlines break it into a sequence of smaller ones. Each step takes the output of the previous step as fixed and optimizes the next layer. The schedule decides which flights exist; fleet assignment decides which aircraft type flies each one; routing decides which physical aircraft; crew pairing builds anonymous multi-day trips for crews; rostering assigns those trips to named people. On the day, recovery repairs whatever the weather broke.
| Step | Question | Typical model |
|---|---|---|
| Schedule design | Which flights, at what times? | Network design with passenger flows (see NP 101) |
| Fleet assignment | Which aircraft type on each flight? | Multicommodity flow on a time-space network |
| Aircraft routing | Which tail number, respecting maintenance? | Set partitioning over aircraft routes |
| Crew pairing | Which legs are chained into legal multi-day trips? | Set partitioning with column generation |
| Crew rostering | Which person flies which trip? | Generalized set partitioning, seniority bidding |
| Recovery | How to repair the plan after a disruption? | Fast MIPs and heuristics on a short horizon |
Before the airline models, the next four chapters build the toolkit they all rely on: linear programs, their duals, integer programs and network flows.
Every optimization model has the same three ingredients. Decision variables are the things you control. An objective is the number you want to make as large or as small as possible. Constraints are the rules any acceptable answer has to respect. A linear program (LP) is the special case where the objective and every constraint are linear in the variables: no products of variables, no squares, no "if" statements.
Linearity sounds restrictive, and it is, but it buys something enormous: LPs with millions of variables can be solved to proven optimality in seconds or minutes. A surprising share of real problems are linear, or close enough that a linear model gives the right answer.
A small airline has a fixed pool of aircraft hours and crew hours each week and must decide how many round trips to fly on two routes. Route A is a short sector; route B is longer and more profitable per trip, but also hungrier for resources.
| Per weekly round trip | Route A | Route B | Available per week |
|---|---|---|---|
| Contribution ($k) | 5 | 12 | |
| Aircraft block hours | 4 | 12 | 240 |
| Crew duty hours | 6 | 12 | 300 |
| Market cap (round trips) | max 40 | none |
With two variables, we can draw it. Every constraint is a straight line that cuts the plane in half; the points that satisfy all of them form the feasible region, a polygon. The objective is a family of parallel lines of equal profit. Pushing that line as far as it will go while still touching the polygon gives the optimum.
The best plan is 30 round trips on route A and 10 on route B, for a weekly contribution of $270k. Notice where it sits: at a corner of the polygon, where two constraints are tight at the same time. That is not a coincidence.
The fundamental theorem of linear programming says that if an LP has an optimal solution, at least one optimal solution is at a corner (a vertex) of the feasible region. Intuitively: if you are in the middle of an edge, sliding one way or the other along it never makes things worse, so you can always slide to an end.
That turns an infinite search into a finite one. The simplex method starts at one corner and repeatedly moves along an edge to a neighbouring corner with a better objective, stopping when no neighbour improves. In our example it might go from \((0,0)\) to \((40,0)\) worth 200, then \((40,5)\) worth 260, then \((30,10)\) worth 270, where both remaining neighbours are worse. In the worst case the number of steps can grow exponentially, but in practice simplex is astonishingly fast, and modern solvers pair it with interior-point methods that cut through the middle of the region instead of walking along its edges.
Solving the two-route LP tells us what to do. Its dual tells us something almost more useful: what each scarce resource is worth. If the airline could buy one more aircraft hour per week, how much should it be willing to pay? That question has an exact answer, and it comes for free with the solution.
Every LP, the primal, has a twin called the dual. Where the primal has one variable per activity and one constraint per resource, the dual has one variable per resource and one constraint per activity. The dual variable \(y_i\) can be read as a price on resource \(i\).
Two results tie them together. Weak duality: any feasible dual solution gives an upper bound on the primal, \(c^\top x \le b^\top y\). Strong duality: at the optimum the two are equal. And complementary slackness says that a resource with spare capacity at the optimum has a price of zero, and an activity that is used has its full value exactly paid for by the resources it consumes.
The optimal dual values are called shadow prices. They answer "what if" questions without re-solving anything: one extra aircraft hour adds $500 of contribution; ten fewer crew hours cost $5,000. They also tell you where to look. A shadow price of zero on the market cap says that lobbying for more slots on route A is pointless right now, however attractive the route seems.
Two caveats. Shadow prices are marginal: they hold only over a range, after which a different set of constraints becomes binding and the prices jump. And in integer programs, which is most of what follows, duals are no longer exact. They remain a very useful approximation, and the next paragraph is the reason every RM analyst should care about them.
The two-route LP happened to give whole numbers. Usually it does not. And many airline decisions are inherently indivisible: you cannot lease half an aircraft, assign 0.4 of a fleet to a flight, or roster a pilot to 70% of a trip. When some variables must be integers, the model becomes a mixed-integer program (MIP), and everything gets harder.
The obvious shortcut is to solve the LP and round the answer. It fails in two ways: the rounded point may break a constraint, or it may be feasible but far from the best integer solution. A small example shows both.
The standard exact method, introduced by Ailsa Land and Alison Doig in 1960, is branch and bound. Solve the LP relaxation. If a variable that should be an integer is fractional, say \(W = 2.5\), split the problem in two: one branch adds \(W \le 2\), the other \(W \ge 3\). Neither branch loses any integer solution, but both exclude the fractional point. Solve each branch's LP, and keep going.
The "bound" part is what makes it practical. The LP value of a branch is an upper bound on any integer solution inside it. Once you have found a good integer solution (the incumbent), any branch whose bound is no better can be discarded without being explored.
At any moment a solver holds two numbers: the value of the best integer solution found so far, and the best bound still open in the tree. The difference, the MIP gap, measures how far from optimal the incumbent could possibly be. Real airline models are often stopped at a gap of a fraction of a percent rather than solved to zero.
How fast the gap closes depends mostly on how tight the LP relaxation is. Two formulations with exactly the same integer solutions can have very different relaxations, and the tighter one can be solved orders of magnitude faster. Modern solvers add cutting planes, extra constraints that shave off fractional corners without removing any integer point, and combine them with branching into branch-and-cut. When a model has too many variables to write down at all, as in crew pairing, branching is combined with column generation into branch-and-price (Chapter 07).
Some integer programs are secretly easy. If the constraints describe a flow of goods through a network, where each node's inflow must equal its outflow, the LP relaxation always has an integer optimal solution when capacities and supplies are integers. You solve an LP and get whole numbers for free. The technical reason is that the constraint matrix of a network is totally unimodular: every square submatrix has determinant 0, 1 or −1, which forces every corner of the feasible region to be integer.
The trick that makes network flows so useful for airlines is to put time into the graph. In a time-space network, each node is an airport at a moment in time: a departure or an arrival event. Two kinds of arcs connect them. Flight arcs go from a departure node at one airport to an arrival node at another. Ground arcs link consecutive events at the same airport and carry the aircraft that are sitting on the ground in between. A final wrap-around arc links the last node of the day back to the first, because tomorrow's schedule repeats today's.
An aircraft is now a unit of flow, and flow conservation at every node says exactly what it should: an aircraft that arrives must either wait on the ground or leave on a flight. To count how many aircraft the schedule needs, draw a vertical count line at any moment, typically the quietest time of night, and add up the flow on every arc that crosses it. In the picture, the two aircraft parked overnight at the hub are the whole fleet this schedule needs.
This picture is the foundation of the next two chapters. If every flight must be flown by exactly one of several aircraft types, each type becomes its own flow through the same network, and the problem becomes a multicommodity flow. That breaks total unimodularity, so integrality is no longer free, but the network structure keeps the LP relaxation tight enough to solve very large instances.
Once the schedule is set, every flight needs an aircraft type. Put a 300-seat aircraft on a flight with 150 passengers and you burn fuel and ownership cost to fly empty seats. Put a 150-seater on a flight with 250 passengers and you spill 100 of them to competitors, or to other flights. NP 101, Chapter 05 explains the trade-off in words; here is the model that airlines actually solve. The version below is the classic one from Hane, Barnhart, Johnson, Marsten, Nemhauser and Sigismondi (1995), and variations of it are still at the heart of most commercial fleeting tools.
All the commercial intelligence sits in \(c_{ik}\). It is usually built as operating cost plus expected spill cost:
The spill formula above treats each leg independently, which is the same mistake leg-based RM makes (RM 101, Chapter 06). A connecting passenger spilled from a small first leg is also lost on the second leg. Extensions such as the Itinerary-Based Fleet Assignment Model (IFAM) add passenger-flow variables per itinerary, with recapture onto alternative flights, so the model sees the network revenue of a fleeting decision. They are bigger and harder to solve, and they are one of the clearest places where network planning and revenue management use the same math.
Fleet assignment says "an A320 flies this leg". It does not say which A320. Aircraft routing, also called maintenance routing or, closer to the day, tail assignment, gives each physical aircraft (identified by its tail number) a sequence of flights. The FAM solution guarantees that the flow of aircraft balances; routing turns that flow into actual lines of flying that individual aircraft can follow.
What makes routing more than bookkeeping is maintenance. Aircraft need frequent routine checks, which have to happen at a station with the right hangar and staff, usually overnight. A route that keeps an aircraft away from maintenance-capable stations for too long is illegal, however efficient it looks. Other considerations pile on: some tails have specific equipment or restrictions, some routes need an aircraft cleared for long overwater flights, and planned heavy checks take tails out of service entirely.
A common approach enumerates strings: sequences of connected flights that begin and end at a maintenance station and respect the maximum time between checks. The model then picks a set of strings that covers every flight exactly once and can be flown with the aircraft available.
Close to departure, tail assignment becomes an operational tool: it is re-solved as aircraft go unserviceable, maintenance slots move and flights are swapped. Some airlines also solve fleet assignment and routing together, since a fleeting that cannot be routed legally is not a real plan.
Crew pairing is the problem that made airline OR famous. A pairing is a sequence of duty periods, separated by rest, that starts and ends at the same crew base: fly out on Monday, layover in one city, fly on Tuesday, layover in another, return home on Wednesday. Pairings are anonymous; no person is attached yet. The goal is to cover every flight in the schedule with the cheapest set of legal pairings.
Legality is a thicket of rules from aviation regulators and labour agreements: maximum flight time and duty time per day, minimum rest between duties, minimum and maximum connection times, limits on the number of landings, maximum days away from base. Cost is just as intricate. Crews are often paid the maximum of several quantities, such as actual flying time, a guaranteed minimum per duty, or a fraction of time away from base, plus hotel and per-diem costs for layovers. Much of the cost is "unproductive": time sitting between flights, overnight layovers, and deadheads, where a crew rides as passengers to reposition.
The model is almost embarrassingly simple to write. The difficulty is \(\mathcal{P}\): for a large airline the number of legal pairings runs into the billions and beyond. Nobody can enumerate them, let alone put them all in a solver.
The way out is to never write down \(\mathcal{P}\) at all. Column generation, whose roots go back to Dantzig and Wolfe (1960) and Gilmore and Gomory (1961), solves the LP relaxation with only a small subset of pairings, the restricted master problem. Its dual gives a price \(\pi_i\) for covering each leg. A second problem, the pricing problem, then searches the space of legal pairings for one whose cost is less than the value of the legs it covers:
The pricing problem is a resource-constrained shortest path on a network whose nodes are duties or flights and whose resources track duty time, flying time, landings and days away. It is still hard, but it is far smaller than enumerating everything, and it can be solved with dynamic programming. When the column generation LP is embedded inside branch and bound, re-generating columns at every node of the tree, the method is called branch-and-price. It is the standard exact approach for large crew-pairing problems.
Pairings are anonymous. Rostering turns them into monthly schedules for named pilots and flight attendants, adding everything the pairing step ignored: each person's vacation, training, medical checks, previous month's carry-over, days off requirements and qualifications. Where pairing is mostly about cost, rostering is also about fairness and quality of life, and in many airlines it is governed by seniority.
| Approach | How it works | Optimization question |
|---|---|---|
| Bidlines | Anonymous monthly lines are built, then crew bid for whole lines in seniority order | Build lines that are efficient and attractive |
| Preferential bidding | Crew state preferences (days off, destinations, trip lengths); the system builds personal rosters respecting seniority | Satisfy preferences lexicographically by seniority |
| Rostering | The airline assigns rosters to balance workload and fairness, with requests as soft constraints | Minimize cost and unfairness, maximize requests granted |
The structure is the same as crew pairing, one level up, and so is the solution method: rosters are generated by column generation, with a pricing problem per crew member. Seniority adds a twist. In preferential bidding, the most senior person must get the best roster the rules allow before the second person is considered, which is typically solved as a sequence of optimizations, one seniority level at a time, each fixing what the one before achieved.
Every plan in the previous chapters is optimized for a world where everything runs on time. Then a snowstorm closes a hub for six hours, an aircraft goes unserviceable, or a crew times out. The plan is broken, and the airline has to repair it within minutes, not weeks. This is the domain of the Operations Control Centre (OCC), and OR tools increasingly sit inside it.
Recovery usually runs in the same order as planning. Aircraft recovery decides which flights to delay, cancel or swap between tails so that the remaining aircraft can fly a feasible schedule. Crew recovery repairs the pairings and rosters that the new aircraft plan broke, using reserve crew, deadheads and swaps while respecting every legality rule. Passenger recovery rebooks disrupted passengers onto the new schedule.
The hard part is time. A model that finds the perfect answer in two hours is useless when the controller needs a decision in ten minutes. Recovery models therefore limit the horizon (a day or two), limit the options (a handful of delay steps per flight), and lean on heuristics that find good answers fast.
Solving aircraft, crew and passengers sequentially is fast, but a "cheap" aircraft solution that strands three crews is not cheap. Integrated recovery models that consider all three at once are an active area, and they face the same tension as integrated planning: better answers, bigger models, less time to solve them.
Every model so far has treated its inputs as known: demand, block times, crew availability. None of them are. There are two broad ways to take uncertainty seriously: plan for many possible futures at once, or make the plan less sensitive to which future happens.
A two-stage stochastic program splits decisions into those made now, before uncertainty resolves, and those made later, once it has. The first-stage decisions are optimized against the expected cost of the best reaction to each possible outcome.
The appeal is that the model values flexibility. A fleeting that looks slightly more expensive on average demand may win clearly once you account for the spill it avoids in high-demand scenarios. The cost is size: each scenario adds a copy of the second-stage problem.
A different approach is to build plans that break less. Typical examples: buffers in block times and turn times where delays are likely; crew pairings that keep a crew on the same aircraft through a connection, so a late inbound does not also delay a different flight; and aircraft routings that leave spare tails at the hubs. Robust optimization formalizes this by protecting against the worst case in an uncertainty set, rather than the average case.
When the question is "how does this plan behave?" rather than "what is the best plan?", Monte Carlo simulation is often the right tool: draw thousands of random days, run the plan through each, and look at the distribution of outcomes. The booking-limit simulator does exactly this on the revenue side, testing EMSR-b against first come, first served on 2,000 simulated flights.
Revenue management is, underneath, a set of OR models. RM 101 explains them through their intuition; this chapter shows the optimization problems behind three of its central ideas.
Littlewood's rule (RM 101, Chapter 03) is an instance of one of the oldest models in OR, the newsvendor: choose a quantity before uncertain demand is known, balancing the cost of having too much against the cost of having too little. The optimal quantity sits at the critical fractile of the demand distribution.
The exact single-leg problem is a dynamic program. Divide the booking window into periods small enough that at most one request arrives in each. Let \(V_t(x)\) be the expected revenue-to-go with \(t\) periods left and \(x\) seats left. In each period a request for fare class \(j\) arrives with probability \(\lambda_j\):
That right-hand side, \(\Delta V_{t-1}(x) = V_{t-1}(x) - V_{t-1}(x-1)\), is the bid price, now derived exactly rather than approximated. The catch is dimension: on a network, \(x\) becomes a vector of seats remaining on every leg, and the number of states explodes. That is why networks use the approximation below.
The DLP replaces random demand with its mean, which makes it an LP that can be solved for a whole network in seconds. Its duals \(\pi_l\) are the network bid prices, and the control rule follows directly from Chapter 02: accept product \(j\) if its fare covers the shadow value of the capacity it uses.
That one line is the whole of O&D control in RM 101, Chapter 06. The network bid price demo solves a small version of it around a hub, and the buy-down simulator shows what happens when the demand fed into models like these is itself biased by the controls. In practice the DLP is refined in many ways (re-solving frequently, randomizing demand, adding choice behaviour), but the DP-and-LP pair is the backbone of network RM.
The core models of airline OR are decades old, but the field is far from finished. A few directions stand out.
Computing power and solver technology have improved enough that steps once solved separately can increasingly be solved together: fleet assignment with routing, routing with crew pairing, schedule design with fleet assignment and passenger flows. Each integration removes a source of sub-optimality that Chapter 00 described. The same push is happening in recovery, where integrated aircraft, crew and passenger models are moving from research papers towards operations control.
OR and machine learning are converging from both sides. Learned models provide better inputs: forecasts of demand, block times, delay propagation and no-shows that feed the optimization. They also speed up the solvers themselves, for example by learning which variable to branch on, which columns are worth generating, or what a good starting solution looks like for a problem the airline solves every day with small changes. The optimization still guarantees feasibility and legality; the learning makes it faster and better informed.
Commercial MIP solvers have become dramatically faster over the last three decades, and strong open-source options now exist too. First-order methods that run on GPUs are starting to solve very large LPs that were out of reach before. For airlines, faster solvers mean shorter planning cycles, more what-if scenarios, and re-optimization closer to the day of operation.
The last few years made resilience expensive to ignore. Planning models are increasingly judged on how the plan performs in simulated operations, not just on its planned cost. I expect the line between planning and recovery to keep blurring, with plans built from the start to be easy to repair.
If you want to follow where these models are going, OR 102 is a reader's guide to the current research and to AGIFORS papers.
Anyway, that's the overview. If something here was unclear or you want to go deeper on any chapter, feel free to reach out. I find this stuff genuinely fascinating, and I'm always happy to talk about it.
OR origins and the simplex method: Wikipedia, Operations research.
AGIFORS (1961) and American Airlines' OR history: INFORMS, History of O.R. Excellence: American Airlines.
TRIP: Anbil et al., "Recent Advances in Crew-Pairing Optimization at American Airlines", Interfaces 21(1), 1991.
Fleet assignment: Hane et al., "The fleet assignment problem: Solving a large-scale integer program", Mathematical Programming 70, 1995.
CrewSolver: Yu et al., "A New Era for Crew Recovery at Continental Airlines", Interfaces 33(1), 2003.
Branch and bound: Land and Doig, "An automatic method of solving discrete programming problems", Econometrica 28(3), 1960.