网络收益管理问题中的动态定价问题:改进行生成算法

Constraint Generation Algorithms for Approximate Linear Programs in Dynamic Pricing Problems

研究了MNL需求下网络收益管理中的动态定价问题。建立了动态规划模型并使用基于线性的近似动态规划方法来处理动态规划中的“维数灾难”问题。尽管如此,因为动态规划问题的价格决策空间是连续的,得到的近似线性规划(ALP)是一个半无限的线性规划,故将使用行生成算法来求解近似线性规划。基于ALP问题最优解的特性,简化了ALP规划,改进了行生成算法。数值实验显示,改进的行生成算法的收敛时间比原来的行生成算法快了近70%。

In this paper,we study a dynamic pricing problem in network revenue management with multinomial logit demand.A dynamic program is formulated and a linear-based approximate dynamic programming approach is applied to deal with the curse of dimensionality.However,due to the continuous decision space of price,the approximate linear program(ALP)is a semi-infinite linear program and a constraint generation algorithm is applied to solve it.Based on the structural property of the optimal solution in ALP,we formulate a reduced ALP and improve the constraint generation algorithm.The numerical study shows that the improved constraint generation algorithm takes about 70% less time to converge.