張宇寧　牟德一　趙宇洋　姚雨沁　 高忠文　何楚君

摘 ? 要：為了減少航空公司的損失，提高航班客座利用率，提出一種面對多航節(jié)的聯(lián)程超售策略，并考慮到實(shí)際情況的隨機(jī)性，建立隨機(jī)規(guī)劃模型。通過蒙特卡羅方法對現(xiàn)實(shí)情況進(jìn)行仿真，再利用冒泡搜索算法，搜索出模擬情況中使超售成本最低的超售數(shù)量。通過實(shí)際應(yīng)用算例驗(yàn)證，此模型能夠有效降低成本，反映了該模型的優(yōu)越性，具有一定實(shí)用價(jià)值。

關(guān)鍵詞：隨機(jī)規(guī)劃 ?蒙特卡洛模擬 ?超售

中圖分類號：F560 ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A ? ? ? ? ? ? ? ? ? ? ? ?文章編號：1674-098X（2019）06（b）-0017-07

Abstract： In order to reduce the loss of airlines and improve the passenger utilization rate of flights， a multi-schedule overbooking strategy is proposed， and a stochastic programming model is established considering the randomness of the actual situation. The Monte Carlo method is used to simulate the real situation， and then the bubble search algorithm is used to search for the overbooking quantity that minimizes the overbooking cost in the simulation case. Through practical application examples， this model can effectively reduce costs， reflecting the superiority of the model， and has certain practical value.

Key Words： Stochastic programming; Monte carlo simulation; Overbooking

自從20世紀(jì)80年代美國政府放松對航空運(yùn)輸業(yè)的管制，允許航空公司在一定范圍內(nèi)自主定價(jià)以來，收益管理開始出現(xiàn)和發(fā)展，其主要目的是以合適的價(jià)格在正確的時(shí)間將合適的產(chǎn)品銷售給對應(yīng)的顧客。收益管理通過需求預(yù)測、超售、座艙控制以及動態(tài)定價(jià)，使航空公司收益最大化，是航空領(lǐng)域中先進(jìn)的管理思想和決策的重要基礎(chǔ)構(gòu)成，美國航空公司依靠收益管理成功地在激烈的市場競爭中取得優(yōu)勢。如今國內(nèi)航空運(yùn)輸業(yè)進(jìn)入新時(shí)代，國家政策大力扶持航空業(yè)發(fā)展，加上外航進(jìn)入?yún)⑴c國際航線部分的市場競爭，并且國內(nèi)航空公司收益管理部分較國外發(fā)展情況尚有提升空間，結(jié)合國內(nèi)復(fù)雜的航線運(yùn)輸網(wǎng)絡(luò)和巨大的交通流量，收益管理得到發(fā)展與應(yīng)用是必然趨勢。

收益管理中的超售問題是研究歷史最久的一個(gè)分支，最早由塔斯曼帝國航空公司Beckman[1]提出，將旅客到來近似看作γ分布，但此模型需要預(yù)估旅客需求和已訂座的旅客與撤銷訂座的旅客的概率分布，無法在實(shí)際情況中應(yīng)用。此后在1961年，Thompson[2]提出忽略旅客到來的概率分布和超售成本，并提出條件超售概率，但是這兩個(gè)模型都屬于靜態(tài)模型，沒有考慮到實(shí)際情況的變化。1971年Rothstein在研究酒店收益管理中，提出了動態(tài)規(guī)劃模型，第一次用動態(tài)規(guī)劃解決超售問題，也由此展開了動態(tài)超售的研究。Alstrup[3]利用動態(tài)規(guī)劃針對兩等級艙位超售問題進(jìn)行研究。Chatwin[4]建立了單一票價(jià)，分多階段的離散動態(tài)超售模型，證明了動態(tài)超售問題最優(yōu)解的存在。目前的趨勢是結(jié)合大數(shù)據(jù)技術(shù)和計(jì)算機(jī)技術(shù)對超售問題進(jìn)行求解。Brinkmann[5]等人提出了用高性能計(jì)算機(jī)群（HPC）解決超售問題的一種方案，Hauser等人提出了一種在iaaS云計(jì)算系統(tǒng)中解決動態(tài)超售問題的方法。國內(nèi)的朱金福、高強(qiáng)[6]等人將排隊(duì)論和靜態(tài)超售模型結(jié)合。后仍由其提出利用馬爾科夫隨機(jī)過程模擬超售過程，并且擴(kuò)展至多艙位等級。

