網(wǎng)絡(luò)收益管理問題中的動態(tài)定價問題：改進(jìn)行生成算法

柯劍男

摘 要： 研究了MNL需求下網(wǎng)絡(luò)收益管理中的動態(tài)定價問題。建立了動態(tài)規(guī)劃模型并使用基于線性的近似動態(tài)規(guī)劃方法來處理動態(tài)規(guī)劃中的“維數(shù)災(zāi)難”問題。盡管如此，因?yàn)閯討B(tài)規(guī)劃問題的價格決策空間是連續(xù)的，得到的近似線性規(guī)劃（ALP）是一個半無限的線性規(guī)劃，故將使用行生成算法來求解近似線性規(guī)劃?；贏LP問題最優(yōu)解的特性，簡化了ALP規(guī)劃，改進(jìn)了行生成算法。數(shù)值實(shí)驗(yàn)顯示，改進(jìn)的行生成算法的收斂時間比原來的行生成算法快了近70%。

關(guān)鍵詞： 近似動態(tài)規(guī)劃;半無窮線性規(guī)劃;行生成算法

中圖分類號： F 272 ? 文獻(xiàn)標(biāo)志碼： 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 文獻(xiàn)綜述

動態(tài)定價問題一直是收益管理和交通工程領(lǐng)域的熱門問題，決策者（企業(yè)）通過動態(tài)調(diào)整價格來實(shí)現(xiàn)收益最大化。而在網(wǎng)絡(luò)收益管理中，不同的產(chǎn)品會競爭同一種資源，“資源-產(chǎn)品”網(wǎng)絡(luò)結(jié)構(gòu)增加了問題分析和求解的難度。比如：在航空行業(yè)中，資源是每段航班，產(chǎn)品是聯(lián)程航班;在酒店行業(yè)中，資源是顧客住宿一天，產(chǎn)品是顧客連續(xù)住宿多天的訂單;在交通工程中，資源是原始帶寬，產(chǎn)品是提供給用戶的服務(wù)包，比如音頻、數(shù)據(jù)或者視頻。Gallego和van Ryzin （1997）研究了網(wǎng)絡(luò)收益管理中的動態(tài)定價問題，并給出了兩種近似最優(yōu)策略。

對于網(wǎng)絡(luò)收益管理中的動態(tài)定價問題，常見的分析方法是把問題建立成一個動態(tài)規(guī)劃模型。然而，動態(tài)規(guī)劃存在“維數(shù)災(zāi)難”問題，求解復(fù)雜度隨著維數(shù)的增加呈指數(shù)級增長。Adelman （2007）針對網(wǎng)絡(luò)收益管理中的容量控制（capacity control）問題提出了近似動態(tài)規(guī)劃方法研究框架，首先把動態(tài)規(guī)劃轉(zhuǎn)化為等價的線性規(guī)劃，然后對線性規(guī)劃中的價值函數(shù)使用函數(shù)比如線性函數(shù)（affine approximation）、分段線性函數(shù)（piecewise linear approximation））近似，將線性規(guī)劃轉(zhuǎn)化成近似線性規(guī)劃（approximate linear program， ALP），最后對ALP求解得到近似函數(shù)中的參數(shù)和ALP問題的最優(yōu)值。如果使用的近似函數(shù)是線性函數(shù)，函數(shù)中資源的系數(shù)被理解成動態(tài)投標(biāo)價格（bid price）。ALP問題的最優(yōu)值是動態(tài)投標(biāo)價格策略的上界。投標(biāo)價格策略來源于Talluri （1998），即如果產(chǎn)品的價格大于該產(chǎn)品組成資源的價值（由投標(biāo)價格衡量），那么接受顧客的購買請求。在對應(yīng)的確定性模型（deterministic program）中，資源約束的對偶變量的值被當(dāng)成靜態(tài)投標(biāo)價格，在已有的文獻(xiàn)比較中，基于動態(tài)投標(biāo)價格的策略比基于靜態(tài)投標(biāo)價格的策略表現(xiàn)要好。然而在ALP問題中，約束對于所有的狀態(tài)和決策都需要被滿足，因此約束數(shù)量非常多。因此，除了約束抽樣（constraint sampling algorithm）方法外（de Farias、Van Roy， 2004），行生成/列生成方法（constraint/column generation algorithm）成為求解ALP一個常用的方法（Zhang、Adelman，2009;Zhang，2011）。在本文中，我們將主要使用行生成算法求解動態(tài)定價問題下的ALP問題。

