基于策略學習的機票動態定價算法

盧 敏 張耀元 盧 春

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

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

1 引言

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

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

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

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

2 航班機票動態定價算法

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

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

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

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

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

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

3 實驗

3 .1 實驗設置

3.1.1 數據集

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

表1 機票動態定價策略學習算法

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

3.1.2 評價指標

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

3.1.3 基準算法

(1)航班現行定價策略

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

表2 旅客訂票記錄示例

表3 實驗數據集的統計信息

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

3.1.4 參數設置和運行環境

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

3.2 實驗對比及分析

3.2.1 航班 CA1501實驗結果

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

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

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

3.2.2 航班JR1505實驗結果

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

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

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

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

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

3.4 學習速率的影響分析

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

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

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

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

4 結論

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