一种基于航空公司与旅客间交互的两阶段延误恢复方法

1.本发明属于航班恢复技术领域，涉及一种基于航空公司与旅客间交互的两阶段延误恢复方法。


背景技术：

2.随着国民经济的高速发展，旅客出行需求的快速增长给航空运输系统带来了巨大挑战。航班延误直接导致了旅客行程被迫取消或停滞，对其出行计划带来了巨大的负面影响，使得旅客和航空公司间因航班延误而发生的矛盾时有发生。多数情况下，旅客负面感受的来源并非航班延误事件本身，而是对于航空公司的处理和保障环节不满导致的。因此，如何高效对受扰航班及旅客进行恢复，通过调整可用资源在尽可能短的时间内完成旅客运输和时刻表恢复运行的任务，是航空公司亟需解决的难题。
3.实际运营中的航班延误恢复工作，通常由航空公司单方主持，仅针对于公司内部资源的协调与控制，以恢复经济损失最小为目标，在行程最终恢复计划后直接发布给旅客。这样的恢复方法存在如下局限：
①
旅客与航空公司间缺少信息互动，旅客仅能被动接受航空公司提供的单一恢复计划，其对于恢复方案的选择权没有得到保障。
②
这种恢复方式没有考虑到旅客意愿的异质性和随机性，难以契合真实延误环境，容易造成旅客不满情绪的滋生，流失高质量旅客，影响航空公司口碑。
4.科学技术的进步及民航信息化发展，使得旅客出行变得更加智能化。技术革新拓宽了旅客获取航班信息的渠道，也为信息交互提供了硬件条件。旅客可以通过手机app和微信公众号等平台主动搜集信息，并通过终端系统提出恢复请求。然而这些信息系统目前仅停留在发布延误信息的阶段，难以充分满足旅客对航班延误状况的知情需求，且航空公司无法实时了解旅客对于恢复计划的意愿反馈。
5.目前航班延误恢复相关研究已较为成熟，通过公开资料可查找到相关专利及学术期刊论文，包括公开号为cn112862258b的发明专利“一种考虑旅客偏好的有限理性的航班恢复方法”，公开号为cn112819317b的发明专利“一种不正常航班飞机、旅客及机务一体化恢复系统”，姜茂等发表于《华中师范大学学报(自然科学版)》2015年第49期的“基于航班延误的飞机和乘客恢复模型”，黄俊生等发表于《交通运输系统工程与信息》2018年第18期的“航班延误恢复的建模与算法研究”。
6.上述研究已基本解决了将飞机、机组与旅客一体化恢复的建模与算法问题，但缺少有效机制将旅客行程恢复方案的选择和航班延误恢复计划的制定过程相结合，没有真正发挥旅客在延误恢复中的主观能动性作用。同时在恢复过程中较少考虑不同舱位等级旅客在延误损失，舱位容量等方面的异质性，与现实延误情景存在偏差。目前航班恢复问题所涉及的算法多为启发式算法，该算法求解步骤繁琐通常难以获得精确解，因此实际应用性不强，在效率表现方面仍有较大改善空间。


技术实现要素：

