網絡收益管理問題中的動態定價問題：改進行生成算法

柯劍男

摘 要： 研究了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.