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

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

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

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

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

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

1 ?問題提出

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

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

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

2 ?符號說明

符號說明見表1所示。

3 ?模型建立

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

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

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

3.1.1 空座成本

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

3.1.2 拒載成本

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

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

3.2 B→C航段上的總成本

3.2.1 空座成本

此時空座成本只有BC段上的，因為在計算AB段成本時已將AC段空座成本計入，出現(xiàn)空座成本的情況只有一種，即為s2

3.2.2 拒載成本

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

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

3.3 總成本

總期望成本即為：

超售模型為：

其中，τ為每個航段上的超售率。

4 ?求解算法

4.1 蒙特卡洛模擬

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

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

si=s（ω，μ，σ）

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

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

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

整個算法求解的流程如圖2所示。

5 ?算例分析

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

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

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

最后結果如表3所示。

6 ?結語

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

參考文獻

[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] 高強，朱金福.航空收益管理中不定期票的優(yōu)化控制方法.2007，26（2）：72-75.

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