张宇宁　牟德一　赵宇洋　姚雨沁　 高忠文　何楚君

摘   要：为了减少航空公司的损失，提高航班客座利用率，提出一种面对多航节的联程超售策略，并考虑到实际情况的随机性，建立随机规划模型。通过蒙特卡罗方法对现实情况进行仿真，再利用冒泡搜索算法，搜索出模拟情况中使超售成本最低的超售数量。通过实际应用算例验证，此模型能够有效降低成本，反映了该模型的优越性，具有一定实用价值。

关键词：随机规划  蒙特卡洛模拟  超售

中图分类号：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年代美国政府放松对航空运输业的管制，允许航空公司在一定范围内自主定价以来，收益管理开始出现和发展，其主要目的是以合适的价格在正确的时间将合适的产品销售给对应的顾客。收益管理通过需求预测、超售、座舱控制以及动态定价，使航空公司收益最大化，是航空领域中先进的管理思想和决策的重要基础构成，美国航空公司依靠收益管理成功地在激烈的市场竞争中取得优势。如今国内航空运输业进入新时代，国家政策大力扶持航空业发展，加上外航进入参与国际航线部分的市场竞争，并且国内航空公司收益管理部分较国外发展情况尚有提升空间，结合国内复杂的航线运输网络和巨大的交通流量，收益管理得到发展与应用是必然趋势。

收益管理中的超售问题是研究历史最久的一个分支，最早由塔斯曼帝国航空公司Beckman[1]提出，将旅客到来近似看作γ分布，但此模型需要预估旅客需求和已订座的旅客与撤销订座的旅客的概率分布，无法在实际情况中应用。此后在1961年，Thompson[2]提出忽略旅客到来的概率分布和超售成本，并提出条件超售概率，但是这两个模型都属于静态模型，没有考虑到实际情况的变化。1971年Rothstein在研究酒店收益管理中，提出了动态规划模型，第一次用动态规划解决超售问题，也由此展开了动态超售的研究。Alstrup[3]利用动态规划针对两等级舱位超售问题进行研究。Chatwin[4]建立了单一票价，分多阶段的离散动态超售模型，证明了动态超售问题最优解的存在。目前的趋势是结合大数据技术和计算机技术对超售问题进行求解。Brinkmann[5]等人提出了用高性能计算机群（HPC）解决超售问题的一种方案，Hauser等人提出了一种在iaaS云计算系统中解决动态超售问题的方法。国内的朱金福、高强[6]等人将排队论和静态超售模型结合。后仍由其提出利用马尔科夫随机过程模拟超售过程，并且扩展至多舱位等级。

本文针对机票销售过程的不确定性，提出随机规划模型，考虑旅客No-show和拒载成本（Denied Boarding），使空座成本和拒载成本之和最小。使用蒙特卡洛随机模拟方法，对实际情况进行模拟，利用统计学中的中心极限定理，用大量的模拟过程近似成本期望值。最后利用简单搜索算法在得出的解空间内搜索最优解。

1  问题提出

多航段超售模型旨在旅客开始订票之前，已知初始的订座数限制和旅客到来情况的概率分布的基础上确定各个航段的超售的座位数，以求出期望损失最小对应的各个航段上的超售座位数。

以三地A，B，C為例简述多航段超售模型的建立。在多航段中，如果仍按照单航段的超售策略来安排座位，即每个航段有固定的超售座位数，不同航段对应的超售座位不可互相调整。若实际到来的旅客数少于该航段预留的座位数，就会产生空座成本;反之，若实际到来的旅客数多于该航段预留的座位数，就会产生拒载成本。如果引入多航段的超售策略，即依据实际到来的旅客数调整每个航段上的超售座位数，例如当AB航段出现拒载成本，而AC航段出现空座成本，我们就可以增加AB航段的超售座位数，减少AC航段的超售座位数，以减少成本损失。基于以上想法，我们提出下面的多航段超售策略：

