技术领域
本发明属于空中飞行线路技术领域，具体涉及一种不正常航班一体化智能恢复方法。
背景技术
随着交通工具的换代升级，飞机出行已经成为了一种主流选择。然而由于较为苛刻的飞行条件，航班延误概率成了除价格外旅客选择该出行方式的主要考虑因素之一。2019年民航行业发展统计公报显示，全国客运航空公司共执行航班461.11万班次，其中正常航班376.52万班次，平均航班正常率仅有81.65％，平均延误时间为14分钟。大多数情况下，突发事件难以避免，其导致的不正常航班在损害旅客利益的同时也损害了航司的声誉和经济效益。因此在突发事件后对航空公司的所有相关资源(航班、飞机和机组)以及受影响的旅客进行科学、快速、有效的恢复具有很大的研究价值和社会意义。
目前，大多数国内航空公司仍旧通过业务人员对不正常航班及相关资源进行手动恢复。业务人员往往遵循公司惯常的恢复原则及不同恢复场景的目标凭借个人经验依次对航班、飞机、机组以及旅客计划进行调整。这种调整方式存在着一些弊端：(1)恢复方案质量不稳定。一方面，当问题规模较小时，业务人员能够根据个人经验给出相对不错的解决方案。当问题规模增加时，业务人员无法通过人脑统筹考虑上千条航班的恢复，容易出现局部最优，如部分航班得到较快恢复但有更多航班面临取消风险。另一方面，业务人员通常情况下是按序恢复各个资源，因此无法考虑到各个资源之间的恢复相关性，导致前阶段制定的航班恢复方案留给后续资源的恢复余地很小。另外，由于人员的专业知识和工作经验存在差异，不同人员对同一个突发事件的处置结果差异很大。(2)方案制定耗时久。人工制定方案耗时较长。针对大规模不正常航班，手动制定方案长达6-8小时，导致错过不正常航班恢复的最佳时间，增加了航班的总延误时长和取消率。(4)个性化程度低下。对于不同的恢复场景，通常有不同的恢复目标和要求。人工调整能够在不违背总体恢复目标的情况下进行调整，但无法有效回应更细化的需要从全局考虑的要求，比如对不同恢复方式的偏好等。
发明内容
鉴于以上存在的技术问题，本发明用于提供一种不正常航班一体化智能恢复方法，通过建立优化模型和设计优化算法等技术手段，能在短时间内提供大规模不正常航班的一体化恢复方案。
为解决上述技术问题，本发明采用如下的技术方案：
一种不正常航班一体化智能恢复方法，包括以下步骤：
进行航班相关数据采集输入，模型/算法参数配置和恢复场景配置；
建立飞机路径恢复、机组排班恢复和旅客行程恢复的混合整数模型并使用以列生成为核心的算法进行求解；
根据计算结果输出航班、飞机、机组的调整计划以及旅客的恢复计划，并根据执行情况统计各类评估指标。
优选地，航班相关数据采集输入具体包括将与航班恢复相关的航班相关数据转化为需要的数据格式以供后续模型和算法使用，所述航班相关数据包括飞机信息、机型信息、机场信息、航线信息、航班信息、机组人员信息和基础维修计划信息。
优选地，模型/算法参数配置具体包括对算法模型中的相关参数进行配置从而调整想获得的恢复方案的求解偏好，包括罚分类和限制类两类，其中罚分类指各种恢复措施的额罚分；限制类则指不同航空公司和机场的各类运营限制。
优选地，恢复场景配置指将实际的恢复场景转化为对具体航班、飞机或者机场的设置。
优选地，构建飞机路径恢复的整数规划模型并运用以列生成为核心的分支定价法进行求解，计算流程如下：
步骤101，在历史飞机路径的基础上结合启发式算法或随机深度优先搜索算法得到初始飞机路径集合，同时设定第一步长ε
步骤102，求解飞机路径恢复模型，其中A表示可用飞机的集合，I表示旅客行程的集合，R表示飞机可选路径的集合，L表示所有航段的集合，模型的目标函数为：
目标函数中
模型包括以下三个约束条件：
其中Itin(i)表示行程i包含的航段集合，第一个约束保证了每一架飞机都被安排给一个路径；第二个约束表示每个航班必须被包含在飞机路径中执行，否则被取消；第三个约束结合目标函数保证如果某行程i的一个航班被取消，则该行程被取消；
步骤103，判断当前解是否为整数解，如果不是执行步骤104，否则退出，获得新的飞机路径调整计划和航班调整计划；
步骤104，判断有哪些
步骤105，对于
步骤106，求解模型主问题的线性松弛解；
步骤107，判断是否有可行解，如果有可行解则执行步骤108，否则更新
步骤108，比较固定路径航班前后两次线性松弛解，判断其目标值是否变大，如果目标值变大，则执行步骤109，否则返回步骤103；
步骤109，采用飞机路径恢复列生成算法为每个飞机找到更优的路径r
优选地，所述飞机路径恢复列生成算法的计算过程如下：
步骤1091，根据需求构建航班连接网络，该网络被用于飞机路径子问题，为每一架飞机构建起点和终点，网络中剩下的点代表不同的飞机任务，网络中的弧代表可行的飞机任务连接，点集被表示为N
步骤1092，初始化所有点的标签，将出发点设置为0，将其他点设置为空；
步骤1093，按照拓扑排序依次遍历每一个点i∈N
步骤1094，对于点i的后续集合S(i)中的点j，根据i和j(j∈S(i))两个事件点之间的关系进行占优判断，从而对j的子结点集合进行更新，更新完毕则返回步骤1093；
步骤1095，根据上一轮模型主问题的对偶变量的值计算出可行的所有路径的检验数，选出检验数，即飞机路径成本最小的一条路径，若检验数小于0，则该条路径被采用。
优选地，构建机组排班恢复的整数规划模型并运用以列生成为核心的分支定价法进行求解，计算过程如下：
步骤201，在历史机组排班计划的基础上结合启发式算法或随机深度优先搜索算法得到初始机组排班计划集合，同时设定第二步长ε
步骤202，求解机组排班恢复模型，其中k表示可用机组的集合，p表示机组可选排班计划的集合，模型的目标函数为：
目标函数中
模型包括以下三个约束条件：
其中，第一个约束保证了每一个机组都被指派一个排班计划；第二个约束表示每个航班必须被包含在机组排班计划中执行，否则被取消；第三个约束结合目标函数保证如果某行程i的一个航班被取消，则该行程被取消；
步骤203，判断当前解是否为整数解，如果不是执行步骤204，否则退出，获得新的机组排班计划；
步骤204，判断有哪些
步骤205，对于
步骤206，求解模型主问题(主问题)的线性松弛解；
步骤207，判断是否有可行解，如果有可行解则执行步骤208，否则更新
步骤208，比较固定排班计划前后两次线性松弛解，判断其目标值是否变大，如果目标值变大，则执行步骤209，否则返回步骤203；
步骤209，列生成算法为每个机组找到更优的排班计划p
优选地，所述机组排班恢复列生成算法的计算过程如下：
步骤2091，根据需求构建航班连接网络，该网络被用于机组排班子问题，为每一个机组构建起点和终点，网络中剩下的点代表机组的任务，点集被表示为N
步骤2092，初始化所有点的标签，将出发点设置为0，将其他点设置为空；
步骤2093，按照拓扑排序依次遍历每一个点i∈N
步骤2094，对于点i的后续集合S(i)中的点j，根据i和j(j∈S(i))两个事件点之间的关系进行占优判断，从而对j的子结点集合进行更新，更新完毕则返回步骤2093；
步骤2095，根据上一轮模型主问题的对偶变量的值计算出可行的所有路径的检验数，选出检验数，即机组排班成本最小的一条机组任务串，若检验数小于0，则该机组排班计划被采用。
优选地，构建旅客行程恢复的整数规划模型并运用以行列生成为核心的分支定价法进行求解，计算过程如下：
步骤301，得到初始行程集合；
步骤302，求解旅客行程恢复模型，它的目标函数为：
其中参数
其中，Γ(i)表示行程i的备选行程集合，Cap
步骤303，获得求解旅客行程恢复模型后的对偶变量，利用旅客行程恢复列生成算法解决备选行程子问题；
步骤304，通过检验数判断是否存在更优的旅客行程，如果存在，添加新的行程变量和对应约束到主模型中，转步骤302；否则转步骤305；
步骤305，输出旅客行程调整计划。
优选地，所述旅客行程恢复列生成算法的计算的过程如下：
步骤3031，根据需求构建航班连接网络，该网络被旅客行程生成子问题，为每一组行程受影响的旅客构建起点和终点，网络中剩下的点代表被影响的旅客的同一类行程的其它可选航班，点集被表示为N
步骤3032，初始化所有点的标签，将出发点设置为0，将其他点设置为空；
步骤3033，按照拓扑排序依次遍历每一个点i∈N
步骤3034，对于点i的后续集合S(i)，根据i和j(j∈S(i))两个事件点之间的关系进行占优判断，根据占优结果对j的子结点集合进行更新，更新完毕则返回步骤3033；
步骤3035，根据上一轮模型主问题的对偶变量的值计算出可行的所有路径的检验数，选出检验数，即旅客行程成本最小的一条备选旅客行程，若检验数小于0，则该条备选旅客行程被采用。
采用本发明具有如下的有益效果：
(1)高质量的恢复方案。该发明技术方案不囿于人工编排、经验编排的局限性，能够从全局的角度对所涉及的资源进行统筹规划，避免出现资源分配不均衡或者资源按序恢复导致的后期求解空间小的情形。据测算，该算法可降低该航司7％的延误和2％的取消，年均节省数千万元人民币。
(2)高求解速度。以列生成为基本框架的核心算法可以在较短时间内给出一套完整优质的恢复方案。以台风场景下的不正常航班恢复为例，通过调用本算法，航司的调整时间从原来的6-8小时缩减至了15分钟。
(3)高个性化程度。算法可适配丰富灵活的恢复规则、偏好设置和具体的恢复场景设置，从而提供高个性化且贴合实际的恢复方案。
(4)一方面，航空公司通过调用本算法，可以有效提高其资源利用率、对不正常航班及时做出反应从而降低航班延误率。在降低航司运营成本的同时树立良好形象以吸引潜在顾客；另一方面，能够及时恢复航班可以优化旅客的出行体验，具有一定的社会意义。
附图说明
图1为本发明实施例的不正常航班一体化智能恢复方法的步骤流程图；
图2为飞机路径恢复分支定价流程图；
图3为机组排班恢复分支定价流程图；
图4为旅客行程恢复行列生成流程图。
具体实施方式
下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
智能恢复方法分为三个主要的步骤：一、输入步骤；二、核心算法步骤；三、输出步骤。参照图1，所示为本发明实施例的不正常航班一体化智能恢复方法的步骤流程图，包括以下步骤：
进行航班相关数据采集输入，模型/算法参数配置和恢复场景配置；
建立飞机路径恢复、机组排班恢复和旅客行程恢复的混合整数模型并使用以列生成为核心的算法进行求解；
根据计算结果输出航班、飞机、机组的调整计划以及旅客的恢复计划，并根据执行情况统计各类评估指标。
航班相关数据采集输入具体包括将与航班恢复相关的航班相关数据转化为需要的数据格式以供后续模型和算法使用，所述航班相关数据包括飞机信息、机型信息、机场信息、航线信息、航班信息、机组人员信息和基础维修计划信息。具体应用实例中，飞机信息包括机号、机型、座位数、布局等；机型信息包括机型、可用架次、子机型、长短机型和最长飞行时间等；机场信息包括机场四码、机场三码、城市名、机场名、滑行时间和国际国内等；航线信息包括机型、起飞机场、落地机场、航季和飞行时间等；航班信息包括计划起终机场、计划起终时刻等；机组人员信息包括基础信息、资质和证件等。
具体应用实例中，模型/算法参数配置具体包括对算法模型中的相关参数进行配置从而调整想获得的恢复方案的求解偏好，包括罚分类和限制类两类，其中罚分类指各种恢复措施的额罚分；限制类则指不同航空公司和机场的各类运营限制。罚分类包括各类航班(飞机)恢复措施的罚分(取消、提前/延误、换机型、换飞机、调机、联程拆分/拉直、维修延误等)、机组恢复措施的罚分(置位、机组交换等)和旅客恢复措施的罚分(延误、取消、签转、降舱等)；限制类包括恢复窗口设置、最大提前时间、最大延误时间、最大取消航班数、飞机过站时间、机组中转时间、旅客中转时间、机场容量限制、过夜停机限制、机库停机限制等。
具体应用实例中，恢复场景配置指将实际的恢复场景转化为对具体航班、飞机或者机场的设置。(1)航班：设置受影响航班的可起飞时间段；进行“航班调减”或“机型调减”设置；“可调机航线”设置；是否允许连接拆分、是否允许取消/延误/提前/拉直航班(航班锁定)；(2)飞机：“飞机故障条目”设置；飞机锁定设置(该飞机计划执飞航班不可被延误、取消、提前或者换飞机)；是否允许忽略维修弱限制计划。(3)机场：机场容量限制；(4)其它：“联程航班拆分”设置；“固定航班衔接”设置；设置“自定义过站时间”；“优化过站时间不足航班”设置。(5)特征恢复场景：“台风场景设置”，包括对受台风影响的机场投入使用的时间段的设置等。
飞机路径恢复模块旨在对航班进行调整并为飞机重新安排恢复期内的航班路径，该模块同时加入了机组恢复和旅客行程恢复的考虑。航班调整支持航班取消、航班延误、飞机交换和调机等恢复方式；为飞机重新安排路径能够满足飞机的维修要求，满足机务需求。构建飞机路径恢复的整数规划模型并运用以列生成为核心的分支定价法进行求解，计算流程如下：
步骤101，在历史飞机路径的基础上结合启发式算法或随机深度优先搜索算法得到初始飞机路径集合，同时设定第一步长ε
步骤102，求解飞机路径恢复模型，其中A表示可用飞机的集合，I表示旅客行程的集合，R表示飞机可选路径的集合，L表示所有航段的集合，模型的目标函数为：
目标函数中
模型包括以下三个约束条件：
其中Itin(i)表示行程i包含的航段集合，第一个约束保证了每一架飞机都被安排给一个路径；第二个约束表示每个航班必须被包含在飞机路径中执行，否则被取消；第三个约束结合目标函数保证如果某行程i的一个航班被取消，则该行程被取消；
步骤103，判断当前解是否为整数解，如果不是执行步骤104，否则退出，获得新的飞机路径调整计划和航班调整计划；
步骤104，判断有哪些
步骤105，对于
步骤106，求解模型主问题的线性松弛解；
步骤107，判断是否有可行解，如果有可行解则执行步骤108，否则更新
步骤108，比较固定路径航班前后两次线性松弛解，判断其目标值是否变大，如果目标值变大，则执行步骤109，否则返回步骤103；
步骤109，采用飞机路径恢复列生成算法为每个飞机找到更优的路径r
为便于理解，分支定价具体流程可参见图2，其中步骤103-107为求整数解的潜水算法。其中飞机路径恢复列生成算法通过多标签最短路径实现。
具体地，飞机路径恢复列生成算法的计算过程如下：
步骤1091，根据需求构建航班连接网络，该网络被用于飞机路径子问题，为每一架飞机构建起点和终点，网络中剩下的点代表不同的飞机任务(包括不同类型的维修任务和航班任务等)，网络中的弧代表可行的飞机任务连接，点集被表示为N
步骤1092，初始化所有点的标签，将出发点设置为0，将其他点设置为空，；
步骤1093，按照拓扑排序依次遍历每一个点i∈N
步骤1094，对于点i的后续集合S(i)中的点j，根据i和j(j∈S(i))两个事件点之间的关系，构建从点i去往点j的后续子结点集合，对该集合中的每个待选点与j的所有现有子结点之间进行占优判断，即对于两个结点来说某个结点的各个标签均不差于另一个，则被认为是前者优于后者。在实际的飞机路径网络中，标签为路径成本、累计延误时间等。根据占优结果对j的子结点集合进行更新。更新完毕则返回步骤1093；
步骤1095，根据上一轮模型主问题的对偶变量的值计算出可行的所有路径的检验数，选出检验数，即飞机路径成本最小的一条路径，若检验数小于0，则该条路径被采用。
机组排班恢复是在飞机路径恢复的基础上进行的，旨在实现机组任务重排，尽可能减少和原排班计划的出入和相关的置位成本。由于飞机路径恢复过程中考虑了机组排班可行性，因此相比于传统求解方法，本算法的机组恢复部分有较大的求解空间。构建机组排班恢复的整数规划模型并运用以列生成为核心的分支定价法进行求解，计算过程如下：
步骤201，在历史机组排班计划的基础上结合启发式算法或随机深度优先搜索算法得到初始机组排班计划集合，同时设定第二步长ε
步骤202，求解机组排班恢复模型，其中k表示可用机组的集合，p表示机组可选排班计划的集合，模型的目标函数为：
目标函数中
模型包括以下三个约束条件：
其中，第一个约束保证了每一个机组都被指派一个排班计划；第二个约束表示每个航班必须被包含在机组排班计划中执行，否则被取消；第三个约束结合目标函数保证如果某行程i的一个航班被取消，则该行程被取消；
步骤203，判断当前解是否为整数解，如果不是执行步骤204，否则退出，获得新的机组排班计划；
步骤204，判断有哪些
步骤205，对于
步骤206，求解模型主问题的线性松弛解；
步骤207，判断是否有可行解，如果有可行解则执行步骤208，否则更新
步骤208，比较固定排班计划前后两次线性松弛解，判断其目标值是否变大，如果目标值变大，则执行步骤209，否则返回步骤203；
步骤209，机组排班恢复列生成算法为每个机组找到更优的排班计划p
为便于理解，分支定价具体流程可参见图3，其中步骤203-207为求整数解的潜水算法。其中机组排班恢复列生成算法通过多标签最短路径实现。
进一步的，机组排班恢复列生成算法的计算过程如下：
步骤2091，根据需求构建航班连接网络，该网络被用于机组排班子问题，为每一个机组构建起点和终点，网络中剩下的点代表机组的任务(包括航班任务、机组人员的占位和置位等)，点集被表示为N
步骤2092，初始化所有点的标签，将出发点设置为0，将其他点设置为空；
步骤2093，按照拓扑排序依次遍历每一个点i∈N
步骤2094，对于点i的后续集合S(i)中的点j，根据i和j(j∈S(i))两个事件点之间的关系，构建从点i去往点j的后续子结点集合，对该集合中的每个待选点与j的所有现有子结点之间进行占优判断。在实际的机组排班网络中，标签为机组排班成本和当前任务串结束时间等。根据占优结果对j的子结点集合进行更新，更新完毕则返回步骤2093；
步骤2095，根据上一轮模型主问题的对偶变量的值计算出可行的所有路径的检验数，选出检验数，即机组排班成本最小的一条机组任务串，若检验数小于0，则该机组排班计划被采用。
旅客行程恢复是在飞机路径恢复的基础上进行的，旨在实现旅客重安排，尽可能减少旅客行程延误，由于在飞机路径恢复模块和机组排班恢复模块中均包含估计的旅客成本，旅客行程恢复模块的解空间相对较大。构建旅客行程恢复的整数规划模型并运用以行列生成为核心的分支定价法进行求解，计算过程如下：
步骤301，得到初始行程集合；
步骤302，求解旅客行程恢复模型，它的目标函数为：
其中参数
其中，Γ(i)表示行程i的备选行程集合，Cap
步骤303，获得求解旅客行程恢复模型后的对偶变量，利用旅客行程恢复列生成算法解决备选行程子问题；
步骤304，通过检验数判断是否存在更优的旅客行程，如果存在，添加新的行程变量和对应约束到主模型中，转步骤302；否则转步骤305；
步骤305，输出旅客行程调整计划。
具体应用实例中，旅客行程恢复列生成算法的计算的过程如下：
步骤3031，根据需求构建航班连接网络，该网络被旅客行程生成子问题，为每一组行程受影响的旅客构建起点和终点，网络中剩下的点代表被影响的旅客的同一类行程的其它可选航班，点集被表示为N
步骤3032，初始化所有点的标签，将出发点设置为0，将其他点设置为空；
步骤3033，按照拓扑排序依次遍历每一个点i∈N
步骤3034，对于点i的后续集合S(i)中的点j，根据i和j(j∈S(i))两个事件点之间的关系，构建从点i去往点j的后续子结点集合，对该集合中的每个待选点与j的所有现有子结点之间进行占优判断。在实际的旅客行程网络中，标签为行程成本和累计旅客延误时间等。根据占优结果对j的子结点集合进行更新。更新完毕则返回步骤3033；
步骤3035，根据上一轮模型主问题的对偶变量的值计算出可行的所有路径的检验数，选出检验数，即旅客行程成本最小的一条备选旅客行程，若检验数小于0，则该条备选旅客行程被采用。
目前，本方法除了被应用于民航业以外还被应用于物流业，如顺丰的货运航班恢复。目前，本方法已被应用于顺丰的五个模拟实景恢复：机场容量限制、航班强制取消、飞机故障、航班调减以及台风场景。其中，货物的转运相似于乘客的重排，算法一致。针对顺丰的141个航班的60架次飞机的航线网络，算法运用效果如下表所示：
应当理解，本文所述的示例性实施例是说明性的而非限制性的。尽管结合附图描述了本发明的一个或多个实施例，本领域普通技术人员应当理解，在不脱离通过所附权利要求所限定的本发明的精神和范围的情况下，可以做出各种形式和细节的改变。
机译： 制造高度透气的智能织物的方法，以及包含织物的一体化智能伤口绷带
机译： 智能农场碳零一体化私人太阳能温室系统
机译： 一体化智能传感器灯具UVLED
