Dynamic Pricing Problems In Network Revenue Management

Revenue management is widely employed from its original application in airlines to business practice in different industries such as hotel management,fashion retail.A more complicated version is network revenue management,in which a set of products share a common set of resources and are sold in a finite selling horizon.Pricing problems and capacity control problems are two main categorizations in revenue management.In this thesis,we study dynamic pricing problems,in which the firm make decisions for products’ price to maximize total expected revenue over the finite sales horizon with limited capacity and demand arises as a stochastic process with intensity related to price.An efficient method to deal with dynamic pricing problems is to approximate the customer demand with their expectation and build a mathematical program to maximize the revenue with resource constraints,which is a deterministic problem.Meanwhile,dynamic programming methods have advantages in modeling problems through keeping track of resource levels over time.In this work,we build a dynamic program for the dynamic pricing problem and use approximate dynamic programming approach to solve the problem.The approximate dynamic programming approach starts with an equivalent linear programming formulation of the dynamic programming formulation and approximates the value function with the weighted sum of a set of pre-selected basis functions,resulting in approximate linear programs.Unlike capacity control problems,the approximate linear programs(ALPs)for dynamic pricing problems are semi-infinite linear programs due to the continuous decision space of price.To deal with the infinite of constraints in ALPs,we propose a column generation algorithm,which often poses considerable computational challenge.Furthermore,we propose a general scheme to reduce the ALPs to compact programs whose size is not related to decision space.This general scheme can be applied to both capacity control problems and dynamic pricing problems in network revenue management.We illustrate the power of this general scheme through establishing compact reformulations of ALPs for capacity control problems discussed in Vossen and Zhang(2015b),which consider ALPs with affine and separable piecewise linear approximations under either independent or discrete choice models of demand.Their proof relates the ALPs to the Danzig-Wolfe decomposition of compact linear programs that are much smaller in size.While our general scheme is based on reformulations of constraints and duality arguments.We also explore theoretical and practical results in applying this general scheme to dynamic pricing problems under different demand.For the affine approximation under a linear independent demand model,we show that the ALPs can be reformulated as compact second order cone programs(SOCPs)through duality analysis and variable aggregation.The size of the SOCP formulation is linear in model primitives,including the number of resources,the number of products,and the number of periods.Moreover,we show that this reduction approach can be applied to other independent demand model such as log linear independent demand.In addition,we consider a version of the model with discrete price sets and show that the resulting ALPs admit compact reformulations.We report numerical results on computational and policy performance on a set of huband-spoke problem instances.For dependent demand model,such as multinomial logit demand,we have to enumerate all the state in order to solve the column generation subproblem in ALPs,which make the constraint generation algorithm much more computational intensive.We utilize the structural property of the optimal solution in ALPs and remove the term associated with state in constraints.Based on this reformulated ALPs,we improve the constraint generation algorithm and obtain a reduced ALP.The numerical study shows that the improved constraint generation algorithm takes about 70% less time to converge and solving the reduced ALPs can be magnificent faster than the constraint generation algorithm.