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

柯剑男

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

关键词： 近似动态规划;半无穷线性规划;行生成算法

中图分类号： F 272   文献标志码： A

Abstract： 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.

Key words： approximate dynamic program; semi-infinite linear program; constraint generation

1 文献综述

动态定价问题一直是收益管理和交通工程领域的热门问题，决策者（企业）通过动态调整价格来实现收益最大化。而在网络收益管理中，不同的产品会竞争同一种资源，“资源-产品”网络结构增加了问题分析和求解的难度。比如：在航空行业中，资源是每段航班，产品是联程航班;在酒店行业中，资源是顾客住宿一天，产品是顾客连续住宿多天的订单;在交通工程中，资源是原始带宽，产品是提供给用户的服务包，比如音频、数据或者视频。Gallego和van Ryzin （1997）研究了网络收益管理中的动态定价问题，并给出了两种近似最优策略。

对于网络收益管理中的动态定价问题，常见的分析方法是把问题建立成一个动态规划模型。然而，动态规划存在“维数灾难”问题，求解复杂度随着维数的增加呈指数级增长。Adelman （2007）针对网络收益管理中的容量控制（capacity control）问题提出了近似动态规划方法研究框架，首先把动态规划转化为等价的线性规划，然后对线性规划中的价值函数使用函数比如线性函数（affine approximation）、分段线性函数（piecewise linear approximation））近似，将线性规划转化成近似线性规划（approximate linear program， ALP），最后对ALP求解得到近似函数中的参数和ALP问题的最优值。如果使用的近似函数是线性函数，函数中资源的系数被理解成动态投标价格（bid price）。ALP问题的最优值是动态投标价格策略的上界。投标价格策略来源于Talluri （1998），即如果产品的价格大于该产品组成资源的价值（由投标价格衡量），那么接受顾客的购买请求。在对应的确定性模型（deterministic program）中，资源约束的对偶变量的值被当成静态投标价格，在已有的文献比较中，基于动态投标价格的策略比基于静态投标价格的策略表现要好。然而在ALP问题中，约束对于所有的状态和决策都需要被满足，因此约束数量非常多。因此，除了约束抽样（constraint sampling algorithm）方法外（de Farias、Van Roy， 2004），行生成/列生成方法（constraint/column generation algorithm）成为求解ALP一个常用的方法（Zhang、Adelman，2009;Zhang，2011）。在本文中，我们将主要使用行生成算法求解动态定价问题下的ALP问题。

然而在动态定价问题中，约束有无限多個，列生成方法需要很长的时间求解。对于容量控制问题，在独立需求情形下，Tong和Topaloglu （2013）、Vossen和Zhang （2015） 都缩小了ALP的规模，但是在非独立需求下，Vossen和Zhang （2015）得到的简化ALP约束数量仍然随着资源呈指数增长。对于动态定价问题，Ke等人（2019）在线性独立需求下成功地将ALP转化成二次锥规划（second order cone program， SOCP），得到的SOCP规模仅线性依赖于资源数量、产品数量、周期，但是该转化方法无法应用于非独立需求情形下。因此，在动态定价问题中，列生成算法仍然是一种主要的求解方法。

我们的动态规划问题考虑了非独立需求中的MNL选择模型，即顾客选择某一个产品的概率依赖于其他产品带来的效用，而效用是价格的函数（Wang，2012）。自从McFadden提出MNL模型以来，该模型就被广泛应用在经济、营销和运营管理中。Liu和van Ryzin （2008）、Zhang和Adelman （2009）在容量控制问题中考虑了选择需求函数，并基于动态投标价格设计了控制策略，Zhang和Lu （2013） 在动态定价问题中考虑了选择需求函数，但是他们使用增广拉格朗日乘子法（augmented Lagrangian algorithms）求解确定性模型，并基于静态投标价格设计了定价策略。给定资源状态，行生成子问题可以被看作只有一个周期的确定性问题。我们把行生成子问题转化为一个凸规划问题并使用CVX求解。

在动态定价问题下的近似动态规划，因为离散的状态变量和连续的价格决策变量，列生成算法的主要难点在于列生成子问题是非线性整数规划。因此，对于每个周期，我们必须穷举所有可能的资源状态，然后在每个状态下求解行生成子问题。Adelman （2007）观察到动态投标价格具有长时间保持不变的性质，Vossen和Zhang （2012）利用动态投标价格的这种趋势为简化的ALP设计出了更快的求解办法。在本文中，我们也将应用这种性质改进行生成算法。

在ALP中，对于连续个周期投标价格不变的约束，资源状态变量的影响将会被消除，列生成子问题将会转化为非线性规划，而不是非线性整数规划。通过对偶分析，我们把ALP简化为对数线性规划。基于这个简化的数学规划，我们针对网络收益管理中的动态定价问题提出了一种改进的列生成算法。因为在简化的ALP中，一些周期的约束不再是无限数量，改进列生成算法比列生成算法收敛速度更快，计算时间更短。第4部分的数值实验验证了这点。

2 动态定价问题

4 数值实验

在本节的数值实验中，我们考虑航空领域的Hub-spoke网络和交通工程领域中的网络，如图2所示。其中，Hub-spoke网络有1个Hub结点、4个非Hub结点（如图2所示），那么资源有4种，产品有8种。交通工程领域中的网络有6种资源和35种产品。考虑周期为{50，100，200，400}，对应的每个资源初始库存为{4，7，11，25}。MNL模型中参数αt，j，t，j为[0，10]之间的随机数，βt，1=βt，2=…=βt，n，t为[0，1]之间的随机数。一般来说，>1min{ci，i}，因此在改进行生成算法中，对于所有的算例设置=45T。

