Managing Uncertain Capacities for Network Revenue Optimization

Abstract

Problem definition: We study the problem of managing uncertain capacities for revenue optimization over a network of resources. The uncertainty could be due to (i) the need to reallocate initial capacities among resources or (ii) the random availability of physical capacities by the time of service execution. Academic/practical relevance: The analyzed control policy is aligned with the current industry practice, with a virtual capacity and a bid price associated with each network resource. The seller collects revenues from an arriving stream of customers. Admitted requests that cannot be accommodated within the final, effective capacities incur a penalty cost. The objective is to maximize the total cumulative net revenue (sales revenue minus penalty cost). The problem arises in practice, for instance, when airlines are subject to last-minute change of aircrafts and in cargo revenue management where the capacity left by the passengers? load is used for freight. Methodology: We present a stochastic dynamic programming formulation for this problem and propose a stochastic gradient algorithm to approximately solve it. All limit points of our algorithm are stationary points of the approximate expected net revenue function. Results: Through an exhaustive numerical study, we show that our controls are computed efficiently and deliver revenues that are almost consistently higher than the ones obtained from benchmarks based on the widely adopted deterministic linear programming model. Managerial implications: We obtain managerial insights about the impact of the timing of the capacity uncertainty clearance, the capacity heterogeneity, the network congestion, and the penalty for not being able to accommodate the previously accepted demand. Our approach tends to offer the best performance across different parameterizations of the problem.