带限制的民航航路规划方法与流程

1.本发明涉及民用航空运行指挥技术领域，尤其涉及一种带限制的民航航路规划方法。


背景技术：

2.飞行计划是飞行员执行航班任务时最重要的飞行文件之一。航路规划是飞行计划系统的核心技术。航班执行前，签派员需要综合考虑飞机使用性能、机场和航路限制、气象条件和航行情报等各方面影响，确定实际的飞行剖面，计算并确定可携带的商载及带油量和飞行时间。确保飞行安全的同时，有效地降低航班运营成本。航空公司通过飞行计划系统制作每个航班的计算机飞行计划和签派放行等工作，以规范运行管理、提高工作效率、控制航班运行风险、节约航班运营成本，实现增加运营效益。
3.传统的寻路算法如深度优先搜索dfs、广度优先搜索bfs、dijkstra算法、a*算法均可实现从一个顶点到其他各点的最短航线，但经典算法无法处理航路相关限制，因此难以直接用于航路规划。


技术实现要素：

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.从获取的节点对中的后节点往前回溯至其前序节点，直至所述前序节点的出度大于1；
33.以所述前序节点为偏离点，从所述航线网络图中随机选取不在所述不可经过节点集合中的其他节点作为后续节点进行路径规划，直至与所述最短航线有公共节点返回所述最短航线，得到满足航路限制的到当前候选航线；
34.当获取的节点对属于所述第二航路限制集合时，判断获取的节点对中的后节点是否与预设终点连通；
35.若否，则删除获取的节点对中的前节点；
36.若是，则从获取的节点对中的前节点开始检查所述最短航线，将获取的节点对中
的后节点插入所述最短航线，并从所述航线网络图中随机选取后续节点进行路径规划，直至与所述最短航线有公共节点后返回所述最短航线，得到满足航路限制的到当前候选航线。
37.作为上述方案的改进，所述构造当前候选航线的邻域，得到新增候选航线，包括：
38.检查所述候选解池中的候选航线数量；
39.当所述候选解池中的候选航线数量大于设定数量阈值时，采用路径交叉算法和/或路径变异算法构造当前候选航线的邻域，得到新增候选航线；
40.当所述候选解池中的候选航线数量不大于设定数量阈值时，采用路径变异算法构造当前候选航线的邻域，得到新增候选航线。
41.作为上述方案的改进，采用路径变异算法构造当前候选航线的邻域，具体包括以下步骤：
42.从当前候选航线中随机选取一个节点作为变异点，采用dijkstra算法生成从所述变异点至预设终点的变异路径；
43.对当前候选航线中从预设起点到所述变异点的路径和所述变异路径进行拼接，得到新增候选航线。
44.作为上述方案的改进，采用路径交叉算法构造当前候选航线的邻域，具体包括以下步骤：
45.从当前候选航线中随机选取一个节点作为交叉点；
46.从所述候选解池中找出含有所述交叉点的至少一条其他候选航线；
47.将当前候选航线和每条其他候选航线在所述交叉点处进行交叉，得到至少一条交叉路线；
48.从所述交叉路线中选取距离最短对应的路线作为新增候选航线。
49.相对于现有技术，本发明实施例的有益效果在于：通过获取航路数据和航路限制数据，并根据所述航路数据和所述航路限制数据生成航线网络图；根据所述航线网络图，计算在不带航路限制的情况下从预设起点到预设终点的最短航线；对所述最短航线进行航路限制检查；当所述最短航线通过航路限制检查时，输出所述最短航线，作为带航路限制的最短航线；当所述最短航线未通过航路限制检查时，根据所述最短航线进行路径修复和邻域构造，得到多条满足航路限制的候选航线，并将多条所述候选航线添加到预设的候选解池中进行最优路线迭代计算直至满足预设的约束条件；输出所述候选解池中的最优路线，作为带航路限制的最短航线。本发明实施例能快速找到满足所有航路限制的合法路径，提高了航线寻优效率。
附图说明
50.为了更清楚地说明本发明的技术方案，下面将对实施方式中所占据要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施方式，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
51.图1是本发明实施例提供的一种带限制的民航航路规划方法的流程图；
52.图2是本发明实施例提供的航线寻优的整体流程图；
53.图3是本发明实施例提供的航线网络图的有向图。
具体实施方式
54.下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
55.请参见图1，其是本发明实施例提供的一种带限制的民航航路规划方法的流程图。所述带限制的民航航路规划方法，包括：
56.s1：获取航路数据和航路限制数据，并根据所述航路数据和所述航路限制数据生成航线网络图；
57.其中，所述航线网络图包括第一航路限制集合和第二航路限制集合；其中，所述第一航路限制集合包括多个用于指示经过前节点后不能经过后节点的航路限制的节点对；所述第二航路限制集合包括多个用于指示经过前节点后必须经过后节点的航路限制的节点对。
58.示例性，设起点为s，终点为t，所述航线网络图中的第一航路限制集合f＝{(v1,v2),(v3,v4),...}节点对(v1,v2)表示过v1点后不能过v2点，所述航线网络图中的第二航路限制集合m＝{(v1,v2),(v3,v4),...}中节点对(v1,v2)表示过v1点后必须经过v2点。需要说明的是，以上受限制的节点对有顺序和方向性，例如(v1,v2)∈f仅限制过v1后不能经过v2点，但可以过v2点再经过v1点。且节点对之间不一定直接相连，例如若存在(v1,v2)∈f，则v1经过若干其他节点后与v2相连也违反该限制。
59.s2：根据所述航线网络图，计算在不带航路限制的情况下从预设起点到预设终点的最短航线；
60.进一步，在不考虑第一航路限制集合f和第二航路限制集合m的限制的情况下，采用dijkstra算法生成起点s到终点t的最短路径，作为不带限制的初始最短航线p0。
61.采用dijkstra算法生成起点s到终点t的最短路径的步骤具体如下：
62.步骤a：建立一个open list，一个close list，均始化为空，所有节点状态初始化为open；其中，节点状态为open表示相应节点可用，节点状态为close表示相应节点不可用。
63.步骤b：将起点s放入open list，成本设为0，若open list为空，则程序终止；
64.步骤c：若open list不为空，则从open list中找到成本最小的节点n；
65.步骤d：将节点n从open list中删除，若close list中已经包含节点n，则跳过，选取下一个节点，否则将节点n加入close list。若节点n为终点t，则找到一条路径。
66.步骤e：遍历节点n有出边的节点m，若节点m的状态不为close，则将其加入open list并计算其成本；
67.步骤f：返回步骤c。
68.s3：对所述最短航线进行航路限制检查；
69.进一步，判断所述最短航线是否违反所述第一航路限制集合、所述第二航路限制集合中的至少一条航路限制；
70.若否，确定所述最短航线通过航路限制检查；
71.若是，确定所述最短航线未通过航路限制检查。
72.s4：当所述最短航线通过航路限制检查时，输出所述最短航线，作为带航路限制的
最短航线；
73.s5：当所述最短航线未通过航路限制检查时，根据所述最短航线进行路径修复和邻域构造，得到多条满足航路限制的候选航线，并将多条所述候选航线添加到预设的候选解池中进行最优路线迭代计算直至满足预设的约束条件；
74.s6：输出所述候选解池中的最优路线，作为带航路限制的最短航线。
75.当所述最短航线p0不违反所述第一航路限制集合f、所述第二航路限制集合m中的航路限制时，确定所述最短航线p0为合法完全路径，则直接输出所述最短航线p0，得到带限制的最短航线；否则，需要对所述最短航线p0进行路径修复和邻域构造，得到多条满足航路限制的候选航线，并将多条所述候选航线添加到预设的候选解池，通过对候选解池中的最优路线进行迭代计算，得到最终的带航路限制的最短航线；本发明实施例能快速找到满足所有航路限制的合法路径，耗时短，大大提高了航线寻优效率。
76.在一种可选的实施例中，s5：根据所述最短航线进行路径修复和邻域构造，得到多条满足航路限制的候选航线，并将多条所述候选航线添加到预设的候选解池中进行最优路线迭代计算直至满足预设的约束条件，包括：
77.s51：对所述最短航线进行路径修复，得到满足航路限制的到当前候选航线，并将当前候选航线添加到预设的候选解池中，所述候选解池中的最优路线更新为当前候选航线；
78.s52：构造当前候选航线的邻域，得到新增候选航线；
79.s53：对所述新增候选航线进行航路限制检查；
80.s54：当所述新增候选航线通过航路限制检查时，将新增候选航线添加到所述候选解池中；
81.s55：当所述新增候选航线未通过航路限制检查时，对所述新增候选航线进行路径修复，以使得修复后的新增候选航线满足航路限制，并将修复后的新增候选航线添加到所述候选解池中；
82.s56：从所述新增候选航线和所述最优路线中选取最短距离对应路线更新所述候选解池中的最优路线；
83.s57：从所述候选解池中选取一条候选航线作为当前候选航线，并返回步骤s52进行下一轮迭代计算直至满足预设的约束条件。
84.其中，所述约束条件为：所述候选解池中的最优路线连续多轮迭代计算过程中未更新或者迭代次数达到预设的最大迭代次数。
85.结合图2所示，所述候选解池中的最优路线的迭代计算过程如下：
86.预先构造一个候选解池l。设定所述候选解池l的最大长度为50，即所述候选解池l中最多保存50条当前找到的最好的候选航线，当找的新的候选航线时，检查所述候选解池l中是否已经有50条候选航线，若否，则将新的候选航线直接插入；若是，则比较新的候选航线是否优于所述候选解池l中最差的候选航线，如是则将新的候选航线直接插入且丢弃所述候选解池l中最差的候选航线，否则丢弃新的候选航线。
87.在检查到当前采用dijkstra算法得到的最短航线p0违反航路限制时，对其进行修复，生成满足航路限制的最短航线p0’
，将满足航路限制的最短航线p0’
加入到候选解池l，令p
best
＝p0’
，pc＝p0’
；
88.构造最短航线p0的邻域，并对得到的新增候选航线解进行航路限制检查，如违反所述第一航路限制集合f、所述第二航路限制集合m中的航路限制，则对其进行修复，得到的新的合法完全路径p
c’；
89.将p
c’加入候选解池l；如超过候选解池l的最大长度，则排序后删掉多余候选航线，如果p
c’优于p
best
，则p
best
＝p
c’；其中，通过比较两条航线的距离确定航线的优劣，当p
c’的距离小于p
best
，则p
c’优于p
best
，否则，p
best
优于p
c’。
90.如达到设定的最大迭代次数或者连续10轮p
best
没有更新，则终止迭代，输出p
best
。否则，从候选解池中任意选取一个候选路线作为当前解pc，转至邻域构造步骤。
91.在一种可选的实施例中，在将新增候选航线添加到所述候选解池后，还包括：
92.判断所述候选解池的长度是否超出预设的最大长度；
93.若是，将所述候选解池中的候选航线按照距离从短到长进行排序，并从排序的末位开始删除候选航线直至所述候选解池的长度未超出所述最大长度。
94.在一种可选的实施例中，所述对所述最短航线进行路径修复，得到满足航路限制的到当前候选航线，包括：
95.获取所述最短航线违反的航路限制对应的节点对；
96.当获取的节点对属于所述第一航路限制集合时，将获取的节点对中的后节点加入到预设的不可经过节点集合中；
97.从获取的节点对中的后节点往前回溯至其前序节点，直至所述前序节点的出度大于1；
98.以所述前序节点为偏离点，从所述航线网络图中随机选取不在所述不可经过节点集合中的其他节点作为后续节点进行路径规划，直至与所述最短航线有公共节点返回所述最短航线，得到满足航路限制的到当前候选航线；
99.当获取的节点对属于所述第二航路限制集合时，判断获取的节点对中的后节点是否与预设终点连通；
100.若否，则删除获取的节点对中的前节点；
101.若是，则从获取的节点对中的前节点开始检查所述最短航线，将获取的节点对中的后节点插入所述最短航线，并从所述航线网络图中随机选取后续节点进行路径规划，直至与所述最短航线有公共节点后返回所述最短航线，得到满足航路限制的到当前候选航线。
102.在本发明实施例中，对于当前规划处的违反航路限制的最短航线，先判断最短航线违反的哪一个集合中的航路限制，如果是违反第一航路限制集合f，则对其违反的规则(v1，v2)依次进行如下处理：将v2加入不可经过节点集合vf。从v2点往前回溯至其前序节点v
p
，如v
p
的出度大于1，则以v
p
点为偏离点一直随机选择不在集合vf中的后续节点直至与原路径pc有公共节点vc则从vc点以后复制原路径。如果v
p
的出度等于1，则继续回溯至出度大于1的节点为偏离点，然后一直随机选取不在集合vf中的后续节点直至与原路径pc有公共节点vc，则从vc点以后复制原路径。
103.如果路径违反第二航路限制集合m中的规则，则对其违反的规则(v1,v2)，进行如下处理：当v2不与终点t联通，则删掉v1；否则从v1点开始检查原路径，如有后续节点为v2的节点则插入v2点，再随机选取后续节点，直至与原路径pc有公共节点vc则从vc后返回原路径。
104.反复上述过程直至得到一条合法完全路径为止。
105.在一种可选的实施例中，所述构造当前候选航线的邻域，得到新增候选航线，包括：
106.检查所述候选解池中的候选航线数量；
107.当所述候选解池中的候选航线数量大于设定数量阈值时，采用路径交叉算法和/或路径变异算法构造当前候选航线的邻域，得到新增候选航线；
108.当所述候选解池中的候选航线数量不大于设定数量阈值时，采用路径变异算法构造当前候选航线的邻域，得到新增候选航线。
109.进一步，采用路径变异算法构造当前候选航线的邻域，具体包括以下步骤：
110.从当前候选航线中随机选取一个节点作为变异点，采用dijkstra算法生成从所述变异点至预设终点的变异路径；
111.对当前候选航线中从预设起点到所述变异点的路径和所述变异路径进行拼接，得到新增候选航线。
112.进一步，采用路径交叉算法构造当前候选航线的邻域，具体包括以下步骤：
113.从当前候选航线中随机选取一个节点作为交叉点；
114.从所述候选解池中找出含有所述交叉点的至少一条其他候选航线；
115.将当前候选航线和每条其他候选航线在所述交叉点处进行交叉，得到至少一条交叉路线；
116.从所述交叉路线中选取距离最短对应的路线作为新增候选航线。
117.为了方便操作，对候选航线进行编码。采用可变长编码方式，编码串的每一位为候选航线上节点的序号，一条完全路径为从起点s到终点t的节点号编码串表示。一条由起点s到终点t的且不违反限制集合f和m中任意规则的路径称为合法完全路径。
118.基于以下候选航线的编码串对路径变异算法和路径交叉算法构造邻域的过程进行说明：
119.路径变异算法：
120.路径变异前：
121.sv
1v2v5v8v10v12
t
122.任意选择路径中1个位置va，保留s至va的路径，用dijkstra算法生成va至t的最短路径，合并s至va及va至t的路径生成s至t的新路径，如违反规则，则对路径进行修复。
123.例如选择v5为变异节点，则路径变异后：
124.sv
1v2v5v7v9v11v15
t
125.路径交叉算法：任意选择路径中1个位置va,从候选解池l中找出含va点的所有解(即候选航线)在va点与所选路径进行交叉，生成新的解，将新解中最优的一个作为当前解
126.同样选择v5为交叉节点，假设从候选解池l中找出含v5点的两条候选航线为：
[0127][0128][0129]
则路径交叉后：
[0130][0131][0132]
当候选解池中的候选航线的数量《＝10时，可以选择变异算法构造邻域，当候候选解池中的候选航线的数量》10时，随机选择交叉和变异算法生成邻域。上述步骤中如需要输出k条航线，则可输出候选解池中的前k条候选航线。候选解池l的长度和最大迭代次数可根据航线网络图的大小确定。
[0133]
如图3所示的航线网络图的有向图，假设起点为节点1，终点为节点26，求图中节点1至节点26的最短距离，图中边上的数字为该边的权重，限制为f＝{(12,19)}，m＝{(5,14)}，即过节点12后不能过节点19，过节点5后必须过节点14。航线的总成本为该航线上所有边的权重之和。图3中不带限制的最短航线为1-5-12-19-26，总成本为122。满足f和m集合中所有路径限制的带限制的前五条最优航线如下表所示：
[0134][0135]
则，带限制的最短航线为1-5-13-14-20-26，总成本为134。
[0136]
相对于现有技术，本发明实施例的有益效果在于：
[0137]
(1)可以快速找到满足所有航路限制且成本较小的合法路径，同时由于本发明实施例仅对找到的较好的路径进行限制检查，大大提高了寻优效率。
[0138]
(2)通过构造航路限制集合，当有新的限制时算法容易扩展。
[0139]
(3)通过路径的邻域构造，可以同时找出前n条最优航路作为备选路径。
[0140]
以上所述是本发明的优选实施方式，应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做出多台改进和润饰，这些改进和润饰也视为本发明的保护范围。

