Introduction
Network Revenue Management (NRM) is the strategic process of allocating perishable, limited resources—such as airline seats, hotel rooms, or cloud computing capacity—to maximize total revenue over a finite horizon. Traditionally, NRM models have relied on the assumption of independent customer arrivals, where the probability of a specific request today is entirely decoupled from yesterday's demand.
In practice, however, demand is frequently correlated. Macroeconomic shifts, weather events, and seasonal trends create "bursty" demand patterns that independent models fail to capture. While previous research has attempted to model these correlations, solutions were often either too narrow in scope or computationally intractable. This paper introduces a unified framework that models arrivals through a time-inhomogeneous Markov chain, offering a tractable "bid price" policy with a guaranteed constant approximation ratio.
The Markovian-Correlated Arrival Model
The author proposes a Markovian-correlated arrival model to bridge the gap between theoretical simplicity and real-world complexity. In this framework, the system state—which determines the type of customer arriving at any given time—evolves according to a Markov chain. This approach is highly flexible, capable of representing:
- High-variance or "bursty" demand patterns.
- Non-stationary trends over the planning horizon.
- Scenarios where the total number of arrivals is unknown.
By treating the arrival process as a state-dependent evolution, the model encompasses several existing arrival models (such as the INDEP and CORREL models) as special cases, providing a "super-model" for revenue management.
Methodology: LP Approximation and Bid Price Policy
Solving the NRM problem exactly via Dynamic Programming is often impossible due to the "curse of dimensionality." To address this, the paper utilizes two primary technical pillars:
1. Linear Programming (LP) Approximation
The author approximates the "value-to-go" function (the expected future revenue) as a linear combination of the remaining resources. This transformation results in a tractable Linear Program that provides a theoretical upper bound on the maximum possible revenue the system could generate.
2. State-Dependent Bid Price Policy
Using the LP results, the author derives a policy where each resource is assigned a "bid price," representing its internal opportunity cost. A customer's request is accepted only if the offered reward exceeds the sum of the bid prices for all resources consumed by that request. Crucially, these bid prices are not static; they are calculated using a backward induction process that accounts for the current state of the Markov chain. This allows the seller to adjust their thresholds in anticipation of expected surges or droughts in demand.
Theoretical and Empirical Results
The paper provides a rigorous theoretical foundation for the proposed policy, complemented by empirical validation.
Theoretical Guarantees
The most significant theoretical contribution is the $1/(1+L)$ approximation guarantee. The author proves that the proposed policy will always collect at least $1/(1+L)$ of the optimal expected reward, where $L$ is the maximum number of resources a single customer can demand. Notably, this ratio is independent of the time horizon ($T$) or the total number of resources ($m$), making the algorithm exceptionally robust for long-term planning. Furthermore, the policy is shown to be asymptotically optimal; as resource capacities scale toward infinity, the LP upper bound becomes perfectly tight.
Empirical Performance
The framework was tested using a synthetic hub-and-spoke airline revenue management simulator involving 8 flight legs and 40 customer classes. The simulation explored both time-dependent arrival probabilities and direct correlations between consecutive customers.
In these experiments, the gap between the proposed policy and the theoretical maximum revenue averaged only 6.60%. This suggests that while the $1/(1+L)$ bound provides a safe "worst-case" floor, the policy's actual performance in realistic scenarios is significantly higher.
Conclusion and Future Directions
This research provides a robust, unified framework for managing revenue in environments with correlated demand. By moving beyond the independence assumption, the Markovian-correlated model offers a more realistic tool for practitioners without sacrificing theoretical rigor.
Future work may extend this model to include:
- Reusable Resources: Adapting the framework for resources that return to inventory, such as rental cars or cloud instances.
- Overbooking: Incorporating cancellations and no-shows into the state-dependent logic.
- Advanced Basis Functions: Exploring non-linear or neural-network-based approximations for the value function to further close the empirical performance gap.
Summary updated