航班超售與艙位控制綜合優(yōu)化

樂美龍，張健澤

(上海海事大學(xué)a.科學(xué)研究院;b.物流研究中心，上海201306)

0 引言

航空收益管理是航空公司進(jìn)行定量化管理提高收益的重要手段，多年來國外已經(jīng)有了許多深入的研究［1－2］，其主要包括超售、艙位控制、動(dòng)態(tài)定價(jià)等方面。超售指可預(yù)訂座位量超過飛機(jī)的實(shí)際容量，用于控制航班空位現(xiàn)象的發(fā)生。國外對于超售的研究較早，1985 年，文獻(xiàn)［3］提出了一個(gè)單票價(jià)靜態(tài)超售模型，考慮空位與拒載成本之間的平衡關(guān)系來求解超售數(shù)量;1995 年，文獻(xiàn)［4］提出了多票價(jià)等級靜態(tài)超售模型，采用近似替代方法進(jìn)行求解;1999 年，文獻(xiàn)［5］將預(yù)訂請求的到達(dá)假設(shè)為齊次泊松過程，運(yùn)用Bellman-Jacobi 方程對模型進(jìn)行分析，并求解了分段超售限制的最優(yōu)解;文獻(xiàn)［6］假設(shè)一個(gè)時(shí)間段內(nèi)只允許預(yù)訂或取消事件發(fā)生，提出了一般性情況下的多票價(jià)等級超售模型;2004 年，文獻(xiàn)［7］考慮在座位等級可替代情況下研究超售問題，證明此方法可有效降低拒載人數(shù);2011 年，文獻(xiàn)［8］在需求和到達(dá)率不確定下建立靜態(tài)超售模型，并分析了超售水平與航空公司服務(wù)質(zhì)量之間的關(guān)系。

艙位控制是航空收益管理的核心問題，較為著名的研究是Belobaba 于1987 年提出的EMSRa 模型［9］，用于計(jì)算多艙位等級的預(yù)訂限制和保護(hù)水平;后來又提出了更加符合實(shí)際的EMSRb 模型［10］。2006 年，文獻(xiàn)［11］對艙位控制問題進(jìn)行了較為系統(tǒng)的研究，考慮了競爭環(huán)境、批量訂購及多航段等情況下的艙位控制。

在以上研究中，多數(shù)將艙位控制與超售分開討論，因問題的復(fù)雜性，兩者綜合起來進(jìn)行研究存在較大的困難，在靜態(tài)建模方面，2006 年，文獻(xiàn)［12］研究了多等級超售與艙位靜態(tài)控制問題;文獻(xiàn)［13］將訂座過程假設(shè)為排隊(duì)系統(tǒng)進(jìn)行研究;2010 年，文獻(xiàn)［14］建立靜態(tài)模型求解超售策略下的艙位控制問題，并運(yùn)用Jensen 不等式將模型轉(zhuǎn)化成線性規(guī)劃問題進(jìn)行近似求解。動(dòng)態(tài)建模方面，2007 年文獻(xiàn)［15］運(yùn)用馬爾科夫過程建立動(dòng)態(tài)超售模型，假設(shè)了航班艙位開放的先后次序，在串行控制和并行控制下求解得到單等級和多等級的座位分配數(shù)量。

1 模型建立

模型假設(shè)每一個(gè)預(yù)訂或取消行為獨(dú)立發(fā)生，乘客在飛機(jī)起飛之前取消預(yù)訂的平均退款為κ，Noshow 情況下則不給予退款。為便于建模，本文中航班乘客的到達(dá)率與取消率均與艙位等級無關(guān)，用平均到達(dá)率βs與平均取消率βc來表示。另外，當(dāng)?shù)竭_(dá)乘客數(shù)量大于飛機(jī)實(shí)際容量時(shí)，有一部分乘客不得不被拒載，航空公司要為此支付賠償，拒載成本與票價(jià)無關(guān)，這與實(shí)際情況相符合。