AB段乘客可以调配到AC段的空位上，但AC段乘客无法调配到AB段的空位上，同理BC段乘客可以调到AC段空位上。

2  符号说明

符号说明见表1所示。

3  模型建立

航班超售总成本分为两部分，一部分是空座成本，另一部分是拒载成本。实际飞行过程为从A到B到C，所以这里将总成本分两步考虑。

首先我们假设旅客到来情况服从参数为（b，λ）的二项分布，即超售水平为b时每位旅客到来的概率为

3.1  A→B航段上的总成本

3.1.1 空座成本

空座成本产生的情况分为两种，一种为s3

3.1.2 拒载成本

拒载成本产生的情况同样分为两种，一种为s3>P3且s1>P1，即从A到B和从A到C的乘客数量都比预留的座位数多;第二种为s1>P1+P3-s3且s3

AB段上的期望总成本期望为：

3.2 B→C航段上的总成本

3.2.1 空座成本

此时空座成本只有BC段上的，因为在计算AB段成本时已将AC段空座成本计入，出现空座成本的情况只有一种，即为s2

3.2.2 拒载成本

拒载成本出现的情况分为两种，一种为s2>P2且s3>P3;另一种为s2>P2+P3-s3且s3

BC航段上的总成本期望为：

3.3 总成本

总期望成本即为：

超售模型为：

其中，τ为每个航段上的超售率。

4  求解算法

4.1 蒙特卡洛模拟

蒙特卡洛模擬是在二战期间，当时在原子弹研制的项目中，为了模拟裂变物质的中子随机扩散现象，由美国数学家冯·诺伊曼和乌拉姆等发明的一种统计方法，后来发展至项目定量风险分析中常用的一种模拟技术，在计算机上模拟足够多的次数，每次的输入是随机的，最终得出一个累计概率分布图，这个就是蒙特卡洛模拟。

由于目标函数C中到来的人数是一个不确定值，而这个不确定值影响了最后的决策，并且让整个规划问题成为一个随机规划。实到旅客人数si受随机扰动影响的可以描述为：

si=s（ω，μ，σ）

表示实到人数受扰动影响，围绕均值μ和标准差σ产生波动。在模型建立中，我们假设s服从二项分布，于是通过运用蒙特卡洛方法，对于每个航段上旅客实到人数依据概率分布产生N组独立同分布的数据，si（1）～si（N），针对每一组样本，实到人数为一个确定值。当产生的随机数足够大时，我们可以用均值法来消除扰动，以每组样本下的目标函数均值作为总体的目标函数。此时将随机规划转化成整数规划求解。

4.2 冒泡搜索求最优解

根据航空公司相关规定，一般超售数量不超过可用座位数的20%，针对目前飞机运载规模，即使考虑联程的情况下，解空间的规模也还在一般计算机的处理能力之内。所以我们先枚举出解空间下所有的目标函数值E，再利用简单的冒泡搜索算法，在由所有目标函数组成的一维解空间f（E）中得出最优目标函数值。

整个算法求解的流程如图2所示。

5  算例分析

为直观描述该模型的优点，我们以南京—大连—石家庄的航线数据为例对该模型进行验证（见表2）。

如果根据单航段超售策略计算联程超售成本，与采用该超售模型之后相比，成本明显要高。

设置迭代次数为50次，最后的解趋于稳定。

最后结果如表3所示。

6  结语

本文研究了在轮辐式航线网络结构下的超售成本问题，从超售策略提出角度出发，以最小化超售成本为目的，建立了随机规划超售模型。运用蒙特卡洛模拟仿真和冒泡算法对模型进行求解，得到各航段的最优超售数目。应用算例结果显示，本文提出的基于蒙特卡洛模拟的随机规划的超售模型，能有效的降低超售成本，证明了该模型的有效性，能够给航空公司的超售决策带来一定参考价值。

参考文献

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

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