不正常航班旅客流恢复方法研究

顾兆军　安一然　潘　杰

(中国民航大学计算机科学与技术学院　天津 300300)



不正常航班旅客流恢复方法研究

顾兆军安一然潘杰

(中国民航大学计算机科学与技术学院天津 300300)

摘要针对不正常航班所引起的投诉与纠纷现象日益严重，以及航空公司恢复受扰旅客行程的实际需求，提出一种基于旅客类别的旅客流恢复模型，以最小化旅客行程恢复损失成本为目标，并给出适用于此模型的求解算法。利用该模型，航空公司可以确定旅客优先级，得到旅客优先恢复序列，降低了不正常航班的经济损失，同时赢得了良好的品牌信誉。实验结果证明，该模型具有实用性和有效性，航空公司可以快速获得优化的、可行的、经济的旅客流恢复方案。

关键词航班延误旅客流恢复旅客分类排序算法

0引言

近年来，随着国内航空业的飞速发展，不正常航班问题，尤其是航班延误频繁发生，旅客与航空公司之间也时有矛盾发生，航空公司在这方面付出的经济赔偿也越来越高。旅客是航空公司收益的主要来源，航空公司的服务质量对旅客的购买意愿存在直接或间接的影响。并且旅客对航班延误问题解决的满意度是航空公司提高市场竞争力，构建品牌服务的核心所在[1]。如何快速恢复受扰旅客流，减少航空公司损失的同时促进品牌服务的构建，是目前各航空公司的迫切需求。

国外很早就认识到不正常航班恢复对航空公司的重要性，并较早展开研究，但主要集中在飞机恢复和机组恢复方面，旅客保护问题研究还比较少。Clarke等[2]构建了一个旅客流模型PFM(PassengerFlowModel)，以最大化旅客收益为目标，根据OD对定义旅客优先级，并依据此优先级恢复旅客，但对于相同OD对内的旅客优先级未定义。Barnhart等[3]以受扰旅客延误最少为目标，将旅客流恢复问题处理成多商品网络流问题，但随着受扰旅客数量增加，求解时间也迅速增加。Bratu等[4]则采用启发式算法来解决这个问题，并加入一些恢复约束(如常旅客优先、先受扰先恢复等)，但这些约束对确定旅客优先级效果不明显，对旅客经济价值的考虑不全面。Jafari等[5]重新定义了恢复期，研究不正常航班的飞机路线和旅客流同步恢复问题，采用路线恢复概念以减小问题规模，但由于此线性规划问题规模仍太大，求解效率不高。Bisaillon等[6]通过构建、修复、改进三阶段来解决飞机路线恢复、机型指派和旅客流恢复问题，以恢复行程旅客数量最多为目标，在构建完可行飞机路线之后，采用最短路算法构建初始路线。然后进行放松延误时间的枚举尝试，但枚举效率低，且无法保证解的最优性。Petersen等[7]则将航空恢复问题分为航班时刻表恢复、飞机恢复、机组恢复和旅客流恢复等四个模块，运用列生成和Benders分解算法，通过问题分解、优化的迭代计算，获取整体最优解。

与国外相比，国内对不正常航班问题的研究还处于起步阶段。赵秀丽等[8]建立了一体化恢复模型，并采用Benders分解算法求解，此模型分为主问题航班恢复，以及子问题飞机、机组和旅客恢复。陆宏兰等[9-11]构建的旅客流恢复模型，将问题转化为运输匹配问题，以延误成本最小为目标，采用单纯形法进行求解，虽然优化了存储方法和搜索策略，但求解效率不高。王莹等[12]分析了航班延误补偿的经济效益问题，并提出了飞机路线和旅客行程一体化恢复模型，旅客流恢复及恢复成本基于OD对，未考虑旅客价值，会影响旅客优先恢复序列的确定。李雄等[13,14]研究了航班延误引发的航空公司及旅客经济损失问题，详细分析了不正常航班成本构成旅客赔偿和隐性损失。

