Data-driven robust network revenue management

Abstract

In this research, we focus on data-driven distributionally robust controls for the quantity-based network revenue management (NRM) problem in which the decision maker accepts or rejects each arriving customer request irrevocably with the goal of maximizing the total expected revenue over a finite selling horizon given limited resources. Instead of the deterministic linear programming (DLP) formulation widely adopted in literature, we approximate the value function of dynamic programming (DP) for NRM problem as probabilistic nonlinear programming (PNLP) in order to capture the randomness in demand. We further take the uncertainty in distribution estimation resulting from either the limited information or the changing environment into account by incorporating the distribution ambiguity into the PNLP formulation. We therefore solve a distributionally robust optimization (DRO) problem to determine an optimal partitioned allocation of capacity to each product against a worst-case distribution in the ambiguity set. We assume that the decision maker does not know the distribution of demand but has access to historical data, which is assumed to be independent and identically distributed (i.i.d.). In this setting, we define our data-driven ambiguity set as a confidence region of a goodness-of-fit (GoF) hypothesis test and then formulate a tractable robust static model. Furthermore, we extend our robust static NRM model to a multi-stage version. More specifically, we formulate the multi-stage robust NRM model as a robust DP and solve this robust DP using approximate dynamic programming (ADP) approach. The resulting robust ADP model generates robust dynamic bid prices from a conic optimization to help us construct capacity allocation policies. We also provide a constraint generation procedure for solving this robust ADP. To improve the efficiency of problem-solving, we further derive an equivalent reformulation for the robust ADP model, which is computationally tractable and of practical interpretation. By solving this reformulation that approximates the evolution of the selling system under demand uncertainty, we can construct a robust dynamic booking limit policy. We also verify the performance of both our robust static and dynamic policy via numerical experiments.