本文使用的符號如下所示:m 為航班的艙位等級總數(shù);Di為i 艙位等級的需求數(shù)量，i =1，…，m;C為飛機(jī)座位容量;n 為售票過程中的座位預(yù)訂數(shù)量;bi為i 艙位等級的預(yù)訂限制，i=1，…，m;ri為i 艙位等級的票價(jià);βs為航班乘客平均到達(dá)率;βc為航班乘客平均取消預(yù)訂的概率;κ 為航班乘客取消預(yù)訂的平均退款;θ 為每一位被拒載乘客所獲得的補(bǔ)償成本，與艙位等級i 無關(guān)。

根據(jù)以上假設(shè)及描述建立離散時(shí)間動(dòng)態(tài)模型，由于每一個(gè)預(yù)訂請求的到達(dá)是隨機(jī)的，各艙位等級之間的預(yù)訂請求，通過設(shè)置一定的參數(shù)來模擬實(shí)際到達(dá)的先后順序。在某一時(shí)間點(diǎn)當(dāng)預(yù)訂請求到達(dá)時(shí)，系統(tǒng)決定接受還是拒絕該預(yù)訂請求，確定航班的座位分配方案，以達(dá)到期望總收益的最大化。

圖1 為動(dòng)態(tài)訂座過程，圖1 中，0 代表機(jī)票開始預(yù)訂時(shí)刻;T 表示航班起飛時(shí)刻，預(yù)訂請求及取消請求在離散時(shí)間點(diǎn)tk=kh，k =1，…，K－1 發(fā)生，并且兩者相互獨(dú)立，T=Kh，t0=0，在時(shí)間段區(qū)間Ik=［tk－1，tk)內(nèi)至多只有一個(gè)請求。

圖1 動(dòng)態(tài)訂座過程

對于取消請求過程，由于每一個(gè)取消請求都是獨(dú)立的，假設(shè)區(qū)間Ik取消的概率是c(Ik)，k =2，…，K，在時(shí)刻tk－1，已接受的預(yù)訂請求數(shù)量為n，那么在時(shí)間段Ik取消的人數(shù)服從二項(xiàng)分布B(c(Ik)，n)，在時(shí)刻tk之前，接受的預(yù)訂請求數(shù)量服從B(1－c(Ik)，n)，當(dāng)c(Ik)=1－exp(－λch)，取消過程可以用參數(shù)為λc的齊次馬爾科夫生滅過程來表示，此時(shí)取消概率并不依賴于預(yù)訂數(shù)量，稱該性質(zhì)為“無記憶性”。

另外，假設(shè)在時(shí)間點(diǎn)tk艙位等級i 預(yù)訂請求到達(dá)的概率為pi(tk)，用r0=0 表示乘客到達(dá)卻沒有購買機(jī)票的情況，不失一般性，假設(shè)r0＜r1＜…＜rm，每一個(gè)取消預(yù)訂請求獲得固定的退款為κ，對于拒載的乘客賠付的補(bǔ)償為θ。

改善灌溉質(zhì)量，優(yōu)化水源布局。項(xiàng)目區(qū)農(nóng)田集中連片，田間輸水大面積實(shí)現(xiàn)管道化，不僅使灌溉保證率大大提高，灌溉質(zhì)量大為改善，也使畝均灌溉定額降低到110m3左右，節(jié)水率高達(dá)60%以上。通過實(shí)施高標(biāo)準(zhǔn)節(jié)水灌溉工程，進(jìn)一步優(yōu)化了水源布局，把原有井控面積從70～80畝提高到現(xiàn)在的160～300畝，將過去井群密集、出水量小、能耗高、控制面積小的機(jī)電井徹底壓減封閉，做到了真壓井、壓真井。兩年來，全市累計(jì)壓減機(jī)電井1.3萬眼，節(jié)約水資源3.1億m3，農(nóng)業(yè)用水比例由原來的85%下降到80%。

