航行任务生成方法、电子设备、存储介质与流程

1.本技术涉及航空运输资源分配技术领域，尤其是涉及一种航行任务生成方法、电子设备、存储介质。


背景技术：

2.航空运输资源是指支持和保障实现航空运输的各种资源。航行任务中需要对航空运输资源作出合理分配，以使得航空运输系统尽可能发挥其作用。需要指出，对航空运输资源作出合理分配是一个较为复杂的决策问题，需要考虑航班规划、机型分配、航空运输资源分配等多方面的因素。
3.相关技术中，往往将分配航空运输资源分解成若干方面的子问题，再将这若干方面的子问题进行整合求解。航空运输资源的分配问题规模较大，数据维度多，问题复杂。目前主要思路为采用高性能的元启发式或者大规模精确式算法求解。然而，元启发式算法在求解时难以保证算法的收敛性，进而难以评价得到的决策结果的质量；另外，目标多数大规模精确式算法的各类应用，集中在对算法本身性能的提升，而非针对航空运输资源分配问题的特殊性来优化算法。因此，如何在航行任务的生成过程中，实现航空运输资源的周全调度与合理分配，仍然是业内亟待解决的一大难题。


技术实现要素：

4.本技术旨在至少解决现有技术中存在的技术问题之一。为此，本技术提出一种航行任务生成方法、电子设备、存储介质，能够在航行任务的生成过程中，实现航空运输资源的周全调度与合理分配。
5.根据本技术的第一方面实施例的航行任务生成方法，包括：
6.获取备选行程信息、航行需求信息与航行限制信息；
7.基于所述备选行程信息、所述航行需求信息与所述航行限制信息，构建资源分配模型；其中，所述资源分配模型包括资源分配主问题模型与资源分配子问题模型；
8.对所述资源分配模型进行迭代更新；每一轮迭代更新中，对所述资源分配子问题模型进行求解，并基于对所述资源分配子问题模型的求解结果更新所述资源分配主问题模型，基于更新后所述资源分配主问题模型对所述资源分配子问题模型进行更新；
9.当所述资源分配模型符合第一预设条件，基于所述资源分配模型确定资源分配策略信息；
10.基于所述资源分配策略信息生成航行任务。
11.本技术的一些实施例中，所述基于所述备选行程信息、所述航行需求信息与所述航行限制信息，构建资源分配模型，包括：
12.基于所述备选行程信息生成行程时空网络；
13.基于所述备选行程信息、所述航行需求信息，确定模型目标函数；
14.基于所述航行需求信息与所述航行限制信息，配置模型约束条件；
15.基于所述行程时空网络、所述模型目标函数与所述模型约束条件，构建得到所述资源分配模型。
16.本技术的一些实施例中，所述备选行程信息包括每一所述备选航行行程对应的起始机场、目标机场与备选航班，所述基于所述备选行程信息生成行程时空网络，包括：
17.基于每一所述备选航行行程对应的所述起始机场、所述目标机场与所述备选航班，确定多个机场节点与多个航班节点；
18.根据多个所述机场节点与多个所述航班节点，生成所述行程时空网络。
19.本技术的一些实施例中，所述基于所述行程时空网络、所述模型目标函数与所述模型约束条件，构建得到所述资源分配模型，包括：
20.基于所述行程时空网络、所述模型目标函数与所述模型约束条件，构建所述资源分配主问题模型，所述资源分配主问题模型用于确定所述备选行程信息中资源收益符合第二预设条件的备选航行行程；
21.基于所述资源分配主问题模型进行求解，得到对偶信息；
22.基于所述资源分配主问题模型与所述对偶信息，构建资源分配子问题模型，所述资源分配子问题模型用于扩充所述备选行程信息中的所述备选航行行程；
23.将所述资源分配主问题模型与所述资源分配子问题模型进行整合，得到所述资源分配模型。
24.本技术的一些实施例中，所述基于所述行程时空网络、所述模型目标函数与所述模型约束条件，构建所述资源分配主问题模型，包括：
25.对所述模型目标函数进行第一集合切割变量转换，得到主目标函数；
26.对所述行程时空网络与所述模型约束条件进行第二集合切割变量转换，生成主约束矩阵；
27.基于所述主目标函数与所述主约束矩阵，构建所述资源分配主问题模型，所述主约束矩阵用于配置所述资源分配主问题模型的可行域。
28.本技术的一些实施例中，所述基于所述资源分配主问题模型进行求解，得到对偶信息，包括：
29.对所述资源分配主问题模型进行求解，得到所述主约束矩阵中不同约束对应的多个对偶值；
30.将多个所述对偶值确定为所述对偶信息。
31.本技术的一些实施例中，所述基于所述资源分配主问题模型与所述对偶信息，构建资源分配子问题模型，包括：
32.基于所述资源分配主问题模型的主目标函数与所述对偶信息，生成子目标函数；
33.基于所述资源分配主问题模型的主约束矩阵，确定子约束矩阵；
34.基于所述子目标函数与所述子约束矩阵，构建所述资源分配子问题模型。
35.本技术的一些实施例中，所述当所述资源分配模型符合第一预设条件，基于所述资源分配模型确定资源分配策略信息，包括：
36.当所述资源分配子问题模型无法扩充资源收益更大的所述备选航行行程，确定所述资源分配模型符合所述第一预设条件；
37.基于符合所述第一预设条件的所述资源分配模型进行求解，得到所述资源分配策
略信息。
38.第二方面，本技术实施例提供了一种电子设备，包括：存储器、处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现如本技术第一方面实施例中任意一项所述的航行任务生成方法。
39.第三方面，本技术实施例提供了一种计算机可读存储介质，所述存储介质存储有程序，所述程序被处理器执行实现如本技术第一方面实施例中任意一项所述的航行任务生成方法。
40.根据本技术实施例的航行任务生成方法、电子设备、存储介质，至少具有如下有益效果：
41.本技术航行任务生成方法中，需要先获取备选行程信息、航行需求信息与航行限制信息。再基于备选行程信息、航行需求信息与航行限制信息，构建资源分配模型；其中，资源分配模型包括资源分配主问题模型与资源分配子问题模型。进一步，对资源分配模型进行迭代更新；每一轮迭代更新中，对资源分配子问题模型进行求解，并基于对资源分配子问题模型的求解结果更新资源分配主问题模型，基于更新后资源分配主问题模型对资源分配子问题模型进行更新。当资源分配模型符合第一预设条件，基于资源分配模型确定资源分配策略信息。再进一步，基于资源分配策略信息生成航行任务。需要指出，资源分配模型符合第一预设条件，意味着资源分配模型能够基于航空运输资源作出合理的资源分配策略。因此，通过符合第一预设条件的资源分配模型来确定资源分配策略信息，进而基于资源分配策略信息生成航行任务，能够在航行任务的生成过程中，实现航空运输资源的周全调度与合理分配。
42.本技术的附加方面和优点将在下面的描述中部分给出，部分将从下面的描述中变得明显，或通过本技术的实践了解到。
附图说明
43.本技术的上述和/或附加的方面和优点从结合下面附图对实施例的描述中将变得明显和容易理解，其中：
44.图1为本技术实施例提供的航行任务生成方法的流程示意图；
45.图2为本技术实施例提供的航行任务生成方法的另一流程示意图；
46.图3为本技术实施例行程时空网络的示意图；
47.图4为本技术实施例提供的航行任务生成方法的另一流程示意图；
48.图5为本技术实施例提供的航行任务生成方法的另一流程示意图；
49.图6为本技术实施例提供的航行任务生成方法的另一流程示意图；
50.图7是本技术实施例提供的电子设备的硬件结构示意图。
具体实施方式
51.下面详细描述本技术的实施例，实施例的示例在附图中示出，其中自始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元件。下面通过参考附图描述的实施例是示例性的，仅用于解释本技术，而不能理解为对本技术的限制。
52.在本技术的描述中，若干的含义是一个或者多个，多个的含义是两个以上，大于、
小于、超过等理解为不包括本数，以上、以下、以内等理解为包括本数。如果有描述到第一、第二只是用于区分技术特征为目的，而不能理解为指示或暗示相对重要性或者隐含指明所指示的技术特征的数量或者隐含指明所指示的技术特征的先后关系。
53.在本说明书的描述中，参考术语“一个实施例”、“一些实施例”、“示意性实施例”、“示例”、“具体示例”、或“一些示例”等的描述意指结合该实施例或示例描述的具体特征、结构、材料或者特点包含于本技术的至少一个实施例或示例中。在本说明书中，对上述术语的示意性表述不一定指的是相同的实施例或示例。而且，描述的具体特征、结构、材料或者特点可以在任何的一个或多个实施例或示例中以合适的方式结合。
54.本技术的描述中，需要说明的是，除非另有明确的限定，设置、安装、连接等词语应做广义理解，所属技术领域技术人员可以结合技术方案的具体内容合理确定上述词语在本技术中的具体含义。另外，下文中对于具体步骤的标识并不代表对于步骤顺序与执行逻辑的限定，各个步骤之间的执行顺序与执行逻辑应参照实施例所表述的内容进行理解与推定。
55.航空运输资源是指支持和保障实现航空运输的各种资源。航行任务中需要对航空运输资源作出合理分配，以使得航空运输系统尽可能发挥其作用。需要指出，对航空运输资源作出合理分配是一个较为复杂的决策问题，需要考虑航班规划、机型分配、航空运输资源分配等多方面的因素。
56.需要指出，正因为航空运输资源是一个较为复杂的决策问题，故而整体上解决航空运输资源分配的所有决策问题从求解难度和计算时间上均不可行。目前的一些研究中，通常会将航空运输资源分配的整体决策问题分割成不同的子问题，通过降低各子问题的求解复杂度来提高整体决策过程的求解能力。其中，航班规划问题、机型分配问题、航空运输资源分配问题是对航空运输资源分配影响重大的决策子问题。
57.具体而言，航班规划问题的主要内容是为设计航班计划表，航班计划表记录了所有开设航班的出发时间、到达时间、出发机场与到达机场；机型分配问题的主要内容是基于航班计划表来确定不同机型的飞机机队数量；航空运输资源分配问题的主要内容是决定每架飞机执行飞行任务时被分配的航节。需要指出，航空运输资源分配涉及的子问题不限于上述举例。
58.近年来，考虑到独立求解各决策问题无法得到全局决策的最优解，以及，硬件设备的算力提升和求解方法也在不断优化。针对以上各个子问题得到整合研究具有越来越强的现实意义，因此合并多个子问题的整合决策问题被认为具有重要的研究价值。
59.其一方面，目前整合多个子问题的方式，尚未能涵盖全面的现实需求以及约束，航空运输资源分配的求解结果的可靠性有限。
60.另一方面，相关技术中往往将分配航空运输资源分解成若干方面的子问题，再将这若干方面的子问题进行整合求解。航空运输资源的分配问题规模较大，数据维度多，问题复杂。目前主要思路为采用高性能的元启发式或者大规模精确式算法求解。然而，元启发式算法在求解时难以保证算法的收敛性，进而难以评价得到的决策结果的质量；另外，目标多数大规模精确式算法的各类应用，集中在对算法本身性能的提升，而非针对航空运输资源分配问题的特殊性来优化算法。因此，如何在航行任务的生成过程中，实现航空运输资源的周全调度与合理分配，仍然是业内亟待解决的一大难题。
61.本技术旨在至少解决现有技术中存在的技术问题之一。为此，本技术提出一种航行任务生成方法、电子设备、存储介质，能够在航行任务的生成过程中，实现航空运输资源的周全调度与合理分配。
62.下面依据本技术附图作出进一步说明。
63.参照图1，根据本技术实施例的航行任务生成方法，可以包括，但不限于下述步骤s101至步骤s105。
64.步骤s101，获取备选行程信息、航行需求信息与航行限制信息；
65.步骤s102，基于备选行程信息、航行需求信息与航行限制信息，构建资源分配模型；其中，资源分配模型包括资源分配主问题模型与资源分配子问题模型；
66.步骤s103，对资源分配模型进行迭代更新；每一轮迭代更新中，对资源分配子问题模型进行求解，并基于对资源分配子问题模型的求解结果更新资源分配主问题模型，基于更新后资源分配主问题模型对资源分配子问题模型进行更新；
67.步骤s104，当资源分配模型符合第一预设条件，基于资源分配模型确定资源分配策略信息；
68.步骤s105，基于资源分配策略信息生成航行任务。
69.经由步骤s101至步骤s105示出的本技术实施例中，需要先获取备选行程信息、航行需求信息与航行限制信息。再基于备选行程信息、航行需求信息与航行限制信息，构建资源分配模型；其中，资源分配模型包括资源分配主问题模型与资源分配子问题模型。进一步，对资源分配模型进行迭代更新；每一轮迭代更新中，对资源分配子问题模型进行求解，并基于对资源分配子问题模型的求解结果更新资源分配主问题模型，基于更新后资源分配主问题模型对资源分配子问题模型进行更新。当资源分配模型符合第一预设条件，基于资源分配模型确定资源分配策略信息。再进一步，基于资源分配策略信息生成航行任务。需要指出，资源分配模型符合第一预设条件，意味着资源分配模型能够基于航空运输资源作出合理的资源分配策略。因此，通过符合第一预设条件的资源分配模型来确定资源分配策略信息，进而基于资源分配策略信息生成航行任务，能够在航行任务的生成过程中，实现航空运输资源的周全调度与合理分配。
70.一些实施例的步骤s101中，获取备选行程信息、航行需求信息与航行限制信息。备选行程信息指的是可供选择的、航行行程信息。其中，备选行程信息可以包括多个备选航行行程，每个备选航行行程包括对应的起始机场、目标机场与备选航班。
71.一些较为具体的实施例中，起始机场可以从机场a1、机场a2、机场a3中选择，目标机场也可以从机场a1、机场a2、机场a3中选择，应理解，起始机场与目标机场一般不会是同一个机场。另外，备选航班可以包括航班f1、航班f2、航班f3、航班f4、航班f5、航班f6。因此，可供选择的备选航行行程可以包括，但不限于：从机场a1搭乘航班f1到机场a2、从机场a1搭乘航班f2到机场a2、从机场a1搭乘航班f4到机场a3、从机场a2搭乘航班f3到机场a3、从机场a3搭乘航班f5到机场a2、从机场a3搭乘航班f6到机场a2，等各种各样的备选航行行程。
72.需要说明的是，由于现有技术中整合航空运输资源分配的多个子问题的方式，尚未能涵盖全面的现实需求以及约束，航空运输资源分配的求解结果的可靠性有限。为解决这一问题，本技术可以通过覆盖更多的现实需求与现实约束，来构建用于确定资源分配策略信息的资源分配模型，以提升资源分配策略信息的现实意义。需要指出，以上提到的现实
需求即为航行需求信息；现实约束即为航行限制信息。
73.一些较为具体的实施例中，航行需求信息可以包括，但不限于：飞机服务航班的行程需求、选择性开设的航班需求、飞机服务航班的盈利水平需求、上下游航班的时间连续性需求、上下游航班的机场一致性需求等；
74.一些较为具体的实施例中，航行限制信息可以包括，但不限于：飞机的最大飞行时间限制、飞机的飞机数量限制、飞机服务航班的运营成本限制、飞机座位的票价等级限制、飞机的座位容量限制等。
75.在步骤s102中，基于备选行程信息、航行需求信息与航行限制信息，构建资源分配模型；其中，资源分配模型包括资源分配主问题模型与资源分配子问题模型。需要说明的是，资源分配模型用于整合航空运输资源分解成的若干方面的子问题，通过对资源分配模型进行求解，即可确定出资源分配的策略。
76.本技术一些示例性的实施例中，基于备选行程信息、航行需求信息与航行限制信息，可以先构建出混合整数线性规划(mixed integer linear programming,milp)模型形式的资源分配模型，然后再将资源分配模型从混合整数线性规划模型形式的资源分配模型的形式，转换成集合分割(set-partition)模型的形式。其中，集合分割模型形式的资源分配模型可以包括资源分配主问题模型与资源分配子问题模型。需要指出，本技术实施例将混合整数线性规划模型转换成集合分割模型的形式，旨在为资源分配模型的求解提供便利。
77.参照图2，本技术的一些实施例中，步骤s102可以包括，但不限于：
78.步骤s201，基于备选行程信息生成行程时空网络；
79.步骤s202，基于备选行程信息、航行需求信息，确定模型目标函数；
80.步骤s203，基于航行需求信息与航行限制信息，配置模型约束条件；
81.步骤s204，基于行程时空网络、模型目标函数与模型约束条件，构建得到资源分配模型。
82.在步骤s201中，基于备选行程信息生成行程时空网络。需要强调的是，备选行程信息可以包括多个备选航行行程，每个备选航行行程包括对应的起始机场、目标机场与备选航班。
83.需要说明，时空网络中不同网络成员的属性会具有时间和空间的变化趋势，因此时空网络可以应用于描述备选航行行程的基本网络形式。本技术使用的时空网络连接形式中，节点用于描述飞机的起始机场、目标机场或者备选航班，弧段用于描述连续两个节点间的可行连接，需要指出，弧段既可以连接机场节点与航班节点，又可以连接航班节点和航班节点。需要明确，行程时空网络指的是用于描述备选航行行程的时空网络。
84.本技术的一些实施例中，备选行程信息包括每一备选航行行程对应的起始机场、目标机场与备选航班，步骤s201具体可以包括，但不限于：
85.基于每一备选航行行程对应的起始机场、目标机场与备选航班，确定多个机场节点与多个航班节点；
86.根据多个机场节点与多个航班节点，生成行程时空网络。
87.参照图3，一些更为具体的实施例中，可供选择的备选航行行程通过行程时空网络的方式加以呈现。图3示出了备选航行行程对应的行程时空网络，其中基于机场a1、机场a2、
机场a3这三个机场形成了三个机场节点a1、a2、a3。另外，基于航班f1、航班f2、航班f3、航班f4、航班f5、航班f6这六个航班，形成了六个航班节点f1、f2、f3、f4、f5、f6。通过机场节点与航班节点之间的箭头指向，表明可供选择的备选航行行程。例如，从机场a1搭乘航班f1到机场a2，在图3中表示为：箭头由机场节点a1指向航班节点f1，另一箭头再由航班节点f1指向机场节点a2。应理解，其他备选航行行程的表示方式可以与上述举例一致，在此不一一赘述。
88.在步骤s202至步骤s203中，基于备选行程信息、航行需求信息，确定模型目标函数，并基于航行需求信息与航行限制信息，配置模型约束条件。需要说明，基于备选行程信息、航行需求信息与航行限制信息，可以先构建出混合整数线性规划模型形式的资源分配模型，然后再将资源分配模型从混合整数线性规划模型形式的资源分配模型的形式，转换成集合分割模型的形式。需要指出，混合整数线性规划模型形式的资源分配模型中，对应的目标函数即为模型目标函数，对应的约束条件即为模型约束条件。
89.针对混合整数线性规划模型作出的说明：在解释混合整型线性规划模型之前，需要介绍一下线性规划模型(linear programming,lp)。应理解，任何一个优化问题都可以划分成目标与约束两个部分。当这两个部分都是线性的时候，就可以称这个问题是一个线性规划问题，而针对线性规划问题求解的模型即为线性规划模型。线性规划模型的定义比较简单，它指的就是目标函数是线性的，所有约束也是线性的，最后，决策变量可以取任何的实数。进一步，如果在线性规划问题中有部分决策变量要求必须是整数，那么这时的规划问题就转变成混合整数线性规划问题了，也即说优化问题不止有条件约束，还有整数约束。
90.需要强调的是，资源分配模型用于整合航空运输资源分解成的若干方面的子问题，通过对资源分配模型进行求解，即可确定出资源分配的策略。一些实施例中，将资源分配模型用于确定出资源分配的策略，旨在确定出资源收益较高的备选航行行程，因此模型目标函数则能够以最大化利润为目标来确定模型目标计算项。
91.本技术一些较为具体的实施例中，为了涵盖较为全面的现实需求以及约束，针对资源分配模型可以从以下航行需求信息或者航行限制信息选择模型构建的考虑因素：
92.(1)飞机可用性约束
93.在飞机排班过程中，指定执行航班的飞机必须在出发时间之前位于出发机场待命，且一架飞机不可以执行两个飞行时间段存在重叠的航班，此时确定飞机在指定航班起飞之前处于可用状态；
94.(2)航班连续性约束
95.飞机执行连续航班时，前序航班的到达机场与后序航班的出发机场一致，且基于不同机型的过站时间要求，前序航班的到达时间与后序航班间的时间差必须大于等于飞机完成一次过站作业所需花费的最短时间，同时某航班被指派时，当前航班一定会存在前序航班(或首班航班)和后序航班(或末班航班)；
96.(3)流量一致性约束
97.在任何时刻下，处于整个航空运输资源分配系统中的飞机总数恒定，被任何航班指派的飞机数量有且只有一架；
98.(4)基地一致性约束
99.飞机具有基地属性，在完成所有航班任务后必须返回基地，即该飞机的首班航班
的出发机场与末班航班的到达机场一致；
100.(5)机型系列
101.机型是指具有相同驾驶舱配置、相同机组人员等级、相同驾驶舱容量和相同运营成本的机队集合；而机型系列是机型的集合；需要指出，机型系列中存在各种各样的机型，这些机型基于相同驾驶舱配置和机组人员等级而可以在机型系列中聚合成不同的组别。需要说明，机组人员通常在接受训练后，可以驾驶系列中的任何型号的飞机。在向航班指派某种型号的飞机时，可以优先选择向航班指派某种型号的机型系列，然后再分配某种型号的飞机服务、当前机型系列的航班任务，进而可以提升飞机间的替代能力，减少因飞机数量不足而产生的空飞任务。需要强调，将机型系列作为构建资源分配模型的考量因素，目的在于，当向航班指派飞机时，得以将传统的向航班指派机型的方式改进为向航班指派机型系列的方式，以使得机型系列的指派优先级大于机型的指派优先级，因此提升了不同机型间的互相替代性。在应对不确定性扰动时，可以在某种型号飞机机队数量不足或机型能力不足的情况下，用同一机型系列的其他机型进行替换。
102.(6)选择性飞行
103.一些情况下，基于航班运营淡季和旺季的航班需求量差异，部分营运航班会选择性开设。选择性飞行的存在提供了更灵活的路线选择方式，也可以对航班运输任务的不确定性影响起到缓冲作用。
104.(7)计算时间线
105.考虑到不同机型的机队规模固定，因此同一时刻系统内使用的各型号飞机数量不能超过该型号机队规模，而飞机总数量包括执行飞行任务的属于航班集合的飞机数量和不执行飞行任务的处于地面弧段集合的飞机数量。为了控制飞机数量一致，需要增加航班飞机与地面弧段飞机间的转换关系，使飞机总数量保持恒定。在模型中刻画飞机数量时，需要同时考虑飞机的起飞状态和落地停留状态，才能获取具体的各机型机队数量，而计算时间线的加入可以保证同一时刻各类型飞机的使用数量不会超过该类型的机队规模。
106.(8)空飞任务
107.由于各机场处停靠的机队数量不一定能完全满足当前机场的飞行任务，所以当部分航班因飞机数量不足而无法完成飞行任务时，可以从附近机场调取飞机执行空飞任务，在航班出发时间之前到达该机场，并执行当前航班的飞行任务。空飞任务提供了飞机服务一条不完全符合从当前飞机基地出发，到当前飞机基地位置结束的飞行任务航节，飞机可以在完成飞行任务的过程中选择执行空飞任务，前往其他机场执行航班任务，进而产生相应的空飞成本。
108.(9)最大连续飞行时间
109.一般情况下，指派飞机服务行程需求时，考虑到飞行的安全性，飞机在完成一天内的连续航班任务时存在飞行时间限制，飞机执行连续航班任务时，最大的连续飞行时间不能超过最大连续飞行时间。这条约束在飞机服务更多航班的收益性与飞机因执行飞行任务而产生安全隐患之间进行权衡。
110.(10)行程需求
111.航班不同票价等级的行程服务会产生不同的需求，通过对各类行程需求的满足，可以获得相应的票价收益。因此，航空运输资源分配时将会期望尽可能服务更多的不同票
价下的行程需求，而服务能力与指派飞机的机型对应票价容量与行程的需求量相关，因此投放的飞机机型具备的各票价行程服务能力直接决定了资源收益的水平。
112.(11)运营成本
113.将飞机投入服务以解决行程需求时，会根据飞机执行飞行任务时被指派的航班产生相应的运营成本。通常飞机的运营成本与飞机的飞行时间呈正相关，也可能与飞机运营产生的维修成本等相关，运营成本决定了当前航班满足市场需求后是否对企业产生盈利情况。
114.一些更为具体的实施例中，资源分配模型建立所涉及的相关变量可以包括，但不限于下述提及的变量。
115.其一，资源分配模型涉及的变量存储集合如表1所示：
[0116][0117][0118]
表1
[0119]
其二，模型涉及的参数如表2所示：
[0120][0121]
表2
[0122]
其三，模型涉及的决策变量如表3所示：
[0123][0124]
表3
[0125]
进一步，在明确以上各个参数含义的基础上，混合整数线性规划模型形式的资源分配模型可以表示为表4：
[0126][0127][0128]
表4
[0129]
表4中，包括模型目标函数(1)以及模型约束条件(2)-(19)。
[0130]
模型目标函数(1)为模型目标计算项，模型以最大化利润为目标，考虑了通过满足市场不同票价等级下的乘客行程需求获得的票价收益，飞机营运航班产生的运营成本和飞机空飞产生的惩罚成本。考虑到两个成本项量纲一致，因此不需要增加权重系数；
[0131]
模型约束条件(2)-(5)用于描述机型系列、机型与飞机三种单元间支配关系的相关约束，机型系列作为支配项，优先向航班指派，基于航班的选择性飞行属性，为必须执行的航班指派一个机型系列，选择性执行的航班最多只能指派一个机型。完成机型系列指派后向被指派机型系列的航班选择一个机型执行任务，并从机型中选择一架飞机执行任务，
进而将飞行单元向下调整至飞机，追踪每一架飞机的飞行状态；
[0132]
模型约束条件(6)-(7)用于描述飞机的飞行能力约束，其中(6)用于描述飞机的最大连续飞行时长约束，即该飞机服务的航班任务航节所花费的飞行时间之和不能超过最大连续飞行时长，(7)用于描述飞机的最大连续作业时长约束，包括飞机的航班飞行时间与飞机的连续航班间过站时间；
[0133]
模型约束条件(8)-(10)用于描述机场流量约束，其中(8)控制每个机场的最大出度,约束(9)控制每个机场的最大入度，约束(10)用于描述机场出入度流量平衡，流量约束用于控制每个航班有且仅有一个出发机场和到达机场；
[0134]
模型约束条件(11)-(12)用于描述连续航班间连续性约束，即当某航班被指派时，该航班一定存在连续的前序航班和后序航班，连续性约束保证了一条航行行程的顺利运行，避免模型结果中出现航班中断或上下游航班时间、机场不匹配的情况发生；
[0135]
模型约束条件(13)用于表示飞机在各航班处的空飞任务和飞行任务最多只能执行一个，保证同一时间飞机最多只能执行一种飞行任务，即多种飞行任务间不存在交集；
[0136]
模型约束条件(14)用于描述连续航班间的时间连续性约束，即后序航班的出发时间必须考虑前序航班的出发时间、飞行时间与过站时间的总时间花费，保证上下游航班关系符合业务需求；
[0137]
模型约束条件(15)用于描述机队规模的数量约束，即在计算时间线上每种机型的总数量不能超过该机型的机队规模；
[0138]
模型约束条件(16)-(17)用于描述各行程的乘客接受水平，约束(16)表示经过该航班的各行程接受总人数不能超过分配给该航班的机型总容量，约束(17)表示行程接受总人数不能超过该行程的需求量；
[0139]
模型约束条件(18)明确了x
if
,y
jt
,w
jz
,m
ijk
的取值限制；
[0140]
模型约束条件(19)明确了π
jh
的取值限制。
[0141]
在步骤s204中，基于行程时空网络、模型目标函数与模型约束条件，构建得到资源分配模型。需要说明的是，在确定了以上行程时空网络、模型目标函数与模型约束条件之后，方可进行模型构建，得到资源分配模型
[0142]
参照图4，本技术的一些实施例中，步骤s204可以包括，但不限于：
[0143]
步骤s401，基于行程时空网络、模型目标函数与模型约束条件，构建资源分配主问题模型，资源分配主问题模型用于确定资源收益符合第二预设条件的备选航行行程；
[0144]
步骤s402，基于资源分配主问题模型进行求解，得到对偶信息；
[0145]
步骤s403，基于资源分配主问题模型与对偶信息，构建资源分配子问题模型，资源分配子问题模型用于扩充备选行程信息中的备选航行行程；
[0146]
步骤s404，将资源分配主问题模型与资源分配子问题模型进行整合，得到资源分配模型。
[0147]
需要强调的是，本技术一些示例性的实施例中，基于备选行程信息、航行需求信息与航行限制信息，可以先构建出混合整数线性规划模型形式的资源分配模型，然后再将资源分配模型从混合整数线性规划模型形式的资源分配模型的形式，转换成集合分割模型的形式。其中，集合分割模型形式的资源分配模型可以包括资源分配主问题模型与资源分配
子问题模型。需要指出，本技术实施例将混合整数线性规划模型转换成集合分割模型的形式，旨在为资源分配模型的求解提供便利。
[0148]
在步骤s401中，基于行程时空网络、模型目标函数与模型约束条件，构建资源分配主问题模型，资源分配主问题模型用于确定资源收益符合第二预设条件的备选航行行程。需要说明的是，某备选航行行程的资源收益符合第二预设条件，意味着该备选航行行程对应的航空运输资源分配策略将达到预期的资源收益。
[0149]
参照图5，本技术一些较为具体的实施例中，步骤s401可以包括，但不限于：
[0150]
步骤s501，对模型目标函数进行第一集合切割变量转换，得到主目标函数；
[0151]
步骤s502，对行程时空网络与模型约束条件进行第二集合切割变量转换，生成主约束矩阵；
[0152]
步骤s503，基于主目标函数与主约束矩阵，构建资源分配主问题模型，主约束矩阵用于配置资源分配主问题模型的可行域。
[0153]
需要说明的是，为求解资源分配模型，需要将资源分配模型从混合整数线性规划模型转换成集合分割模型的形式。此过程中，需要生成资源分配主问题模型。
[0154]
将资源分配模型从混合整数线性规划模型转换成集合分割模型的形式，对应的构造思路为：将用于描述节点信息的模型变量转化为描述涵盖一组信息的变量，用新变量来描述对应的混合整数线性规划模型。通过新变量确定新模型一个列，并将变量与权值系数组合形成新模型的约束矩阵，进而基于新变量构造集合分割模型的可行域与目标函数，建立集合分割模型形式的资源分配模型。
[0155]
资源分配主问题模型可以等价为最佳行程选择问题，主要用于在各类型飞机数量限制和各航班最多只能被一条飞行行程服务的限制下，选择收益最大的航行行程集合。资源分配主问题模型中，选择的决策变量用于描述对应混合整数线性规划模型中的可行航行行程，每条航行行程的0-1选择构成主问题模型的一列，主问题模型的目标为对当前模型中包含的航行行程进行选择，使得在满足航班约束、飞机类型约束等模型约束条件的前提下，可以保证利润的最大化。
[0156]
在步骤s402中，基于资源分配主问题模型进行求解，得到对偶信息。
[0157]
本技术的一些实施例中，步骤s402具体可以包括，但不限于：
[0158]
对资源分配主问题模型进行求解，得到主约束矩阵中不同约束对应的多个对偶值；
[0159]
将多个对偶值确定为对偶信息。
[0160]
需要说明的是，求解资源分配主问题模型可以得到各约束对应的对偶变量值，即可为子问题的求解提供必要的对偶信息。
[0161]
在步骤s403中，基于资源分配主问题模型与对偶信息，构建资源分配子问题模型，资源分配子问题模型用于扩充备选行程信息中的备选航行行程。
[0162]
参照图6，本技术的一些实施例中，步骤s403具体可以包括，但不限于：
[0163]
步骤s601，基于资源分配主问题模型的主目标函数与对偶信息，生成子目标函数；
[0164]
步骤s602，基于资源分配主问题模型的主约束矩阵，确定子约束矩阵；
[0165]
步骤s603，基于子目标函数与子约束矩阵，构建资源分配子问题模型。
[0166]
需要说明的是，资源分配子问题模型可等价为最大收益行程搜索问题，在资源分
配子问题模型中，根据求解主问题得到对应约束的对偶值，可以求出为主问题模型带来节约开支的新航行行程，即主模型的新列，因此节约开支为子问题的子目标函数。同时，资源分配子问题模型构造出的航行行程需要满足对应混合整数线性规划模型中的模型约束条件，因此需要构造资源分配子问题模型的子约束矩阵。如此一来，包括子目标函数与子约束矩阵的资源分配子问题模型即可被构建出来。
[0167]
在步骤s404中，将资源分配主问题模型与资源分配子问题模型进行整合，得到资源分配模型。资源分配主问题模型与资源分配子问题模型均被构建完成后，将资源分配主问题模型与资源分配子问题模型进行整合，得到资源分配模型。
[0168]
通过步骤s401至步骤s404示出的本技术实施例，将资源分配模型从混合整数线性规划模型形式的资源分配模型的形式，转换成集合分割模型的形式，能够为资源分配模型的求解提供便利。
[0169]
在步骤s103中，对资源分配模型进行迭代更新；每一轮迭代更新中，对资源分配子问题模型进行求解，并基于对资源分配子问题模型的求解结果更新资源分配主问题模型，基于更新后资源分配主问题模型对资源分配子问题模型进行更新。需要说明的是，资源分配主问题模型用于确定资源收益符合第二预设条件的备选航行行程，需要明确，本技术对资源分配主问题模型进行更新，旨在提升资源分配主问题模型对备选航行行程的筛选能力；另外，资源分配子问题模型用于扩充备选行程信息中的备选航行行程，需要明确，本技术对资源分配子模型进行更新，旨在提升资源分配子问题模型对备选航行行程的扩充能力。需要进一步明确，资源分配主问题模型和资源分配子模型密切相关，资源分配主问题模型的求解可以为资源分配子模型提供必要的对偶信息，这些对偶信息可以作为资源分配子模型计算检验数所需的计算项；相应的，资源分配子模型的求解，可以为资源分配主问题模型提供非基变量的搜索方向，即确定资源分配主问题模型优化更新的方向；更新之后的资源分配主问题模型又可以提供新的对偶信息，来对资源分配子模型进行更新。因此，通过资源分配主问题与资源分配子模型之间的相互配合，方能持续对资源分配模型进行迭代更新，以使得资源分配模型得以持续优化，直至资源分配模型的优化程度达到预期，方可基于资源分配模型来确定资源分配策略信息。
[0170]
在步骤s104中，当资源分配模型符合第一预设条件，基于资源分配模型确定资源分配策略信息。需要说明的是，资源分配模型符合第一预设条件，意味着资源分配模型的优化程度达到预期，也即资源分配模型已经可以较为精确、合理以及周全地生成航空运输资源的分配策略。如此一来，通过符合第一预设条件的资源分配模型，即可确定出较为精确、合理以及周全的资源分配策略信息。
[0171]
本技术的一些实施例中，步骤s104可以包括，但不限于下述：
[0172]
当资源分配子问题模型无法扩充资源收益更大的备选航行行程，确定资源分配模型符合第一预设条件；
[0173]
基于符合第一预设条件的资源分配模型进行求解，得到资源分配策略信息。
[0174]
需要说明的是，列生成算法是一种用于求解大规模线性优化问题的高效算法，作为一种迭代搜索算法，其基本思路为通过求解子问题来找到可以产生检验数存在优化空间的新非基变量，并加入主模型计算新的非基变量检验数，直到当前模型达到最优状态，说明模型的最优解被发现。列生成的子问题和主问题密切相关，主问题和其对偶问题的求解可
以为子问题提供必要的对偶信息，作为子问题计算检验数的计算项。同时子问题可以为主问题提供非基变量的搜索方向，即确定主问题的优化方向。
[0175]
一些示例性的实施例中，本技术将列生成算法应用于对资源分配模型进行求解：对资源分配模型进行迭代更新，当资源分配模型符合第一预设条件，意味着资源分配模型的优化程度达到预期，也即资源分配模型已经可以较为精确、合理以及周全地生成航空运输资源的分配策略。如此一来，通过符合第一预设条件的资源分配模型，即可确定出较为精确、合理以及周全的资源分配策略信息。
[0176]
一些较为具体的实施例中，利用列生成算法对本技术资源分配模型进行求解，具体可以包括以下两大步骤：
[0177]
其一，初始解构造：基于集合分割模型形式的资源分配模型，需要确定一个初始解算法，用于得到一组航行行程作为主模型的初始列，并构成资源分配主问题模型的初始约束矩阵，进而限制资源分配主问题模型的可行域，此时资源分配主问题模型将会转化为一个规模更小的受限主模型(restricted master problem)，加快模型的运行速度。此时，受限主模型可以求解当前状态下的最优解。
[0178]
其二，子问题搜索：为了迭代更新该受限主模型，使得其找到的当前最优解向全局最优解方向移动，资源分配子问题模型基于当前受限主模型最优状态下的非基变量检验数集合，找到对主目标函数具备优化力度的非基变量组，在资源分配子问题模型中非基变量的实际意义为满足约束的航行行程。此时，如果非基变量的检验数可以对受限主模型产生优化空间，则将资源分配子问题模型产生的航行行程转换为资源分配主问题模型的一列，并将列插入到受限主模型的约束空间中。如果无法插入任何一条可以产生优化的航行行程，确定资源分配模型符合第一预设条件，意味着当前受限主模型运行找到的基变量达到模型的最优状态，可以产生全局最优解。此时终止迭代，列生成算法随即可以确定出最优的航行行程集合。如此一来，便可以基于资源分配模型确定出资源分配策略信息。
[0179]
一些更为具体的实施例中，初始解构造算法如下：
[0180]
初始解构造算法可以基于贪心策略的最优插入算法用于生成初始航行行程集合，并将航行行程集合翻译为受限主模型所需的决策变量集合和约束矩阵。基于贪心最优插入算法构造航行行程集合的过程中，需要构造一个评估函数用于评估当前插入可以带来的收益情况，进而判断当前插入位置的优劣，同时需要构造插入的可行性判断函数，用于保证构造出的航行行程满足子问题的航行行程构造约束。基于评估函数和可行性判断函数，不断循环贪心最优插入过程，直到所有的航班均被飞机服务或所有的飞机均被派出，结束循环。
[0181]
一些更为具体的实施例中，资源分配子问题模型的构造算法如下：
[0182]
列生成子问题的目标为求解满足资源分配模型约束的最大收益航行行程问题，为了达到这一目标可以选择标签设定算法，标签设定算法的原理为通过解池记录当前的所有航行行程，并不断取出池中航行行程，扩展当前航行行程并重新加入解池，直到找到目标航行行程或者无法扩展。
[0183]
由于备选的飞机集合中飞机型号不同的飞机具有不同的基地，即航行行程的构造可能由不同的出发点和到达点组成，因此子问题并非属于单车场规划问题，因此本技术设置的解池中初始航行行程由各机场的所有可行组合构成，因此子问题解池中包含的航行行程数量可能会因为指数级增长而出现维度爆炸的问题，需要设置控制规则来控制子问题的
运行时间，例如将作为贪心规则作为控制规则而采用，贪心规则即在相同出发点的航行行程包含相同航班时，以当前航班的标签值作为评价标准，只保留最优的当前航行行程。标签设置作为标签设定算法的核心步骤，目的是更新每个航班节点处的标签值，并根据控制规则确定其前驱节点。
[0184]
一些更为具体的实施例中，将资源分配子问题模型产生的航行行程转换为资源分配主问题模型的一列，具体的转换方法可以是：初始化总长为航班数量与飞机数量之和的列表，然后根据服务飞机编号和航班编号将列表中对应值修改为1。
[0185]
需要强调，本技术将列生成算法应用于对资源分配模型进行求解，在保证收敛性的同时具有更高效的求解能力，在应对大规模的航行任务规划时具备优势。
[0186]
在步骤s105中，基于资源分配策略信息生成航行任务。需要说明的是，在确定出较为精确、合理以及周全的资源分配策略信息之后，方可基于资源分配策略信息生成航行任务，通过这种方式来生成航行任务，能够实现航空运输资源的周全调度与合理分配。
[0187]
图7示出了本技术实施例提供的电子设备700。电子设备700包括：处理器701、存储器702及存储在存储器702上并可在处理器701上运行的计算机程序，计算机程序运行时用于执行上述的航行任务生成方法。
[0188]
处理器701和存储器702可以通过总线或者其他方式连接。
[0189]
存储器702作为一种非暂态计算机可读存储介质，可用于存储非暂态软件程序以及非暂态性计算机可执行程序，如本技术实施例描述的航行任务生成方法。处理器701通过运行存储在存储器702中的非暂态软件程序以及指令，从而实现上述的航行任务生成方法。
[0190]
存储器702可以包括存储程序区和存储数据区，其中，存储程序区可存储操作系统、至少一个功能所需要的应用程序。存储数据区可存储执行上述的航行任务生成方法。此外，存储器702可以包括高速随机存取存储器702，还可以包括非暂态存储器702，例如至少一个储存设备存储器件、闪存器件或其他非暂态固态存储器件。在一些实施方式中，存储器702可选包括相对于处理器701远程设置的存储器702，这些远程存储器702可以通过网络连接至该电子设备700。上述网络的实例包括但不限于互联网、企业内部网、局域网、移动通信网及其组合。
[0191]
实现上述的航行任务生成方法所需的非暂态软件程序以及指令存储在存储器702中，当被一个或者多个处理器701执行时，执行上述的航行任务生成方法，例如，执行图1中的方法步骤s101至步骤s105、图3中的方法步骤s201至步骤s204、图4中的方法步骤s401至步骤s404、图5中的方法步骤s501至步骤s503、图6中的方法步骤s601至步骤s603。
[0192]
本技术实施例还提供了计算机可读存储介质，存储有计算机可执行指令，计算机可执行指令用于执行上述的航行任务生成方法。
[0193]
在一实施例中，该计算机可读存储介质存储有计算机可执行指令，该计算机可执行指令被一个或多个控制处理器执行，例如，执行图1中的方法步骤s101至步骤s105、图3中的方法步骤s201至步骤s204、图4中的方法步骤s401至步骤s404、图5中的方法步骤s501至步骤s503、图6中的方法步骤s601至步骤s603。
[0194]
本领域普通技术人员可以理解，上文中所公开方法中的全部或某些步骤、系统可以被实施为软件、固件、硬件及其适当的组合。某些物理组件或所有物理组件可以被实施为由处理器，如中央处理器、数字信号处理器或微处理器执行的软件，或者被实施为硬件，或
者被实施为集成电路，如专用集成电路。这样的软件可以分布在计算机可读介质上，计算机可读介质可以包括计算机存储介质(或非暂时性介质)和通信介质(或暂时性介质)。如本领域普通技术人员公知的，术语计算机存储介质包括在用于存储信息(诸如计算机可读指令、数据结构、程序模块或其他数据)的任何方法或技术中实施的易失性和非易失性、可移除和不可移除介质。计算机存储介质包括但不限于ram、rom、eeprom、闪存或其他存储器技术、cd-rom、数字多功能盘(dvd)或其他光盘存储、磁盒、磁带、储存设备存储或其他磁存储装置、或者可以用于存储期望的信息并且可以被计算机访问的任何其他的介质。此外，本领域普通技术人员公知的是，通信介质通常包括计算机可读指令、数据结构、程序模块或者诸如载波或其他传输机制之类的调制数据信号中的其他数据，并且可包括任何信息递送介质。还应了解，本技术实施例提供的各种实施方式可以任意进行组合，以实现不同的技术效果。
[0195]
以上是对本技术的较佳实施进行了具体说明，但本技术并不局限于上述实施方式，熟悉本领域的技术人员在不违背本技术精神的共享条件下还可作出种种等同的变形或替换，这些等同的变形或替换均包括在本技术权利要求所限定的范围内。

