基于策略學(xué)習(xí)的機(jī)票動(dòng)態(tài)定價(jià)算法

盧 敏 張耀元 盧 春

①(中國(guó)民航大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 天津 300300)

②(中國(guó)南方航空股份有限公司信息中心 廣州 510000)

1 引言

航空公司采用收益管理技術(shù)提升了2%至8%的票務(wù)年收入[1]。機(jī)票動(dòng)態(tài)定價(jià)是收益管理的核心，旨在構(gòu)建航班機(jī)票售價(jià)策略，將不同票價(jià)等級(jí)的機(jī)票適時(shí)地銷(xiāo)售給不同的消費(fèi)者，以實(shí)現(xiàn)收益最大化。

Gallego等人[2]使用強(qiáng)度控制理論求解了不確定需求下預(yù)期收入的上限。Otero等人[3]采用階段類(lèi)型分布和更新過(guò)程建?？蛻?hù)購(gòu)買(mǎi)機(jī)票的時(shí)間及購(gòu)買(mǎi)概率。Delahaye等人[4]通過(guò)細(xì)分商務(wù)和休閑旅客的不同價(jià)格敏感度進(jìn)行動(dòng)態(tài)定價(jià)。高金敏等人[5]研究了時(shí)變需求下動(dòng)態(tài)定價(jià)模型。Selcuk等人[6]針對(duì)4種不同的價(jià)格需求關(guān)系提出了精確的動(dòng)態(tài)規(guī)劃方法。除了上述面向壟斷市場(chǎng)環(huán)境的定價(jià)研究[1-6]，還有從競(jìng)爭(zhēng)角度出發(fā)的定價(jià)研究[7,8]。Lin等人[7]構(gòu)建了基于博弈論的實(shí)時(shí)價(jià)格預(yù)測(cè)模型。施飛等人[8]通過(guò)航空公司與旅客的動(dòng)態(tài)博弈解決各等級(jí)票價(jià)的售票時(shí)間。

現(xiàn)有機(jī)票動(dòng)態(tài)定價(jià)方法都建立在提前預(yù)測(cè)各票價(jià)等級(jí)的需求量基礎(chǔ)之上。然而，實(shí)際應(yīng)用中各等級(jí)票價(jià)的需求量受節(jié)假日、季節(jié)、售票時(shí)機(jī)等諸多因素影響?；跉v史銷(xiāo)售數(shù)據(jù)進(jìn)行函數(shù)擬合的需求量預(yù)測(cè)方法存在預(yù)測(cè)偏差，降低了建立在需求量預(yù)測(cè)方法之上的模型性能。為此，本文提出基于策略學(xué)習(xí)的機(jī)票動(dòng)態(tài)定價(jià)算法。其核心是不再直接預(yù)測(cè)各票價(jià)等級(jí)的需求量，而是從歷史購(gòu)票數(shù)據(jù)上學(xué)習(xí)具有最大期望收益的機(jī)票定價(jià)策略。在兩趟航班兩年歷史銷(xiāo)售數(shù)據(jù)上的多組模擬定價(jià)結(jié)果表明：相比于現(xiàn)行定價(jià)策略，策略學(xué)習(xí)算法的票務(wù)收益平均提升率分別為30.94%和39.96%，且比需求量預(yù)測(cè)方法提升了6.04%和3.36%。

目前存在將強(qiáng)化學(xué)習(xí)應(yīng)用于收益管理領(lǐng)域的研究，如電動(dòng)汽車(chē)[9]、廣告競(jìng)價(jià)[10]、可再生能源管理[11]、機(jī)票超售及座位控制[12-15]。Gosavii等人[12]提出了面向超售和多等級(jí)票價(jià)的半馬爾可夫決策模型。Shihab等人[13]采用深度強(qiáng)化學(xué)習(xí)優(yōu)化航班座位控制策略。Qiu等人[14]建模了旅客行為驅(qū)動(dòng)的航班定價(jià)。Lawhead等人[15]提出一種航班座位收益有界的動(dòng)作評(píng)論算法。不同于上述工作，本文聚焦于采用離線強(qiáng)化學(xué)習(xí)求解機(jī)票動(dòng)態(tài)定價(jià)策略。