為便于說明，假設(shè)t+k表示在區(qū)間Ik內(nèi)預(yù)訂請求到達(dá)時(shí)，采取接受還是拒絕的決策時(shí)間點(diǎn)，k =1，…，K－1，預(yù)訂數(shù)量為n 時(shí)，令Jk(n)，k=1，…，K－1 表示從時(shí)間點(diǎn)t+k到t+K的期望收益，在時(shí)間點(diǎn)t+k有n 個(gè)已接受的預(yù)訂請求之后，在區(qū)間Ik+1內(nèi)取消預(yù)訂的數(shù)量服從二項(xiàng)分布B(c(Ik+1)，n)。因此，在時(shí)刻tk+1前的總預(yù)訂數(shù)量為B(1－c(Ik+1)，n)，那么在航班起飛時(shí)刻的總預(yù)訂數(shù)量服從B(1－c(IK)，n)，到達(dá)的乘客總數(shù)服從B(βs(1－c(IK))，n)，并且E(B(c(Ik+1)，n))=nc(Ik)。根據(jù)以上假設(shè)及描述，建立動(dòng)態(tài)規(guī)劃模型PDP:

其邊界條件為:

當(dāng)n=0 時(shí)，有P(B(1－c(Ik+1)，0)=0)=1，因此，式(1)的初始邊界條件為:

式(1)中第1 項(xiàng)表示在k+1 時(shí)刻取消預(yù)訂的退款;第2 項(xiàng)表示在k+1 時(shí)刻乘客到達(dá)但沒有預(yù)訂機(jī)票的情況下，維持原系統(tǒng)預(yù)訂人數(shù)下的期望收益;第3 項(xiàng)表示在不同艙位等級的預(yù)訂請求發(fā)生時(shí)系統(tǒng)的期望收入;式(2)第2 項(xiàng)中，E(［B(βs(1－c(IK)，n)－C］+)表示在飛機(jī)起飛時(shí)刻，由于超售所造成的期望拒載人數(shù);式(3)表示當(dāng)系統(tǒng)中第一個(gè)請求到達(dá)時(shí)的初始條件。

為求解該模型，對模型的性質(zhì)進(jìn)行如下分析:

定理1 假設(shè)r ＞0，當(dāng)函數(shù)f 是離散上凸函數(shù)，那么函數(shù)h(n):h(n)=max{r+f(n+1)，f(n)}也是離散上凸函數(shù)。

限于篇幅，證明從略。

證明 由二項(xiàng)分布的性質(zhì)可知:二項(xiàng)分布B(p，n)可分解成n 個(gè)獨(dú)立0－1 分布之和，因此，二項(xiàng)分布B(p，n)可分解為:

證畢。

定理3 對于k=1，…，K－1，函數(shù)Jk(n)是關(guān)于n 的離散上凸函數(shù)。

證明 引入函數(shù)

則PDP可變換為:

證畢。

在實(shí)際中，對于求解的每一個(gè)艙位等級的獨(dú)立座位數(shù)量意義不大，因?yàn)楹娇展就ǔ?huì)采取嵌套策略，即當(dāng)高票價(jià)的座位數(shù)量售完，低票價(jià)的座位容量有剩余時(shí)，系統(tǒng)仍然會(huì)接受一個(gè)高票價(jià)的預(yù)訂請求，即高票價(jià)的艙位等級可以利用比它低的票價(jià)等級的座位(稱為每一等級的預(yù)訂限制)，這樣才能獲得更高的收益。引入變量bki= max{n ∈Z+:ri≥Jk+1(n)- Jk+1(n +1)}，根據(jù)離散上凸函數(shù)的差分遞減的性質(zhì)，滿足在tk時(shí)刻系統(tǒng)接受i 艙位等級預(yù)訂請求下，并且該艙位等級預(yù)訂數(shù)量≤bki時(shí)，該預(yù)訂數(shù)量為最優(yōu)超售水平，根據(jù)假設(shè)r0＜r1＜… ＜rm，可得到預(yù)訂限制策略為bk1≤bk2≤…≤bkm。

2 算例分析

2.1 算例模擬

本節(jié)建立模擬過程，假設(shè)預(yù)訂請求的到達(dá)服從參數(shù)為λa的齊次泊松過程，對于艙位等級i 的取消過程服從參數(shù)為λc馬爾科夫生滅過程，因此，對于k = 1，…，K -1，有

