方 園，樂美龍

（南京航空航天大學(xué)民航學(xué)院，江蘇 南京 21100）

隨著航運市場的不斷擴大，各航空公司之間的競爭越來越激烈。 大部分航線會有多家航空公司同時運營，這些具有相同起訖點的航班稱為平行航班。價格成為影響其收益的主要因素。航空公司之間的競爭以及供求關(guān)系的變化導(dǎo)致航線產(chǎn)品的價值在不斷變化，不論是對航空公司還是旅客來說，進行動態(tài)定價十分必要。 現(xiàn)有機器學(xué)習(xí)和大數(shù)據(jù)技術(shù)的發(fā)展以及航空市場的寬松環(huán)境也為動態(tài)定價提供了有利的環(huán)境。

原有的較多收益管理都從艙位分配的角度進行研究[1-2]，還有將艙位控制和定價同時進行的[3]，現(xiàn)在逐漸轉(zhuǎn)向從價格的角度進行收益管理。 Gallego G 等[4]最早研究多產(chǎn)品下的動態(tài)定價問題，他們將單產(chǎn)品的研究拓展到多產(chǎn)品的動態(tài)定價中，采用強度控制的方法求解多產(chǎn)品的動態(tài)規(guī)劃問題，導(dǎo)出相應(yīng)的Hamilton-Jacobi-Bellman 方程得到漸進最優(yōu)解。Zhang D 等[5]用馬爾可夫決策過程對多個相同目的地之間的可替代航班進行動態(tài)定價。 通過上下限和啟發(fā)式的方法進行求解，并通過定期更新各時點的狀態(tài)來改變價格。 Akcay Y 等[6]建立了一種能捕捉縱向和橫向的產(chǎn)品異質(zhì)性的線性隨機效用框架， 并在此基礎(chǔ)上進行多產(chǎn)品聯(lián)合動態(tài)定價，采用微分方程進行求解。 Gallego G 等[7]采用連續(xù)時間上的隨機博弈，他們利用仿射函數(shù)逼近的方法求解微分博弈，并獲得漸近均衡解。 曹海娜[8]和朱志愚等[9]采用MNL（multinomial logit model）選擇模型對平行航班進行動態(tài)定價。 以上這些研究大多采用近似的方法對NP 問題進行求解，使得求解結(jié)果不夠準確。 目前有部分研究利用強化學(xué)習(xí)方法解決動態(tài)定價問題。 Han W 等[10]通過提前建立其他主體的決策模型并預(yù)測他們的價格來構(gòu)建自身的定價模型，使得問題從多主體決策轉(zhuǎn)變成單主體決策，并采用改進的Q 學(xué)習(xí)方法求解。王金田等［11］和陸慧[12]根據(jù)消費者的選擇行為是否易受折扣的影響，將其分為兩大類，采用強化學(xué)習(xí)對雙賣家市場進行動態(tài)定價，但對消費者選擇行為的考慮較為簡單。 Rana R 等[13-14]利用帶資格跡的強化學(xué)習(xí)方法分析高峰時刻和非高峰時刻的定價區(qū)別，并考慮多個具有關(guān)聯(lián)性產(chǎn)品的定價問題。 通過為其它關(guān)聯(lián)性產(chǎn)品對需求的影響設(shè)置參數(shù)，問題仍轉(zhuǎn)變?yōu)閱沃黧w的強化學(xué)習(xí)問題。文獻［15－17］研究智能電網(wǎng)的最優(yōu)動態(tài)定價問題。 通過顧客消費模型構(gòu)建定價的環(huán)境， 同時將動態(tài)零售定價問題轉(zhuǎn)化為有限離散馬爾可夫決策過程（MDP），并采用Q 學(xué)習(xí)求解最優(yōu)定價策略。本文將在以往研究的基礎(chǔ)上增加對旅客類型，以及需求在各時間段內(nèi)的異質(zhì)性的考慮，并將智能電網(wǎng)相關(guān)研究中所采用的單主體動態(tài)定價方法拓展至平行航班的多主體動態(tài)定價問題中。 相比于以往研究，得到的定價策略更加合理精確，且能有效地捕捉不同類型旅客的選擇行為，并有效提升航空公司收益。

1 系統(tǒng)模型