7.发明目的：为了克服现有不正常航班恢复方法操作繁琐，流程固化，不能兼顾航空公司与旅客双方利益的不足，本发明提供了一种基于航空公司与旅客间交互的两阶段恢复方法，旨在充分利用信息化技术，在航空公司与旅客间信息充分沟通的基础上，动态制定和调整延误恢复方案。通过“预先制定-意愿反馈-动态调整”机制，在保证航空公司利益的前提下，使得旅客充分参与延误恢复过程，从而实现延误恢复效率和质量的提升。
8.技术方案：为了实现上述目的，本发明采用的技术方案为：
9.一种基于航空公司与旅客间交互的两阶段延误恢复方法，所述的两阶段分别为计划静态制定阶段和计划动态调整阶段，其中计划静态制定阶段包括以下步骤：
10.步骤s1、建立航班信息数据库、机场信息数据库、延误场景数据库、旅客行程数据库；获取受扰航班与旅客信息数据，分别载入航班信息数据库与旅客行程数据库；
11.步骤s2、初始化每架飞机的执飞航班，得到初始飞机路径集合；
12.步骤s3、建立计划静态制定阶段飞机航班的恢复模型minf1如下：
[0013][0014]
其中：dcf表示航班f的执行成本，包括燃油费、服务费与停机费；ccf表示航班f的取消成本；yf表示航班f是否取消；dpk表示k类旅客的单位时间价值，k＝1表示经济舱旅客、k＝2表示商务舱旅客、k＝3表示头等舱旅客；表示航班f上的k类旅客人数；表示由飞机i执行的航班f的延误时间；表示航班f是否在路径r中；其中a、r、f和k分别表示飞机的总数、路径的总数、航班的总数和旅客的类别数；将定义为决策变量,表示是否由由飞机a执行路径r；
[0015]
对恢复模型minf1进行约束：
[0016][0017][0018][0019][0020]
式(1)为航班f的飞机覆盖约束，含义为：如果航班f被取消，则包含该航班的所有路径不能被执行；反之若航班f未被取消，则有且仅有一条包含该航班的路径被有且仅有一架飞机执行；
[0021]
式(2)为飞机i的路径唯一约束，含义为：飞机a最多只能被指派一条路径；
[0022]
式(3)为航班延误时间为实际起飞时间与计划起飞时间的差值，其中指飞机a执行航班f时的实际起飞时间，tf指航班f的原计划起飞时间；
[0023]
式(4)表示决策变量的取值约束；
[0024]
步骤s4、调取航班信息数据库，基于列生成算法求解飞机与航班的恢复模型min f1，获取飞机与航班之间的对应关系生成恢复计划；
[0025]
步骤s5、识别因航班取消和衔接失败造成行程中断的受扰旅客，根据行程属性、行
程地点和时间将受扰旅客分为z个od交通流；将恢复计划与航班上的受扰旅客对应，汇总各od交通流受扰旅客恢复计划；将恢复计划以短信形式向受扰旅客发布，等待受扰旅客做出接受、退票或寻求其他恢复计划的反馈；
[0026]
恢复计划调整阶段包括以下步骤：
[0027]
步骤d1、受扰旅客做出接受、退票或寻求其他恢复计划的反馈；
[0028]
步骤d2、航空公司实时接收受扰旅客的反馈，并根据反馈完成计划动态调整阶段；将发布恢复计划信息时刻为t0，设置调整时间窗为δt，以调整时间窗δt为单位对受扰旅客做出的反馈进行调整更新；在每个调整时间窗δt结束时对接收到的反馈进行分类统计，分别表示t+δt时间窗内行程i中接受、退票和寻求其他恢复计划的k类受扰旅客的人数；
[0029]
步骤d3、针对接受恢复计划的受扰旅客，执行步骤d4；针对主动退票的受扰旅客，执行步骤d5；针对寻求其他恢复计划的受扰旅客，执行步骤d6；
[0030]
步骤d4、针对接受恢复计划的受扰旅客，按照恢复计划安排受扰旅客行程；
[0031]
步骤d5、针对主动退票的受扰旅客，将该部分受扰旅客从计划静态制定阶段的恢复计划中删除；
[0032]
步骤d6、调用旅客反馈插入算法，从可行行程集合i
fe
中搜索，找到符合剩余容量限制的可行行程，将该od流受扰旅客插入；若无可行行程可插入，则将结果向受扰旅客反馈，同时时间窗向后移动δt，返回步骤d2，直到受扰旅客接受恢复计划或退票；
[0033]
步骤d7、航空公司筛选出最终的恢复方案，以每架飞机执行的航班序列集合{f1,f2,f3,...}，旅客行程序列集合{(f1,f2),f3,...}的形式输出。
[0034]
优选的，所述计划动态调整阶段中，调整时间窗δt的长度设置遵循以下规则：
[0035]
t
edt
表示本次延误恢复工作的结束时间，为航空公司根据延误规模设置；t
cur
表示当前时间；当t
edt-t
cur
≥3h时，δt设置为1h；当t
edt-t
cur
∈(1,3)时，δt设置为30min；当t
edt-t
cur
≤1h时，δt设置为10min，且在距离t
edt
30分钟开始停止收集受扰旅客反馈，未收到反馈意愿的受扰旅客视为服从步骤d7的最终的恢复方案。
[0036]
优选的，所述计划动态调整阶段，遵循以下三项规则：
[0037]
(1)退票旅客移除机制
[0038]
在调整时间窗开始时，统计上一时间窗内各od流中选择主动退票的旅客，并将该部分旅客从原行程中删除，该部分旅客原先所处的行程被其他旅客选择；
[0039]
(2)行程优先恢复机制
[0040]
在计划动态调整阶段，较早提交反馈的旅客具有优先匹配行程的权利，且当该旅客的恢复行程锁定后，在后续调整时间窗内内，确保该部分旅客行程不变的前提下，进行其他旅客行程恢复；
[0041]
(3)随机分配行程机制
[0042]
在可行行程容量大于有改签需求的od交通流旅客总人数时，仅能满足部分旅客的改签需求，此时将随机确定改签至该行程的旅客，继续为其余旅客搜索其他可行行程。
[0043]
优选的，在执行步骤d2时，设定行程恢复的目标函数minf2如下：
[0044]
其中决策变量为0-1变量，表示由行程i分配至行程i’的k类受扰旅客人数；表示原行程i中的k类旅客总人数；delt
i'
表示行程i’的延误时间；dk、uk、ck分别表示k类旅客单位时间延误损失、意愿违背损失和行程取消损失；
[0045]
对行程恢复的目标函数min f2进行约束：
[0046][0047][0048][0049][0050]
式(5)为时间衔接约束，表示联程行程i’中后序航班的起飞时间，表示前序航班的到达时间，t
mct
表示最短中转时间，该约束表示联程旅客行程中两航班的衔接时间不得小于最短中转时间；式(6)为空间衔接约束，dep
i'2
表示行程i’中后续航班的出发机场，arr
i'1
表示行程i’中前序航班的到达机场，该约束表示联程旅客行程中后续航班的出发机场与前序航班的到达机场相同；式(7)为行程容量约束，表示航班f的k舱位最大载客量，表示行程i'中的原有k类旅客，为0-1变量，表示行程i'中是否包含航班f，该约束表示行程i'的k类旅客人数不得超过该行程中航班k舱位容量的最小值；式(8)表示变量的取值约束。
[0051]
优选的，所述的旅客反馈插入算法包括以下步骤：
[0052]
步骤i-1：调取受扰旅客的原行程i的信息，包括是否联程、行程起止地点depi与arri、原航班f预计起飞时间与到达时间和舱位等级k；若受扰旅客为直飞旅客，执行方法i-1；若受扰旅客为联程旅客，执行方法i-2；
[0053]
步骤i-2：若步骤i-11无法得到直飞的恢复行程，发送问询是否接受联程行程，接受反馈时间为t2，若受扰旅客接受，执行方法i-2，若受扰旅客不接受，则视为旅客退票；
[0054]
步骤i-3：将搜索完毕后得到的可行行程发布给受扰旅客，征求其反馈意见；
[0055]
其中，方法i-1包含以下步骤：
[0056]
步骤i-11：在步骤d7的最终的恢复方案中搜索起飞机场为depi，降落机场为arri的航班；
[0057]
步骤i-12：筛选的可行航班加入可行直飞行程集合i
df
，其中表示航班f的起飞时间按照时间次序排列；
[0058]
步骤i-13：按次序逐个检查i
df
中航班是否符合航班容量限制条件；若同一航班中该舱位等级容量不足以安排全部受扰旅客，则检查其他等级舱位容量，若满足则将该行程保留在集合i
df
中；若该行程无法容纳全部受扰旅客，则在集合i
df
中删除该行程，检查下一行程，直到所有航班搜索完毕；
[0059]
步骤i-14：输出搜索完毕后的集合i
df
；
[0060]
其中，方法i-2包括以下步骤：
[0061]
步骤i-21：在步骤d7的最终的恢复方案中搜索起飞机场为depi且的航
班，设为集合f
fea1
，降落机场为arri且的航班，设为集合f
fea2
，去除集合交集中的直飞航班；
[0062]
步骤i-22：从集合f
fea1
中搜索出第p个航班f
p
，从集合f
fea2
中搜索出第q个航班fq，检查两航班是否满足时间和空间衔接约束，将搜索到的联程航班确定为一可行行程i，完成一次搜索并循环，设可行联程行程集合为i
af
；
[0063]
步骤i-23：次序逐个检查i
af
中行程是否符合容量限制条件，联程行程中包含两段航班，需要满足改变行程的受扰旅客人数不超过两段航班容量的较小值，即∑
i,i'∈i
t
ii'
+psg
i'
≤min{cap
f1
,cap
f2
}，若航班中该舱位等级容量不足以安排全部受扰旅客，则检查其他等级舱位容量；若行程无法容纳全部受扰旅客，则在集合i
af
中删除该行程，检查下一联程行程，直到集合内所有航班搜索完毕；
[0064]
步骤i-24：输出搜索完毕后的i
af
集合。
[0065]
与现有延误恢复技术方法相比，本发明的有益效果在于：
[0066]
一方面，现有航班延误恢复方法主要可分为分阶段恢复和一体化恢复两大类。分阶段恢复将飞机、航班和旅客按顺序分开恢复，各部分独立搜索最优解，可能产生次优解甚至不可行恢复方案，导致旅客行程与航班计划的匹配失败。一体化恢复步骤繁琐，问题规模较大，对于智能算法的要求较高，在实际应用中可操作性不强。本发明提出的基于主体间交互的两阶段恢复方法不囿于人工编排的落后性，通过信息化技术平台，增强飞了机恢复与旅客行程之间的互动性，在实际延误处置场景中的实时性能更强。本方法将有利于平衡多方利益的全局恢复的实施，航空公司延误恢复工作提供战术决策支持。
[0067]
另一方面，现有恢复方法仅从航空公司利益出发，对旅客恢复意愿重视不足，旅客仅能被动接收延误恢复后的航班安排，容易滋生旅客不满，从而对航空公司长期盈利和持久发展造成负面影响。旅客作为航空业务中的主要利益来源，其出行体验感应该引起航空公司的充分重视。因此，本发明通过航空公司于旅客间信息交互反馈，使得旅客可根据自身实际需求参与航班延误恢复过程，有利于航班恢复方案充分反映航空公司与旅客双方利益诉求。此外，本发明通过旅客实时反馈动态调整和修正恢复方案，及时更新航班容量，将有限的座位提供给有切实需要的旅客，大幅缩减恢复过程中的资源浪费。
附图说明
[0068]
图1为本发明提出两阶段延误恢复方法的主流程图；
[0069]
图2为本发明中第一阶段航班恢复模型求解流程图；
[0070]
图3为本发明中旅客意愿插入式算法流程图。
具体实施方案
[0071]
为使本领域技术人员更好地理解本发明的技术方案，下面结合附图和具体实施方案对本发明作进一步详细描述。
[0072]
一种基于航空公司与旅客间交互的两阶段延误恢复方法，如图1所示，包括静态阶段和动态阶段。首先在静态阶段对延误基本情况进行判定，对飞机、航班和旅客的数量和时间信息进行整理，为后续延误恢复做好数据准备。接着以航空公司延误损失最小为目标函
数进行飞机航班恢复，得到航班恢复计划和基于此生成对应旅客行程恢复预方案，并将该方案向旅客发布。在动态阶段设置调整时间窗分类统计旅客反馈信息，并基于此以旅客延误损失最小为目标动态调整旅客行程，最终生成飞机航班和旅客行程恢复方案。
[0073]
具体而言，静态制定阶段包括以下步骤：
[0074]
s1、建立航班信息数据库、机场信息数据库、延误场景数据库、旅客行程数据库，获取受扰航班与旅客信息数据，分别载入对应数据库，配置旅客参数与模型参数；
[0075]
s3、初始化每架飞机的执飞航班，得定义飞行路径rof(routeofflight)为由同一飞机执行的，满足时间和空间衔接条件的一个或多个航班组成的路径，满足时间和空间衔接条件；
[0076]
s4、根据航空公司直接经济损失和间接经济损失之和最小为目标函数，机场容量限制和节点飞机流量平衡限制为约束条件，基于最小成本多商品网络流问题建立第一阶段飞机与航班恢复模型。第一阶段为飞机航班恢复，本质为将飞机指派给符合运行约束条件的航班上，使得延误给航空公司带来的直接经济损失和间接经济损失之和最小，即飞机路径集合的总成本最小。
[0077]
模型遵循以下假设：
[0078]
(1)恢复方法适用的大面积航班延误场景包括由于机场暂时关闭和部分飞机停止使用引发的航班延误。
[0079]
(2)不考虑航班恢复优先级，恢复过程中不区分国内航班与国际航班。
[0080]
(3)规定延误时间不可超过最长允许延误时间3小时，若航班预计延误时间超过3小时，则直接取消该航班。
[0081]
(4)考虑不同航班因飞机机型不同造成的容量限制，考虑飞机交换时的机型匹配限制。
[0082]
模型目标函数如下：
[0083][0084]
其中决策变量包括：表示是否由由飞机i执行路径r；表示航班f是否在路径r中；yf表示航班f是否取消；其中dcf表航班f的执行成本(包括燃油费、服务费与停机费等，与飞机机型有关)；ccf表示航班f的取消成本(与旅客人数和票价有关)；dpk表示k类旅客(k＝1表示经济舱旅客；k＝2表示商务舱旅客；k＝3表示头等舱旅客)的单位时间价值，表示由飞机i执行的航班f的延误时间，表示航班f上的k类旅客人数；第一阶段恢复从航空公司角度出发，为飞机重新安排执飞航班，对行程受扰旅客进行重新安排，以最小化航班延误成本、行程改签成本和行程取消成本为目标；
[0085][0086][0087][0088]
[0089]
模型共包含三个约束条件，其中式(1)为航班的飞机覆盖约束，表示如果航班被取消，则包含该航班的所有路径不能被执行；反之若航班未被取消，则有且仅有一条包含该航班的路径被有且仅有一架飞机执行；式(2)为飞机的路径唯一约束，表示每架飞机最多只能被指派一条路径，可以存在不被分配路径的飞机；式(3)表示航班延误时间为实际起飞时间与计划起飞时间的差值；式(4)表示决策变量的取值约束。
[0090]
s5、调取航班信息数据，基于列生成算法求解飞机航班恢复模型，并生成对应旅客行程恢复安排，具体包括以下步骤：
[0091]
s5-1.设置占优规则对in(r)进行初步筛选，减少模型规模。规则一：rof中飞机交换的次数应该尽可能少。规则二：考虑到延误时间应尽可能短，故起始点位于两已有航班起始点之间的rof被淘汰；
[0092]
s5-2.根据设置限制主问题(rmp)，求解rmp生成初始飞机路径集合加入fn(r)，将此时的最小成本记为初始目标值；
[0093]
s5-3.求解对偶子问题获得in(r)中的rof对总成本的减少值，将求得可行解时的总成本值与初始目标值比较，若小于目标值，则将求得的可行rof加入fn(r)；
[0094]
s5-4.反复迭代求解子问题，生成最终fn(r)。
[0095]
s5-5.生成新的飞机与航班间的对应关系即航班恢复计划，根据该计划生成对应旅客行程恢复方案。
[0096]
s6、识别因航班取消和衔接失败造成行程中断的受扰旅客，根据行程属性、行程地点和时间将旅客分为z个od流；将航班恢复计划与航班上的旅客对应，汇总各od流旅客行程恢复预方案；将该方案以短信形式向受扰旅客发布，等待旅客做出接受、退票或寻求其他恢复方案的意愿反馈；
[0097]
在恢复计划调整阶段遵循如下三项规则：
[0098]
(1)退票旅客移除机制
[0099]
在调整时间窗开始时，统计上一时间窗内各od流中选择主动退票的旅客，并将其从原行程中删除，其原先所处的行程可被其他旅客选择；比如在第个调整时间窗开始时刻，统计第时间窗内选择退票的旅客，若其原行程已被取消，则仅统计舱位和票价信息；若未被取消，则将该行程容量释放相应单位，自第个时间窗起，其他旅客可被安排至该行程；
[0100]
(2)行程优先恢复机制
[0101]
在动态调整旅客恢复行程时，较早提交反馈的旅客具有优先匹配行程的权利，且当该旅客的恢复行程锁定后，在后续调整时间窗内内，需确保该部分旅客行程不变的前提下，进行其他旅客行程恢复；比如在第个调整时间窗内，行程i1已被改签旅客占用，无剩余容量，则在调整时间窗内的旅客不得再被分配至i1行程，即使该行程符合其改签需求。
[0102]
(3)随机分配行程机制
[0103]
在可行行程容量大于有改签需求的od流旅客总人数时，仅能满足部分旅客的改签需求。此时将随机确定改签至该行程的旅客，继续为其余旅客搜索其他可行行程。比如od流z中旅客总人数为nz，可行行程i’的剩余容量为ni，ni＜nz，随机选取ni名旅客安排至行程i’，z中旅客人数减少至n
z-ni名。
[0104]
具体而言，动态调整阶段包括以下步骤：
[0105]
d1、旅客结合自身方案偏好和对推荐方案的接纳程度对推荐做出反馈；
[0106]
d2、航空公司实时接收旅客反馈意见，并根据反馈中完成第二阶段计划调整；
[0107]
将发布推荐方案信息时刻为t0，设置调整时间窗为δt，以调整时间窗为单位对旅客行程恢复方案进行调整更新。考虑到旅客查看航班延误信息的频率越接近预计起飞时间越高，其给予反馈的速度越快，将δt长度同t
cur
距离预计起飞时间t
edt
的时间间建立映射关系。当t
edt-t
cur
≥3h时，δt设置为1h；当t
edt-t
cur
∈(1,3)时，δt设置为30min；当t
edt-t
cur
≤1h时，δt设置为10min，且在距离t
edt
30分钟开始停止收集旅客反馈，未收到反馈意愿的旅客视为服从航班恢复计划对应恢复行程。
[0108]
在每个时间窗结束时对接收到的旅客反馈意见进行分类统计，在每个时间窗结束时对接收到的旅客反馈意见进行分类统计，分别表示t+δt时间窗内行程i中接受安排、主动退票和寻求其他改签方案的k类旅客人数。
[0109]
d3、针对接受恢复方案的旅客，执行步骤d4；针对主动退票的旅客，执行步骤d5；针对寻求其他方案的旅客，执行步骤d6；
[0110]
d4、按照预计划安排旅客行程，将该部分旅客恢复行程固定，该行程剩余可容纳人数不变；
[0111]
d5、将该部分旅客从第一阶段分配的恢复行程中删除，该行程剩余k舱位容量释放个单位；
[0112]
d6、以旅客延误损失最小为目标函数，建立旅客行程恢复模型。调用旅客意愿插入算法，根据旅客预计划中恢复行程的出发时间和联程情况，分别从可行行程集合i
fe
中搜索，找到符合剩余容量限制的可行插入该od流旅客；若无可行行程可插入，则将结果向旅客反馈，时间窗向后移动δt，返回步骤d2，直到旅客接受分配方案或退票；
[0113]
d7、航空公司筛选出最终恢复方案，以每架飞机执行的航班序列集合{f1,f2,f3,...}，旅客行程序列集合{(f1,f2),f3,...}的形式输出。
[0114]
步骤d5中的旅客行程恢复模型遵循如下假设：
[0115]
(1)定义受扰旅客为因航班延误造成行程衔接失败的联程旅客，以及行程中有航班被取消的旅客。
[0116]
(2)不考虑旅客在购买机票时的价格差异，默认同一航班同一座舱等级的旅客购买机票成本相同；由于升舱和降舱以恢复行程的决策均遵循旅客本人意愿，故改变舱位造成的损失不在目标函数中体现。
[0117]
(3)仅考虑直飞行程以及仅包含一次中转的联程旅客，在第一阶段恢复过程中，不为直飞旅客安排联程恢复行程，可为联程旅客安排直飞恢复行程，且无需旅客退还或支付差价。
[0118]
旅客行程恢复模型目标函数如下：
[0119][0120]
从旅客角度出发，考虑延误等待损失、意愿违背损失和行程取消损失三类恢复成本。其中决策变量为0-1变量，表示由行程i分配至行程i’的k类受扰旅客人数；表示原行程i中的k类旅客总人数；delt
i'
表示行程i’的延误时间；dk、uk、ck分别表示k类旅客单位时
间延误损失、意愿违背损失和行程取消损失；
[0121]
模型包括4个约束条件：
[0122][0123][0124][0125][0126]
式(5)为时间衔接约束，表示联程旅客行程中后序航班的出发时间与前序航班的到达时间之差不得小于旅客最短中转时间；式(6)为空间衔接约束，表示联程旅客行程中后续航班的出发机场与前序航班的到达机场相同；式(7)为行程容量约束，表示航班f的k舱位最大载客量，表示行程i'中的原有k类旅客，为0-1变量，表示行程i'中是否包含航班f，该约束表示行程i'的k类旅客人数不得超过该行程中航班k舱位容量的最小值；式(8)表示变量的取值约束。
[0127]
步骤d5中的旅客意愿插入算法包括以下步骤：
[0128]
步骤i1：调取该部分旅客的原行程i的信息，包括是否联程、行程起止地点depi与arri、原航班f预计起飞时间与到达时间和舱位等级k。若旅客为直飞旅客，执行算法i-1；若旅客为联程旅客，执行算法i-2。
[0129]
步骤i2：若i-11无法得到直飞恢复行程，发送问询是否接受联程行程，接受反馈时间为t2，若旅客接受，执行算法i-12，若旅客不接受，则视为旅客退票；
[0130]
步骤i3：将搜索完毕后得到的可行行程发布给旅客，征求其反馈意见。
[0131]
其中，直飞行程搜索算法i-1过程为：
[0132]
步骤i-11：在航班恢复计划表中搜索起飞机场为depi，降落机场为arri的航班；
[0133]
步骤i-12：筛选的可行航班加入可行直飞行程集合i
df
，按照时间次序排列；
[0134]
步骤i-13：按次序逐个检查中航班是否符合航班容量限制条件。若同一航班中该舱位等级容量不足以安排全部旅客，则检查其他等级舱位容量，若满足则将该行程保留在i
df
中；若该行程无法容纳全部旅客，则在i
df
中删除该行程，检查下一行程，直到所有航班搜索完毕；
[0135]
步骤i-14：输出搜索完毕后的i
df
集合。
[0136]
联程行程搜索算法i-2过程为：
[0137]
步骤i-21：在航班恢复计划表中搜索起飞机场为depi且的航班，设为集合f
fea1
，降落机场为arri且的航班，设为集合f
fea2
，去除集合交集中的直飞航班；
[0138]
步骤i-22：从f
fea1
中搜索出第p个航班f
p
，从f
fea2
中搜索出第q个航班fq。检查两航班是否满足时间和空间衔接约束，将搜索到的联程航班确定为一可行行程i，完成一次搜索
并循环，设可行联程行程集合为i
af
；
[0139]
步骤i-23：次序逐个检查i
af
中行程是否符合容量限制条件。联程行程中包含两段航班，需要满足改变行程的旅客人数不超过两段航班容量的较小值，即∑
i,i'∈i
t
ii'
+psg
i'
≤min{cap
f1
,cap
f2
}。若航班中该舱位等级容量不足以安排全部旅客，则检查其他等级舱位容量；若行程无法容纳全部旅客，则在i
af
中删除该行程，检查下一联程行程，直到集合内所有航班搜索完毕；
[0140]
步骤i-24：输出搜索完毕后的i
af
集合。
[0141]
本说明书中的各个实施例均采用递进的方式描述，各个实施例之间相同相似的部分互相参见即可，每个实施例重点说明的都是与其他实施例的不同之处。尤其，对于设备实施例而言，由于其基本相似于方法实施例，所以描述得比较简单，相关之处参见方法实施例的部分说明即可。以上所述，仅为本发明的具体实施方式，但本发明的保护范围并不局限于此，任何熟悉本技术领域的技术人员在本发明揭露的技术范围内，可轻易想到的变化或替换，都应涵盖在本发明的保护范围之内。因此，本发明的保护范围应该以权利要求的保护范围为准。