2 航班機(jī)票動(dòng)態(tài)定價(jià)算法

在機(jī)票銷(xiāo)售期內(nèi)以某票價(jià)等級(jí)出售機(jī)票，售票系統(tǒng)會(huì)得到立即收益，即座位銷(xiāo)售數(shù)×票價(jià)等級(jí)×機(jī)票全價(jià)，同時(shí)減少航班剩余座位數(shù)。為了最大化后期座位收益，航班剩余座位數(shù)又影響下一時(shí)刻的機(jī)票定價(jià)。為此，機(jī)票動(dòng)態(tài)定價(jià)受航班剩余座位數(shù)、定價(jià)策略和收益等相互影響，可建模為強(qiáng)化學(xué)習(xí)問(wèn)題。

航班機(jī)票動(dòng)態(tài)定價(jià)的強(qiáng)化學(xué)習(xí)要素分別為：(1)狀態(tài)集 S 表示航班剩余座位數(shù)。設(shè)n 為某航班座位容量，航班在時(shí)刻t 的狀態(tài)(剩余座位數(shù))st∈S ={n,n-1,···,0} 。 (2)動(dòng)作集 A表示所有的票價(jià)等級(jí)，本質(zhì)為經(jīng)濟(jì)艙全票價(jià)的折扣率。航班在時(shí)刻 t采用的動(dòng)作(票價(jià)等級(jí))為 αt∈A 。(3)策略函數(shù)π (α|s)表示在狀態(tài)s 下執(zhí)行動(dòng)作α 的概率。策略函數(shù)是算法的學(xué)習(xí)目標(biāo)，使得算法根據(jù)它產(chǎn)生動(dòng)作序列。(4)收益函數(shù) r(s,α) 表示在狀態(tài)s 下執(zhí)行動(dòng)作α 的立即收益，取值為p ×α×N ，其中p ,N分別為經(jīng)濟(jì)艙全價(jià)和銷(xiāo)售的座位數(shù)。

引入動(dòng)作值函數(shù) qπ(s,α) 以 評(píng)估策略函數(shù)π(α|s)的好壞程度，見(jiàn)式(1)。式(1)的物理含義是給定狀態(tài)s 沿著策略π 執(zhí)行序貫性決策后預(yù)期總折扣獎(jiǎng)勵(lì)。

其中，P r(st+1|st=s,at=a)表 示在狀態(tài)st下執(zhí)行動(dòng)作 at后 跳轉(zhuǎn)到狀態(tài)st+1的概率。由于機(jī)票銷(xiāo)售過(guò)程無(wú)法建模上述轉(zhuǎn)移概率而僅可觀察剩余座位數(shù)st+1，采用時(shí)序差分法[16]更新動(dòng)作值函數(shù)。

其中， η表示學(xué)習(xí)速率。當(dāng)動(dòng)作值函數(shù)通過(guò)更新達(dá)到收斂后，每個(gè)狀態(tài)s 在最優(yōu)策略π?的 動(dòng)作π?(s)為

由于航班動(dòng)態(tài)定價(jià)的狀態(tài)空間和動(dòng)作空間都離散且有限，提出基于策略學(xué)習(xí)的機(jī)票動(dòng)態(tài)定價(jià)算法，見(jiàn)表1。算法首先初始化一個(gè)2維矩陣Q-table以表示動(dòng)作值函數(shù) q (s,α)，其中矩陣的行數(shù)為狀態(tài)空間數(shù)| S|， 列數(shù)是動(dòng)作空間數(shù)| A|。其次，在航班的第1天到 T -1天的歷史銷(xiāo)售序列上依次據(jù)式(3)和式(4)進(jìn)行策略 π的評(píng)估和改進(jìn)。重復(fù)上述循環(huán)操作 ，直至算法達(dá)到預(yù)先設(shè)定的最大迭代次數(shù)。

3 實(shí)驗(yàn)

3 .1 實(shí)驗(yàn)設(shè)置