本文在细分航班延误成本的基础上，以最小化航空公司延误损失为目标，结合飞机容量限制、航班订座信息(如团体购票)等因素，构造一种基于旅客类别的旅客流恢复模型。并给出适用于此模型的求解方法，极大地缩小了问题规模，减少了迭代次数。其中，旅客优先级的确定是利用大堆排序和归并排序相结合的思想进行排序，并依次推荐高价值受扰旅客恢复行程。最后通过实验验证了此模型及求解算法的可行性和有效性。

1不正常航班旅客分类模型

1.1数据预处理

PNR数据是航空旅客订座记录，抽取PNR有用属性对现有数据进行数据预处理后得到实验分类属性如表1所示。

表1　类别属性

旅客的性质(是否常旅客) 、购票的方式(是否团队购票) 、舱位性质(折扣级别) 、提前订票时长、旅客忠诚度，以及航班是否中转等都直接或间接反映着旅客的价值。

1.2多元变量潜在类别模型

潜在类别模型[15-17]通过潜在类别变量解释并估计各外显变量间的关联，它有两个很重要的参数：潜在类别概率和条件概率。潜在类别概率用于说明旅客分类结果中各类旅客所占比例；条件概率指在某潜在类内，某旅客在某外显变量上的响应概率。潜在类别模型一般处理备选取值情况相似的观测变量，对于备选取值情况不相同的民航旅客行为数据，此模型不再适用。因此本文提出多元变量潜在类别模型，用函数表示观测变量的取值，以解决取值情况不同问题。

对于一个潜在类别变量X和四个观测变量(A,B,C,D)，多元潜在类别模型可表示为潜在类别概率和条件概率的连乘积，如下所示：

(1)

观测变量的取值结果用函数表示，定义变量i在s水平的取值函数如下所示：

(2)

1.3改进的EM算法

方法：

i←0，knz←kmax，ε←+∞，T(可接受误差)

form=1,…,kmax，i=1,…,n

whileknz>kmindo

//分类数目约束

i←i+1

form= 1toknzdo

//判断外显变量的概率值是否为正，剔出无意义的概率值

else

knz=knz-1

endif

endfor

until|ε|≤T

//输出最佳分类模型

endwhile

endfor

1.4旅客分类结果

采用国内某航空公司的27 688条订座数据，利用改进的EM算法，得到最优分类模型的分类数目为4，其类别概率和类内条件概率的估计结果如表2所示。

表2　潜在类别条件概率与潜在类别概率估计

表3为各组合的分类结果(由于组合比较多，一共216种，只列举了其中几个)。

表3　分类结果表

利用聚类准确性检测方法检验此分类结果，经计算得到分类正确率为95.84%，说明分类基本正确。

2不正常航班旅客流恢复模型

2.1模型假设

为了简化模型和求解算法，对航空公司不正常航班恢复的实际操作规范和原则进行适当抽象，做以下假设：

(1) 不正常航班发生后，先获得航班恢复方案，再进行旅客行程恢复，旅客行程恢复的过程中不对航班计划进行调整；

(2) 只针对无中转航班的受扰旅客进行行程恢复；

(3) 受扰旅客通过签转方式获得新的行程；无法签转的旅客则取消行程。

2.2模型构建

2.2.1成本分解

不正常航班旅客流恢复问题涉及的航空公司损失成本主要包括旅客行程取消成本Cf，即为旅客购票票价；旅客延误成本Df，与旅客总延误时间有关；旅客签转成本Sf，即转换成其他运输工具或其他航空公司航班给本航空公司造成的惩罚成本；若签转至本航空公司航班，则不计此成本；以及旅客信度损失成本Uf，即旅客认可度降低而引起的潜在经济损失。

受扰旅客的单位时间延误成本：即为在航班延误时间段内旅客可创造的经济价值。计算公式如下：

Vp=η·Wavg/2000

式中，Wavg为全国职工年平均工资，2000为年有效工时的平均值；η为时间价值比例系数，依据旅客的类别(fareClass)取不同值，是决定旅客时间价值的关键因素。

受扰旅客的延误成本：Df=Vp·t

式中，t为航班延误时间。

受扰旅客的签转成本：Sf=λ·w·Cf

式中，λ为惩罚系数，其值大于1;w∈{0,1}:w=1表示旅客签转至其他航空公司的航班；否则，w=0;Cf为旅客的购票票价。