技术特征：
1.一种基于航空公司与旅客间交互的两阶段延误恢复方法，其特征在于，所述的两阶段分别为计划静态制定阶段和计划动态调整阶段，其中计划静态制定阶段包括以下步骤：步骤s1、建立航班信息数据库、机场信息数据库、延误场景数据库、旅客行程数据库；获取受扰航班与旅客信息数据，分别载入航班信息数据库与旅客行程数据库；步骤s2、初始化每架飞机的执飞航班，得到初始飞机路径集合；步骤s3、建立计划静态制定阶段飞机航班的恢复模型minf1如下：其中：dc
f
表示航班f的执行成本，包括燃油费、服务费与停机费；cc
f
表示航班f的取消成本；y
f
表示航班f是否取消；dp
k
表示k类旅客的单位时间价值，k＝1表示经济舱旅客、k＝2表示商务舱旅客、k＝3表示头等舱旅客；表示航班f上的k类旅客人数；表示由飞机i执行的航班f的延误时间；表示航班f是否在路径r中；其中a、r、f和k分别表示飞机的总数、路径的总数、航班的总数和旅客的类别数；将定义为决策变量,表示是否由由飞机a执行路径r；对恢复模型minf1进行约束：对恢复模型minf1进行约束：对恢复模型minf1进行约束：对恢复模型minf1进行约束：式(1)为航班f的飞机覆盖约束，含义为：如果航班f被取消，则包含该航班的所有路径不能被执行；反之若航班f未被取消，则有且仅有一条包含该航班的路径被有且仅有一架飞机执行；式(2)为飞机i的路径唯一约束，含义为：飞机a最多只能被指派一条路径；式(3)为航班延误时间为实际起飞时间与计划起飞时间的差值，其中指飞机a执行航班f时的实际起飞时间，t
f
指航班f的原计划起飞时间；式(4)表示决策变量的取值约束；步骤s4、调取航班信息数据库，基于列生成算法求解飞机与航班的恢复模型minf1，获取飞机与航班之间的对应关系生成恢复计划；步骤s5、识别因航班取消和衔接失败造成行程中断的受扰旅客，根据行程属性、行程地点和时间将受扰旅客分为z个od交通流；将恢复计划与航班上的受扰旅客对应，汇总各od交通流受扰旅客恢复计划；将恢复计划以短信形式向受扰旅客发布，等待受扰旅客做出接受、退票或寻求其他恢复计划的反馈；恢复计划调整阶段包括以下步骤：步骤d1、受扰旅客做出接受、退票或寻求其他恢复计划的反馈；步骤d2、航空公司实时接收受扰旅客的反馈，并根据反馈完成计划动态调整阶段；将发布恢复计划信息时刻为t0，设置调整时间窗为δt，以调整时间窗δt为单位对受扰旅客做
出的反馈进行调整更新；在每个调整时间窗δt结束时对接收到的反馈进行分类统计，分别表示t+δt时间窗内行程i中接受、退票和寻求其他恢复计划的k类受扰旅客的人数；步骤d3、针对接受恢复计划的受扰旅客，执行步骤d4；针对主动退票的受扰旅客，执行步骤d5；针对寻求其他恢复计划的受扰旅客，执行步骤d6；步骤d4、针对接受恢复计划的受扰旅客，按照恢复计划安排受扰旅客行程；步骤d5、针对主动退票的受扰旅客，将该部分受扰旅客从计划静态制定阶段的恢复计划中删除；步骤d6、调用旅客反馈插入算法，从可行行程集合i
fe
中搜索，找到符合剩余容量限制的可行行程，将该od流受扰旅客插入；若无可行行程可插入，则将结果向受扰旅客反馈，同时时间窗向后移动δt，返回步骤d2，直到受扰旅客接受恢复计划或退票；步骤d7、航空公司筛选出最终的恢复方案，以每架飞机执行的航班序列集合{f1,f2,f3,...}，旅客行程序列集合{(f1,f2),f3,...}的形式输出。2.根据权利要求1所述的一种基于航空公司与旅客间交互的两阶段延误恢复方法，其特征在于：所述计划动态调整阶段中，调整时间窗δt的长度设置遵循以下规则：t
edt
表示本次延误恢复工作的结束时间，为航空公司根据延误规模设置；t
cur
表示当前时间；当t
edt-t
cur
≥3h时，δt设置为1h；当t
edt-t
cur
∈(1,3)时，δt设置为30min；当t
edt-t
cur
≤1h时，δt设置为10min，且在距离t
edt
30分钟开始停止收集受扰旅客反馈，未收到反馈意愿的受扰旅客视为服从步骤d7的最终的恢复方案。3.根据权利要求2所述的一种基于航空公司与旅客间交互的两阶段延误恢复方法，其特征在于：所述计划动态调整阶段，遵循以下三项规则：(1)退票旅客移除机制在调整时间窗开始时，统计上一时间窗内各od流中选择主动退票的旅客，并将该部分旅客从原行程中删除，该部分旅客原先所处的行程被其他旅客选择；(2)行程优先恢复机制在计划动态调整阶段，较早提交反馈的旅客具有优先匹配行程的权利，且当该旅客的恢复行程锁定后，在后续调整时间窗内内，确保该部分旅客行程不变的前提下，进行其他旅客行程恢复；(3)随机分配行程机制在可行行程容量大于有改签需求的od交通流旅客总人数时，仅能满足部分旅客的改签需求，此时将随机确定改签至该行程的旅客，继续为其余旅客搜索其他可行行程。4.根据权利要求3所述的一种基于航空公司与旅客间交互的两阶段延误恢复方法，其特征在于：在执行步骤d2时，设定行程恢复的目标函数minf2如下：其中决策变量为0-1变量，表示由行程i分配至行程i’的k类受扰旅客人数；表示原行程i中的k类旅客总人数；delt
i'
表示行程i’的延误时间；d
k
、u
k
、c
k
分别表示k类旅客单位时间延误损失、意愿违背损失和行程取消损失；对行程恢复的目标函数minf2进行约束：
式(5)为时间衔接约束，表示联程行程i’中后序航班的起飞时间，表示前序航班的到达时间，t
mct
表示最短中转时间，该约束表示联程旅客行程中两航班的衔接时间不得小于最短中转时间；式(6)为空间衔接约束，dep
i'2
表示行程i’中后续航班的出发机场，arr
i'1
表示行程i’中前序航班的到达机场，该约束表示联程旅客行程中后续航班的出发机场与前序航班的到达机场相同；式(7)为行程容量约束，表示航班f的k舱位最大载客量，表示行程i'中的原有k类旅客，为0-1变量，表示行程i'中是否包含航班f，该约束表示行程i'的k类旅客人数不得超过该行程中航班k舱位容量的最小值；式(8)表示变量的取值约束。5.根据权利要求4所述的一种基于航空公司与旅客间交互的两阶段延误恢复方法，其特征在于，所述的旅客反馈插入算法包括以下步骤：步骤i-1：调取受扰旅客的原行程i的信息，包括是否联程、行程起止地点dep
i
与arr
i
、原航班f预计起飞时间与到达时间和舱位等级k；若受扰旅客为直飞旅客，执行方法i-1；若受扰旅客为联程旅客，执行方法i-2；步骤i-2：若步骤i-11无法得到直飞的恢复行程，发送问询是否接受联程行程，接受反馈时间为t2，若受扰旅客接受，执行方法i-2，若受扰旅客不接受，则视为旅客退票；步骤i-3：将搜索完毕后得到的可行行程发布给受扰旅客，征求其反馈意见；其中，方法i-1包含以下步骤：步骤i-11：在步骤d7的最终的恢复方案中搜索起飞机场为dep
i
，降落机场为arr
i
的航班；步骤i-12：筛选的可行航班加入可行直飞行程集合i
df
，其中表示航班f的起飞时间按照时间次序排列；步骤i-13：按次序逐个检查i
df
中航班是否符合航班容量限制条件；若同一航班中该舱位等级容量不足以安排全部受扰旅客，则检查其他等级舱位容量，若满足则将该行程保留在集合i
df
中；若该行程无法容纳全部受扰旅客，则在集合i
df
中删除该行程，检查下一行程，直到所有航班搜索完毕；步骤i-14：输出搜索完毕后的集合i
df
；其中，方法i-2包括以下步骤：步骤i-21：在步骤d7的最终的恢复方案中搜索起飞机场为dep
i
且的航班，设为集合f
fea1
，降落机场为arr
i
且的航班，设为集合f
fea2
，去除集合交集中的直飞航班；
步骤i-22：从集合f
fea1
中搜索出第p个航班f
p
，从集合f
fea2
中搜索出第q个航班f
q
，检查两航班是否满足时间和空间衔接约束，将搜索到的联程航班确定为一可行行程i，完成一次搜索并循环，设可行联程行程集合为i
af
；步骤i-23：次序逐个检查i
af
中行程是否符合容量限制条件，联程行程中包含两段航班，需要满足改变行程的受扰旅客人数不超过两段航班容量的较小值，即∑
i,i'∈i
t
ii'
+psg
i'
≤min{cap
f1
,cap
f2
}，若航班中该舱位等级容量不足以安排全部受扰旅客，则检查其他等级舱位容量；若行程无法容纳全部受扰旅客，则在集合i
af
中删除该行程，检查下一联程行程，直到集合内所有航班搜索完毕；步骤i-24：输出搜索完毕后的i
af
集合。

技术总结
本发明公开了一种基于航空公司与旅客间交互的两阶段延误恢复方法，包括静态和动态两阶段，可对航班延误恢复计划进行预先指定和动态调整。静态阶段以飞机航班为恢复对象，建立了以航空公司直接恢复成本和间接恢复成本之和最小为目标的航班恢复模型，获得飞机航班恢复恢复计划，并将该方案以推荐方案的形式发布给旅客。动态阶段基于实时接收的旅客反馈，以旅客延误损失最小为目标，对旅客行程恢复方案进行实时调整，生成最终航班与旅客恢复方案。本发明不仅能够平衡航空公司经济成本与旅客延误损失，且考虑了旅客行程恢复意愿对恢复计划制定的影响，更加契合航班延误的实际情景。具有广泛的应用前景与现实意义。具有广泛的应用前景与现实意义。具有广泛的应用前景与现实意义。


技术研发人员：邵荃 陆溪 朱培 李雅聪 张生润
受保护的技术使用者：南京航空航天大学
技术研发日：2023.03.24
技术公布日：2023/7/17