技术特征：
1.一种带限制的民航航路规划方法，其特征在于，包括：获取航路数据和航路限制数据，并根据所述航路数据和所述航路限制数据生成航线网络图；根据所述航线网络图，计算在不带航路限制的情况下从预设起点到预设终点的最短航线；对所述最短航线进行航路限制检查；当所述最短航线通过航路限制检查时，输出所述最短航线，作为带航路限制的最短航线；当所述最短航线未通过航路限制检查时，根据所述最短航线进行路径修复和邻域构造，得到多条满足航路限制的候选航线，并将多条所述候选航线添加到预设的候选解池中进行最优路线迭代计算直至满足预设的约束条件；输出所述候选解池中的最优路线，作为带航路限制的最短航线。2.如权利要求1所述的带限制的民航航路规划方法，其特征在于，所述航线网络图包括第一航路限制集合和第二航路限制集合；其中，所述第一航路限制集合包括多个用于指示经过前节点后不能经过后节点的航路限制的节点对；所述第二航路限制集合包括多个用于指示经过前节点后必须经过后节点的航路限制的节点对。3.如权利要求2所述的带限制的民航航路规划方法，其特征在于，对所述最短航线进行航路限制检查，包括：判断所述最短航线是否违反所述第一航路限制集合、所述第二航路限制集合中的至少一条航路限制；若否，确定所述最短航线通过航路限制检查；若是，确定所述最短航线未通过航路限制检查。4.如权利要求3所述的带限制的民航航路规划方法，其特征在于，所述根据所述最短航线进行路径修复和邻域构造，得到多条满足航路限制的候选航线，并将多条所述候选航线添加到预设的候选解池中进行最优路线迭代计算直至满足预设的约束条件，包括：对所述最短航线进行路径修复，得到满足航路限制的到当前候选航线，并将当前候选航线添加到预设的候选解池中，所述候选解池中的最优路线更新为当前候选航线；构造当前候选航线的邻域，得到新增候选航线；对所述新增候选航线进行航路限制检查；当所述新增候选航线通过航路限制检查时，将新增候选航线添加到所述候选解池中；当所述新增候选航线未通过航路限制检查时，对所述新增候选航线进行路径修复，以使得修复后的新增候选航线满足航路限制，并将修复后的新增候选航线添加到所述候选解池中；从所述新增候选航线和所述最优路线中选取最短距离对应路线更新所述候选解池中的最优路线；从所述候选解池中选取一条候选航线作为当前候选航线，并返回邻域构造步骤进行下一轮迭代计算直至满足预设的约束条件。5.如权利要求4所述的带限制的民航航路规划方法，其特征在于，所述约束条件为：所述候选解池中的最优路线连续多轮迭代计算过程中未更新或者迭代次数达到预设的最大
迭代次数。6.如权利要求4所述的带限制的民航航路规划方法，其特征在于，在将新增候选航线添加到所述候选解池后，还包括：判断所述候选解池的长度是否超出预设的最大长度；若是，将所述候选解池中的候选航线按照距离从短到长进行排序，并从排序的末位开始删除候选航线直至所述候选解池的长度未超出所述最大长度。7.如权利要求4所述的带限制的民航航路规划方法，其特征在于，所述对所述最短航线进行路径修复，得到满足航路限制的到当前候选航线，包括：获取所述最短航线违反的航路限制对应的节点对；当获取的节点对属于所述第一航路限制集合时，将获取的节点对中的后节点加入到预设的不可经过节点集合中；从获取的节点对中的后节点往前回溯至其前序节点，直至所述前序节点的出度大于1；以所述前序节点为偏离点，从所述航线网络图中随机选取不在所述不可经过节点集合中的其他节点作为后续节点进行路径规划，直至与所述最短航线有公共节点返回所述最短航线，得到满足航路限制的到当前候选航线；当获取的节点对属于所述第二航路限制集合时，判断获取的节点对中的后节点是否与预设终点连通；若否，则删除获取的节点对中的前节点；若是，则从获取的节点对中的前节点开始检查所述最短航线，将获取的节点对中的后节点插入所述最短航线，并从所述航线网络图中随机选取后续节点进行路径规划，直至与所述最短航线有公共节点后返回所述最短航线，得到满足航路限制的到当前候选航线。8.如权利要求4所述的带限制的民航航路规划方法，其特征在于，所述构造当前候选航线的邻域，得到新增候选航线，包括：检查所述候选解池中的候选航线数量；当所述候选解池中的候选航线数量大于设定数量阈值时，采用路径交叉算法和/或路径变异算法构造当前候选航线的邻域，得到新增候选航线；当所述候选解池中的候选航线数量不大于设定数量阈值时，采用路径变异算法构造当前候选航线的邻域，得到新增候选航线。9.如权利要求8所述的带限制的民航航路规划方法，其特征在于，采用路径变异算法构造当前候选航线的邻域，具体包括以下步骤：从当前候选航线中随机选取一个节点作为变异点，采用dijkstra算法生成从所述变异点至预设终点的变异路径；对当前候选航线中从预设起点到所述变异点的路径和所述变异路径进行拼接，得到新增候选航线。10.如权利要求8所述的带限制的民航航路规划方法，其特征在于，采用路径交叉算法构造当前候选航线的邻域，具体包括以下步骤：从当前候选航线中随机选取一个节点作为交叉点；从所述候选解池中找出含有所述交叉点的至少一条其他候选航线；将当前候选航线和每条其他候选航线在所述交叉点处进行交叉，得到至少一条交叉路
线；从所述交叉路线中选取距离最短对应的路线作为新增候选航线。

技术总结
本发明公开了一种带限制的民航航路规划方法，通过获取航路数据和航路限制数据，并根据航路数据和航路限制数据生成航线网络图；根据航线网络图，计算在不带航路限制的情况下从预设起点到预设终点的最短航线；对最短航线进行航路限制检查；当最短航线通过航路限制检查时，输出最短航线，作为带航路限制的最短航线；当最短航线未通过航路限制检查时，根据最短航线进行路径修复和邻域构造，得到多条满足航路限制的候选航线，并将多条候选航线添加到预设的候选解池中进行最优路线迭代计算直至满足预设的约束条件；输出候选解池中的最优路线，作为带航路限制的最短航线。本发明实施例能快速找到满足所有航路限制的合法路径，提高了航线寻优效率。线寻优效率。线寻优效率。


技术研发人员：许南 伍翔 常先英 吴东岳 张苗苗 黄旭 丁树民
受保护的技术使用者：中国南方航空股份有限公司
技术研发日：2023.03.21
技术公布日：2023/7/6