技术特征：
1.一种航行任务生成方法，其特征在于，包括：获取备选行程信息、航行需求信息与航行限制信息；基于所述备选行程信息、所述航行需求信息与所述航行限制信息，构建资源分配模型；其中，所述资源分配模型包括资源分配主问题模型与资源分配子问题模型；对所述资源分配模型进行迭代更新；每一轮迭代更新中，对所述资源分配子问题模型进行求解，并基于对所述资源分配子问题模型的求解结果更新所述资源分配主问题模型，基于更新后所述资源分配主问题模型对所述资源分配子问题模型进行更新；当所述资源分配模型符合第一预设条件，基于所述资源分配模型确定资源分配策略信息；基于所述资源分配策略信息生成航行任务。2.根据权利要求1所述的方法，其特征在于，所述基于所述备选行程信息、所述航行需求信息与所述航行限制信息，构建资源分配模型，包括：基于所述备选行程信息生成行程时空网络；基于所述备选行程信息、所述航行需求信息，确定模型目标函数；基于所述航行需求信息与所述航行限制信息，配置模型约束条件；基于所述行程时空网络、所述模型目标函数与所述模型约束条件，构建得到所述资源分配模型。3.根据权利要求2所述的方法，其特征在于，所述备选行程信息包括每一所述备选航行行程对应的起始机场、目标机场与备选航班，所述基于所述备选行程信息生成行程时空网络，包括：基于每一所述备选航行行程对应的所述起始机场、所述目标机场与所述备选航班，确定多个机场节点与多个航班节点；根据多个所述机场节点与多个所述航班节点，生成所述行程时空网络。4.根据权利要求2或3任一项所述的方法，其特征在于，所述基于所述行程时空网络、所述模型目标函数与所述模型约束条件，构建得到所述资源分配模型，包括：基于所述行程时空网络、所述模型目标函数与所述模型约束条件，构建所述资源分配主问题模型，所述资源分配主问题模型用于确定所述备选行程信息中资源收益符合第二预设条件的备选航行行程；基于所述资源分配主问题模型进行求解，得到对偶信息；基于所述资源分配主问题模型与所述对偶信息，构建资源分配子问题模型，所述资源分配子问题模型用于扩充所述备选行程信息中的所述备选航行行程；将所述资源分配主问题模型与所述资源分配子问题模型进行整合，得到所述资源分配模型。5.根据权利要求4所述的方法，其特征在于，所述基于所述行程时空网络、所述模型目标函数与所述模型约束条件，构建所述资源分配主问题模型，包括：对所述模型目标函数进行第一集合切割变量转换，得到主目标函数；对所述行程时空网络与所述模型约束条件进行第二集合切割变量转换，生成主约束矩阵；基于所述主目标函数与所述主约束矩阵，构建所述资源分配主问题模型，所述主约束
矩阵用于配置所述资源分配主问题模型的可行域。6.根据权利要求5所述的方法，其特征在于，所述基于所述资源分配主问题模型进行求解，得到对偶信息，包括：对所述资源分配主问题模型进行求解，得到所述主约束矩阵中不同约束对应的多个对偶值；将多个所述对偶值确定为所述对偶信息。7.根据权利要求5所述的方法，其特征在于，所述基于所述资源分配主问题模型与所述对偶信息，构建资源分配子问题模型，包括：基于所述资源分配主问题模型的主目标函数与所述对偶信息，生成子目标函数；基于所述资源分配主问题模型的主约束矩阵，确定子约束矩阵；基于所述子目标函数与所述子约束矩阵，构建所述资源分配子问题模型。8.根据权利要求7所述的方法，其特征在于，所述当所述资源分配模型符合第一预设条件，基于所述资源分配模型确定资源分配策略信息，包括：当所述资源分配子问题模型无法扩充资源收益更大的所述备选航行行程，确定所述资源分配模型符合所述第一预设条件；基于符合所述第一预设条件的所述资源分配模型进行求解，得到所述资源分配策略信息。9.一种电子设备，其特征在于，包括：存储器、处理器，所述存储器存储有计算机程序，所述处理器执行所述计算机程序时实现如权利要求1至8中任意一项所述的航行任务生成方法。10.一种计算机可读存储介质，其特征在于，所述存储介质存储有程序，所述程序被处理器执行实现如权利要求1至8中任意一项所述的航行任务生成方法。

技术总结
本申请涉及航空运输资源分配技术领域，尤其是涉及一种航行任务生成方法、电子设备、存储介质。航行任务生成方法需要先获取备选行程信息、航行需求信息与航行限制信息。再基于备选行程信息、航行需求信息与航行限制信息，构建资源分配模型。对资源分配模型进行迭代更新。当资源分配模型符合第一预设条件，基于资源分配模型确定资源分配策略信息，进而生成航行任务。资源分配模型符合第一预设条件，意味着资源分配模型能够基于航空运输资源作出合理的资源分配策略。因此，通过符合第一预设条件的资源分配模型来确定资源分配策略信息，进而基于资源分配策略信息生成航行任务，能够在航行任务的生成过程中，实现航空运输资源的周全调度与合理分配。全调度与合理分配。全调度与合理分配。


技术研发人员：张莲民 李若愚 钱雄文 陈国华 张海伦
受保护的技术使用者：深圳市大数据研究院
技术研发日：2023.06.14
技术公布日：2023/10/5