Network Revenue Management

Single-leg revenue management optimizes capacity allocation for one resource. Network revenue management extends this to interconnected resources—an airline network where a connecting itinerary A→B→C consumes capacity on two legs simultaneously.

The Problem

Consider a hub-and-spoke airline operating three airports: A, B (the hub), and C. The airline flies two legs—A→B and B→C—each with a capacity of 100 seats. Three itineraries are offered to passengers:

A→B (local): fare $200
B→C (local): fare $250
A→B→C (connecting): fare $350

A connecting passenger occupies one seat on each leg. Should the airline sell a $350 connecting ticket that uses capacity worth $200 + $250 = $450 in local fares? If local demand is strong enough to fill both legs, the answer is no—the connecting passenger displaces two local passengers who together would generate $100 more in revenue. This displacement effect is the defining challenge of network revenue management.

The difficulty is that the airline does not know with certainty how many local passengers will eventually book. If local demand turns out to be weak, rejecting the connecting fare leaves empty seats. The network RM problem is to make accept/reject decisions on each booking request so as to maximize total expected revenue across the entire network.

Mathematical Formulation

The Deterministic LP

Let the network have $m$ legs, each with capacity $C_i$ , and $n$ itineraries, each with fare $f_j$ and mean demand $d_j$ . Define the incidence matrix $A$ where $a_{ij} = 1$ if itinerary $j$ uses leg $i$ , and 0 otherwise. The deterministic linear programming (DLP) formulation maximizes total revenue subject to capacity and demand constraints:

\max_{\mathbf{x}} \; \sum_{j=1}^{n} f_j \, x_j \quad \text{s.t.} \quad \sum_{j \in S(i)} x_j \le C_i \;\; \forall\, i, \quad 0 \le x_j \le d_j \;\; \forall\, j

(1)

where $S(i) = \{j : a_{ij} = 1\}$ is the set of itineraries that use leg $i$ . The decision variable $x_j$ represents the number of seats allocated to itinerary $j$ .

Definition — Bid Price

The bid price $\pi_i$ of leg $i$ is the dual variable (shadow price) of the capacity constraint $\sum_{j \in S(i)} x_j \le C_i$ in the DLP. It represents the marginal revenue value of one additional seat on leg $i$ —the rate at which optimal revenue increases if one more unit of capacity were available on that leg.

The Bid-Price Accept/Reject Rule

Given the bid prices $\pi_i$ from the DLP, the airline applies a simple decision rule to each incoming booking request for itinerary $j$ :

\text{Accept itinerary } j \iff f_j \ge \sum_{i \in \text{legs}(j)} \pi_i

(2)

In words: accept the booking if and only if the fare exceeds the sum of bid prices on every leg the itinerary uses. The sum $\sum_{i \in \text{legs}(j)} \pi_i$ represents the opportunity cost of the capacity consumed by the itinerary—the revenue that could have been earned by selling those seats to other passengers.

Optimality of the Bid-Price Policy

The bid-price policy is optimal for the deterministic LP relaxation. It provides an upper bound on the expected revenue of any capacity allocation policy. In particular, the DLP objective value at the optimum is an upper bound on the expected revenue achievable under any booking control policy with stochastic demand (Talluri and van Ryzin, 2004).

For the simple example above, if bid prices turn out to be $\pi_{AB} = 200$ and $\pi_{BC} = 250$ , then the connecting itinerary A→B→C with fare $350 is rejected because $350 < 200 + 250 = 450$ . Only when local demand is weak enough to push bid prices down will the connecting fare be accepted.

Virtual Nesting

Directly implementing bid-price controls requires resolving the LP frequently as bookings arrive. An alternative approach, widely used in airline practice, is virtual nesting—a method that maps multi-leg itineraries back to single-resource problems that can be solved with standard single-leg techniques such as EMSR.

Definition — Displacement-Adjusted Revenue (DAR)

The displacement-adjusted revenue of itinerary $j$ on leg $i$ is the fare minus the opportunity cost on all other legs used by that itinerary:

\text{DAR}_{ij} = f_j - \sum_{k \in \text{legs}(j),\, k \ne i} \pi_k

It answers the question: “What is this itinerary worth to leg $i$ , net of what it costs on the other legs?”

Definition — Virtual Nesting