受扰旅客的失望信度：即为在非正常航班出现导致旅客对航空公司的认可度降低的情况下，旅客以后再次选择搭乘该航空公司航班的概率，主要考虑延误时间的影响。计算公式如下：

受扰旅客的信度损失成本：Uf=up·η·Cf

式中，Cf为旅客的购票票价；up为旅客的失望信度；f为航班号；η为信度影响因子，其值等于时间价值比例系数。

因此，就某一非正常航班，航班延误导致的航空公司经济损失的计算公式如下：

C=CFf+SFf

CFf=Cf+Uf

SFf=Df+Sf+Uf

式中，CFf表示取消航班的旅客损失成本；SFf表示签转航班的旅客损失成本。

2.2.2符号定义

F为旅客行程集合；RF为旅客行程f的候选行程集合；

Nf为旅客行程f上的旅客流量；Yf∈{0,1}:Yf=1表示由于航班取消造成旅客行程f中断；否则，Yf=0。

uf表示签转至航班的航班容量，限制为航班剩余座位数。

2.2.3数学模型

旅客流恢复模型数学模型如下所示：

(3)

(4)

(5)

(6)

(7)

(8)

(9)

目标函数式(3)表示所有受扰旅客重新调配恢复行程的总损失成本最小，包括受扰旅客的延误成本、受扰旅客的取消成本、受扰旅客的签转惩罚成本，以及受扰旅客的信度损失成本。约束式(4)为行程p中断情况下候选行程r上的旅客数量平衡约束，即当行程p中断后转移到行程r上的旅客数量不得超过行程p上的旅客数量。约束式(5)为行程p不中断情况下行程p上的旅客数量平衡约束，即行程p上被服务的旅客数量就是行程p上的旅客总数。约束式(6)为行程p中断的情况下行程p上的旅客数量平衡约束，即签转至行程r上的旅客数量加上取消行程的旅客数量等于初始行程p上的旅客数量。约束式(7)为行程p上购票团体m的旅客要同时安排，且安排在同一个航班上。约束式(8)为航班座位容量限制约束，要求安排到此航班的受扰旅客总数不大于此航班的剩余可用座位数。约束式(9)为变量取值约束，要求签转至每个航班的旅客人数和取消行程的旅客人数为非负整数。

2.3模型求解算法

航空公司若发生不正常航班，在进行旅客行程恢复安排时，为了减少损失，航空公司会优先将旅客安排在本航空公司的航班上。另外，随着旅客等待时间的延长，其签转成本有可能会高于取消成本，本着航班延迟损失最少的原则，这些旅客则需要取消航班，而需要签转的旅客则需要按一定顺序恢复行程。

2.3.1航班选择算法

航空公司为了保证运营，对于受扰旅客一般都会安排签转，但是，签转至其他航空公司会产生较多成本。本文提出以下算法以确保旅客会优先签转至本航空公司的航班。

第一步确定各类延误时间阈值。即确定签转至本航空公司航班的损失成本小于或等于签转至其他航空公司航班或其他运输方式的延误时间。

第二步延误时间小于或等于阈值，依据本航空公司的候选行程安排受扰旅客。

第三步延误时间大于阈值，则依据所有航空公司的候选行程或其他运输方式安排受扰旅客。

2.3.2旅客签转算法

由成本公式可看出，签转航班的旅客成本是关于延误时间的增函数，而取消航班的旅客成本是关于延误时间的减函数。所以两函数必然相交，且相交于一点。此点所代表的成本值即为签转航班或取消航班的阈值，高于此阈值的旅客取消签转航班，反之，则签转航班。

第一步确定各类旅客的签转成本阈值。即旅客签转航班成本小于或等于取消航班成本的成本值。这个比较标准可以转化为旅客的最大等待签转时间阈值。

第二步结合航班情况，计算各类旅客的签转成本，进而确定可以签转的旅客。

第三步依据旅客的签转成本确定优先顺序，排序算法随后阐述。

第四步依据签转至航班的可用座位数uf确定此次签转的旅客，即从已排序的序列中推荐出uf位旅客。

2.3.3旅客排序算法

本文采用大堆排序和归并排序相结合的思想进行旅客排序。结合本文实际具体算法如下：

