盧 敏 張耀元 盧 春

①(中國民航大學計算機科學與技術(shù)學院 天津 300300)

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

1 引言

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

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

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

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

2 航班機票動態(tài)定價算法

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

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

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

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

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

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

3 實驗

3 .1 實驗設置

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

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

表1 機票動態(tài)定價策略學習算法

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

3.1.2 評價指標

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

3.1.3 基準算法

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

(2)票價等級需求量預測方法

表2 旅客訂票記錄示例

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

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

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

航班CA1501和JR1505經(jīng)濟艙總座位數(shù) N分別為255和52。算法需預先設置的參數(shù)分別為：學習速率 η =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。實 驗訓練共耗約142 h。

3.2 實驗對比及分析

3.2.1 航班 CA1501實驗結(jié)果

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

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

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

3.2.2 航班JR1505實驗結(jié)果

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

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

3.3 票價等級精度對收益的影響

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

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

3.4 學習速率的影響分析

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

表4 票價等級精確度影響分析

圖2 2011年6月22日航班CA1501在精度為0.0100和0.0001下的實驗對比

圖3 學習速率對算法性能的影響

4 結(jié)論

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