本系統(tǒng)中包含兩個重要的角色，分別是旅客和航空公司。 假設(shè)兩家航空公司各自運營的一個航班為平行航班，且出發(fā)時刻較為接近。兩個航班的旅客群體設(shè)為I。由于航線產(chǎn)品屬于易逝品，具有一定長度的銷售區(qū)間。 在以往的大部分研究中，通過對銷售區(qū)間進行細分，使得每個時間段至多只有一名旅客到達。 但這種細分方式導(dǎo)致狀態(tài)非常多，使得實際問題的求解時間大大增加。 另外，在航空公司的實際定價中，也不可能每銷售出去一個座位就重新定價，這會使得旅客產(chǎn)生負面情緒。 因此，本文考慮以天為單位，將銷售區(qū)間分為T 個時間段，每個時間段t 表示一天。通過機票可銷售價格的離散化，將其定義為價格集合A。集合的大小是確定且有限的。

在每個時間段t，兩家航空公司分別確定該航班的票價，旅客則根據(jù)剩余艙位數(shù)和當(dāng)前票價確定自身的購票需求。航空公司的目標是實現(xiàn)自身收益最大化。在銷售區(qū)間結(jié)束后，艙位沒有剩余價值。假設(shè)系統(tǒng)不考慮超售和團隊旅客，且兩個平行航班的初始艙位數(shù)和各個時間段內(nèi)的可選擇價格都已知。

1.1 旅客行為建模

旅客行為具有兩個重要特征，分別是到達率和估值。 假設(shè)旅客的到達率λ 服從泊松分布。 此外，還需考慮旅客在兩個競爭航班之間的選擇行為。 MNL 模型是一個隨機效用最大化模型，用來描述旅客在平行航班間的選擇。 假設(shè)每個旅客購買機票i 后獲得的產(chǎn)品效用為：Ui=ui+εi，其中ui=υi+ηfi。 因此，Ui=υi+ηfi+εi，i=1，2。υi表示航班i 的平均價值，η 表示價格反應(yīng)系數(shù)，fi為機票的定價，εi為隨機變量， 用來描述不能觀測到的效用隨機項。 假設(shè)εi服從二重指數(shù)分布且各變量兩兩相互獨立，將旅客放棄購買航班機票的效用定義為0，則每個旅客的購買概率為

旅客放棄購買任何一個航班機票的概率為

考慮到旅客的策略性行為，短視型旅客在到達的當(dāng)前時間段，會通過效用模型計算購買概率，若效用值小于0，則會放棄購買；若大于0，則選擇購買效用高的航線。 而策略型旅客不止看到當(dāng)期的效用，還會和未來預(yù)期的效用進行比較，這也就造成了計算的復(fù)雜性。 但旅客對于未來預(yù)期的收益并不能做到完全理性的判斷，只是一個自身的經(jīng)驗估計值。 本文利用歷史該階段售價的均值計算未來預(yù)期的效用。

1.2 航線產(chǎn)品定價方建模

單航班的動態(tài)定價問題通常采用馬爾可夫決策過程（MDP）建模。 將單個航空公司的動態(tài)定價問題拓展至平行航班的定價問題上，構(gòu)建多主體的隨機博弈Γ。 對一個具有兩個玩家和多個狀態(tài)的隨機博弈而言，可以看成是MDP 和矩陣博弈的組合，它是將MDP 拓展至兩個Agent 上，也是將矩陣博弈拓展多個狀態(tài)上。 隨機博弈同樣具有馬爾可夫性質(zhì)。

航線產(chǎn)品的定價方稱為Agent，分別用（i=1，2）表示。 兩個航班的座位總數(shù)分別用N1，N2表示。xit表示航班i 在時間段t 的剩余艙位數(shù)。隨機博弈可用元組表示為（S，A1，A2，r1，r2，p，γ）。S 表示狀態(tài)空間，用當(dāng)前時間段和兩個航班的剩余艙位數(shù)表示，st=（t，x1t，x2t）。 在每個時間段內(nèi)，有旅客到達并且購票，狀態(tài)會發(fā)生變化，時間段t 會減1，兩個航班的庫存水平的狀態(tài)也會根據(jù)當(dāng)前時間段售出的艙位數(shù)而發(fā)生變化。

式中：E（rit|π1，π2，s0=s）表示在初始狀態(tài)s，策略為π1，π2時，在t 時間段的期望收益值。 則Vi（s，a1，a2）為從0開始到結(jié)束的總收益。當(dāng)航班起飛后，不具有剩余價值。因此，最后的收斂條件為：Vi（（x，N，n），π1，π2）=0 或Vi（（x，n，N），π1，π2）=0；Vi（（0，x1，x2），π1，π2）=0。 銷售區(qū)間結(jié)束后，或者當(dāng)某個航班的艙位全部售出后的收益值為0。 當(dāng)滿足這兩個條件之一時，平行航班之間的競爭結(jié)束。