本文針對機(jī)票銷售過程的不確定性，提出隨機(jī)規(guī)劃模型，考慮旅客No-show和拒載成本（Denied Boarding），使空座成本和拒載成本之和最小。使用蒙特卡洛隨機(jī)模擬方法，對實(shí)際情況進(jìn)行模擬，利用統(tǒng)計(jì)學(xué)中的中心極限定理，用大量的模擬過程近似成本期望值。最后利用簡單搜索算法在得出的解空間內(nèi)搜索最優(yōu)解。

1 ?問題提出

多航段超售模型旨在旅客開始訂票之前，已知初始的訂座數(shù)限制和旅客到來情況的概率分布的基礎(chǔ)上確定各個(gè)航段的超售的座位數(shù)，以求出期望損失最小對應(yīng)的各個(gè)航段上的超售座位數(shù)。

以三地A，B，C為例簡述多航段超售模型的建立。在多航段中，如果仍按照單航段的超售策略來安排座位，即每個(gè)航段有固定的超售座位數(shù)，不同航段對應(yīng)的超售座位不可互相調(diào)整。若實(shí)際到來的旅客數(shù)少于該航段預(yù)留的座位數(shù)，就會產(chǎn)生空座成本;反之，若實(shí)際到來的旅客數(shù)多于該航段預(yù)留的座位數(shù)，就會產(chǎn)生拒載成本。如果引入多航段的超售策略，即依據(jù)實(shí)際到來的旅客數(shù)調(diào)整每個(gè)航段上的超售座位數(shù)，例如當(dāng)AB航段出現(xiàn)拒載成本，而AC航段出現(xiàn)空座成本，我們就可以增加AB航段的超售座位數(shù)，減少AC航段的超售座位數(shù)，以減少成本損失?；谝陨舷敕ǎ覀兲岢鱿旅娴亩嗪蕉纬鄄呗裕?/p>

AB段乘客可以調(diào)配到AC段的空位上，但AC段乘客無法調(diào)配到AB段的空位上，同理BC段乘客可以調(diào)到AC段空位上。

2 ?符號說明

符號說明見表1所示。

3 ?模型建立

航班超售總成本分為兩部分，一部分是空座成本，另一部分是拒載成本。實(shí)際飛行過程為從A到B到C，所以這里將總成本分兩步考慮。

首先我們假設(shè)旅客到來情況服從參數(shù)為（b，λ）的二項(xiàng)分布，即超售水平為b時(shí)每位旅客到來的概率為

3.1 ?A→B航段上的總成本

3.1.1 空座成本

空座成本產(chǎn)生的情況分為兩種，一種為s3

3.1.2 拒載成本

拒載成本產(chǎn)生的情況同樣分為兩種，一種為s3>P3且s1>P1，即從A到B和從A到C的乘客數(shù)量都比預(yù)留的座位數(shù)多;第二種為s1>P1+P3-s3且s3

AB段上的期望總成本期望為：

3.2 B→C航段上的總成本

3.2.1 空座成本

此時(shí)空座成本只有BC段上的，因?yàn)樵谟?jì)算AB段成本時(shí)已將AC段空座成本計(jì)入，出現(xiàn)空座成本的情況只有一種，即為s2

3.2.2 拒載成本

拒載成本出現(xiàn)的情況分為兩種，一種為s2>P2且s3>P3;另一種為s2>P2+P3-s3且s3

BC航段上的總成本期望為：

3.3 總成本

總期望成本即為：

超售模型為：

其中，τ為每個(gè)航段上的超售率。

4 ?求解算法

4.1 蒙特卡洛模擬

蒙特卡洛模擬是在二戰(zhàn)期間，當(dāng)時(shí)在原子彈研制的項(xiàng)目中，為了模擬裂變物質(zhì)的中子隨機(jī)擴(kuò)散現(xiàn)象，由美國數(shù)學(xué)家馮·諾伊曼和烏拉姆等發(fā)明的一種統(tǒng)計(jì)方法，后來發(fā)展至項(xiàng)目定量風(fēng)險(xiǎn)分析中常用的一種模擬技術(shù)，在計(jì)算機(jī)上模擬足夠多的次數(shù)，每次的輸入是隨機(jī)的，最終得出一個(gè)累計(jì)概率分布圖，這個(gè)就是蒙特卡洛模擬。