在航空售票過程中，不同時(shí)刻下不同艙位等級的預(yù)訂請求密度不是一成不變的，而是隨著預(yù)訂時(shí)間的推移而發(fā)生改變，低票價(jià)等級的預(yù)訂請求到達(dá)時(shí)間早于高票價(jià)等級的預(yù)訂請求，為模擬這一條件，假設(shè)在時(shí)間點(diǎn)tk，不同艙位等級的預(yù)訂請求到達(dá)的概率為fi(tk)，fi(tk)服從參數(shù)為αi和βi的Beta 分布，由于Beta 分布的曲線由α 和β 兩個(gè)參數(shù)來決定，其形狀變化幅度較大，在本文中選取適當(dāng)?shù)膮?shù)來描述不同艙位等級乘客的到達(dá)過程。不同艙位等級的預(yù)訂請求到達(dá)概率計(jì)算如下:

2.2 算例求解

以國內(nèi)某航班數(shù)據(jù)為例，該航班的容量C 為150 個(gè)座位，設(shè)有4 個(gè)艙位等級Y、M、Q、K，票價(jià)fi分別為［1 000，800，600，400］(單位:元)，各艙位等級的需求期望和標(biāo)準(zhǔn)差如表1 所示。根據(jù)歷史數(shù)據(jù)統(tǒng)計(jì)，取消預(yù)訂的平均退款為500 元。平均取消概率為5%，為分析航班乘客到達(dá)率對于最優(yōu)超售水平的影響，本文分別選取平均到達(dá)率βs=［0.91，0.93，0.95，0.97］進(jìn)行分析，將預(yù)訂時(shí)期分為100 個(gè)時(shí)間段，時(shí)間段間隔h=0.1，K=100，預(yù)訂請求的到達(dá)參數(shù)λa=1，取消請求的到達(dá)參數(shù)λa=0.5。超售造成的拒載成本θ 為2 000 元，拒載成本大于Y 艙票價(jià)，表示由于拒載而對顧客所做出的補(bǔ)償大小，另外，拒載還會(huì)導(dǎo)致航空公司的潛在信譽(yù)損失，但該部分損失難以定量，在文獻(xiàn)［16］的研究中，將其假設(shè)為遞增下凸函數(shù)，表示邊際拒載成本遞增。為便于求解，在本文中不考慮該部分損失。

表2 設(shè)定了服從Beta 分布的不同艙位等級的預(yù)訂請求到達(dá)分布參數(shù)，表示不同時(shí)刻下預(yù)訂請求的到達(dá)先后順序。具體參數(shù)設(shè)置如表2 所示。

表1 艙位等級需求表

通過以上參數(shù)設(shè)置及模擬仿真過程，對模型進(jìn)行求解得到的結(jié)果見表3。由表3 可以看出:Y 艙為票價(jià)最高的艙位等級，故Y 艙無預(yù)訂限制，可用座位數(shù)為本航班的總超售數(shù)量，其他艙位等級都有預(yù)訂限制，括號內(nèi)數(shù)字表示在該超售水平下艙位等級的訂座數(shù)量。當(dāng)乘客平均到達(dá)率較低時(shí)，為防止飛機(jī)起飛時(shí)造成的空位虛耗損失，允許的超售數(shù)量較大;當(dāng)乘客到達(dá)率增大時(shí)，總超售水平降低，以避免過多的拒載人數(shù)而造成拒載損失，同時(shí)收益也有所減少，表明乘客平均到達(dá)率越高，允許超售數(shù)量越少，同時(shí)造成拒載的人數(shù)也相對增加，導(dǎo)致期望收益降低。

表2 Beta 分布參數(shù)表

表3 艙位等級預(yù)訂限制及收益情況表

另外，模型在不同的乘客到達(dá)率下，超售率均維持在較低水平，航班平均拒載人數(shù)均小于1，較好地符合實(shí)際情況。航空公司采取超售策略可以銷售大于航班實(shí)際容量的座位數(shù)來增加期望收益，同時(shí)，在最優(yōu)超售水平下，超售造成的平均拒載成本遠(yuǎn)遠(yuǎn)小于期望收益，因此，采取有效的超售策略可以增加航空公司的收益。