输入：待签转至航班时刻time_new；待签转至航班容量nums_new；延误航班时刻time_old；延误航班容量nums_old；受扰旅客集S。

输出：签转旅客集P。

方法：

(1)if(w== 0)then

//w表示是否为本航空公司航班

(2)time=time_new-time_old

(3)foreachTreshold[i][1]

(4)if(time<=Treshold[i][1] )

(5)num[j] =Treshold[i]

(6)foreachfareClassp∈num[j],do

(7)bigHeapSort(p)

(8)elsebigHeapSort(S)

(9)k= 0

(10)//P[p][]存储筛选的p类旅客的前nums_new位

(11)addgetTop(p)orgetTop(S)toP[p][nums_new]

(12)k++

(13)if(k<=nums_new)then

(14)return(11)

(15)mergeSort(P[][])toS[],P[]=S[0...nums_new-1]

(16)//第四类旅客较多为团体购票

(17)if(num[j] ==3 )

(18)foreachfare∈P[]

(19)if(P[nums_new].group== 1)then

(20)group[k][i]

//k团体标号，i该旅客的数组序列标号

(21)foreachgroup∈group[k][]

(22)count[k]++

//k号团体的旅客数量

(23)if(count[k] <=nums_new)then

(24)deleteP[i] //i为group[k][i]中的i

(25)addP[0..nums_new-1-count[k]])∪count[k]toP[]

(26)deleteP[i]

(27)addS[nums_new..nums_new+group[k].length])toP[]

(28)k=0

(29)printP[k]

(30)k++

(31)if(k<=nums_new)then

(32)return(29)

3实验结果与分析

实验采用国内某航空公司的27 688条订座数据，模型中各参数的设计如下：Ⅰ类、Ⅱ类、Ⅲ类、Ⅳ类旅客的η取值分别为8.4、14、11、3，则各类受扰旅客的单位延误成本可表示为Vp=3η。其中3表示全国平均每分钟的经济价值；受扰旅客转换其他航空公司航班的惩罚系数λ=1.1。

3.1延误时间阈值

由于各类旅客的签转成本与旅客的类别有关，因此各类旅客的延误时间阈值也不尽相同，在本算例中，各类旅客的延误时间阈值如表4所示。

表4　各类旅客的延误时间阈值

3.2签转成本阈值

各类旅客签转或取消的成本与旅客类别有关，假设旅客所能忍受的最长延误时间为12h。在本算例中，各类旅客的签转成本阈值及最大等待签转时间阈值如表5所示。

表5　各类旅客的签转成本阈值

3.3旅客推荐结果分析

若某航班发生延误后，目前航空公司的旅客恢复一般是按受扰顺序直接顺延恢复旅客。按此方案恢复旅客流的性能指标如表6所示。

表6　随机恢复方案性能指标

采用本文的旅客流恢复模型进行旅客推荐恢复后的性能指标如表7所示。

表7　旅客流恢复方案性能指标

由上述两表对比可发现，经过调整的旅客恢复方案的旅客平均调配成本为3256元。如果在不正常航班发生后，采用随机恢复受扰旅客行程所产生的平均延误成本为6499元，优化前后旅客恢复的平均调配成本降低了3243元。

签转至本航空公司航班的旅客特点：本航空公司航班的延误时间在旅客的延误时间阈值内，且未超过其最大签转等待时间；签转至其他航空公司航班的旅客特点：本航空公司航班的延误时间超过旅客的延误时间阈值，但未超过其最大签转等待时间。每次签转均依据旅客优先级，优先签转的旅客是待签转旅客中具有较低签转成本的旅客类，或者是同类中具有较高经济价值的旅客。而取消航班的旅客特点则是航班延误时间已超过旅客的最大签转等待时间，或者其取消成本较签转成本小。

4结语

本文研究了航空公司在不正常航班发生时，受扰旅客的行程恢复问题。考虑了旅客经济价值、飞机容量限制、旅客类别和团体购票等因素，同时对航班延误损失成本进行细分。尤其是还考虑了隐性成本损失，并构建了旅客流恢复模型，以及适用于此模型的求解算法，对旅客流恢复问题进行了精确求解。通过算例验证了运用本文模型及算法，航空公司可以取得优化的、可行的、经济的旅客流恢复方案，使得经济损失最小的同时获得良好口碑。

