柯劍男
摘 要: 研究了MNL需求下網(wǎng)絡(luò)收益管理中的動(dòng)態(tài)定價(jià)問題。建立了動(dòng)態(tài)規(guī)劃模型并使用基于線性的近似動(dòng)態(tài)規(guī)劃方法來處理動(dòng)態(tài)規(guī)劃中的“維數(shù)災(zāi)難”問題。盡管如此,因?yàn)閯?dòng)態(tài)規(guī)劃問題的價(jià)格決策空間是連續(xù)的,得到的近似線性規(guī)劃(ALP)是一個(gè)半無限的線性規(guī)劃,故將使用行生成算法來求解近似線性規(guī)劃?;贏LP問題最優(yōu)解的特性,簡化了ALP規(guī)劃,改進(jìn)了行生成算法。數(shù)值實(shí)驗(yàn)顯示,改進(jìn)的行生成算法的收斂時(shí)間比原來的行生成算法快了近70%。
關(guān)鍵詞: 近似動(dòng)態(tài)規(guī)劃;半無窮線性規(guī)劃;行生成算法
中圖分類號(hào): 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)綜述
動(dòng)態(tài)定價(jià)問題一直是收益管理和交通工程領(lǐng)域的熱門問題,決策者(企業(yè))通過動(dòng)態(tài)調(diào)整價(jià)格來實(shí)現(xiàn)收益最大化。而在網(wǎng)絡(luò)收益管理中,不同的產(chǎn)品會(huì)競(jìng)爭(zhēng)同一種資源,“資源-產(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ò)收益管理中的動(dòng)態(tài)定價(jià)問題,并給出了兩種近似最優(yōu)策略。
對(duì)于網(wǎng)絡(luò)收益管理中的動(dòng)態(tài)定價(jià)問題,常見的分析方法是把問題建立成一個(gè)動(dòng)態(tài)規(guī)劃模型。然而,動(dòng)態(tài)規(guī)劃存在“維數(shù)災(zāi)難”問題,求解復(fù)雜度隨著維數(shù)的增加呈指數(shù)級(jí)增長。Adelman (2007)針對(duì)網(wǎng)絡(luò)收益管理中的容量控制(capacity control)問題提出了近似動(dòng)態(tài)規(guī)劃方法研究框架,首先把動(dòng)態(tài)規(guī)劃轉(zhuǎn)化為等價(jià)的線性規(guī)劃,然后對(duì)線性規(guī)劃中的價(jià)值函數(shù)使用函數(shù)比如線性函數(shù)(affine approximation)、分段線性函數(shù)(piecewise linear approximation))近似,將線性規(guī)劃轉(zhuǎn)化成近似線性規(guī)劃(approximate linear program, ALP),最后對(duì)ALP求解得到近似函數(shù)中的參數(shù)和ALP問題的最優(yōu)值。如果使用的近似函數(shù)是線性函數(shù),函數(shù)中資源的系數(shù)被理解成動(dòng)態(tài)投標(biāo)價(jià)格(bid price)。ALP問題的最優(yōu)值是動(dòng)態(tài)投標(biāo)價(jià)格策略的上界。投標(biāo)價(jià)格策略來源于Talluri (1998),即如果產(chǎn)品的價(jià)格大于該產(chǎn)品組成資源的價(jià)值(由投標(biāo)價(jià)格衡量),那么接受顧客的購買請(qǐng)求。在對(duì)應(yīng)的確定性模型(deterministic program)中,資源約束的對(duì)偶變量的值被當(dāng)成靜態(tài)投標(biāo)價(jià)格,在已有的文獻(xiàn)比較中,基于動(dòng)態(tài)投標(biāo)價(jià)格的策略比基于靜態(tài)投標(biāo)價(jià)格的策略表現(xiàn)要好。然而在ALP問題中,約束對(duì)于所有的狀態(tài)和決策都需要被滿足,因此約束數(shù)量非常多。因此,除了約束抽樣(constraint sampling algorithm)方法外(de Farias、Van Roy, 2004),行生成/列生成方法(constraint/column generation algorithm)成為求解ALP一個(gè)常用的方法(Zhang、Adelman,2009;Zhang,2011)。在本文中,我們將主要使用行生成算法求解動(dòng)態(tài)定價(jià)問題下的ALP問題。
然而在動(dòng)態(tài)定價(jià)問題中,約束有無限多個(gè),列生成方法需要很長的時(shí)間求解。對(duì)于容量控制問題,在獨(dú)立需求情形下,Tong和Topaloglu (2013)、Vossen和Zhang (2015) 都縮小了ALP的規(guī)模,但是在非獨(dú)立需求下,Vossen和Zhang (2015)得到的簡化ALP約束數(shù)量仍然隨著資源呈指數(shù)增長。對(duì)于動(dòng)態(tài)定價(jià)問題,Ke等人(2019)在線性獨(dú)立需求下成功地將ALP轉(zhuǎn)化成二次錐規(guī)劃(second order cone program, SOCP),得到的SOCP規(guī)模僅線性依賴于資源數(shù)量、產(chǎn)品數(shù)量、周期,但是該轉(zhuǎn)化方法無法應(yīng)用于非獨(dú)立需求情形下。因此,在動(dòng)態(tài)定價(jià)問題中,列生成算法仍然是一種主要的求解方法。
我們的動(dòng)態(tài)規(guī)劃問題考慮了非獨(dú)立需求中的MNL選擇模型,即顧客選擇某一個(gè)產(chǎn)品的概率依賴于其他產(chǎn)品帶來的效用,而效用是價(jià)格的函數(shù)(Wang,2012)。自從McFadden提出MNL模型以來,該模型就被廣泛應(yīng)用在經(jīng)濟(jì)、營銷和運(yùn)營管理中。Liu和van Ryzin (2008)、Zhang和Adelman (2009)在容量控制問題中考慮了選擇需求函數(shù),并基于動(dòng)態(tài)投標(biāo)價(jià)格設(shè)計(jì)了控制策略,Zhang和Lu (2013) 在動(dòng)態(tài)定價(jià)問題中考慮了選擇需求函數(shù),但是他們使用增廣拉格朗日乘子法(augmented Lagrangian algorithms)求解確定性模型,并基于靜態(tài)投標(biāo)價(jià)格設(shè)計(jì)了定價(jià)策略。給定資源狀態(tài),行生成子問題可以被看作只有一個(gè)周期的確定性問題。我們把行生成子問題轉(zhuǎn)化為一個(gè)凸規(guī)劃問題并使用CVX求解。
在動(dòng)態(tài)定價(jià)問題下的近似動(dòng)態(tài)規(guī)劃,因?yàn)殡x散的狀態(tài)變量和連續(xù)的價(jià)格決策變量,列生成算法的主要難點(diǎn)在于列生成子問題是非線性整數(shù)規(guī)劃。因此,對(duì)于每個(gè)周期,我們必須窮舉所有可能的資源狀態(tài),然后在每個(gè)狀態(tài)下求解行生成子問題。Adelman (2007)觀察到動(dòng)態(tài)投標(biāo)價(jià)格具有長時(shí)間保持不變的性質(zhì),Vossen和Zhang (2012)利用動(dòng)態(tài)投標(biāo)價(jià)格的這種趨勢(shì)為簡化的ALP設(shè)計(jì)出了更快的求解辦法。在本文中,我們也將應(yīng)用這種性質(zhì)改進(jìn)行生成算法。
在ALP中,對(duì)于連續(xù)個(gè)周期投標(biāo)價(jià)格不變的約束,資源狀態(tài)變量的影響將會(huì)被消除,列生成子問題將會(huì)轉(zhuǎn)化為非線性規(guī)劃,而不是非線性整數(shù)規(guī)劃。通過對(duì)偶分析,我們把ALP簡化為對(duì)數(shù)線性規(guī)劃?;谶@個(gè)簡化的數(shù)學(xué)規(guī)劃,我們針對(duì)網(wǎng)絡(luò)收益管理中的動(dòng)態(tài)定價(jià)問題提出了一種改進(jìn)的列生成算法。因?yàn)樵诤喕腁LP中,一些周期的約束不再是無限數(shù)量,改進(jìn)列生成算法比列生成算法收斂速度更快,計(jì)算時(shí)間更短。第4部分的數(shù)值實(shí)驗(yàn)驗(yàn)證了這點(diǎn)。
2 動(dòng)態(tài)定價(jià)問題
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個(gè)Hub結(jié)點(diǎn)、4個(gè)非Hub結(jié)點(diǎn)(如圖2所示),那么資源有4種,產(chǎn)品有8種。交通工程領(lǐng)域中的網(wǎng)絡(luò)有6種資源和35種產(chǎn)品。考慮周期為{50,100,200,400},對(duì)應(yīng)的每個(gè)資源初始庫存為{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)行生成算法中,對(duì)于所有的算例設(shè)置=45T。
我們?cè)谘b有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)在動(dòng)態(tài)定價(jià)問題中動(dòng)態(tài)投標(biāo)價(jià)格V長時(shí)間保持不變的特性是否仍然成立,我們首先在圖3中給出了兩種網(wǎng)絡(luò)結(jié)構(gòu)下從行生成算法中得到的動(dòng)態(tài)投標(biāo)價(jià)格V的變化趨勢(shì)。
從圖3我們發(fā)現(xiàn),在50個(gè)周期的問題中,動(dòng)態(tài)投標(biāo)價(jià)格V至少在前35個(gè)周期保持不變。這樣一來,可以使用改進(jìn)的行生成算法。行生成算法和改進(jìn)的行生成算法表現(xiàn)如表1所示。表1中的第一行表示問題的周期,可以發(fā)現(xiàn)隨著周期越來越長,兩種算法的計(jì)算時(shí)間呈線性增長。第一列表示算法的求解精確度。毫不意外的是,對(duì)于兩種算法來說,精確度=0.1%所需要的求解時(shí)間比精確度=1%所需要的求解時(shí)間更長。
表1中的第一部分和第二部分分別是Hub-spoke網(wǎng)絡(luò)和交通工程網(wǎng)絡(luò)下的計(jì)算結(jié)果。顯然,交通工程網(wǎng)絡(luò)規(guī)模更大,所需要的求解時(shí)間也更長。對(duì)于所有的算例,與行生成算法相比,改進(jìn)的行生成算法用更快的時(shí)間給出了基本一樣的最優(yōu)值。在求解精確度下,平均來看,改進(jìn)的行生成算法節(jié)省了70%的時(shí)間。
在計(jì)算表現(xiàn)上起著至關(guān)重要的作用。越大,每次循環(huán)生成的行越少,求解時(shí)間越短。但是當(dāng)?shù)闹党^min{τi,i}時(shí),它會(huì)傳遞出錯(cuò)誤的信息V,i=V+1,i,得到的也是劣質(zhì)的解。圖4中展示了Hub-spoke網(wǎng)絡(luò)中100周期、求解精確度=0.1%下計(jì)算時(shí)間和最優(yōu)值的變化。從圖4中可以發(fā)現(xiàn),當(dāng)從52增長到98時(shí),計(jì)算時(shí)間會(huì)從1007.05減少到47.70,最優(yōu)值會(huì)在=84之后變得不可靠。
5 結(jié)語
網(wǎng)絡(luò)收益管理中的動(dòng)態(tài)定價(jià)問題一直是收益管理理論中的熱門問題。在實(shí)際行業(yè)應(yīng)用中,航空公司和連鎖酒店也會(huì)考慮如何對(duì)產(chǎn)品(聯(lián)程航班、酒店連續(xù)多天的訂單)定價(jià)來最大化收益。然而,需求的隨機(jī)性和產(chǎn)品組合的多樣性增加了問題的復(fù)雜性,需求的相互依賴和價(jià)格的連續(xù)性使得問題的分析和求解變得更加困難。
動(dòng)態(tài)定價(jià)常用的模型為動(dòng)態(tài)規(guī)劃模型,考慮到動(dòng)態(tài)規(guī)劃模型的“維數(shù)災(zāi)難”,近似動(dòng)態(tài)規(guī)劃方法將動(dòng)態(tài)規(guī)劃中的價(jià)值函數(shù)使用函數(shù)近似,減少了變量的數(shù)量。然而,近似動(dòng)態(tài)規(guī)劃中約束的數(shù)量仍然依賴于動(dòng)態(tài)規(guī)劃中狀態(tài)空間和決策空間的規(guī)模。對(duì)于這類大規(guī)模線性規(guī)劃問題我們經(jīng)常使用行生成算法(列生成算法)求解,盡管這類算法收斂速度較慢??紤]到近似動(dòng)態(tài)規(guī)劃得到的動(dòng)態(tài)投標(biāo)價(jià)格在大部分時(shí)間保持不變這一特性,我們改進(jìn)了行生成算法,并通過數(shù)值實(shí)驗(yàn)說明改進(jìn)的算法具有更快的收斂速度。我們相信本文中的分析方法可以應(yīng)用到其他需求函數(shù)下的動(dòng)態(tài)定價(jià)問題之中。
對(duì)于動(dòng)態(tài)定價(jià)問題,確定性模型一般可以直接求解,而使用行生成算法求解近似動(dòng)態(tài)規(guī)劃仍然需要較大的計(jì)算工作量,在未來的工作中我們會(huì)接著分析近似動(dòng)態(tài)規(guī)劃中的特點(diǎn),降低求解近似動(dòng)態(tài)規(guī)劃的難度。另一方面,實(shí)際生活中的定價(jià)問題會(huì)有更多的假設(shè)和約束,比如Nadarajah等人(2015)在酒店收益管理中設(shè)定住宿多天價(jià)格是單天價(jià)格的總和,我們也將在動(dòng)態(tài)定價(jià)問題中考慮更多實(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.