航班属性：根据航班是否为特殊保障航班、是否能协调到起落机场的时刻和是否临近起飞等特征，航空公司会对其可采取的恢复措施进行限制，包括 不可延误/不可取消/必须取消/最大可延误时长等。另外，每个航空公司会通过运行品质分析系统（不同航空公司该类系统的名称可能存在差异）对各个航班的正常率进行跟踪。若某个航班历史正常率较低，则需尽量 避免取消该航班，否则就会面临局方收回航线的风险。此外，航空公司也可以指定航班必须由哪些飞机/机型执飞。
机务相关
维修任务：调整后的航班计划需要保证飞机能够在其维修任务开始前飞到维修机场，同时也不能给它安排任何和维修时间冲突的航班。
维修任务又分为 定检和 航线维修任务两类。定检是为了保证飞机的适航性而制定的周期性检查，对设备和机务人员的要求较高，因此通常不能更换机场、更改时间或者取消。而航线维修任务主要是为了保障飞机日常运行而定的例行检查，可取消、延误或者调整到备用维修机场执行。
飞机起降次数/飞时限制：维修任务（尤其是定检）一般是按照飞行小时或者起降次数来编排的，比如波音737-300的A检间隔约为200飞行小时。由于飞机实际飞行情况的不确定性，它在临近下次维修之前的 剩余可飞行小时数（起降次数）可能会不足。此时就需要在恢复中对航班进行调减以避免其超过飞时（起降次数）上限。
机组相关
已知机组-航班的分配计划，需要保证调整后的航班计划不会对当前机组排班计划造成影响。
机组—机型匹配：保证调整过程中不会给该航班分配与执飞该航班的 机组资质不匹配的飞机。出于安全考虑，飞行员和乘务员在一天内只能飞一种机型。
机组过站：机组过站有两种情况：一种情况是执飞的两个航班被分配给同一架飞机，意味着机组不需要换机。航班计划只需要满足飞机的过站时间要求即可。另一种情况是执飞的两个航班被分配给不同的飞机。此时就需要保证这两个航班的时间间隔大于机组换机的最小过站时间，一般为2-3小时。
旅客/货物相关
旅客和货物均作为飞机可运载的实体，在限制方面具有一定的相似性。
旅客相关：
飞机座位数上限：使用了同一个航段的旅客总量不能超过被分配飞机的各舱座位数；
联程航班：保证联程航班由同一架飞机执飞；
最大签转/延误时间：保证调整后的旅客到达目的机场的时间仍在其接受范围内。
货物相关：
飞机货物容量上限：考虑不同机型可运载的货物数量上限；
货物中转时间：考虑货物在不同机场换飞机所需要的中转时间；
最晚送达时间：保证在货物的最晚送达时间之前将其运至目的地机场。
调整相关考虑
基地平衡：恢复期结束时各个机场各类机型的飞机数量需要等于后续航班在各个机场所需要的各类机型的飞机数量，以 确保恢复后航班的正常运行。
如下图所示，假设当前网络里只有两架飞机，调整窗口内只有4个航班，已知当前蓝色飞机的航班1和航班2之间过站时间不足。若不考虑机型平衡限制，为了避免航班延误可采取的措施为航班2和航班4互换飞机。仅从调整窗口内的航班网络看，这个措施是合理的。但调整完会发现，航班4和蓝色飞机原后续航班5机场无法衔接，该方案实际不可行。
指定过夜基地：航空公司也可以直接对飞机的过夜基地进行指定。这类需求通常出于以下考虑：在指定机场进行航后检查/训练或者作为次日重要航班的主备机。
航班调时/调减：如上一篇推文中所说，除了航空公司自己的原因外还有很多外部因素干扰航班的正常运行，比如天气和军事活动等。这些因素会先经过局方和机场的评估，发行正式的航行通告，再由情报席的签派员进行解析。该类信息到计划席时，一般就会被转换为更为直接的 航班调时和调减指令。这类指令有多种形式，可以指定某航班集合内必须取消一定数量的班次，也可以要求在某时段某机场的起降/起飞/降落/停场航班不能超过指定架次。后者这种形式的特殊应用场景包括机场关闭和台风等，相关航班数量会直接被限制为0。
其它：可以对 最大换机数量、航班最大延误时间、旅客最大签转时间等指标进行限制。
二、问题建模
与飞机排班问题相比，飞机航班计划恢复问题影响的时间相对较短（几个小时到几日不等），主要是为了捋顺恢复期内的航班，并确保恢复期之后的航班不受影响。
这一节我们会简单介绍两类常用的建模方式（基于弧的模型和基于路径的模型）。本篇推文里展示的这两类基础模型只考虑航班交换、取消和延误这三类恢复措施。
基于弧的模型(Arc-based Model)
此模型通常借助时空网络 [3]建立（网络中的具体要素可参考），形态与单机型的机型指派模型相似。为了将延误决策考虑到模型中，会复制多条不同延误时间的航班弧，继而在模型中进行选择。此类模型的航班连接关系决策空间大，模型复杂度和恢复方案的优度很大程度上取决于航班弧复制的粒度。
集合
A为飞机的集合；F为航班集合；Fn+和Fn-表示离开/进入节点n的航班弧集合；N为初始节点和中间节点的集合；E为调整结束时各个机场飞机的需求节点集合；I(f)是一个包含了航班f的原始航班弧和相应复制航班弧的弧集合。
参数
参数c fta是航班f的第t个复制航班弧分配给飞机a的成本，该分配成本包含了延误成本和换飞机成本；cf是航班的取消成本；Nume表示需求节点e要求的飞机数量。
变量
决策变量xfta表示航班f是否选择第t个复制航班弧且分配给飞机a，若选择则为1，否则为0；变量yan+表示节点n之后飞机a是否在该机场 ，是为1，否则为0；变量yan-表示节点n之前飞机a是否在该机场，是为1，否则为0。对于每架飞机调整开始时所在机场的初始节点，该变量直接设置为1；决策变量zf表示航班f是否被取消，被取消则为1，否则为0。
模型
式（1）为目标函数，旨在最小化总换机成本、延误成本和航班取消成本；
式（2）为航班覆盖约束，确保每个航班要么被取消，要么根据计划起飞时间或延误起飞时间执行；
式（3）表示在恢复期结束时各个机场的飞机数量等于需求数量；
式（4）确保了每个节点各个飞机的流量平衡。
基于路径的模型(Path-based Model)
对于每一架飞机来说，航班恢复就是给它重新定一条航班路径。因此很多学者以此为基本单位来构建决策模型[4]。路径模型在路径生成时便可进行可行性检查（即保证最小中转时间），并在路径生成的过程中实现部分约束和规则，从而避免将复杂约束放入模型中。与基于弧的模型相比，基于路径的模型约束数量少，但可行路径（变量）较多。方案的最优性取决于可行路径的质量，该类模型通常结合列生成计算框架进行求解。
补充标识
Ra表示可分配给飞机a的路径集合；参数car表示将飞机a分配给路径r的成本； δfr参数表示路径r是否包含航班f，如包含则为1，否则为0；决策变量xar表示飞机a是否分配给路径r，如分配则为1，否则为0。
模型
式（5）中的目标函数旨在最小化分配成本（包含换飞机和延误成本）和航班取消成本；
式（6）限制每架飞机执行的路径最多只有一条；
式（7）为覆盖约束，表示每个航班至多被一架飞机执行，若没有可用飞机，该航班被取消。
三、应用情况
我们发现航班恢复长期面临着理论和实际脱节的问题。本着学以致用的原则，团队近年来和很多航空公司展开了深入的合作。一方面希望能在实践中检验理论的有效性并挖掘新的研究方向。另一方面，想将所学真正运用于实际，为提高国内航空公司运营效率贡献力量。
系统优势
在民航领域，欧美供应商长期垄断着核心技术，想要有效推广算法，需要依托于现代化的系统平台。团队自研了一整套搭载了智能算法的航班恢复系统，主要具有以下优势：
（1）高效性
无论是手动调整还是调用算法进行智能调整，签派员都需要快速掌握当前的航班情况。系统开发的甘特图组件支持签派员 自定义展示信息，从而帮助他们快速抓取航班重点以提高决策效率。另外，甘特图 加载速度远超同类产品，能够在3秒内加载2万个航班。
面对很多恢复场景，签派员只需要确认相关航班的恢复情况即可。因此系统设计了和航班、航班预警、正常性、机场相关的近100种 快捷搜索指令，可以根据不同使用者的监控需求针对性配置甘特图的展示信息。
下图按序展示了以下搜索指令：
1、筛选计划过站不足的航班
2、筛选未按时起飞的航班
3、LC：搜索联程航班
4、ZUUU：搜索双流机场航班
相关航班在运行搜索指令后被置顶
（2）全面性
告警种类多样，包括运行规范、预计公司原因延误、机场关闭、预计延误、计划过站不足、航班不衔接、CTOT、PTOT等16种。当航班计划有任何的风吹草动，签派员都能在第一时间感知并处理。
（3）个性化
不同航空公司在不同航班干扰场景下对恢复方案会有不同的偏好。比如台风场景航空公司对取消航班的接受度会比日常高。相较于干线航空，廉航可能会更关注航班计划的收益。为了更好地兼容各种恢复偏好，系统配置了丰富的参数以供使用者调整。场景参数包含7大项，包括航班、飞机、机务、机组、旅客、收益和偏好设置，200左右个小项。
此外，系统还提供 航班回溯、方案对比、快捷手动调整（ 延误、一键顺延、换飞机、互换飞机、航班拉直、取消航班、新增航班、备降返航、新增飞机故障、新增临时维修等）、 信息维护、权限管理等基础功能。
落地情况
我们团队所研发的航班恢复智能算法目前已落地于多家航空公司。经过多年打磨，目前算法可考虑的业务因素涵盖机务、飞行、旅服等多个部门。算法输入文件多达 38类，包含各类基础数据、限制以及参数，其中仅航班数据的参数多达 51个，开放了接口以综合考虑多达 53种成本项。各航空公司的方案采纳率均 超过80%，算法能够在有效缩减预案制定时间的同时降低航班的延误率和取消率。
四、结语
本期介绍了航班恢复需要考虑的限制、基础的建模方式以及算法的应用情况。返回搜狐，查看更多