参考文献

[1] 龙继林,刘光才.我国中小航空公司未来成长的必然选择[J].经济问题探索,2012(7):163-168.

[2]ClarkeMDD.Developmentofheuristicproceduresforflightreschedulingintheaftermathofirregularairlineoperation[D].MassachusettsInstituteofTechnology,1998.

[3]BarnhartC,KnikerTS,LohatepanontM.Itinerary-basedairlinefleetassignment[J].TransportationScience,2002,36(2):199-217.

[4]BratuS,BarnhartC.Ananalysisofpassengerdelaysusingflightoperationsandpassengerbookingdata[J].AirTrafficControlQuarterly,2005,13(1):1-28.

[5]JafariN,ZegordiSH.Simultaneousrecoverymodelforaircraftandpassengers[J].JournaloftheFranklinInstitute,2011,48(7):1638-1655.

[6]BisaillonS,CordeauJF,LaporteG,etal.Alargeneighborhoodsearchheuristicfortheaircraftandpassengerrecoveryproblem[J].AQuarterlyJournalofOperationsResearch,2011,9(2):139-157.

[7]PetersenJD,SölvelingG.Anoptimizationapproachtoairlineintegratedrecovery[J].TransportationScience,2012,46(4):482-500.

[8] 赵秀丽.航空公司不正常航班恢复模型及算法研究[D].南京:南京航空航天大学,2010.

[9] 陆宏兰.基于旅客行程的飞机航班一体化恢复研究[D].南京:南京航空航天大学图书馆,2010.

[10] 高强,严俊,陆宏兰.不正常航班旅客流恢复方法[J].科学技术与工程,2011,27(11):6670-6673.

[11] 严俊,高强,吴桐水,等.航班计划恢复中旅客流恢复问题的研究[J].交通信息与安全,2012,30(1):20-23.

[12] 王莹,朱金福.不正常航班和旅客行程恢复问题研究[D].南京: 南京航空航天大学,2013.

[13] 顾欣,李明楚.非正常航班的成本研究与分析[D].大连:大连理工大学,2013.

[14] 李雄,刘光才,颜明池,等.航班延误引发的航空公司及旅客经济损失[J].系统工程,2007,25(12):20-23.

[15] 邱皓政.潜在类别模型的原理与技术[M].北京:教育科学出版社,2008.

[16]SantiagoIglesias-Pradas,FélixPascual-Miguel.Barriersanddriversfornon-shoppersinB2Ce-commerce:Alatentclass:exploratoryanalysis[J].ComputersinHumanBehavior,2013,29(2):314-322.

[17]GoodmanLA.Exploratorylatentstructureanalysisusingbothidentifiableandunidentifiablemodels[J].Biometrika,1974,61(2):215-231.

ON PASSENGERS FLOW RESTORING METHOD FOR IRREGULAR FLIGHTS

Gu ZhaojunAn YiranPan Jie

(School of Computer Science and Technology,Civil Aviation University of China,Tianjin 300300,China)

AbstractAs the phenomenon in complaints and disputes caused by irregular flights getting increasingly worse and aiming at the actual demands of airlines in restoring the journey of the affected passengers, we proposed a passengers class-based passenger flow restoring model, which is targeted at minimising the cost of loss in restoring passengers journey, and presented the solutions applicable to the model as well. Using this model, the airlines can determine the priority of passengers to get the prior restoring sequence for passengers, this lowers the economical loss of the irregular flights, and gains good reputation on brand as well. Experimental results proved the practicality and effectiveness of the model. The airlines can quickly get optimised, feasible and economical passenger flow restoring solutions.

KeywordsFlights delayPassengers flow restoringPassenger classificationSort algorithm

收稿日期：2014-12-18。中国民航局科技项目(MHRD201128)；中央高校基本科研业务费中国民航大学专项(3122013C004)；中国民航大学科研启动项目(2013QD24X)。顾兆军，教授，主研领域：网络与信息，搜索引擎，民航信息系统。安一然，硕士生。潘杰，硕士生。

中图分类号TP311

文献标识码A

DOI:10.3969/j.issn.1000-386x.2016.06.020