3 結(jié)束語

本文研究了考慮超售策略下航班艙位分配控制問題，以收益最大化為目標(biāo)，考慮乘客平均到達(dá)率、取消率及拒載成本下建立動(dòng)態(tài)艙位控制模型。根據(jù)某航班數(shù)據(jù)進(jìn)行算例模擬，得到在不同乘客平均到達(dá)率下總超售數(shù)量和每一艙位等級的預(yù)訂限制，其結(jié)果驗(yàn)證了本文模型的有效性，較好地符合實(shí)際情況，對于機(jī)票銷售過程中的艙位分配優(yōu)化提供一定的決策支持。但本文中假設(shè)了與艙位等級無關(guān)的平均到達(dá)率，因此考慮與艙位等級有關(guān)的退票費(fèi)率，到達(dá)率下的綜合建模研究有待于進(jìn)一步的討論。圍繞艙位分配控制問題，下一步的研究將在以下幾個(gè)方面進(jìn)行:多航段下超售和艙位控制問題;動(dòng)態(tài)定價(jià)與艙位控制綜合問題;競爭與聯(lián)盟下的艙位控制問題等。

［1］ Kevin P，Nanda P. Airline Revenue Management:an Overview of OR Techniques 1982－2001［J］. ERIM Report Series Research in Management，2002，12(2):23－52.

［2］ Rothstein M.OR and the Airline Overbooking Problem［J］.Operations Research，1985，33:237－248.

［3］ Beckman J M.Decision and Team Problems in Airline Reservations［J］. Econometrica，1958，26:134－145.

［4］ Chi Z. Airline Yield Management in a Dynamic Network Environment［D］. Cambridge:Operations Research Center，Massachusetts Institute of Technology，1995.

［5］ Chatwin R E.Continuous-time Airline Overbooking with Time Dependent Fares and Refunds［J］.Transportation Science，1999，33:182－191.

［6］ Subramanian J，Stidham S，Lautenbacher C.Airline Yield Management with Overbooking，Cancellations，and No-shows［J］.Transportation Science，1999，33:147－167.

［7］ Karaesmen I Z，van Ryzin G J.Overbooking with Substitutable Inventory Classes［J］.Operations Research，2004，52:83－104.

［8］ Lan Y，Ball M O，Karaesmen I Z. Regret in Overbooking and Fare-class Allocation for Single Leg［J］. Manufacturing ＆Service Operations Management，2011，13(2):194－208.

［9］ Belobaba P P. Air Travel Demand and Airline Seat Inventory Management［D］. Cambridge:Flight Transportation Laboratory，Massachusetts Institute of Technology，1987.

［10］ Belobaba P P.Application of a Probabilistic Decision Model to Airline Seat Inventory Control［J］.Operations Research，1989，37:183－197.

［11］ 高強(qiáng).航空收益管理中艙位控制問題的研究［D］.南京:南京航空航天大學(xué)，2006.

［12］ 劉瑋.航空客運(yùn)收益管理中超售問題的研究［D］.南京:南京航空航天大學(xué)，2004.

［13］ 朱金福，劉瑋，高強(qiáng).航空客運(yùn)艙位控制和超售綜合靜態(tài)建模研究［J］.中國管理科學(xué)，2006，14(5):68－72.

［14］ Aydin N，Birbil S I，F(xiàn)renk J B G，et al.Single-leg Airline Revenue Management with Overbooking［D］.Turkey:Sabanci University，2010.

［15］ 朱金福，劉瑋，姚韻.航空客運(yùn)艙位控制和超售綜合動(dòng)態(tài)建模研究［J］.系統(tǒng)工程學(xué)報(bào)，2007，22(5):525－531.

［16］ Feng Y，Xiao B. A Continuous-time Seat Control Model for Single-leg Flights with No-shows and Optimal Overbooking Upper Bound［J］.European Journal of Operational Research，2006，174:1298－1316.