Virtual nesting assigns each itinerary to a virtual fare class on each leg it uses, based on its DAR value. Itineraries with high DAR on a given leg are placed in higher virtual classes and receive priority access to capacity. Single-leg booking controls (e.g., nested booking limits or protection levels from EMSR) are then applied independently on each leg using these virtual classes.

The key insight is that a connecting itinerary may be a high-value virtual class on one leg and a low-value class on another, depending on the bid prices. For example, a $350 A→B→C fare with $\pi_{BC} = 200$ has a DAR of $150 on leg A→B (relatively low), but with $\pi_{AB} = 100$ has a DAR of $250 on leg B→C (relatively high). Virtual nesting captures this asymmetry, which a simple fare-based ranking would miss.

Interactive Explorer

Use the sliders to adjust capacities and demand levels across the network. The visualizations compute bid prices and acceptance decisions in real time.

The network diagram shows four airports with three legs. Capacity bars display utilization on each leg. The bid price $\pi_i$ for each leg is computed from the LP solution. The table below shows whether each itinerary is accepted or rejected based on the bid-price rule $f_j \ge \sum \pi_i$ .

Key Insights

1. Connecting Fares Must Exceed the Sum of Bid Prices

A connecting itinerary is accepted only if its fare exceeds the total opportunity cost of capacity on all legs it uses. A fare that looks attractive in isolation may be unprofitable when displacement costs are properly accounted for.

2. Bid Prices Capture Opportunity Cost

The bid price on a leg reflects the marginal revenue value of an additional seat. When a leg is unconstrained (remaining capacity exceeds remaining demand), its bid price falls to zero. When capacity is tight, the bid price rises, making it harder for low-fare itineraries to gain acceptance.

3. Network Effects Can Reverse Single-Leg Intuition

On a single leg, a higher fare is always preferred to a lower one. In a network, a $350 connecting fare can be less desirable than two $200 and $250 local fares because the connecting passenger consumes capacity on two legs simultaneously. Increase local demand in the explorer above and observe the connecting fares being rejected.

4. Virtual Nesting Reduces Network Problems to Single-Leg Problems

By computing displacement-adjusted revenues, the airline can assign each itinerary to a virtual class on each leg and apply standard single-leg controls (EMSR-a, EMSR-b, or optimal nested booking limits). This decomposition is approximate but highly practical and is the basis of most deployed airline RM systems (Williamson, 1992).

5. LP-Based Approaches Provide Upper Bounds but Can Be Loose

The deterministic LP replaces stochastic demand with its mean, ignoring variance. When demand uncertainty is high, the DLP bound can significantly overestimate achievable revenue. Randomized LP approaches and simulation-based methods can tighten the bound but at greater computational cost (de Boer, Freling, and Piersma, 2002).

Extensions

The deterministic LP with bid-price controls is the simplest network RM model. Practical systems extend it in several directions:

Choice-based network RM—The DLP assumes independent demand for each itinerary. In reality, passengers choose among available itineraries based on price and schedule. Choice-based models (e.g., using multinomial logit) jointly optimize which fare classes to open across the network, accounting for substitution effects between itineraries.
Dynamic bid pricing—Rather than solving the LP once and using static bid prices, dynamic approaches re-solve the LP as bookings arrive, updating bid prices to reflect the current state of remaining capacity and updated demand forecasts. This adaptive strategy captures information that accumulates during the booking horizon.
Airline alliances and codeshares—When two or more airlines sell itineraries that span each other’s networks, the revenue management problem becomes a game. Each airline controls capacity on its own legs but must coordinate (or compete) on how to price connecting itineraries. Transfer prices between alliance partners are closely related to bid prices (Phillips, 2021).
Approximate dynamic programming—For large networks where the LP approach becomes computationally expensive, methods such as affine approximations to the value function and column generation decomposition provide scalable alternatives (Talluri and van Ryzin, 2004).

References

de Boer, S. V., Freling, R. & Piersma, N. (2002). “Mathematical Programming for Network Revenue Management Revisited.” European Journal of Operational Research, 137(1), 72–92.
Phillips, R. L. (2021). Pricing and Revenue Optimization, 2nd ed.. Stanford University Press.
Talluri, K. T. & van Ryzin, G. J. (2004). The Theory and Practice of Revenue Management. Springer.
Williamson, E. L. (1992). “Airline Network Seat Inventory Control: Methodologies and Revenue Impacts.” PhD dissertation, MIT.

Managing a Route Network