我们在装有Windows Server 2012 R2 64位系统、Intel Xeon E5-2660U CPU处理器、128G内存的服务器中使用MATLAB调用CVX运行行生成算法和改进的行生成算法。为了检验在动态定价问题中动态投标价格V长时间保持不变的特性是否仍然成立，我们首先在图3中给出了两种网络结构下从行生成算法中得到的动态投标价格V的变化趋势。

從图3我们发现，在50个周期的问题中，动态投标价格V至少在前35个周期保持不变。这样一来，可以使用改进的行生成算法。行生成算法和改进的行生成算法表现如表1所示。表1中的第一行表示问题的周期，可以发现随着周期越来越长，两种算法的计算时间呈线性增长。第一列表示算法的求解精确度。毫不意外的是，对于两种算法来说，精确度=0.1%所需要的求解时间比精确度=1%所需要的求解时间更长。

表1中的第一部分和第二部分分别是Hub-spoke网络和交通工程网络下的计算结果。显然，交通工程网络规模更大，所需要的求解时间也更长。对于所有的算例，与行生成算法相比，改进的行生成算法用更快的时间给出了基本一样的最优值。在求解精确度下，平均来看，改进的行生成算法节省了70%的时间。

在计算表现上起着至关重要的作用。越大，每次循环生成的行越少，求解时间越短。但是当的值超过min{τi，i}时，它会传递出错误的信息V，i=V+1，i，得到的也是劣质的解。图4中展示了Hub-spoke网络中100周期、求解精确度=0.1%下计算时间和最优值的变化。从图4中可以发现，当从52增长到98时，计算时间会从1007.05减少到47.70，最优值会在=84之后变得不可靠。

5 结语

网络收益管理中的动态定价问题一直是收益管理理论中的热门问题。在实际行业应用中，航空公司和连锁酒店也会考虑如何对产品（联程航班、酒店连续多天的订单）定价来最大化收益。然而，需求的随机性和产品组合的多样性增加了问题的复杂性，需求的相互依赖和价格的连续性使得问题的分析和求解变得更加困难。

动态定价常用的模型为动态规划模型，考虑到动态规划模型的“维数灾难”，近似动态规划方法将动态规划中的价值函数使用函数近似，减少了变量的数量。然而，近似动态规划中约束的数量仍然依赖于动态规划中状态空间和决策空间的规模。对于这类大规模线性规划问题我们经常使用行生成算法（列生成算法）求解，尽管这类算法收敛速度较慢。考虑到近似动态规划得到的动态投标价格在大部分时间保持不变这一特性，我们改进了行生成算法，并通过数值实验说明改进的算法具有更快的收敛速度。我们相信本文中的分析方法可以应用到其他需求函数下的动态定价问题之中。

对于动态定价问题，确定性模型一般可以直接求解，而使用行生成算法求解近似动态规划仍然需要较大的计算工作量，在未来的工作中我们会接着分析近似动态规划中的特点，降低求解近似动态规划的难度。另一方面，实际生活中的定价问题会有更多的假设和约束，比如Nadarajah等人（2015）在酒店收益管理中设定住宿多天价格是单天价格的总和，我们也将在动态定价问题中考虑更多实际的设定。

参考文献：

[1] TALLURI K G J， VAN RYZIN. The theory and practice of revenue management[M]. New York： Springer， 2004.

[2] GALLEGO G G J， VAN RYZIN. A multiproduct dynamic pricing problem and its applications to network yield management[J]. Operations Research， 1997， 45（1）：24-41.

[3] ADELMAN D. Dynamic bid-prices in revenue man- agement[J]. Operations Research， 2007， 55（4）：647-661.

[4] DE FARIAS D， VAN ROY B. On constraint sampling in the linear programming approach to approximate dynamic programming[J]. Mathematics of Operations Research， 2004，29（3）：462-478.

[5] ZHANG D， ADELMAN D. An approximate dynamic programming approach to network revenue management with customer choice[J]. Transportation Science， 2009，43（3）：381-394.

[6] ZHANG D. An improved dynamic programming decomposition approach for network revenue management[J]. Manufacturing and Service Operations Management， 2011，13（1）：35-52.

[7] MCFADDEN D. The revealed preferences of a government bureaucracy： empirical evidence[J]. The Bell Journal of Economics， 1976：55-72.

[8] WANG R. Capacitated assortment and price optimization under the multinomial logit model[J]. Operations Research Letters， 2012，40（6）：492-497.

[9] LIU Q， VAN RYZIN G J. Strategic capacity rationing to induce early purchases[J]. Management Science， 2008，54（6）：1115-1131.

[10] ZHANG D， LU Z. Assessing the value of dynamic pricing in network revenue management[J]. Informs Journal on Computing， 2013，25（1）：102-115.

[11] TONG C， TOPALOGLU H. On the approximate linear programming approach for network revenue management problems[J]. Informs Journal on Computing， 2013，26（1）：121-134.

[12] VOSSEN T， ZHANG D. Reductions of approximate linear programs for network revenue management[J]. Operations Research， 2015，63（6）：1352-1371.

[13] KE J， ZHANG D， ZHENG H. An approximate dynamic programming approach to dynamic pricing for network revenue management[J]. Under review， production and operations management， 2019.

[14] VOSSEN T， ZHANG D. A dynamic disaggregation approach to approximate linear programs for network revenue management[J]. Production and Operations Management，2015，24（3）：469-487.

[15] BOYD S， VANDENBERGHE L. Convex optimization. Cambridge： Cambridge university press，2004.

[16] NADARAJAH S， LIM Y F， DING Q. Dynamic pricing for hotel rooms when customers request multiple-day stays[m]. Sigapore： Singapore Management University， 2015.