每個特定狀態(tài)的矩陣博弈稱為階段博弈（stage game）。 由于兩個航班屬于不同航空公司，具有競爭關(guān)系，在每個狀態(tài)下的階段博弈中尋找納什均衡策略以實現(xiàn)收益最大化。

定理1 在一個階段博弈中的納什均衡可以描述為n 個均衡策略的元組，使得Vi（（s，π1*，…，πi*，…，πN*）≥Vi（（s，π1*，…，πi，…，πN*）for all πi∈∏i。

用Vi*（s）表示納什均衡策略下的狀態(tài)值函數(shù)，Q*（s，a1，a2）表示在遵循納什均衡策略下的行動值函數(shù)，則

式中：πi*（s，a2）∈PD（Ai）是在玩家i 的納什均衡策略下在行動ai上的概率分布。T（s，a1，a2，s′）=p（sk+1=s′|sk=s，a1，a2）是在給定狀態(tài)和聯(lián)合行動后轉(zhuǎn)移至該狀態(tài)的概率。

由此，式（5）中的納什均衡可以重寫為

通過在每個階段博弈中求解納什均衡，以此作為在每個狀態(tài)下各Agent 能獲得的回報值，根據(jù)這個回報值進而學(xué)習(xí)最優(yōu)定價策略。

2 算法設(shè)計

通過對旅客和航空公司定價方分別建模，利用強化學(xué)習(xí)算法求解馬爾可夫博弈。 強化學(xué)習(xí)不需要知道環(huán)境的具體模型，只依賴獲得的獎勵學(xué)習(xí)最優(yōu)行動，它是多Agent 系統(tǒng)的自然選擇。 將旅客的選擇行為作為強化學(xué)習(xí)的環(huán)境，每個Agent 通過與環(huán)境交互學(xué)習(xí)最優(yōu)策略。 在單Agent 的強化學(xué)習(xí)環(huán)境中，環(huán)境是相對穩(wěn)定的。 而多Agent 系統(tǒng)中，環(huán)境中還包括其他Agent 的行動和狀態(tài)，即其他Agent 策略的改變也會影響自身最優(yōu)策略，因此環(huán)境是動態(tài)多變的，這對算法的收斂性會帶來影響。此外，在單主體的強化學(xué)習(xí)中，需要存儲動作狀態(tài)Q 值。 而多主體環(huán)境中，隨著主體的增加，狀態(tài)空間也增大，聯(lián)合動作空間呈指數(shù)型增長。 因此，多智能體系統(tǒng)的維度非常大，計算也變得更加復(fù)雜。 本文通過對時間段和剩余座位數(shù)都做了相應(yīng)的處理以減少狀態(tài)數(shù)。

2.1 環(huán)境設(shè)置

環(huán)境設(shè)置的目標是創(chuàng)建一個虛擬的旅客人群，用來模擬在競爭市場中對市場策略的反應(yīng)，作為強化學(xué)習(xí)的學(xué)習(xí)環(huán)境。 由于旅客自身的異質(zhì)性及其購票時的策略行為，將旅客分為4 種類型。 對每種類型的旅客，對其設(shè)置到達概率、策略程度和離散選擇模型的參數(shù)。 具體步驟如下：

1） 根據(jù)該時段內(nèi)各類型旅客的到達率模擬旅客的到達數(shù)；

2） 根據(jù)旅客的離散選擇模型和策略程度確定各類型旅客在該價格下的選擇概率，若概率大于0，則選擇購買概率高的航班；若概率小于0，則放棄購買。

2.2 Nash-Q 算法

在多主體環(huán)境中， 對Q 學(xué)習(xí)算法進行拓展， 將最優(yōu)Q 值定義為在Nash 均衡中收到的Q 值， 表示為Nash-Q 值。 計算納什均衡需要已知自身和對方的收益值和狀態(tài)值，因此需要維護多個Q 值表。 在每一次階段博弈中利用Lemke-Howson 算法計算納什均衡解：（Q1t（st+1，·），…，QMt（st+1，·）），從而計算出在各狀態(tài)下的各Agent 均衡收益值NashQti（s）。 用這個值對每個Agent 的Q 值進行更新。 Q 值的更新規(guī)則為