由于目標(biāo)函數(shù)C中到來的人數(shù)是一個(gè)不確定值，而這個(gè)不確定值影響了最后的決策，并且讓整個(gè)規(guī)劃問題成為一個(gè)隨機(jī)規(guī)劃。實(shí)到旅客人數(shù)si受隨機(jī)擾動影響的可以描述為：

si=s（ω，μ，σ）

表示實(shí)到人數(shù)受擾動影響，圍繞均值μ和標(biāo)準(zhǔn)差σ產(chǎn)生波動。在模型建立中，我們假設(shè)s服從二項(xiàng)分布，于是通過運(yùn)用蒙特卡洛方法，對于每個(gè)航段上旅客實(shí)到人數(shù)依據(jù)概率分布產(chǎn)生N組獨(dú)立同分布的數(shù)據(jù)，si（1）～si（N），針對每一組樣本，實(shí)到人數(shù)為一個(gè)確定值。當(dāng)產(chǎn)生的隨機(jī)數(shù)足夠大時(shí)，我們可以用均值法來消除擾動，以每組樣本下的目標(biāo)函數(shù)均值作為總體的目標(biāo)函數(shù)。此時(shí)將隨機(jī)規(guī)劃轉(zhuǎn)化成整數(shù)規(guī)劃求解。

4.2 冒泡搜索求最優(yōu)解

根據(jù)航空公司相關(guān)規(guī)定，一般超售數(shù)量不超過可用座位數(shù)的20%，針對目前飛機(jī)運(yùn)載規(guī)模，即使考慮聯(lián)程的情況下，解空間的規(guī)模也還在一般計(jì)算機(jī)的處理能力之內(nèi)。所以我們先枚舉出解空間下所有的目標(biāo)函數(shù)值E，再利用簡單的冒泡搜索算法，在由所有目標(biāo)函數(shù)組成的一維解空間f（E）中得出最優(yōu)目標(biāo)函數(shù)值。

整個(gè)算法求解的流程如圖2所示。

5 ?算例分析

為直觀描述該模型的優(yōu)點(diǎn)，我們以南京—大連—石家莊的航線數(shù)據(jù)為例對該模型進(jìn)行驗(yàn)證（見表2）。

如果根據(jù)單航段超售策略計(jì)算聯(lián)程超售成本，與采用該超售模型之后相比，成本明顯要高。

設(shè)置迭代次數(shù)為50次，最后的解趨于穩(wěn)定。

最后結(jié)果如表3所示。

6 ?結(jié)語

本文研究了在輪輻式航線網(wǎng)絡(luò)結(jié)構(gòu)下的超售成本問題，從超售策略提出角度出發(fā)，以最小化超售成本為目的，建立了隨機(jī)規(guī)劃超售模型。運(yùn)用蒙特卡洛模擬仿真和冒泡算法對模型進(jìn)行求解，得到各航段的最優(yōu)超售數(shù)目。應(yīng)用算例結(jié)果顯示，本文提出的基于蒙特卡洛模擬的隨機(jī)規(guī)劃的超售模型，能有效的降低超售成本，證明了該模型的有效性，能夠給航空公司的超售決策帶來一定參考價(jià)值。

參考文獻(xiàn)

[1] Beckmann J. M.，Decision and Team Problems in Airline，Reservations Econometrica，1958（26）：134-145.

[2] Thompson ?H ?R. ?Statistical ?Problems ?in ?Airline ?Reservation ?Control[J].Operational ?Research Quarterly， 1961（12）：167-185.

[3] Alstrup J， Boas S， Madsen O B G. Booking Policy for Flights with Two Types of Passengers[J]. European Journal of Operations Research， 1986（27）：274-288.

[4] Chatwin R. E.，Optimal Airline Overbooking，[PHD]，Palo Alto ， CA， Stanford University， 1992.

[5] Reservation-based overbooking for HPC clusters，Birkenheuer， Georg （Paderborn Center for Parallel Computing （PC2）， University of Paderborn， Germany）; Brinkmann， André Source： Proceedings - IEEE International Conference on Cluster Computing， ICCC， 2011：537-541.

[6] 高強(qiáng)，朱金福.航空收益管理中不定期票的優(yōu)化控制方法.2007，26（2）：72-75.

[7] https：//www.jianshu.com/p/cb44f4b457c3.