基于蒙特卡羅隨機(jī)模擬的多航段超售模型

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

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

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

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

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

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

1 ?問(wèn)題提出

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

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

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

2 ?符號(hào)說(shuō)明

符號(hào)說(shuō)明見(jiàn)表1所示。

3 ?模型建立

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

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

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)象，由美國(guó)數(shù)學(xué)家馮·諾伊曼和烏拉姆等發(fā)明的一種統(tǒng)計(jì)方法，后來(lái)發(fā)展至項(xiàng)目定量風(fēng)險(xiǎn)分析中常用的一種模擬技術(shù)，在計(jì)算機(jī)上模擬足夠多的次數(shù)，每次的輸入是隨機(jī)的，最終得出一個(gè)累計(jì)概率分布圖，這個(gè)就是蒙特卡洛模擬。

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

si=s（ω，μ，σ）

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

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

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

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

5 ?算例分析

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

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

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

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

6 ?結(jié)語(yǔ)

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