其中at是學(xué)習(xí)率，M 為Agent 的個數(shù)。 通過這些Q 值的迭代計算，最后收斂至一個穩(wěn)定值，從而獲得最優(yōu)定價策略。 據(jù)此，Nash-Q 算法的流程如下所示：

步驟一：初始化時間段t，初始狀態(tài)s0，對每個Agent 設(shè)置索引i；

步驟二：對所有的s∈S，以及ai∈Ai，初始化Qit（st，a1，…，aM）=0；

步驟三：與旅客環(huán)境進行交互，通過Lemke-Howson 算法獲得納什均衡解，確定所有玩家的行動ait后，從而計算收益值rt1，…，rtM并確定下一個狀態(tài)st+1=s′，對每個i，利用公式（7）更新Q 值；

步驟四：讓t=t+1，若t 為最終狀態(tài)對應(yīng)的時間段，則結(jié)束該循環(huán)；否則，返回至步驟三。

其中各個階段的狀態(tài)S，做出了相應(yīng)的簡化。狀態(tài)中xit，不用真實的剩余座位數(shù)來表示，而是將一個區(qū)間范圍內(nèi)的剩余座位數(shù)投射到一個值上以表示當(dāng)前剩余座位數(shù)的狀態(tài)。 這大大減少計算過程所需的存儲空間，也加快了求解速度。

2.3 WoLF-PHC 算法

策略梯度爬升（PHC，policy hill climbing）算法的本質(zhì)是在混合策略空間中表現(xiàn)出梯度爬升。 PHC 方法不需要知道玩家最近執(zhí)行行動的信息，以及對手當(dāng)前策略的信息，這可以減少算法所需的存儲空間并且符合實際的競爭環(huán)境。 非Agent 選擇最高值行動的概率會以學(xué)習(xí)率δ∈（0，1]增加，因此策略在不斷提升。PHC算法能保證在算法中學(xué)習(xí)的Agent 是理性的，即如果其他玩家的策略收斂至穩(wěn)定的策略時，那么自身的學(xué)習(xí)策略也會收斂至對其他玩家策略的最佳反應(yīng)策略。

WoLF-PHC 算法是PHC 算法的拓展[18]。 它的關(guān)鍵點為：①兩個學(xué)習(xí)率；②采用平均策略來近似均衡策略以確定輸贏。WoLF 準則用來修正學(xué)習(xí)率。算法有兩個不同的學(xué)習(xí)率：δw表示贏時的學(xué)習(xí)率，δl表示輸時的學(xué)習(xí)率，δl大于δw。 當(dāng)Agent 輸時，學(xué)習(xí)的要比贏的時候快，這使得當(dāng)Agent 學(xué)習(xí)得比期望糟糕時，能對其他Agent 策略的變化適應(yīng)得更快；當(dāng)學(xué)習(xí)得比期望好時，要學(xué)得更謹慎。 這也給其他Agent 足夠的時間來適應(yīng)策略的變化。 平均策略旨在取代未知的其他Agent 均衡策略，它和當(dāng)前策略的不同被用作確定算法贏輸?shù)臉藴?。在很多博弈中，平均貪婪策略在實際上是近似均衡策略的，這是均衡發(fā)揮作用的驅(qū)動機制。WoLF 準則使得PHC 算法在自身博弈中可以收斂至納什均衡解。 由此， 該算法在保留理性的基礎(chǔ)上增加了收斂的性質(zhì)，使其能收斂至其中的一個納什均衡解。 收斂性質(zhì)將從下文的幾個典型案例計算來開展。 Agent i 的Q 學(xué)習(xí)更新規(guī)則如下：

據(jù)此，設(shè)計WoLF-PHC 算法如下所示：

步驟二：對每一次迭代，

1） 在當(dāng)前狀態(tài)下基于一個混合探索-利用策略選擇行動ac，執(zhí)行行動后觀察收益ri以及下一個狀態(tài)s′；

C（s）=C（s）+1，

4） 更新πi（s，ai），πi（s，ai）＝πi（s，ai）+Δsai，?ai∈Ai，其中

步驟三：更新S＝S′，若S 為最終狀態(tài)，結(jié)束該循環(huán)；否則，返回至步驟二。

此算法的狀態(tài)S 所包含的剩余座位數(shù)變量的設(shè)置同Nash-Q 算法一致。

3 仿真分析