3.1.1 數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集是航班歷史機(jī)票銷(xiāo)售序列，是由2010年1月1日到2011年12月31日的民航旅客訂票日志PNR (Passenger Name Record)生成的。一條PNR是一次訂票信息，主要字段包括旅客身份證號(hào)碼(信息加密)、航空公司、航班號(hào)、出發(fā)機(jī)場(chǎng)和到達(dá)機(jī)場(chǎng)(機(jī)場(chǎng)三字碼表示)、訂單編號(hào)、票價(jià)等級(jí)等，示例見(jiàn)表2。

表1 機(jī)票動(dòng)態(tài)定價(jià)策略學(xué)習(xí)算法

折中于算法在民航旅客訂票日志上所有航班的運(yùn)行時(shí)間，以及評(píng)價(jià)航班每一天動(dòng)態(tài)定價(jià)策略，挑選在航線熱度、經(jīng)濟(jì)艙總數(shù)、實(shí)際銷(xiāo)售等方面差異較大的兩個(gè)航班CA1501和JR1505進(jìn)行實(shí)驗(yàn)，其統(tǒng)計(jì)信息見(jiàn)表3。民航旅客訂票日志中票價(jià)等級(jí)的精度為0.0001，且各票價(jià)等級(jí)銷(xiāo)售的機(jī)票數(shù)比較稀疏。意味著很多二元組(剩余座位數(shù)，票價(jià)等級(jí))未在歷史數(shù)據(jù)中出現(xiàn)，使得這些元組對(duì)應(yīng)的動(dòng)作值函數(shù)無(wú)法更新，導(dǎo)致后期動(dòng)態(tài)定價(jià)存在較大的偏差。比如航班CA1501歷史銷(xiāo)售軌跡中產(chǎn)生了5737種票價(jià)等級(jí)，而各票價(jià)等級(jí)產(chǎn)生平均機(jī)票數(shù)為22.68，這表明動(dòng)作值函數(shù)矩陣Q-table中某一列平均至少有255-22.68個(gè)元素未被更新，累計(jì)有5737×(255-22.68)個(gè)元素未更新，其中255是航班CA1501的總座位數(shù)。精確度為千分位也會(huì)產(chǎn)生類(lèi)似的結(jié)論。為此，實(shí)驗(yàn)中將票價(jià)等級(jí)精度降至百分位，并在實(shí)驗(yàn)中分析萬(wàn)分位精度對(duì)航班座位收益的影響。

3.1.2 評(píng)價(jià)指標(biāo)

為評(píng)價(jià)航班動(dòng)態(tài)定價(jià)策略好壞程度，定義航班收益平均提升率ALR@T(Average Lift Rate at T days)：

3.1.3 基準(zhǔn)算法

(1)航班現(xiàn)行定價(jià)策略

(2)票價(jià)等級(jí)需求量預(yù)測(cè)方法

表2 旅客訂票記錄示例

表3 實(shí)驗(yàn)數(shù)據(jù)集的統(tǒng)計(jì)信息

其中，| S|為 航班總座位數(shù)。依式(8)計(jì)算m 個(gè)周期的收益差，需求量預(yù)測(cè)方法和策略 π 在第n 天航班收益差為

3.1.4 參數(shù)設(shè)置和運(yùn)行環(huán)境

航班CA1501和JR1505經(jīng)濟(jì)艙總座位數(shù) N分別為255和52。算法需預(yù)先設(shè)置的參數(shù)分別為：學(xué)習(xí)速率 η =0.2,0.4,0.6,0.8 、折 扣 因 子γ =1、算 法 總迭代次數(shù)e pisodes=5000。算法硬件環(huán)境為Intel(R)Xeon(R) Silver 4110、主頻3.4 GHz、內(nèi)存126 GB。實(shí) 驗(yàn)訓(xùn)練共耗約142 h。

3.2 實(shí)驗(yàn)對(duì)比及分析

3.2.1 航班 CA1501實(shí)驗(yàn)結(jié)果

在航班CA1501進(jìn)行了717組實(shí)驗(yàn)，其結(jié)果見(jiàn)圖1(a)。相比于現(xiàn)行定價(jià)策略，動(dòng)態(tài)定價(jià)策略 π的收益平均提升率A LR@T為30.94%；相比票價(jià)等級(jí)需求量預(yù)測(cè)方法，平均提升率為6.04%。