然而在動態(tài)定價問題中，約束有無限多個，列生成方法需要很長的時間求解。對于容量控制問題，在獨(dú)立需求情形下，Tong和Topaloglu （2013）、Vossen和Zhang （2015） 都縮小了ALP的規(guī)模，但是在非獨(dú)立需求下，Vossen和Zhang （2015）得到的簡化ALP約束數(shù)量仍然隨著資源呈指數(shù)增長。對于動態(tài)定價問題，Ke等人（2019）在線性獨(dú)立需求下成功地將ALP轉(zhuǎn)化成二次錐規(guī)劃（second order cone program， SOCP），得到的SOCP規(guī)模僅線性依賴于資源數(shù)量、產(chǎn)品數(shù)量、周期，但是該轉(zhuǎn)化方法無法應(yīng)用于非獨(dú)立需求情形下。因此，在動態(tài)定價問題中，列生成算法仍然是一種主要的求解方法。

我們的動態(tài)規(guī)劃問題考慮了非獨(dú)立需求中的MNL選擇模型，即顧客選擇某一個產(chǎn)品的概率依賴于其他產(chǎn)品帶來的效用，而效用是價格的函數(shù)（Wang，2012）。自從McFadden提出MNL模型以來，該模型就被廣泛應(yīng)用在經(jīng)濟(jì)、營銷和運(yùn)營管理中。Liu和van Ryzin （2008）、Zhang和Adelman （2009）在容量控制問題中考慮了選擇需求函數(shù)，并基于動態(tài)投標(biāo)價格設(shè)計(jì)了控制策略，Zhang和Lu （2013） 在動態(tài)定價問題中考慮了選擇需求函數(shù)，但是他們使用增廣拉格朗日乘子法（augmented Lagrangian algorithms）求解確定性模型，并基于靜態(tài)投標(biāo)價格設(shè)計(jì)了定價策略。給定資源狀態(tài)，行生成子問題可以被看作只有一個周期的確定性問題。我們把行生成子問題轉(zhuǎn)化為一個凸規(guī)劃問題并使用CVX求解。

在動態(tài)定價問題下的近似動態(tài)規(guī)劃，因?yàn)殡x散的狀態(tài)變量和連續(xù)的價格決策變量，列生成算法的主要難點(diǎn)在于列生成子問題是非線性整數(shù)規(guī)劃。因此，對于每個周期，我們必須窮舉所有可能的資源狀態(tài)，然后在每個狀態(tài)下求解行生成子問題。Adelman （2007）觀察到動態(tài)投標(biāo)價格具有長時間保持不變的性質(zhì)，Vossen和Zhang （2012）利用動態(tài)投標(biāo)價格的這種趨勢為簡化的ALP設(shè)計(jì)出了更快的求解辦法。在本文中，我們也將應(yīng)用這種性質(zhì)改進(jìn)行生成算法。

在ALP中，對于連續(xù)個周期投標(biāo)價格不變的約束，資源狀態(tài)變量的影響將會被消除，列生成子問題將會轉(zhuǎn)化為非線性規(guī)劃，而不是非線性整數(shù)規(guī)劃。通過對偶分析，我們把ALP簡化為對數(shù)線性規(guī)劃?；谶@個簡化的數(shù)學(xué)規(guī)劃，我們針對網(wǎng)絡(luò)收益管理中的動態(tài)定價問題提出了一種改進(jìn)的列生成算法。因?yàn)樵诤喕腁LP中，一些周期的約束不再是無限數(shù)量，改進(jìn)列生成算法比列生成算法收斂速度更快，計(jì)算時間更短。第4部分的數(shù)值實(shí)驗(yàn)驗(yàn)證了這點(diǎn)。

2 動態(tài)定價問題

4 數(shù)值實(shí)驗(yàn)

在本節(jié)的數(shù)值實(shí)驗(yàn)中，我們考慮航空領(lǐng)域的Hub-spoke網(wǎng)絡(luò)和交通工程領(lǐng)域中的網(wǎng)絡(luò)，如圖2所示。其中，Hub-spoke網(wǎng)絡(luò)有1個Hub結(jié)點(diǎn)、4個非Hub結(jié)點(diǎn)（如圖2所示），那么資源有4種，產(chǎn)品有8種。交通工程領(lǐng)域中的網(wǎng)絡(luò)有6種資源和35種產(chǎn)品?？紤]周期為{50，100，200，400}，對應(yīng)的每個資源初始庫存為{4，7，11，25}。MNL模型中參數(shù)αt，j，t，j為[0，10]之間的隨機(jī)數(shù)，βt，1=βt，2=…=βt，n，t為[0，1]之間的隨機(jī)數(shù)。一般來說，>1min{ci，i}，因此在改進(jìn)行生成算法中，對于所有的算例設(shè)置=45T。