假設(shè)兩個航班的參數(shù)一致?？射N售的票價集為{10，15，20，25，30}，總座位數(shù)均為50。假設(shè)剩余銷售期為10 天，對其進行離散化處理，使得每天為一個時間段。 狀態(tài)包括兩個航班的剩余座位數(shù)以及當(dāng)前的時間段。其中，變量xit，將每5 個座位數(shù)為一個狀態(tài)，即將剩余艙位數(shù)除以5 取整作為當(dāng)前的剩余艙位數(shù)狀態(tài)。 對旅客仿真環(huán)境中的參數(shù)進行設(shè)置，建立仿真環(huán)境。 參數(shù)設(shè)置為：?=0.4，φs=0.6，φm=0.6，βLS=0.2，βHS=0.1，不同類型旅客設(shè)定不同的λ，υi，η。 Nash-Q 算法中的參數(shù)設(shè)置為：αi=0.1，γ=0.9。 WoLF-PHC 算法中的參數(shù)設(shè)置為：αi=0.1，γ=0.9，δ＝0.000 1。

通過案例計算，Nash-Q 算法在5 000 次左右收斂，WoLF-PHC 算法在100 000 次左右收斂，表明兩種算法在實際問題中都具有較好的收斂性。 Nash-Q 算法收斂所需的迭代次數(shù)要少于WoLF-PHC 算法，但WoLF-PHC 算法的收斂速度明顯優(yōu)于Nash-Q 算法。 這是符合實際情況的，因為Nash-Q 算法在每個階段中都會計算納什均衡解，而WoLF-PHC 算法只能利用平均策略來近似策略，這使得其需要更多的迭代后才能收斂。 而也正因為Nash-Q 算法需要在每一次階段博弈時計算納什均衡解，這會大大增加求解時間，且該算法需要已知自身和競爭對手雙方的Q 值，這對于存儲空間的要求也有所增加。因此，WoLF-PHC 算法不論是在求解時間還是耗費的存儲空間上都要優(yōu)于Nash-Q 算法。

表1 是航班在各個時間段的定價。 索引行為距離離港日期的時間，0 為停止售票的時間點。 Strategy 1為旅客的保留價格穩(wěn)定不變時的定價策略，Strategy 2 為航班在旅客保留價格隨時間而變時的定價策略，Strategy 3 和Strategy 4 考慮策略型旅客及保留價格變化的定價策略，且Strategy 4 的旅客策略程度的參數(shù)設(shè)置的要高于Strategy 3，由此可以看出策略程度對價格制定也會產(chǎn)生一定的影響，使得整體制定的價格都稍低一些。 從整體上看，由于航空旅客到達的特點，機票的價格曲線處于一個增長的趨勢。 但由于旅客保留價格的變化及其策略行為使得航空公司需要不斷的調(diào)整價格，這也就導(dǎo)致價格在增長的過程中會出現(xiàn)一些波動，這些波動能更好地適應(yīng)旅客行為的變化。將定價策略放到仿真環(huán)境中模擬，得到的收益相比于傳統(tǒng)方法提升約1.34%。

表1 航班定價策略Tab.1 The pricing strategy of flight tickets 元

4 結(jié)論

利用強化學(xué)習(xí)算法求解平行航班的動態(tài)定價問題，發(fā)現(xiàn)該算法對多主體的動態(tài)定價問題具有較好的適應(yīng)性，且能在有限步驟內(nèi)得到收斂，計算時間相比于傳統(tǒng)的近似計算方法較短且更加精確。 通過Nash-Q 算法和WoLF-PHC 算法的求解結(jié)果比較，發(fā)現(xiàn)WoLF-PHC 算法在求解時間上都優(yōu)于Nash-Q 算法，且Nash-Q 算法在維護Q 值表上耗費的空間較大。此外，WoLF-PHC 算法在不同的旅客環(huán)境中，定價策略也會發(fā)生相應(yīng)的變化，能較好地適應(yīng)旅客環(huán)境的變化。由于航空旅客到達策略與其他行業(yè)有所不同，高消費的旅客往往到出發(fā)前期才會購買機票，而低消費的旅客會早早的選擇進行購票，使得航空機票在整體上呈現(xiàn)出增長趨勢。 另外，由于旅客的策略性行為，以及保留價格分布的變化，這也使得航空機票在定價過程中會出現(xiàn)一些波動以適應(yīng)旅客的隨機行為。 WoLF-PHC 算法在平行航班的動態(tài)定價問題中的表現(xiàn)優(yōu)于Nash-Q 算法，且得到的定價策略能有效地增加航空公司收益，對航空公司在越來越劇烈的競爭市場中立于不敗之地具有重要作用。