圖1(a)中動(dòng)態(tài)定價(jià)策略 π相比于現(xiàn)行定價(jià)策略的提升率曲線-策略πvs現(xiàn)行定價(jià)策略-可分為4段。在2010年1月2日到2010年2月10日，1月1日至1月3日票務(wù)收益較差，使得學(xué)習(xí)后的策略收益也低。1月4日收益較1月3日增長(zhǎng)了115%，算法能快速學(xué)習(xí)此定價(jià)策略以用于后續(xù)定價(jià)。故此階段內(nèi)曲線出現(xiàn)驟增，平均提升率 ALR@T穩(wěn)定至約35%。在2010年2月11日到2010年2月19日曲線出現(xiàn)第2次驟增，其原因是：2010年2月11日為農(nóng)歷臘月二十八，出現(xiàn)“倒春運(yùn)”，即機(jī)票銷(xiāo)售數(shù)和價(jià)格都明顯下跌，期間平均收益僅為整體的32.29%。然而，定價(jià)策略π 是從2月11日之前銷(xiāo)售數(shù)據(jù)上學(xué)習(xí)，導(dǎo)致策略 π的機(jī)票價(jià)格要高于“倒春運(yùn)”期間價(jià)格，出現(xiàn)較大收益差值。第3段為2010年2月11日到2011年1月30日，曲線逐漸降低并趨于平穩(wěn)，收斂至約21%。其原因是：在大量歷史數(shù)據(jù)上的學(xué)習(xí)，動(dòng)態(tài)定價(jià)策略與現(xiàn)行定價(jià)策略的收益差值逐漸減小。最后一次曲線提升發(fā)生在2011年2月1日，其原因是：2011年2月1日為農(nóng)歷臘月二十九，也出現(xiàn)“倒春運(yùn)”，因在大量歷史數(shù)據(jù)上的學(xué)習(xí)避免了類(lèi)似第1次突變，趨于平穩(wěn)。

圖1(a)也列出了定價(jià)策略 π相比于需求量預(yù)測(cè)方法的提升率曲線-策略 πvs需求量預(yù)測(cè)方法。實(shí)驗(yàn)初期因訓(xùn)練數(shù)據(jù)較少，動(dòng)態(tài)定價(jià)策略產(chǎn)生的收益低于需求量預(yù)測(cè)方法。隨著訓(xùn)練數(shù)據(jù)的增加，策略學(xué)習(xí)方法與需求量預(yù)測(cè)方法的收益差距逐漸減小，曲線平穩(wěn)提升并趨于穩(wěn)定，最終收益平均提升率 為6.04%。

3.2.2 航班JR1505實(shí)驗(yàn)結(jié)果

相比于航班CA1501，航班JR1505收益更易受定價(jià)影響。航班JR1505上的610組實(shí)驗(yàn)結(jié)果見(jiàn)圖1(b)。動(dòng)態(tài)定價(jià)策略 π相比于現(xiàn)行定價(jià)策略和需求量預(yù)測(cè)方法的收益平均提升率 ALR@T分別為39.96%和3.36%。

從圖1(b)可知，動(dòng)態(tài)定價(jià)策略 π相比于現(xiàn)行定價(jià)策略的提升率曲線-策略 πvs現(xiàn)行定價(jià)策略，主要可分為3段。2010年1月26日到2010年11月10日為第1個(gè)增長(zhǎng)期。定價(jià)策略 π通過(guò)不斷學(xué)習(xí)以往經(jīng)驗(yàn)，平均提升率A LR@T逐漸提升，在4月20日趨于平穩(wěn)，收斂至25%。第2個(gè)增長(zhǎng)周期發(fā)生在2010年11月2日，其原因是：航班JR1505在此后一個(gè)月機(jī)票銷(xiāo)售收益較前一月平均降低了43.80%，使得收益差值增加，曲線逐漸上升。第3個(gè)拐點(diǎn)發(fā)生在2011年4月20日，其原因是：航班由淡季轉(zhuǎn)為旺季，此后一月較上月收益提升41.22%。實(shí)際收益的提升使得差值逐漸減小，曲線回落并重新收斂至39%。此外，相比于需求量預(yù)測(cè)方法，策略學(xué)習(xí)方法隨著不斷學(xué)習(xí)，平均提升率 A LR@T平穩(wěn)提升并趨 于穩(wěn)定，最終收斂至約3%。