我們在裝有Windows Server 2012 R2 64位系統(tǒng)、Intel Xeon E5-2660U CPU處理器、128G內(nèi)存的服務(wù)器中使用MATLAB調(diào)用CVX運(yùn)行行生成算法和改進(jìn)的行生成算法。為了檢驗(yàn)在動態(tài)定價問題中動態(tài)投標(biāo)價格V長時間保持不變的特性是否仍然成立，我們首先在圖3中給出了兩種網(wǎng)絡(luò)結(jié)構(gòu)下從行生成算法中得到的動態(tài)投標(biāo)價格V的變化趨勢。

從圖3我們發(fā)現(xiàn)，在50個周期的問題中，動態(tài)投標(biāo)價格V至少在前35個周期保持不變。這樣一來，可以使用改進(jìn)的行生成算法。行生成算法和改進(jìn)的行生成算法表現(xiàn)如表1所示。表1中的第一行表示問題的周期，可以發(fā)現(xiàn)隨著周期越來越長，兩種算法的計(jì)算時間呈線性增長。第一列表示算法的求解精確度。毫不意外的是，對于兩種算法來說，精確度=0.1%所需要的求解時間比精確度=1%所需要的求解時間更長。

表1中的第一部分和第二部分分別是Hub-spoke網(wǎng)絡(luò)和交通工程網(wǎng)絡(luò)下的計(jì)算結(jié)果。顯然，交通工程網(wǎng)絡(luò)規(guī)模更大，所需要的求解時間也更長。對于所有的算例，與行生成算法相比，改進(jìn)的行生成算法用更快的時間給出了基本一樣的最優(yōu)值。在求解精確度下，平均來看，改進(jìn)的行生成算法節(jié)省了70%的時間。

在計(jì)算表現(xiàn)上起著至關(guān)重要的作用。越大，每次循環(huán)生成的行越少，求解時間越短。但是當(dāng)?shù)闹党^min{τi，i}時，它會傳遞出錯誤的信息V，i=V+1，i，得到的也是劣質(zhì)的解。圖4中展示了Hub-spoke網(wǎng)絡(luò)中100周期、求解精確度=0.1%下計(jì)算時間和最優(yōu)值的變化。從圖4中可以發(fā)現(xiàn)，當(dāng)從52增長到98時，計(jì)算時間會從1007.05減少到47.70，最優(yōu)值會在=84之后變得不可靠。

5 結(jié)語

網(wǎng)絡(luò)收益管理中的動態(tài)定價問題一直是收益管理理論中的熱門問題。在實(shí)際行業(yè)應(yīng)用中，航空公司和連鎖酒店也會考慮如何對產(chǎn)品（聯(lián)程航班、酒店連續(xù)多天的訂單）定價來最大化收益。然而，需求的隨機(jī)性和產(chǎn)品組合的多樣性增加了問題的復(fù)雜性，需求的相互依賴和價格的連續(xù)性使得問題的分析和求解變得更加困難。

動態(tài)定價常用的模型為動態(tài)規(guī)劃模型，考慮到動態(tài)規(guī)劃模型的“維數(shù)災(zāi)難”，近似動態(tài)規(guī)劃方法將動態(tài)規(guī)劃中的價值函數(shù)使用函數(shù)近似，減少了變量的數(shù)量。然而，近似動態(tài)規(guī)劃中約束的數(shù)量仍然依賴于動態(tài)規(guī)劃中狀態(tài)空間和決策空間的規(guī)模。對于這類大規(guī)模線性規(guī)劃問題我們經(jīng)常使用行生成算法（列生成算法）求解，盡管這類算法收斂速度較慢?？紤]到近似動態(tài)規(guī)劃得到的動態(tài)投標(biāo)價格在大部分時間保持不變這一特性，我們改進(jìn)了行生成算法，并通過數(shù)值實(shí)驗(yàn)說明改進(jìn)的算法具有更快的收斂速度。我們相信本文中的分析方法可以應(yīng)用到其他需求函數(shù)下的動態(tài)定價問題之中。

對于動態(tài)定價問題，確定性模型一般可以直接求解，而使用行生成算法求解近似動態(tài)規(guī)劃仍然需要較大的計(jì)算工作量，在未來的工作中我們會接著分析近似動態(tài)規(guī)劃中的特點(diǎn)，降低求解近似動態(tài)規(guī)劃的難度。另一方面，實(shí)際生活中的定價問題會有更多的假設(shè)和約束，比如Nadarajah等人（2015）在酒店收益管理中設(shè)定住宿多天價格是單天價格的總和，我們也將在動態(tài)定價問題中考慮更多實(shí)際的設(shè)定。

參考文獻(xiàn)：

[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.