Grégoire Maillard

How it works

The network

An invented airline with a hub at Montréal (YUL): two feeder flights in from Québec City (YQB) and Ottawa (YOW), two long-haul flights out to Paris (CDG) and London (LHR), one direction and one departure day, economy cabin only. That gives eight itineraries: four local (one flight) and four connecting (a feeder plus a long-haul flight), each sold in three fare classes, Y (flexible), M (standard) and Q (discount). Fares, forecasts and capacities come from bidprice.json and are illustrative assumptions.

The linear program and the bid prices

Let j be a product (an itinerary in a class) with fare f_j and expected demand d_j, and c_l the seats on flight l. The deterministic LP (Williamson, 1992) is: maximise Σ_j f_j x_j subject to Σ_{j uses l} x_j ≤ c_l for every flight and 0 ≤ x_j ≤ d_j. The bid price π_l of flight l is the dual value of its seat constraint: how much the optimal revenue would rise with one more seat on it. A request for product j is accepted if f_j ≥ Σ_{l in j} π_l and a seat is left on every flight it uses. The sum of the bid prices is the displacement cost of the booking, the revenue it is expected to push out of the network. The LP is solved in your browser by GLPK, compiled to WebAssembly by glpk.js 5.0.0, which returns the duals of the simplex solution directly.

The booking stream

Each product's demand for one departure is a Poisson draw whose mean is itself random (a gamma factor with a 25% coefficient of variation), so the variance is d + (0.25 d)². Each request then gets a booking time between 0 (sales open) and 1 (departure) from a beta distribution that depends on the class: Beta(2, 5) for Q, Beta(3, 3) for M and Beta(5, 2) for Y, so discount requests come mostly early and flexible ones mostly late, with overlap. Requests are processed in time order. The generator is seeded, so the page opens on the same stream every time; "New booking stream" changes the seed.

The three controls

• No control: accept while there is a seat on every flight the itinerary uses.
• Leg-based EMSR-b: each flight runs its own three-class EMSR-b, as on the booking limits page. A flight's class demand is the demand of every local and connecting product in that class using the flight. A connecting fare is split between its two flights in proportion to the local fares of the same class (so YQB–CDG in M credits 210 / (210 + 820) of its fare to YQB–YUL), and the class fare on a flight is the demand-weighted average of the fares it is credited. Protection levels are nested: class k is open while the seats left exceed the seats protected for the classes above it. A connecting booking needs its class open on both flights.
• O&D bid price: the LP above, re-solved with the seats left and the expected demand still to come.

Both controls re-optimise at the same points: at the first request and then every N requests. The expected demand still to come for product j at time t is d_j · (1 − F_k(t)), where F_k is the beta distribution of its class. Perfect hindsight is the same LP solved once on the demand that actually turned up, the most any control could have earned from that stream. Its solution is always in whole passengers because every itinerary uses at most one feeder and one long-haul flight, which makes the constraint matrix totally unimodular.

Sources

• Williamson, E. L. (1992), Airline network seat inventory control: methodologies and revenue impacts, PhD thesis, MIT. The deterministic LP and its bid prices; in her simulations network control gained nothing over good leg-based control below an average load factor of about 85%, and on the order of 2–4% above it (checked September 2026).
• Talluri, K. and van Ryzin, G. (1998), "An analysis of bid-price controls for network revenue management", Management Science 44(11).
• Talluri, K. and van Ryzin, G. (2004), The Theory and Practice of Revenue Management, Springer, chapter 3 (network capacity control).
• Belobaba, P. (1992), "Optimal vs. heuristic methods for nested seat allocation", AGIFORS Reservations and Yield Management Study Group (EMSR-b).
• Solver: glpk.js 5.0.0 (GPL-3.0), loaded from jsDelivr; charts with D3 7.9.0.

Limitations

• The LP uses expected demand only, so its bid prices ignore uncertainty. They tend to come out as round steps equal to some product's fare, and they drop to zero on any flight the forecast doesn't fill. Real systems use stochastic or dynamic-programming bid prices, and turn bid prices into availability with virtual nesting or DAVN (RM 101, chapter 06).
• When a flight is exactly full in the LP solution the dual can be any value in a range; the solver returns one of them. The "+1 seat" check in the flight table shows the revenue from an extra seat, which can differ from the dual in that case.
• Demand in each product is independent of what is open: passengers never buy down to a cheaper class or switch itinerary (RM 101, chapter 05). No cancellations, no-shows, overbooking or groups.
• Leg-based control here is a fair but simple version: real airlines add rules such as closing connecting fares on busy long-haul flights by hand, which this page doesn't model. Proration by local fares is one of several conventions; mileage-based proration credits even less to the feeder.
• One direction, one day, one cabin. A real hub has hundreds of flights, return trips and several banks of connections, and the gain from O&D control is usually a few percent of revenue rather than the larger gaps in the extreme scenarios.

This is a personal project and isn't affiliated with any airline.