3.3 票價(jià)等級(jí)精度對(duì)收益的影響

表4表明不同的票價(jià)等級(jí)精度產(chǎn)生不同規(guī)模的票價(jià)等級(jí)，為此分析票價(jià)等級(jí)精度對(duì)算法性能的影響。表4列出2011年6月22日航班CA1501在票價(jià)等級(jí)精度為0.0001和0.0100的實(shí)驗(yàn)結(jié)果。萬(wàn)分位精度產(chǎn)生了4590個(gè)動(dòng)作，而百分位精度縮減至120個(gè)動(dòng)作。百分位精度較萬(wàn)分位在平均提升率 A LR@T上提升3.17%。

分析算法在精度為0.0100時(shí)性能提升的原因。圖2(a)列出票價(jià)等級(jí)精度分別為0.0100和0.0001時(shí)定價(jià)策略 π在各狀態(tài)上的票價(jià)等級(jí)差值。統(tǒng)計(jì)表明，不同精度下的模型在所有狀態(tài)上采取的票價(jià)等級(jí)總體相差不大，票價(jià)等級(jí)差的均值為0.05，方差為0.006。仍有部分點(diǎn)波動(dòng)較大，造成收益差距。圖2(b)以波動(dòng)點(diǎn)-剩余座位數(shù)196為例分析。當(dāng)精度為0.0001時(shí)，采取的票價(jià)等級(jí)為0.8453，落在區(qū)間(0.84,0.85]頻數(shù)為8。當(dāng)精度為0.0100時(shí)，采取的票價(jià)等級(jí)為1.04，落在區(qū)間(1.03,1.04]頻數(shù)為65。為此，精度為0.0100更易捕捉具有明顯集中趨勢(shì)的“眾數(shù)”票價(jià)等級(jí)，以代表此狀態(tài)下整體票價(jià)水平 ，而非選擇出現(xiàn)頻次最高的單一票價(jià)等級(jí)。

3.4 學(xué)習(xí)速率的影響分析

學(xué)習(xí)速率η 影響著算法的收斂速度和定價(jià)策略的收益，以2011年12月31日航班CA1501為例分析學(xué)習(xí)速率的影響。圖3(a)指出學(xué)習(xí)速率為0.2, 0.4,0.6, 0.8時(shí)，算法收斂的迭代次數(shù)依次為4860, 2167,1274, 788。因此，經(jīng)驗(yàn)上學(xué)習(xí)速率在0.2以上就能保證算法收斂。圖3(b)指出算法在5000次迭代時(shí)，增大學(xué)習(xí)率不會(huì)對(duì)收益平均提升率 A LR@T產(chǎn)生影響，其中計(jì)算 A LR@T的基準(zhǔn)算法為航班現(xiàn)行定價(jià)策略。

表4 票價(jià)等級(jí)精確度影響分析

圖2 2011年6月22日航班CA1501在精度為0.0100和0.0001下的實(shí)驗(yàn)對(duì)比

圖3 學(xué)習(xí)速率對(duì)算法性能的影響

4 結(jié)論

針對(duì)航班票價(jià)定價(jià)過(guò)程中航班剩余座位數(shù)與機(jī)票價(jià)格相互影響，提出了基于策略學(xué)習(xí)的機(jī)票動(dòng)態(tài)定價(jià)算法。算法通過(guò)定價(jià)策略評(píng)估和策略更新，輸出具有最大期望收益的機(jī)票動(dòng)態(tài)定價(jià)策略。在海量民航旅客訂票日志上兩個(gè)航班的多組模擬定價(jià)結(jié)果表明：相比于現(xiàn)行機(jī)票銷(xiāo)售策略和需求量預(yù)測(cè)方法，算法在收益平均提升率上有顯著的提升。后續(xù)將對(duì)航班狀態(tài)的時(shí)序特征展開(kāi)研究。