空中交通流量调控方法
空中交通流量调控方法
【技术领域】
[0001] 本发明实施例涉及调控技术，尤其涉及一种空中交通流量调控方法。
【背景技术】
[0002] 近年来航空运输业取得了迅猛发展，但是随着空中飞机数量的不断增多，空域拥 挤问题变得日益严重，不仅降低了飞行的安全性，而且给民航带来了巨大的经济损失。空中 交通流量管理是解决空中交通拥挤最为有效和经济的手段，通过改变飞机的起飞时刻、飞 行路径达到流量调控的目的，从而降低空中交通拥挤度，提高空域利用率。其中，改变飞机 的起飞时刻就是改变飞机的时间延误，改变飞行路径也就是改变空域的拥挤度。
[0003] 随着飞机数量的剧增，各部分空域之间的关联性增强，广域空中交通流量调控的 方法逐渐引起了人们的注意。广域空中交通流量管理的首要目标是保证飞机飞行的安全 性，即要降低整个空域拥挤度，其次在保证安全飞行的前提下还要兼顾航空公司的经济利 益和航班之间的公平性，即要尽量均衡地分配飞机的时间延误。其中，广域空域由各部分空 域构成，广域空中交通流量调控需要同时优化所有飞机的时间延误和各个空域拥挤度，是 一个多目标的大规模组合优化问题，而且这两个目标是一对矛盾，在减小空域拥挤度的同 时必然会增加时间延误，因此通过传统的广域空中交通流量调控算法将得到的时间延误和 空域拥挤度的解集转换为一组非支配解，并计算该非支配解的多样性，多样性是评价非支 配解好坏的一个重要指标，它可以反映解的分布是否均匀，如果分布均匀则广域空中交通 流量调控达到的效果较好。
[0004] 传统的遗传算法在解决多目标组合优化问题时已经表现出了一定的优势，但是在 处理大规模的多目标组合优化问题时搜索能力有限，很难充分搜索整个解空间，容易陷入 局部最优，这样就会对航空公司的经济利益和航班之间的公平性产生影响。
【发明内容】
[0005] 本发明实施例提供一种空中交通流量调控方法，以解决在处理大规模的多目标组 合优化问题时搜索能力有限，很难充分搜索整个解空间，容易陷入局部最优，会对航空公司 的经济利益和航班之间的公平性产生影响的问题。
[0006] 本发明实施例提供一种空中交通流量调控方法，包括：
[0007] 第一步，建立待调控空域的航班和空域信息数据库，所述数据库包括所述待调控 空域中所有航班的起飞时刻和飞行路径的集合；
[0008] 第二步，生成初始种群，所述初始种群由预设数量的染色体随机组成，一条染色体 由所述数据库中每一航班的一个飞行路径和一个起飞时刻组成，所述一条染色体包括2N 个基因，N为所述数据库中航班的数量，将所述初始种群作为第g代种群，g为自然数；
[0009] 第三步，使用所述第g代种群计算第一目标函数和第二目标函数，所述第一目标 函数为所述待调控空域的空中交通拥挤度目标函数，所述第二目标函数为所述待调控空域 中所有航班的起飞时刻延误和额外飞行路径的目标函数，得到所述第g代种群的所述第一 目标函数和所述第二目标函数的解集；将所述第g代种群的所述第一目标函数和所述第二 目标函数的解集存放在全局变量中；
[0010] 第四步，计算所述第g代种群的所述第一目标函数和所述第二目标函数的解集的 多样性函数，得到所述第g代的多样性函数值；
[0011] 第五步，根据所述第g代的多样性函数值确定在所述第g代种群中参与局部搜索 的染色体的数量Φ (g);
[0012] 第六步，在所述第g代种群中随机选择Φ (g)条染色体，并替换所述Φ (g)条染色 体中每一染色体的y个基因，将所述第g代种群中除所述Φ (g)条染色体以外的其他染色 体和替换后的所述Φ (g)条染色体作为第g+l代种群；
[0013] 第七步，使用所述第g+Ι代种群计算所述第一目标函数和所述第二目标函数，得 到所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集；根据所述第g+Ι代 种群的所述第一目标函数和所述第二目标函数的解集对所述全局变量中的所述第一目标 函数和所述第二目标函数的解集进行更新；
[0014] 第八步，计算所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集 的多样性函数，得到所述第g+ι代的多样性函数值；
[0015] 第九步，依次循环执行第五步至第八步的处理，得到第g+n代的多样性函数值，直 到第g+n代到达预定循环代数；
[0016] 第十步，将所述全局变量中更新后的解集对应的染色体中的每个航班的起飞时刻 和飞行路径来作为待调控空域的调控依据。
[0017] 进一步地，上述多样性函数值，表示为：
[0019] 其中，
为相邻的所述第一目标函数和所述第二目标函数的解之间 的平均距离，所述第一目标函数和所述第二目标函数的解集为X = (Xl，x2, ...，xn)，山为X i 和x1+1之间的距离，d ￡和d i分别为两个极端解与所述第一目标函数和所述第二目标函数的 解边界值之间的距离，Cl1表示为：
[0020] (Ii=IIy(Xi)I(Xw)II 2 0〈i〈n
[0021] 其中，y是目标函数向量，y = (yi，y2)，yi为所述第一目标函数，y2为所述第二目 标函数。
[0022] 上述根据所述第g代的多样性函数值确定在所述第g代种群中参与局部搜索的染 色体的数量Φ (g)，表示为：
[0024] 其中，ps为所述第g代种群中的染色体数量，τ (g)为第g代局部搜索频率，k为 常数；
[0025] 第g代局部搜索频率τ (g)，表示为：
[0027] n (g)为所述第g代的多样性函数值。
[0028] 上述y个基因为2NXp个基因；其中，p为选择比例，p小于1。
[0029] 上述使用所述第g代种群计算第一目标函数和第二目标函数，得到所述第g代种 群的所述第一目标函数和所述第二目标函数的解集，具体包括：
[0030] 将所述第g代种群中的所述每一条染色体随机分组得到至少两个低维子染色体， 对每个低维子染色体进行差分进化，得到差分进化后的每个低维子染色体，将所述差分进 化后的每个低维子染色体进行合并，生成差分进化后的一条染色体，所述第g代种群的所 述第一目标函数和所述第二目标函数的解集由所述差分进化后的染色体计算得到。
[0031] 上述根据所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集对 所述全局变量中的所述第一目标函数和所述第二目标函数的解集进行更新，具体包括：
[0032] 将所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集中的各个 解进行比较，得到所述第g+Ι代种群的非支配解集；
[0033] 将所述第g+Ι代种群的非支配解集与所述全局变量中的所述第一目标函数和所 述第二目标函数的解集进行比较，如果所述第g+Ι代种群的非支配解集中存在至少一个 解，所述至少一个解支配所述全局变量中的所述第一目标函数和所述第二目标函数的解集 中的解，则用所述至少一个解替换掉所述全局变量中的所述第一目标函数和所述第二目标 函数的解集中被所述至少一个解支配的解。
[0034] 上述第一目标函数为所述待调控空域的空中交通拥挤度目标函数，表示为：
[0036] 其中，
表示扇区Sk在时间T内的总拥挤度，t e T，
表示扇 区Sk在时间T内的最大拥挤度，P表示扇区的数量，Φ和W是介于0到1之间的权重系数；
[0037] 所述待调控空域包括P个扇区，所述扇区Sk表示P个扇区中的第k个扇区，所述扇 区S k的拥挤度为所述扇区Sk在时间T内的一个时刻t的航班数量，所述扇区总拥挤 度为所述扇区S k在时间T内的航班数量之和，所述扇区S k的最大拥挤度为所述扇区S ,在 时间T内一个时刻t的航班数量的最大值。
[0038] 上述扇区&在t时刻的负荷KO包括：监视负荷(〇和协调负荷(?)， 表示为：
[0040] 其中，w, Φ e [0, 1]为所述监视负荷和所述协调负荷的权重；
[0041] 所述监视负荷(0，表示为：
[0043] 其中，MSi (?)与t时刻在所述扇区&内的飞机数目的平方成正比，(?)表示t 时刻所述扇区Sk的监视负荷阈值；
[0044] 所述协调负荷(0可以表示为：
[0046] 其中，义⑴与t时刻穿越所述扇区Sk边界的飞机数目的平方成正比，⑴表 示t时刻所述扇 区S k的协调负荷阈值。
[0047] 上述扇区&在t时刻的负荷Ks (〇包括：监视负荷》;a (〇和协调负荷W。.Si (〇， 表示为：
[0049] 其中，w，Φ e [0, 1]为所述监视负荷和所述协调负荷的权重；
[0050] 所述监视负荷巧略(?)，表示为：
[0052] 其中，(?)与t时刻在所述扇区&内的飞机数目的平方成正比，C," Si (〇表示t 时刻所述扇区Sk的监视负荷阈值；
[0053] 所述协调负荷》（〇可以表示为：
[0055] 其中，Q⑴与t时刻穿越所述扇区Sk边界的飞机数目的平方成正比，Q (〇表 示t时刻所述扇区Sk的协调负荷阈值。
[0056] 上述第二目标函数为所述待调控空域中所有航班的起飞时刻延误和额外飞行路 径的目标函数，所述起飞时刻延误为所述航班的起飞时刻与所述数据库中所述航班的最早 起飞时刻的差值；所述额外飞行路径为所述航班的飞行路径与所述数据库中所述航班的最 短飞行路径的差值；
[0057] 所述第二目标函数表示为：
[0059] 其中，δ⑴为所述航班总的延误，表示为：
[0060] δ ⑴=δ s(i) + δ r(i)
[0061] 其中，Ss⑴为所述航班的地面延误，δ力）为所述航班的空中延误。
[0062] 上述数据库中所述航班包括大、中、小型航班；
[0063] 所述待调控空域中所有航班的起飞时刻延误和额外飞行路径的目标函数，具体表 示为：
[0065] 其中，NB，NM，Nj别表示所述大、中、小型航班的数量，λ Β，λΜ，别表示所述 大、中、小型航班对应的权重系数（λ Β> λ Μ> λ s)。
[0066] 本发明实施例空中交通流量调控方法，通过对每一代种群参与局部搜索的染色体 数量进行动态调整，使每一代种群参与局部搜索的染色体数量都不相同，这样就可以加强 对解空间的搜索能力，不容易陷入局部最优，提高解集的多样性，能够比传统的遗传算法找 到更为满意的结果，保证了在航班安全飞行的前提下尽量兼顾航空公司的经济利益和航班 之间的公平性。
【附图说明】
[0067] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现 有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发 明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以 根据这些附图获得其他的附图。
[0068] 图1为本发明空中交通流量调控方法实施例的流程图；
[0069] 图2为本发明空中交通流量调控方法实施例的染色体的编码结构示意图；
[0070] 图3为本发明空中交通流量调控方法实施例的第一目标函数和第二目标函数的 解集的多样性不意图；
[0071] 图4为本发明空中交通流量调控方法实施例的一条染色体局部搜索示意图。
【具体实施方式】
[0072] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例 中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是 本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员 在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0073] 首先介绍如下概念与定义：
[0074] 航路：由国家统一划定的具有一定宽度的空中通道。有较完善的通信、导航设备， 宽度通常为20KM。划定航路的目的是维护空中交通秩序，提高空间利用率，保证飞行安全。
[0075] 航线：飞机飞行的路线称为空中交通线，简称航线。飞机的航线不仅确定了飞机飞 行具体方向、起讫点和经停点，而且还根据空中交通管制的需要，规定了航线的宽度和飞行 高度，以维护空中交通秩序，保证飞行安全。
[0076] 空域：空域就是飞行所占用的空间。通常以明显地标或导航台为标志。空域同领 土、领海一样，是国家的主权范围，也是重要的军用及民航资源。为了便于地面管制员对于 飞行流量的管理，空域通常被划分为多个扇区，每个扇区可容纳的飞行流量与扇区的大小、 天气情况、管制员数量以及导航设备有关。
[0077] 客机机型：客机按起飞重量与载客量分为小型、中型、大型客机，不同国家划分的 标准也不相同，我国民航总局是按飞机客座数划分大、中、小型飞机的，飞机的客座数在100 座以下的为小型机（S)，100-200座之间为中型机（M)，200座以上为大型机（B)。
[0078] 协同进化：利用分而治之的思想将一个高维问题分解为多个低维问题进行求解， 然后通过低维问题的解的合作得到高维问题的解，优点是可以降低问题的复杂度。
[0079] 文化基因算法（Memetic Algorithm，简称：MA):用局部启发式搜索来模拟由大量 专业知识支撑的变异过程，文化基因算法是一种基于种群的全局搜索和基于个体的局部启 发式搜索的结合体。文化基因算法提出的是一种框架、是一个概念，在这个框架下，采用不 同的搜索策略可以构成不同的文化基因算法，如全局搜索策略可以采用遗传算法、进化策 略、进化规划等，局部搜索策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式 局部搜索等。
[0080] 在本发明中做出如下假设：
[0081] (1)所有的飞机的飞行速度都一样，而且在飞行过程中保持不变；
[0082] (2)所有飞机的起飞时刻都是一个含有有限个元素的集合；
[0083] (3)所有飞机的飞行路径在一定的范围内可选；
[0084] (4)同一个起止点之间的飞机，可选路径集合是一样的。
[0085] 基于上述假设，对具体的实施方式进行说明。
[0086] 图1为本发明空中交通流量调控方法实施例的流程图，如图1所示，本实施例的方 法可以包括：
[0087] 步骤101、第一步，建立待调控空域的航班和空域信息数据库，所述数据库包括所 述待调控空域中所有航班的起飞时刻和飞行路径的集合。
[0088] 所有航班的起飞时刻都必须考虑旅客的需求和航空公司的情况，必须在合理的范 围内进行选择，每个航班的飞行路径集合也有一定的限制，对于每个航班来说，它的最长飞 行路径不能超过最短飞行路径长度的1. 3倍（在本实施例中，以1. 3倍来举例说明，具体的 倍数可以根据实际情况进行设置，在此不加以限定）。空中交通流量调控方法就是通过改变 航班的起飞时刻或飞行路径，使其提前或延后进入某一扇区，从而达到降低该扇区拥挤度 的效果。
[0089] 首先，建立待调控空域的航班和空域信息数据库，其中，该数据库由待调控空域中 所有航班的起飞时刻和飞行路径的集合组成。具体的，每个航班都包括一组变量（δ i, !Ti)， S1表示航班起飞延误的时间，例如一架航班最早起飞时刻为8:20,但是实际起飞时刻为 8:40,所以该航班起飞延误的时间为20分钟。 Γι表示重新选择的飞行路径，δ JPri的可 选集合可以分别表示为：
[0090] Δ = 〇, 1，· · ·，δ ρ-1，δ ρ
[0091] R = r〇, r1; r2, . . . , rnax
[0092] δ p表示航班可以延误的最大时间，r。表示最短飞行路径，r_表示最差飞行路径。 例如一架航班的最早起飞时刻为8:20,可选起飞时刻可以为8:30、8:40、8:50,在本实施例 中，以相邻的时间差为10分钟来举例说明，具体的差值可以根据实际需求进行设置，在此 不加以限定。该航班的最短飞行路径为航线1，可选飞行路径可以为航线2、航线3、航线4。 在本实施例中，以相邻的航线差为20KM来举例说明，具体的差值可以根据实际需求进行设 置，在此不加以限定。在数据库中将起飞时刻和飞行路径转变成对应的数据格式，例如将最 早起飞时刻8:20转变成对应的0数据格式，将可选起飞时间8 :30、8:40、8:50转变成对应 为1、2、3的数据格式，所以该航班的起飞时刻可选数据集合为△= 0, 1，2, 3。将最短飞行 路径航线1转变成对应的1数据格式，将可选飞行路径航线2、航线3、航线4转变成对应为 2、3、4的数据格式，所以该航班的飞行路径可选数据集合为R = 1，2, 3, 4。
[0093] 另外，还有一个约束是连续航班之间的制约，如果一架航班执行 完一次航班任务 后还有另外的航班任务，则这两个航班称为连续航班，两个航班之间必须留有充足的时间 进行飞机的安全检查和清扫工作。假设对于大型机该时间为T b，航班Fab是航班F a的后续 航班，如果Fa在飞行途中花费的时间为Ta，起飞时刻集合 a=〇，l，...，δ a-l，Sa
[0094] 则航班Fab的起飞时刻集合Δ abSTa+TB之后的某个时刻集合。对于小型机和中型 机，连续航班之间的时间间隔记为TjP T M。
[0095] 步骤102、第二步，生成初始种群，所述初始种群由预设数量的染色体随机组成，一 条染色体由所述数据库中每一航班的一个飞行路径和一个起飞时刻组成，所述一条染色体 包括2N个基因，N为所述数据库中航班的数量，将所述初始种群作为第g代种群，g为自然 数。
[0096] 在本实施例中，初始种群由100条染色体组成来举例说明（染色体的数量可以根 据实际需求设定，在此不加以限定）。将初始种群定义为第g代种群，g为自然数，即第g代 初始种群由100条染色体所构成，初始种群就是第1代种群，然后每进化完一代g就加1，直 到达到最大进化代数。这里的g是一个变量，随着进化的进行不断增大。其中，每一条染色 体都是由所有航班的一个飞行路径和一个起飞时刻构成，因此每一条染色体的长度是航班 数量的2倍，所以将数据库中的所有航班数量设置为N，每一条染色体就包括2N个基因。
[0097] 具体的每一条染色体生成过程为：
[0098] 首先，读入数据库中所有航班N的可选飞行路径集合数据和起飞时刻的上下限数 据，作为可选数据集合。接着，在可选数据集合内随机选择数据。最后，初始化每个航班的 起飞时刻和飞行路径，生成一条染色体。
[0099] 图2为本发明空中交通流量调控方法实施例的染色体的编码结构示意图。如 图2所示，&表示航班η的可选飞行路径集合，△ "表示航班η的可选起飞时刻集合，η = 1，. . .，k, . . .，N，N 表示航班数量。一条染色体由;Tp δ . . .，rk、δ k, . . .，rN、δ Ν，2Ν 个基因 组成。
[0100] 另外，将全局变量初始化，初始化的全局变量为空集，用来存放进化最新找到的第 一目标函数和第二目标函数的解集。
[0101] 步骤103、第三步，使用所述第g代种群计算第一目标函数和第二目标函数，所述 第一目标函数为所述待调控空域的空中交通拥挤度目标函数，所述第二目标函数为所述待 调控空域中所有航班的起飞时刻延误和额外飞行路径的目标函数，得到所述第g代种群的 所述第一目标函数和所述第二目标函数的解集；将所述第g代种群的所述第一目标函数和 所述第二目标函数的解集存放在全局变量中。
[0102] 利用第g代种群计算第一目标函数和第二目标函数。
[0103] 其中，第一目标函数为待调控空域的空中交通拥挤度目标函数。这里需要说明的 是，待调控空域的空中交通拥挤度可以通过引入扇区来进行量化，扇区的拥挤度与扇区内 的航班数量和通过扇区边界的航班数量有关，当航班数量小于扇区容量阈值的时候拥挤度 为0,当航班数量超过阈值时，扇区拥挤度会以平方数量级的趋势急剧上升。
[0104] 对于每个航班来说，它的飞行计划就是在某一时刻进入某个扇区然后在随后某一 时刻离开该扇区，因此一个航班计划可以表示为：
[0105] L = (S1, Tin1, Tout1), (S2, Tin2, Tout2),. . . , (Sk, Tink, Toutk),...
[0106] Sk表示航班经过的第k个扇区，Tin k表示进入该扇区的时刻，Tout k表示离开该扇 区的时刻。
[0107] 扇区&在t时刻的负荷》:? (〇包括：监视负荷》⑴和协调负荷G)，其负 荷Md表示为：
[0109] 其中，w, Φ e [0, 1]为监视负荷和协调负荷的权重。
[0110]监视负荷％，表示为：
[0112] 其中，(/)与t时刻在所述扇区&内的飞机数目的平方成正比，C mii (?)表示t 时刻所述扇区Sk的监视负荷阈值；
[0113] 所述协调负荷(〇可以表示为：
[0115] 其中，CSi(i)与t时刻穿越所述扇区Sk边界的飞机数目的平方成正比，（0表 示t时刻所述扇区S k的协调负荷阈值。
[0116] 所以，待调控空域的空中交通拥挤度目标函数最终可以表示为：
[0118] 其中，
表示扇区Sk在时间T内的总拥挤度，t e τ，
表示扇 区Sk在时间T内的最大拥挤度，P表示扇区的数量，Φ和P是介于0到1之间的权重系数。
[0119] 将待调控空域分成P个扇区，该待调控空域的空中交通拥挤度与P个扇区内的航 班数量和通过P个扇区边界的航班数量有关。其中，扇区S k表示P个扇区中的第k个扇区， 扇区Sk的拥挤度为扇区S k在时间T内的一个时刻t的航班数量，扇区S k的总拥挤度为扇区 Sk在时间T内的航班数量之和，扇区Sk的最大拥挤度为扇区Sk在时间T内一个时刻t的航 班数量的最大值。
[0120] 71表示所有扇区的拥挤度之和，Φ和P分别表示每个扇区内总拥挤度和最大拥挤 度在目标函数中所占的比重。
[0121] 第二目标函数为待调控空域中所有航班的起飞时刻延误和额外飞行路径的目标 函数。其中，起飞时刻延误为一架航班的实际的起飞时刻与上述数据库中该航班的最早起 飞时刻的差值。额外飞行路径为一架航班的飞行路径与上述数据库中该航班的最短飞行路 径的差值。
[0122] 对于航班，如果航班i计划在4时刻起飞，而实际上它在t "时刻起飞，这样航班 的地面延误可以表示为：Ss(i) =tn-tk。假设?；表示航班实际飞行需要的时间，T。表示最 短路径需要的时间，由于相同的时间内空中飞行的花费是地面延误的3倍（在本实施例中， 以3倍来举例说明，具体的倍数可以根据实际情况进行设置，在此不加以限定），所以航班 的空中延误可以表示为：\(i) =3*(?；-Τ。）。因此总的延误δ⑴可以表示为：δ (i)= S s(i)+ δ Ji)。为了保证航班之间的公平性，这里将线性的目标函数改为平方和的形式，例 如同样是两个航班一共延误20分钟，我们希望每个航班延误10分钟，而不是一个延误20 分钟，一个没有延误。
[0123] 所以待调控空域中所有航班的起飞时刻延误和额外飞行路径的目标函数可以表 示为：
[0125] 进一步的，在所有航班中，可以将航班机型分成三类，即大、中、小型三种机型，这 三种机型的航班数量分别为：Nb，NJPNs，对于不同机型的航班，相同的时间延误带来的损 失是不相同的，因此将不同的航班赋予权重λΒ，λ#Ρ λ 5(λΒ>λΜ>λ〇。所以待调控空域 中所有航班的起飞时刻延误和额外飞行路径的目标函数可以进一步的改写为：
[0127] -条染色体可以计算出一个第一目标函数值（yi)和一个第二目标函数值（y 2)，可 以将这一个Y1的值和一个y 2的值作为一个解，由于一个种群中存在多条染色体，所以每个 种群对应的就有多个Y1的值，y 2的值，即对应有多个解。另外，并不是将一个种群中所有的 yi、y2的值都作为该种群的最终解进行下一步，在此之前，还需要将这多个解之间进行y满 值，y 2的值的比较。若有一解，该解中的y i的值，y 2的值均小于同一种群的其他解中的y满 值，y2的值，则称该解支配其他解。不被其他结果支配的解称之为非支配解，非支配解的集 合就称为非支配解集，所有非支配解将进入种群的下一代进行进化。
[0128] 优选的是，将所述第g代种群中的所述每一条染色体随机分组得到至少两个低维 子染色体，对每个低维子染色体进行差分进化，得到差分进化后的每个低维子染色体，将所 述差分进化后的每个低维子染色体进行合并，生成差分进化后的一条染色体，所述第g代 种群的所述第一目标函数和所述第二目标函数的解集由所述差分进化后的染色体计算得 到。
[0129] 例如，在第1代种群中，将100条染色体中的每一条染色体随机分组得到5组低维 子染色体，将这5组低维子染色体进行差分进化，得到差分进化后的这5组新的低维子染 色体，将这5组新的低维子染色体进行合并，最终生成差分进化后的一条新染色体，以此类 推，生成差分进化后的100条新染色体，根据这100条新染色体，计算第1代种群的第一目 标函数和第二目标函数的解集，这样 就可以提高解集的多样性。这里需要说明的是，差分进 化是一种已经存在的进化方法，主要包括对染色体进行交叉、变异和选择等几个操作，具体 的在此不加以说明。
[0130] 步骤104、第四步，计算所述第g代种群的所述第一目标函数和所述第二目标函数 的解集的多样性函数，得到所述第g代的多样性函数值。
[0131] 图3为本发明空中交通流量调控方法实施例的第一目标函数和第二目标函数的 解集的多样性示意图。如图3所示，将步骤103中所得到的第g代种群的第一目标函数的 解和第二目标函数的解转变成非支配解的解集的形式，该解集为X = (Xl，x2, ...，xn)。
[0132] 计算多样性函数值的公式表示为：
[0134] 其中
为相邻的第一目标函数和第二目标函数的解之间的平均距 离，山为X JP X 1+1之间的距离，d f和d 别为两个极端解与第一目标函数和第二目标函数 的解边界值之间的距离，Cl1表示为：
[0135] (Ii=IIy(Xi)I(Xw)II 2 0〈i〈n
[0136] 其中，y是目标函数向量，y = (yi，y2)，yi为第一目标函数，y2为所述第二目标函 数。
[0137] 当η = 〇时，非支配解的分布性最好，即广域空中交通流量调控达到的效果较好。
[0138] 可以通过上述的公式，计算出第g代的多样性函数值n (g)。
[0139] 步骤105、第五步，根据所述第g代的多样性函数值确定在所述第g代种群中参与 局部搜索的染色体的数量Φ (g)。
[0140] 本实施例的关键步骤是对第g代种群中的染色体进行局部搜索操作，这对提高第 一目标函数和第二目标函数的解的质量和多样性具有重要的意义。随着进化的进行，种群 的多样性会严重下降，太多的染色体都参与局部搜索会导致非支配解的早熟现象，但是如 果局部搜索的染色体数量太少又会导致搜索的不充分。因此在本实施例中，根据第g代的 多样性函数值来确定在第g代种群中参与局部搜索的染色体的数量Φ (g)。具体的，在第g 代种群中参与局部搜索的染色体的数量Φ (g)可以表示为：
[0142] 其中，ps为第g代种群中的染色体数量，τ (g)为第g代局部搜索频率，k为常数 (在本实施例中，以k = 5来举例说明，具体的数可以根据实际情况来设置，在此不加以限 定）。
[0143] 第g代局部搜索频率τ (g)，可以表示为：
[0145] n (g)为第g代的多样性函数值。
[0146] 步骤106、第六步，在所述第g代种群中随机选择Φ (g)条染色体，并替换所述 Φ (g)条染色体中每一染色体的y个基因，将所述第g代种群中除所述Φ (g)条染色体以外 的其他染色体和替换后的所述Φ (g)条染色体作为第g+Ι代种群。
[0147] y个基因为2NXp个基因。其中，p为选择比例，p小于1，在本实施例中p = 0. 1 来举例说明，具体的倍数可以根据实际情况进行设置，在此不加以限定。
[0148] 由于航班规模比较大，因此得到需要进行局部搜索的Φ (gen)条染色体之后并非 对每条染色体的所有基因都进行局部搜索，而是随机选择每条染色体的部分基因进行局部 搜索。首先，从第g代种群中随机选择Φ (g)条染色体，并在这Φ (g)条染色体的每一染色 体中随机选择2NXp个基因。接着，从数据库中随机选择与第一 2NXp个基因对应的第二 2NXp个基因，用第二2NXp个基因替换第一 2NXp个基因，生成替换后的Φ (g)条染色体。 最后将第g代种群中除Φ (g)条染色体以外的其他染色体和替换后的Φ (g)条染色体作为 第g+Ι代种群。
[0149] 图4为本发明空中交通流量调控方法实施例的一条染色体局部搜索示意图。如图 4所示，首先在染色体中随机选择ra、Sb、δ。、^、^、Sf个基因。接着，在数据库中从各自 基因 ra、Sb、Sc、rd、re、6 ￡所对应的各自的可选集合Ra、Ab、Ac、Rd、R e、Af中随机选择对 应的ra，、δ b，、δ 、δ f，基因。最后，将选择出的ra，、δ b，、δ 、δ f，基因替 换各自所对应的ra、Sb、δ。、^、^、Sf基因，生成基因替换后的新染色体。
[0150] 步骤107、第七步，使用所述第g+Ι代种群计算所述第一目标函数和所述第二目标 函数，得到所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集；根据所述 第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集对所述全局变量中的所述 第一目标函数和所述第二目标函数的解集进行更新。
[0151] 根据步骤103中所提供的第一目标函数和第二目标函数的计算公式，使用步骤 106中确定出来的第g+Ι代种群来计算第一目标函数和第二目标函数，得到第g+Ι代种群的 第一目标函数和第二目标函数的解集。
[0152] 然后，根据第g+Ι代种群的第一目标函数和第二目标函数的解集对全局变量中保 存的第一目标函数和第二目标函数的解集进行更新。其中，具体的过程为：
[0153] 首先，将第g+Ι代种群的第一目标函数和第二目标函数的解集中的各个解进行比 较，得到第g+1代种群的非支配解集；
[0154] 其次，将第g+Ι代种群的非支配解集与全局变量中的第一目标函数和第二目标函 数的非支配解集进行比较；
[0155] 最后，如果第g+Ι代种群的非支配解集中存在至少一个解，该至少一个解支配全 局变量中的第一目标函数和第二目标函数的非支配解集中的解，则用该至少一个解替换掉 全局变量中的第一目标函数和第二目标函数的非支配解集中被该至少一个解支配的解。
[0156] 步骤108、第八步，计算所述第g+Ι代种群的所述第一目标函数和所述第二目标函 数的解集的多样性函数，得到所述第g+ι代的多样性函数值。
[0157] 根据步骤104中所提供的多样性函数值的计算公式，计算得到第g+Ι代的多样性 函数值。
[0158] 步骤109、第九步，依次循环执行第五步至第八步的处理，得到第g+n代的多样性 函数值，直到第g+n代到达预定循环代数。
[0159] 在本实施例中，预定循环代数设定为100代（在本实施例中设置循环代数为100 代来举例说明，具体的代数可以根据实际情况进行设置，在此不加以限定）。当第g+n代 小于100代时，依次循环执行步骤105至步骤108的处理，得到第g+n代的多样性函数值 n (g+n)，直到第g+n代到达预定循环代数为止。
[0160] 步骤110、第十步，将所述全局变量中更新后的解集对应的染色体中的每个航班的 起飞时刻和飞行路径来作为待调控空域的调控依据。
[0161] 达到预定的循环代数后，将全局变量中更新后的解集对应的染色体中的每个航班 的起飞时刻和飞行路径来作为待调控空域的调控依据，从而进行空中交通流量调控。本发 明实施例所提供的空中交通流量调控方法能够同时兼顾安全性和经济性，安全性主要参考 空中交通拥挤度，经济性主要参考航班的时间延误，因此这是一个多目标优化问题。在本步 骤中，最终获得的第一目标函数和第二目标函数的解集中包含了多个非支配解，具体选取 哪个解，可以根据实际情况来考虑。例如，如果当前更侧重于安全性，则可以在全局变量的 解集中选取第一目标函数较小的那个结果，如果当前更侧重于经济性，则可以在全局变量 的解集中选取第二目标函数较小的那个结果。
[0162] 本发明实施例中，首先，建立待调控空域的航班和空域信息数据库，将数据库中的 航班的起飞时刻信息和飞行路径信息随机生成对应的染色体，并由这些染色体组成初始种 群，该初始种群定义为第g代种群，根据第g代种群计算出第一目标函数和第二目标函数的 解集，将解集存放在全局变量中。其次，根据第g代种群的第一目标函数和第二目标函数的 解集得到第g代的多样性函数值n (g)，根据该第g代的多样性函数值n (g)确定在第g代 种群中参与局部搜索的染色体的数量Φ (g)，在第g代种群中随机选择Φ (g)条染色体，并 替换Φ (g)条染色体中每一染色体的y个基因，将第g代种群中除Φ (g)条染色体以外的 其他染色体和替换后的Φ (g)条染色体作为第g+l代种群。接着，根据第g+l代种群计算 出第一目标函数和第二目标函数的解集，根据第g+Ι代的解集对全局变量中的解集进行更 新。最后，依次循环计算下一代的第一目标函数和第二目标函数的解集并与全局变量中的 解集进行比较，直到第g+n代到 达预定循环代数为止，将全局变量中的最终的解集对应的 染色体作为待调控空域的调控依据，从而进行空中交通流量调控。该方法通过对每一代种 群参与局部搜索的染色体数量进行动态调整，使每一代种群参与局部搜索的染色体数量都 不相同，这样就可以加强对解空间的搜索能力，不容易陷入局部最优，提高解集的多样性， 能够比传统的遗传算法找到更为满意的结果，保证了在航班安全飞行的前提下尽量兼顾航 空公司的经济利益和航班之间的公平性。
[0163] 最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制； 尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其 依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征 进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技 术方案的范围。
【主权项】
1. 一种空中交通流量调控方法，其特征在于，所述方法包括： 第一步，建立待调控空域的航班和空域信息数据库，所述数据库包括所述待调控空域 中所有航班的起飞时刻和飞行路径的集合； 第二步，生成初始种群，所述初始种群由预设数量的染色体随机组成，一条染色体由所 述数据库中每一航班的一个飞行路径和一个起飞时刻组成，所述一条染色体包括2N个基 因，N为所述数据库中航班的数量，将所述初始种群作为第g代种群，g为自然数； 第三步，使用所述第g代种群计算第一目标函数和第二目标函数，所述第一目标函数 为所述待调控空域的空中交通拥挤度目标函数，所述第二目标函数为所述待调控空域中所 有航班的起飞时刻延误和额外飞行路径的目标函数，得到所述第g代种群的所述第一目标 函数和所述第二目标函数的解集；将所述第g代种群的所述第一目标函数和所述第二目标 函数的解集存放在全局变量中； 第四步，计算所述第g代种群的所述第一目标函数和所述第二目标函数的解集的多样 性函数，得到所述第g代的多样性函数值； 第五步，根据所述第g代的多样性函数值确定在所述第g代种群中参与局部搜索的染 色体的数量Φ (g); 第六步，在所述第g代种群中随机选择Φ (g)条染色体，并替换所述Φ (g)条染色体中 每一染色体的y个基因，将所述第g代种群中除所述Φ (g)条染色体以外的其他染色体和 替换后的所述Φ (g)条染色体作为第g+Ι代种群； 第七步，使用所述第g+Ι代种群计算所述第一目标函数和所述第二目标函数，得到所 述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集；根据所述第g+Ι代种群 的所述第一目标函数和所述第二目标函数的解集对所述全局变量中的所述第一目标函数 和所述第二目标函数的解集进行更新； 第八步，计算所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集的多 样性函数，得到所述第g+Ι代的多样性函数值； 第九步，依次循环执行第五步至第八步的处理，得到第g+n代的多样性函数值，直到第 g+n代到达预定循环代数； 第十步，将所述全局变量中更新后的解集对应的染色体中的每个航班的起飞时刻和飞 行路径来作为待调控空域的调控依据。2. 根据权利要求1所述的方法，其特征在于，所述多样性函数值，表示为：其中，1为相邻的所述第一目标函数和所述第二目标函数的解之间的平 均距离，所述第一目标函数和所述第二目标函数的解集为X = (Χι，χ2,...，χη)，山为X 4口 χ1+1之间的距离，d f和d 别为两个极端解与所述第一目标函数和所述第二目标函数的解 边界值之间的距离，Cl1表示为： d；= I |y(x i)-y(xi+i) I I2 〇<i<n 其中，y是目标函数向量，y = (yi，y2)，yi为所述第一目标函数，y2为所述第二目标函 数。3. 根据权利要求1或2所述的方法，其特征在于，所述根据所述第g代的多样性函数值 确定在所述第g代种群中参与局部搜索的染色体的数量Φ (g)，表示为：其中，ps为所述第g代种群中的染色体数量，τ (g)为第g代局部搜索频率，k为常数； 第g代局部搜索频率τ (g)，表示为：n (g)为所述第g代的多样性函数值。4. 根据权利要求1或2所述的方法，其特征在于，所述y个基因为2N X P个基因；其中， P为选择比例，P小于1。5. 根据权利要求1或2所述的方法，其特征在于，所述使用所述第g代种群计算第一目 标函数和第二目标函数，得到所述第g代种群的所述第一目标函数和所述第二目标函数的 解集，具体包括： 将所述第g代种群中的所述每一条染色体随机分组得到至少两个低维子染色体，对每 个低维子染色体进行差分进化，得到差分进化后的每个低维子染色体，将所述差分进化后 的每个低维子染色体进行合并，生成差分进化后的一条染色体，所述第g代种群的所述第 一目标函数和所述第二目标函数的解集由所述差分进化后的染色体计算得到。6. 根据权利要求1或2所述的方法，其特征在于，所述根据所述第g+Ι代种群的所述第 一目标函数和所述第二目标函数的解集对所述全局变量中的所述第一目标函数和所述第 二目标函数的解集进行更新，具体包括： 将所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集中的各个解进 行比较，得到所述第g+Ι代种群的非支配解集； 将所述第g+Ι代种群的非支配解集与所述全局变量中的所述第一目标函数和所述第 二目标函数的解集进行比较，如果所述第g+Ι代种群的非支配解集中存在至少一个解，所 述至少一个解支配所述全局变量中的所述第一目标函数和所述第二目标函数的解集中的 解，则用所述至少一个解替换掉所述全局变量中的所述第一目标函数和所述第二目标函数 的解集中被所述至少一个解支配的解。7. 根据权利要求1所述的方法，其特征在于，所述第一目标函数为所述待调控空域的 空中交通拥挤度目标函数，表示为：其中，表不扇区Sk在时间T内的总拥挤度，表不扇区Sk 在时间T内的最大拥挤度，P表示扇区的数量，Φ和0是介于O到1之间的权重系数； 所述待调控空域包括P个扇区，所述扇区Sk表示P个扇区中的第k个扇区，所述扇区 Sk的拥挤度为所述扇区S k在时间T内的一个时刻t的航班数量，所述扇区S k的总拥挤度为 所述扇区Sk在时间T内的航班数量之和，所述扇区Sk的最大拥挤度为所述扇区S k在时间T 内一个时刻t的航班数量的最大值。8. 根据权利要求7所述的方法，其特征在于，所述扇区S ,在t时刻的负荷(?)包括： 监视负荷》⑴和协调负荷Ra G)，表示为：其中，w, Φ e [〇，1]为所述监视负荷和所述协调负荷的权重； 所述监视负荷(力，表示为：其中，MsJi)与t时刻在所述扇区&内的飞机数目的平方成正比，(，)表示t时刻 所述扇区Sk的监视负荷阈值； 所述协调负荷(0可以表示为：其中，仏的与七时刻穿越所述扇区Sk边界的飞机数目的平方成正比，（:、（0表示t时 刻所述扇区Sk的协调负荷阈值。9. 根据权利要求1或2所述的方法，其特征在于，所述第二目标函数为所述待调控空域 中所有航班的起飞时刻延误和额外飞行路径的目标函数，所述起飞时刻延误为所述航班的 起飞时刻与所述数据库中所述航班的最早起飞时刻的差值；所述额外飞行路径为所述航班 的飞行路径与所述数据库中所述航班的最短飞行路径的差值； 所述第二目标函数表示为：其中，S (i)为所述航班总的延误，表示为： δ ⑴=δ s(i)+ δ 力） 其中，Ss⑴为所述航班的地面延误，δ力）为所述航班的空中延误。10. 根据权利要求9所述的方法，其特征在于，所述数据库中所述航班包括大、中、小型 航班； 所述待调控空域中所有航班的起飞时刻延误和额外飞行路径的目标函数，具体表示 为：其中為為以分别表示所述大冲^型航班的数量"^人^人次别表示所述大冲、 小型航班对应的权重系数（λ Β> λ Μ> λ s)。
【专利摘要】本发明实施例提供一种空中交通流量调控方法。本发明空中交通流量调控方法通过对每一代种群参与局部搜索的染色体数量进行动态调整，使每一代种群参与局部搜索的染色体数量都不相同，这样就可以加强对解空间的搜索能力，不容易陷入局部最优，提高解集的多样性，能够比传统的遗传算法找到更为满意的结果，保证了在航班安全飞行的前提下尽量兼顾航空公司的经济利益和航班之间的公平性。
【IPC分类】G06N3/12, G08G5/00
【公开号】CN105489066
【申请号】CN201410471476
【发明人】张学军, 管祥民, 雷佳兴
【申请人】北京航空航天大学
【公开日】2016年4月13日
【申请日】2014年9月16日
【技术领域】
[0001] 本发明实施例涉及调控技术，尤其涉及一种空中交通流量调控方法。
【背景技术】
[0002] 近年来航空运输业取得了迅猛发展，但是随着空中飞机数量的不断增多，空域拥 挤问题变得日益严重，不仅降低了飞行的安全性，而且给民航带来了巨大的经济损失。空中 交通流量管理是解决空中交通拥挤最为有效和经济的手段，通过改变飞机的起飞时刻、飞 行路径达到流量调控的目的，从而降低空中交通拥挤度，提高空域利用率。其中，改变飞机 的起飞时刻就是改变飞机的时间延误，改变飞行路径也就是改变空域的拥挤度。
[0003] 随着飞机数量的剧增，各部分空域之间的关联性增强，广域空中交通流量调控的 方法逐渐引起了人们的注意。广域空中交通流量管理的首要目标是保证飞机飞行的安全 性，即要降低整个空域拥挤度，其次在保证安全飞行的前提下还要兼顾航空公司的经济利 益和航班之间的公平性，即要尽量均衡地分配飞机的时间延误。其中，广域空域由各部分空 域构成，广域空中交通流量调控需要同时优化所有飞机的时间延误和各个空域拥挤度，是 一个多目标的大规模组合优化问题，而且这两个目标是一对矛盾，在减小空域拥挤度的同 时必然会增加时间延误，因此通过传统的广域空中交通流量调控算法将得到的时间延误和 空域拥挤度的解集转换为一组非支配解，并计算该非支配解的多样性，多样性是评价非支 配解好坏的一个重要指标，它可以反映解的分布是否均匀，如果分布均匀则广域空中交通 流量调控达到的效果较好。
[0004] 传统的遗传算法在解决多目标组合优化问题时已经表现出了一定的优势，但是在 处理大规模的多目标组合优化问题时搜索能力有限，很难充分搜索整个解空间，容易陷入 局部最优，这样就会对航空公司的经济利益和航班之间的公平性产生影响。
【发明内容】
[0005] 本发明实施例提供一种空中交通流量调控方法，以解决在处理大规模的多目标组 合优化问题时搜索能力有限，很难充分搜索整个解空间，容易陷入局部最优，会对航空公司 的经济利益和航班之间的公平性产生影响的问题。
[0006] 本发明实施例提供一种空中交通流量调控方法，包括：
[0007] 第一步，建立待调控空域的航班和空域信息数据库，所述数据库包括所述待调控 空域中所有航班的起飞时刻和飞行路径的集合；
[0008] 第二步，生成初始种群，所述初始种群由预设数量的染色体随机组成，一条染色体 由所述数据库中每一航班的一个飞行路径和一个起飞时刻组成，所述一条染色体包括2N 个基因，N为所述数据库中航班的数量，将所述初始种群作为第g代种群，g为自然数；
[0009] 第三步，使用所述第g代种群计算第一目标函数和第二目标函数，所述第一目标 函数为所述待调控空域的空中交通拥挤度目标函数，所述第二目标函数为所述待调控空域 中所有航班的起飞时刻延误和额外飞行路径的目标函数，得到所述第g代种群的所述第一 目标函数和所述第二目标函数的解集；将所述第g代种群的所述第一目标函数和所述第二 目标函数的解集存放在全局变量中；
[0010] 第四步，计算所述第g代种群的所述第一目标函数和所述第二目标函数的解集的 多样性函数，得到所述第g代的多样性函数值；
[0011] 第五步，根据所述第g代的多样性函数值确定在所述第g代种群中参与局部搜索 的染色体的数量Φ (g);
[0012] 第六步，在所述第g代种群中随机选择Φ (g)条染色体，并替换所述Φ (g)条染色 体中每一染色体的y个基因，将所述第g代种群中除所述Φ (g)条染色体以外的其他染色 体和替换后的所述Φ (g)条染色体作为第g+l代种群；
[0013] 第七步，使用所述第g+Ι代种群计算所述第一目标函数和所述第二目标函数，得 到所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集；根据所述第g+Ι代 种群的所述第一目标函数和所述第二目标函数的解集对所述全局变量中的所述第一目标 函数和所述第二目标函数的解集进行更新；
[0014] 第八步，计算所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集 的多样性函数，得到所述第g+ι代的多样性函数值；
[0015] 第九步，依次循环执行第五步至第八步的处理，得到第g+n代的多样性函数值，直 到第g+n代到达预定循环代数；
[0016] 第十步，将所述全局变量中更新后的解集对应的染色体中的每个航班的起飞时刻 和飞行路径来作为待调控空域的调控依据。
[0017] 进一步地，上述多样性函数值，表示为：
[0019] 其中，
为相邻的所述第一目标函数和所述第二目标函数的解之间 的平均距离，所述第一目标函数和所述第二目标函数的解集为X = (Xl，x2, ...，xn)，山为X i 和x1+1之间的距离，d ￡和d i分别为两个极端解与所述第一目标函数和所述第二目标函数的 解边界值之间的距离，Cl1表示为：
[0020] (Ii=IIy(Xi)I(Xw)II 2 0〈i〈n
[0021] 其中，y是目标函数向量，y = (yi，y2)，yi为所述第一目标函数，y2为所述第二目 标函数。
[0022] 上述根据所述第g代的多样性函数值确定在所述第g代种群中参与局部搜索的染 色体的数量Φ (g)，表示为：
[0024] 其中，ps为所述第g代种群中的染色体数量，τ (g)为第g代局部搜索频率，k为 常数；
[0025] 第g代局部搜索频率τ (g)，表示为：
[0027] n (g)为所述第g代的多样性函数值。
[0028] 上述y个基因为2NXp个基因；其中，p为选择比例，p小于1。
[0029] 上述使用所述第g代种群计算第一目标函数和第二目标函数，得到所述第g代种 群的所述第一目标函数和所述第二目标函数的解集，具体包括：
[0030] 将所述第g代种群中的所述每一条染色体随机分组得到至少两个低维子染色体， 对每个低维子染色体进行差分进化，得到差分进化后的每个低维子染色体，将所述差分进 化后的每个低维子染色体进行合并，生成差分进化后的一条染色体，所述第g代种群的所 述第一目标函数和所述第二目标函数的解集由所述差分进化后的染色体计算得到。
[0031] 上述根据所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集对 所述全局变量中的所述第一目标函数和所述第二目标函数的解集进行更新，具体包括：
[0032] 将所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集中的各个 解进行比较，得到所述第g+Ι代种群的非支配解集；
[0033] 将所述第g+Ι代种群的非支配解集与所述全局变量中的所述第一目标函数和所 述第二目标函数的解集进行比较，如果所述第g+Ι代种群的非支配解集中存在至少一个 解，所述至少一个解支配所述全局变量中的所述第一目标函数和所述第二目标函数的解集 中的解，则用所述至少一个解替换掉所述全局变量中的所述第一目标函数和所述第二目标 函数的解集中被所述至少一个解支配的解。
[0034] 上述第一目标函数为所述待调控空域的空中交通拥挤度目标函数，表示为：
[0036] 其中，
表示扇区Sk在时间T内的总拥挤度，t e T，
表示扇 区Sk在时间T内的最大拥挤度，P表示扇区的数量，Φ和W是介于0到1之间的权重系数；
[0037] 所述待调控空域包括P个扇区，所述扇区Sk表示P个扇区中的第k个扇区，所述扇 区S k的拥挤度为所述扇区Sk在时间T内的一个时刻t的航班数量，所述扇区总拥挤 度为所述扇区S k在时间T内的航班数量之和，所述扇区S k的最大拥挤度为所述扇区S ,在 时间T内一个时刻t的航班数量的最大值。
[0038] 上述扇区&在t时刻的负荷KO包括：监视负荷(〇和协调负荷(?)， 表示为：
[0040] 其中，w, Φ e [0, 1]为所述监视负荷和所述协调负荷的权重；
[0041] 所述监视负荷(0，表示为：
[0043] 其中，MSi (?)与t时刻在所述扇区&内的飞机数目的平方成正比，(?)表示t 时刻所述扇区Sk的监视负荷阈值；
[0044] 所述协调负荷(0可以表示为：
[0046] 其中，义⑴与t时刻穿越所述扇区Sk边界的飞机数目的平方成正比，⑴表 示t时刻所述扇 区S k的协调负荷阈值。
[0047] 上述扇区&在t时刻的负荷Ks (〇包括：监视负荷》;a (〇和协调负荷W。.Si (〇， 表示为：
[0049] 其中，w，Φ e [0, 1]为所述监视负荷和所述协调负荷的权重；
[0050] 所述监视负荷巧略(?)，表示为：
[0052] 其中，(?)与t时刻在所述扇区&内的飞机数目的平方成正比，C," Si (〇表示t 时刻所述扇区Sk的监视负荷阈值；
[0053] 所述协调负荷》（〇可以表示为：
[0055] 其中，Q⑴与t时刻穿越所述扇区Sk边界的飞机数目的平方成正比，Q (〇表 示t时刻所述扇区Sk的协调负荷阈值。
[0056] 上述第二目标函数为所述待调控空域中所有航班的起飞时刻延误和额外飞行路 径的目标函数，所述起飞时刻延误为所述航班的起飞时刻与所述数据库中所述航班的最早 起飞时刻的差值；所述额外飞行路径为所述航班的飞行路径与所述数据库中所述航班的最 短飞行路径的差值；
[0057] 所述第二目标函数表示为：
[0059] 其中，δ⑴为所述航班总的延误，表示为：
[0060] δ ⑴=δ s(i) + δ r(i)
[0061] 其中，Ss⑴为所述航班的地面延误，δ力）为所述航班的空中延误。
[0062] 上述数据库中所述航班包括大、中、小型航班；
[0063] 所述待调控空域中所有航班的起飞时刻延误和额外飞行路径的目标函数，具体表 示为：
[0065] 其中，NB，NM，Nj别表示所述大、中、小型航班的数量，λ Β，λΜ，别表示所述 大、中、小型航班对应的权重系数（λ Β> λ Μ> λ s)。
[0066] 本发明实施例空中交通流量调控方法，通过对每一代种群参与局部搜索的染色体 数量进行动态调整，使每一代种群参与局部搜索的染色体数量都不相同，这样就可以加强 对解空间的搜索能力，不容易陷入局部最优，提高解集的多样性，能够比传统的遗传算法找 到更为满意的结果，保证了在航班安全飞行的前提下尽量兼顾航空公司的经济利益和航班 之间的公平性。
【附图说明】
[0067] 为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现 有技术描述中所需要使用的附图作一简单地介绍，显而易见地，下面描述中的附图是本发 明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动性的前提下，还可以 根据这些附图获得其他的附图。
[0068] 图1为本发明空中交通流量调控方法实施例的流程图；
[0069] 图2为本发明空中交通流量调控方法实施例的染色体的编码结构示意图；
[0070] 图3为本发明空中交通流量调控方法实施例的第一目标函数和第二目标函数的 解集的多样性不意图；
[0071] 图4为本发明空中交通流量调控方法实施例的一条染色体局部搜索示意图。
【具体实施方式】
[0072] 为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例 中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是 本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员 在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0073] 首先介绍如下概念与定义：
[0074] 航路：由国家统一划定的具有一定宽度的空中通道。有较完善的通信、导航设备， 宽度通常为20KM。划定航路的目的是维护空中交通秩序，提高空间利用率，保证飞行安全。
[0075] 航线：飞机飞行的路线称为空中交通线，简称航线。飞机的航线不仅确定了飞机飞 行具体方向、起讫点和经停点，而且还根据空中交通管制的需要，规定了航线的宽度和飞行 高度，以维护空中交通秩序，保证飞行安全。
[0076] 空域：空域就是飞行所占用的空间。通常以明显地标或导航台为标志。空域同领 土、领海一样，是国家的主权范围，也是重要的军用及民航资源。为了便于地面管制员对于 飞行流量的管理，空域通常被划分为多个扇区，每个扇区可容纳的飞行流量与扇区的大小、 天气情况、管制员数量以及导航设备有关。
[0077] 客机机型：客机按起飞重量与载客量分为小型、中型、大型客机，不同国家划分的 标准也不相同，我国民航总局是按飞机客座数划分大、中、小型飞机的，飞机的客座数在100 座以下的为小型机（S)，100-200座之间为中型机（M)，200座以上为大型机（B)。
[0078] 协同进化：利用分而治之的思想将一个高维问题分解为多个低维问题进行求解， 然后通过低维问题的解的合作得到高维问题的解，优点是可以降低问题的复杂度。
[0079] 文化基因算法（Memetic Algorithm，简称：MA):用局部启发式搜索来模拟由大量 专业知识支撑的变异过程，文化基因算法是一种基于种群的全局搜索和基于个体的局部启 发式搜索的结合体。文化基因算法提出的是一种框架、是一个概念，在这个框架下，采用不 同的搜索策略可以构成不同的文化基因算法，如全局搜索策略可以采用遗传算法、进化策 略、进化规划等，局部搜索策略可以采用爬山搜索、模拟退火、贪婪算法、禁忌搜索、导引式 局部搜索等。
[0080] 在本发明中做出如下假设：
[0081] (1)所有的飞机的飞行速度都一样，而且在飞行过程中保持不变；
[0082] (2)所有飞机的起飞时刻都是一个含有有限个元素的集合；
[0083] (3)所有飞机的飞行路径在一定的范围内可选；
[0084] (4)同一个起止点之间的飞机，可选路径集合是一样的。
[0085] 基于上述假设，对具体的实施方式进行说明。
[0086] 图1为本发明空中交通流量调控方法实施例的流程图，如图1所示，本实施例的方 法可以包括：
[0087] 步骤101、第一步，建立待调控空域的航班和空域信息数据库，所述数据库包括所 述待调控空域中所有航班的起飞时刻和飞行路径的集合。
[0088] 所有航班的起飞时刻都必须考虑旅客的需求和航空公司的情况，必须在合理的范 围内进行选择，每个航班的飞行路径集合也有一定的限制，对于每个航班来说，它的最长飞 行路径不能超过最短飞行路径长度的1. 3倍（在本实施例中，以1. 3倍来举例说明，具体的 倍数可以根据实际情况进行设置，在此不加以限定）。空中交通流量调控方法就是通过改变 航班的起飞时刻或飞行路径，使其提前或延后进入某一扇区，从而达到降低该扇区拥挤度 的效果。
[0089] 首先，建立待调控空域的航班和空域信息数据库，其中，该数据库由待调控空域中 所有航班的起飞时刻和飞行路径的集合组成。具体的，每个航班都包括一组变量（δ i, !Ti)， S1表示航班起飞延误的时间，例如一架航班最早起飞时刻为8:20,但是实际起飞时刻为 8:40,所以该航班起飞延误的时间为20分钟。 Γι表示重新选择的飞行路径，δ JPri的可 选集合可以分别表示为：
[0090] Δ = 〇, 1，· · ·，δ ρ-1，δ ρ
[0091] R = r〇, r1; r2, . . . , rnax
[0092] δ p表示航班可以延误的最大时间，r。表示最短飞行路径，r_表示最差飞行路径。 例如一架航班的最早起飞时刻为8:20,可选起飞时刻可以为8:30、8:40、8:50,在本实施例 中，以相邻的时间差为10分钟来举例说明，具体的差值可以根据实际需求进行设置，在此 不加以限定。该航班的最短飞行路径为航线1，可选飞行路径可以为航线2、航线3、航线4。 在本实施例中，以相邻的航线差为20KM来举例说明，具体的差值可以根据实际需求进行设 置，在此不加以限定。在数据库中将起飞时刻和飞行路径转变成对应的数据格式，例如将最 早起飞时刻8:20转变成对应的0数据格式，将可选起飞时间8 :30、8:40、8:50转变成对应 为1、2、3的数据格式，所以该航班的起飞时刻可选数据集合为△= 0, 1，2, 3。将最短飞行 路径航线1转变成对应的1数据格式，将可选飞行路径航线2、航线3、航线4转变成对应为 2、3、4的数据格式，所以该航班的飞行路径可选数据集合为R = 1，2, 3, 4。
[0093] 另外，还有一个约束是连续航班之间的制约，如果一架航班执行 完一次航班任务 后还有另外的航班任务，则这两个航班称为连续航班，两个航班之间必须留有充足的时间 进行飞机的安全检查和清扫工作。假设对于大型机该时间为T b，航班Fab是航班F a的后续 航班，如果Fa在飞行途中花费的时间为Ta，起飞时刻集合 a=〇，l，...，δ a-l，Sa
[0094] 则航班Fab的起飞时刻集合Δ abSTa+TB之后的某个时刻集合。对于小型机和中型 机，连续航班之间的时间间隔记为TjP T M。
[0095] 步骤102、第二步，生成初始种群，所述初始种群由预设数量的染色体随机组成，一 条染色体由所述数据库中每一航班的一个飞行路径和一个起飞时刻组成，所述一条染色体 包括2N个基因，N为所述数据库中航班的数量，将所述初始种群作为第g代种群，g为自然 数。
[0096] 在本实施例中，初始种群由100条染色体组成来举例说明（染色体的数量可以根 据实际需求设定，在此不加以限定）。将初始种群定义为第g代种群，g为自然数，即第g代 初始种群由100条染色体所构成，初始种群就是第1代种群，然后每进化完一代g就加1，直 到达到最大进化代数。这里的g是一个变量，随着进化的进行不断增大。其中，每一条染色 体都是由所有航班的一个飞行路径和一个起飞时刻构成，因此每一条染色体的长度是航班 数量的2倍，所以将数据库中的所有航班数量设置为N，每一条染色体就包括2N个基因。
[0097] 具体的每一条染色体生成过程为：
[0098] 首先，读入数据库中所有航班N的可选飞行路径集合数据和起飞时刻的上下限数 据，作为可选数据集合。接着，在可选数据集合内随机选择数据。最后，初始化每个航班的 起飞时刻和飞行路径，生成一条染色体。
[0099] 图2为本发明空中交通流量调控方法实施例的染色体的编码结构示意图。如 图2所示，&表示航班η的可选飞行路径集合，△ "表示航班η的可选起飞时刻集合，η = 1，. . .，k, . . .，N，N 表示航班数量。一条染色体由;Tp δ . . .，rk、δ k, . . .，rN、δ Ν，2Ν 个基因 组成。
[0100] 另外，将全局变量初始化，初始化的全局变量为空集，用来存放进化最新找到的第 一目标函数和第二目标函数的解集。
[0101] 步骤103、第三步，使用所述第g代种群计算第一目标函数和第二目标函数，所述 第一目标函数为所述待调控空域的空中交通拥挤度目标函数，所述第二目标函数为所述待 调控空域中所有航班的起飞时刻延误和额外飞行路径的目标函数，得到所述第g代种群的 所述第一目标函数和所述第二目标函数的解集；将所述第g代种群的所述第一目标函数和 所述第二目标函数的解集存放在全局变量中。
[0102] 利用第g代种群计算第一目标函数和第二目标函数。
[0103] 其中，第一目标函数为待调控空域的空中交通拥挤度目标函数。这里需要说明的 是，待调控空域的空中交通拥挤度可以通过引入扇区来进行量化，扇区的拥挤度与扇区内 的航班数量和通过扇区边界的航班数量有关，当航班数量小于扇区容量阈值的时候拥挤度 为0,当航班数量超过阈值时，扇区拥挤度会以平方数量级的趋势急剧上升。
[0104] 对于每个航班来说，它的飞行计划就是在某一时刻进入某个扇区然后在随后某一 时刻离开该扇区，因此一个航班计划可以表示为：
[0105] L = (S1, Tin1, Tout1), (S2, Tin2, Tout2),. . . , (Sk, Tink, Toutk),...
[0106] Sk表示航班经过的第k个扇区，Tin k表示进入该扇区的时刻，Tout k表示离开该扇 区的时刻。
[0107] 扇区&在t时刻的负荷》:? (〇包括：监视负荷》⑴和协调负荷G)，其负 荷Md表示为：
[0109] 其中，w, Φ e [0, 1]为监视负荷和协调负荷的权重。
[0110]监视负荷％，表示为：
[0112] 其中，(/)与t时刻在所述扇区&内的飞机数目的平方成正比，C mii (?)表示t 时刻所述扇区Sk的监视负荷阈值；
[0113] 所述协调负荷(〇可以表示为：
[0115] 其中，CSi(i)与t时刻穿越所述扇区Sk边界的飞机数目的平方成正比，（0表 示t时刻所述扇区S k的协调负荷阈值。
[0116] 所以，待调控空域的空中交通拥挤度目标函数最终可以表示为：
[0118] 其中，
表示扇区Sk在时间T内的总拥挤度，t e τ，
表示扇 区Sk在时间T内的最大拥挤度，P表示扇区的数量，Φ和P是介于0到1之间的权重系数。
[0119] 将待调控空域分成P个扇区，该待调控空域的空中交通拥挤度与P个扇区内的航 班数量和通过P个扇区边界的航班数量有关。其中，扇区S k表示P个扇区中的第k个扇区， 扇区Sk的拥挤度为扇区S k在时间T内的一个时刻t的航班数量，扇区S k的总拥挤度为扇区 Sk在时间T内的航班数量之和，扇区Sk的最大拥挤度为扇区Sk在时间T内一个时刻t的航 班数量的最大值。
[0120] 71表示所有扇区的拥挤度之和，Φ和P分别表示每个扇区内总拥挤度和最大拥挤 度在目标函数中所占的比重。
[0121] 第二目标函数为待调控空域中所有航班的起飞时刻延误和额外飞行路径的目标 函数。其中，起飞时刻延误为一架航班的实际的起飞时刻与上述数据库中该航班的最早起 飞时刻的差值。额外飞行路径为一架航班的飞行路径与上述数据库中该航班的最短飞行路 径的差值。
[0122] 对于航班，如果航班i计划在4时刻起飞，而实际上它在t "时刻起飞，这样航班 的地面延误可以表示为：Ss(i) =tn-tk。假设?；表示航班实际飞行需要的时间，T。表示最 短路径需要的时间，由于相同的时间内空中飞行的花费是地面延误的3倍（在本实施例中， 以3倍来举例说明，具体的倍数可以根据实际情况进行设置，在此不加以限定），所以航班 的空中延误可以表示为：\(i) =3*(?；-Τ。）。因此总的延误δ⑴可以表示为：δ (i)= S s(i)+ δ Ji)。为了保证航班之间的公平性，这里将线性的目标函数改为平方和的形式，例 如同样是两个航班一共延误20分钟，我们希望每个航班延误10分钟，而不是一个延误20 分钟，一个没有延误。
[0123] 所以待调控空域中所有航班的起飞时刻延误和额外飞行路径的目标函数可以表 示为：
[0125] 进一步的，在所有航班中，可以将航班机型分成三类，即大、中、小型三种机型，这 三种机型的航班数量分别为：Nb，NJPNs，对于不同机型的航班，相同的时间延误带来的损 失是不相同的，因此将不同的航班赋予权重λΒ，λ#Ρ λ 5(λΒ>λΜ>λ〇。所以待调控空域 中所有航班的起飞时刻延误和额外飞行路径的目标函数可以进一步的改写为：
[0127] -条染色体可以计算出一个第一目标函数值（yi)和一个第二目标函数值（y 2)，可 以将这一个Y1的值和一个y 2的值作为一个解，由于一个种群中存在多条染色体，所以每个 种群对应的就有多个Y1的值，y 2的值，即对应有多个解。另外，并不是将一个种群中所有的 yi、y2的值都作为该种群的最终解进行下一步，在此之前，还需要将这多个解之间进行y满 值，y 2的值的比较。若有一解，该解中的y i的值，y 2的值均小于同一种群的其他解中的y满 值，y2的值，则称该解支配其他解。不被其他结果支配的解称之为非支配解，非支配解的集 合就称为非支配解集，所有非支配解将进入种群的下一代进行进化。
[0128] 优选的是，将所述第g代种群中的所述每一条染色体随机分组得到至少两个低维 子染色体，对每个低维子染色体进行差分进化，得到差分进化后的每个低维子染色体，将所 述差分进化后的每个低维子染色体进行合并，生成差分进化后的一条染色体，所述第g代 种群的所述第一目标函数和所述第二目标函数的解集由所述差分进化后的染色体计算得 到。
[0129] 例如，在第1代种群中，将100条染色体中的每一条染色体随机分组得到5组低维 子染色体，将这5组低维子染色体进行差分进化，得到差分进化后的这5组新的低维子染 色体，将这5组新的低维子染色体进行合并，最终生成差分进化后的一条新染色体，以此类 推，生成差分进化后的100条新染色体，根据这100条新染色体，计算第1代种群的第一目 标函数和第二目标函数的解集，这样 就可以提高解集的多样性。这里需要说明的是，差分进 化是一种已经存在的进化方法，主要包括对染色体进行交叉、变异和选择等几个操作，具体 的在此不加以说明。
[0130] 步骤104、第四步，计算所述第g代种群的所述第一目标函数和所述第二目标函数 的解集的多样性函数，得到所述第g代的多样性函数值。
[0131] 图3为本发明空中交通流量调控方法实施例的第一目标函数和第二目标函数的 解集的多样性示意图。如图3所示，将步骤103中所得到的第g代种群的第一目标函数的 解和第二目标函数的解转变成非支配解的解集的形式，该解集为X = (Xl，x2, ...，xn)。
[0132] 计算多样性函数值的公式表示为：
[0134] 其中
为相邻的第一目标函数和第二目标函数的解之间的平均距 离，山为X JP X 1+1之间的距离，d f和d 别为两个极端解与第一目标函数和第二目标函数 的解边界值之间的距离，Cl1表示为：
[0135] (Ii=IIy(Xi)I(Xw)II 2 0〈i〈n
[0136] 其中，y是目标函数向量，y = (yi，y2)，yi为第一目标函数，y2为所述第二目标函 数。
[0137] 当η = 〇时，非支配解的分布性最好，即广域空中交通流量调控达到的效果较好。
[0138] 可以通过上述的公式，计算出第g代的多样性函数值n (g)。
[0139] 步骤105、第五步，根据所述第g代的多样性函数值确定在所述第g代种群中参与 局部搜索的染色体的数量Φ (g)。
[0140] 本实施例的关键步骤是对第g代种群中的染色体进行局部搜索操作，这对提高第 一目标函数和第二目标函数的解的质量和多样性具有重要的意义。随着进化的进行，种群 的多样性会严重下降，太多的染色体都参与局部搜索会导致非支配解的早熟现象，但是如 果局部搜索的染色体数量太少又会导致搜索的不充分。因此在本实施例中，根据第g代的 多样性函数值来确定在第g代种群中参与局部搜索的染色体的数量Φ (g)。具体的，在第g 代种群中参与局部搜索的染色体的数量Φ (g)可以表示为：
[0142] 其中，ps为第g代种群中的染色体数量，τ (g)为第g代局部搜索频率，k为常数 (在本实施例中，以k = 5来举例说明，具体的数可以根据实际情况来设置，在此不加以限 定）。
[0143] 第g代局部搜索频率τ (g)，可以表示为：
[0145] n (g)为第g代的多样性函数值。
[0146] 步骤106、第六步，在所述第g代种群中随机选择Φ (g)条染色体，并替换所述 Φ (g)条染色体中每一染色体的y个基因，将所述第g代种群中除所述Φ (g)条染色体以外 的其他染色体和替换后的所述Φ (g)条染色体作为第g+Ι代种群。
[0147] y个基因为2NXp个基因。其中，p为选择比例，p小于1，在本实施例中p = 0. 1 来举例说明，具体的倍数可以根据实际情况进行设置，在此不加以限定。
[0148] 由于航班规模比较大，因此得到需要进行局部搜索的Φ (gen)条染色体之后并非 对每条染色体的所有基因都进行局部搜索，而是随机选择每条染色体的部分基因进行局部 搜索。首先，从第g代种群中随机选择Φ (g)条染色体，并在这Φ (g)条染色体的每一染色 体中随机选择2NXp个基因。接着，从数据库中随机选择与第一 2NXp个基因对应的第二 2NXp个基因，用第二2NXp个基因替换第一 2NXp个基因，生成替换后的Φ (g)条染色体。 最后将第g代种群中除Φ (g)条染色体以外的其他染色体和替换后的Φ (g)条染色体作为 第g+Ι代种群。
[0149] 图4为本发明空中交通流量调控方法实施例的一条染色体局部搜索示意图。如图 4所示，首先在染色体中随机选择ra、Sb、δ。、^、^、Sf个基因。接着，在数据库中从各自 基因 ra、Sb、Sc、rd、re、6 ￡所对应的各自的可选集合Ra、Ab、Ac、Rd、R e、Af中随机选择对 应的ra，、δ b，、δ 、δ f，基因。最后，将选择出的ra，、δ b，、δ 、δ f，基因替 换各自所对应的ra、Sb、δ。、^、^、Sf基因，生成基因替换后的新染色体。
[0150] 步骤107、第七步，使用所述第g+Ι代种群计算所述第一目标函数和所述第二目标 函数，得到所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集；根据所述 第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集对所述全局变量中的所述 第一目标函数和所述第二目标函数的解集进行更新。
[0151] 根据步骤103中所提供的第一目标函数和第二目标函数的计算公式，使用步骤 106中确定出来的第g+Ι代种群来计算第一目标函数和第二目标函数，得到第g+Ι代种群的 第一目标函数和第二目标函数的解集。
[0152] 然后，根据第g+Ι代种群的第一目标函数和第二目标函数的解集对全局变量中保 存的第一目标函数和第二目标函数的解集进行更新。其中，具体的过程为：
[0153] 首先，将第g+Ι代种群的第一目标函数和第二目标函数的解集中的各个解进行比 较，得到第g+1代种群的非支配解集；
[0154] 其次，将第g+Ι代种群的非支配解集与全局变量中的第一目标函数和第二目标函 数的非支配解集进行比较；
[0155] 最后，如果第g+Ι代种群的非支配解集中存在至少一个解，该至少一个解支配全 局变量中的第一目标函数和第二目标函数的非支配解集中的解，则用该至少一个解替换掉 全局变量中的第一目标函数和第二目标函数的非支配解集中被该至少一个解支配的解。
[0156] 步骤108、第八步，计算所述第g+Ι代种群的所述第一目标函数和所述第二目标函 数的解集的多样性函数，得到所述第g+ι代的多样性函数值。
[0157] 根据步骤104中所提供的多样性函数值的计算公式，计算得到第g+Ι代的多样性 函数值。
[0158] 步骤109、第九步，依次循环执行第五步至第八步的处理，得到第g+n代的多样性 函数值，直到第g+n代到达预定循环代数。
[0159] 在本实施例中，预定循环代数设定为100代（在本实施例中设置循环代数为100 代来举例说明，具体的代数可以根据实际情况进行设置，在此不加以限定）。当第g+n代 小于100代时，依次循环执行步骤105至步骤108的处理，得到第g+n代的多样性函数值 n (g+n)，直到第g+n代到达预定循环代数为止。
[0160] 步骤110、第十步，将所述全局变量中更新后的解集对应的染色体中的每个航班的 起飞时刻和飞行路径来作为待调控空域的调控依据。
[0161] 达到预定的循环代数后，将全局变量中更新后的解集对应的染色体中的每个航班 的起飞时刻和飞行路径来作为待调控空域的调控依据，从而进行空中交通流量调控。本发 明实施例所提供的空中交通流量调控方法能够同时兼顾安全性和经济性，安全性主要参考 空中交通拥挤度，经济性主要参考航班的时间延误，因此这是一个多目标优化问题。在本步 骤中，最终获得的第一目标函数和第二目标函数的解集中包含了多个非支配解，具体选取 哪个解，可以根据实际情况来考虑。例如，如果当前更侧重于安全性，则可以在全局变量的 解集中选取第一目标函数较小的那个结果，如果当前更侧重于经济性，则可以在全局变量 的解集中选取第二目标函数较小的那个结果。
[0162] 本发明实施例中，首先，建立待调控空域的航班和空域信息数据库，将数据库中的 航班的起飞时刻信息和飞行路径信息随机生成对应的染色体，并由这些染色体组成初始种 群，该初始种群定义为第g代种群，根据第g代种群计算出第一目标函数和第二目标函数的 解集，将解集存放在全局变量中。其次，根据第g代种群的第一目标函数和第二目标函数的 解集得到第g代的多样性函数值n (g)，根据该第g代的多样性函数值n (g)确定在第g代 种群中参与局部搜索的染色体的数量Φ (g)，在第g代种群中随机选择Φ (g)条染色体，并 替换Φ (g)条染色体中每一染色体的y个基因，将第g代种群中除Φ (g)条染色体以外的 其他染色体和替换后的Φ (g)条染色体作为第g+l代种群。接着，根据第g+l代种群计算 出第一目标函数和第二目标函数的解集，根据第g+Ι代的解集对全局变量中的解集进行更 新。最后，依次循环计算下一代的第一目标函数和第二目标函数的解集并与全局变量中的 解集进行比较，直到第g+n代到 达预定循环代数为止，将全局变量中的最终的解集对应的 染色体作为待调控空域的调控依据，从而进行空中交通流量调控。该方法通过对每一代种 群参与局部搜索的染色体数量进行动态调整，使每一代种群参与局部搜索的染色体数量都 不相同，这样就可以加强对解空间的搜索能力，不容易陷入局部最优，提高解集的多样性， 能够比传统的遗传算法找到更为满意的结果，保证了在航班安全飞行的前提下尽量兼顾航 空公司的经济利益和航班之间的公平性。
[0163] 最后应说明的是：以上各实施例仅用以说明本发明的技术方案，而非对其限制； 尽管参照前述各实施例对本发明进行了详细的说明，本领域的普通技术人员应当理解：其 依然可以对前述各实施例所记载的技术方案进行修改，或者对其中部分或者全部技术特征 进行等同替换；而这些修改或者替换，并不使相应技术方案的本质脱离本发明各实施例技 术方案的范围。
【主权项】
1. 一种空中交通流量调控方法，其特征在于，所述方法包括： 第一步，建立待调控空域的航班和空域信息数据库，所述数据库包括所述待调控空域 中所有航班的起飞时刻和飞行路径的集合； 第二步，生成初始种群，所述初始种群由预设数量的染色体随机组成，一条染色体由所 述数据库中每一航班的一个飞行路径和一个起飞时刻组成，所述一条染色体包括2N个基 因，N为所述数据库中航班的数量，将所述初始种群作为第g代种群，g为自然数； 第三步，使用所述第g代种群计算第一目标函数和第二目标函数，所述第一目标函数 为所述待调控空域的空中交通拥挤度目标函数，所述第二目标函数为所述待调控空域中所 有航班的起飞时刻延误和额外飞行路径的目标函数，得到所述第g代种群的所述第一目标 函数和所述第二目标函数的解集；将所述第g代种群的所述第一目标函数和所述第二目标 函数的解集存放在全局变量中； 第四步，计算所述第g代种群的所述第一目标函数和所述第二目标函数的解集的多样 性函数，得到所述第g代的多样性函数值； 第五步，根据所述第g代的多样性函数值确定在所述第g代种群中参与局部搜索的染 色体的数量Φ (g); 第六步，在所述第g代种群中随机选择Φ (g)条染色体，并替换所述Φ (g)条染色体中 每一染色体的y个基因，将所述第g代种群中除所述Φ (g)条染色体以外的其他染色体和 替换后的所述Φ (g)条染色体作为第g+Ι代种群； 第七步，使用所述第g+Ι代种群计算所述第一目标函数和所述第二目标函数，得到所 述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集；根据所述第g+Ι代种群 的所述第一目标函数和所述第二目标函数的解集对所述全局变量中的所述第一目标函数 和所述第二目标函数的解集进行更新； 第八步，计算所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集的多 样性函数，得到所述第g+Ι代的多样性函数值； 第九步，依次循环执行第五步至第八步的处理，得到第g+n代的多样性函数值，直到第 g+n代到达预定循环代数； 第十步，将所述全局变量中更新后的解集对应的染色体中的每个航班的起飞时刻和飞 行路径来作为待调控空域的调控依据。2. 根据权利要求1所述的方法，其特征在于，所述多样性函数值，表示为：其中，1为相邻的所述第一目标函数和所述第二目标函数的解之间的平 均距离，所述第一目标函数和所述第二目标函数的解集为X = (Χι，χ2,...，χη)，山为X 4口 χ1+1之间的距离，d f和d 别为两个极端解与所述第一目标函数和所述第二目标函数的解 边界值之间的距离，Cl1表示为： d；= I |y(x i)-y(xi+i) I I2 〇<i<n 其中，y是目标函数向量，y = (yi，y2)，yi为所述第一目标函数，y2为所述第二目标函 数。3. 根据权利要求1或2所述的方法，其特征在于，所述根据所述第g代的多样性函数值 确定在所述第g代种群中参与局部搜索的染色体的数量Φ (g)，表示为：其中，ps为所述第g代种群中的染色体数量，τ (g)为第g代局部搜索频率，k为常数； 第g代局部搜索频率τ (g)，表示为：n (g)为所述第g代的多样性函数值。4. 根据权利要求1或2所述的方法，其特征在于，所述y个基因为2N X P个基因；其中， P为选择比例，P小于1。5. 根据权利要求1或2所述的方法，其特征在于，所述使用所述第g代种群计算第一目 标函数和第二目标函数，得到所述第g代种群的所述第一目标函数和所述第二目标函数的 解集，具体包括： 将所述第g代种群中的所述每一条染色体随机分组得到至少两个低维子染色体，对每 个低维子染色体进行差分进化，得到差分进化后的每个低维子染色体，将所述差分进化后 的每个低维子染色体进行合并，生成差分进化后的一条染色体，所述第g代种群的所述第 一目标函数和所述第二目标函数的解集由所述差分进化后的染色体计算得到。6. 根据权利要求1或2所述的方法，其特征在于，所述根据所述第g+Ι代种群的所述第 一目标函数和所述第二目标函数的解集对所述全局变量中的所述第一目标函数和所述第 二目标函数的解集进行更新，具体包括： 将所述第g+Ι代种群的所述第一目标函数和所述第二目标函数的解集中的各个解进 行比较，得到所述第g+Ι代种群的非支配解集； 将所述第g+Ι代种群的非支配解集与所述全局变量中的所述第一目标函数和所述第 二目标函数的解集进行比较，如果所述第g+Ι代种群的非支配解集中存在至少一个解，所 述至少一个解支配所述全局变量中的所述第一目标函数和所述第二目标函数的解集中的 解，则用所述至少一个解替换掉所述全局变量中的所述第一目标函数和所述第二目标函数 的解集中被所述至少一个解支配的解。7. 根据权利要求1所述的方法，其特征在于，所述第一目标函数为所述待调控空域的 空中交通拥挤度目标函数，表示为：其中，表不扇区Sk在时间T内的总拥挤度，表不扇区Sk 在时间T内的最大拥挤度，P表示扇区的数量，Φ和0是介于O到1之间的权重系数； 所述待调控空域包括P个扇区，所述扇区Sk表示P个扇区中的第k个扇区，所述扇区 Sk的拥挤度为所述扇区S k在时间T内的一个时刻t的航班数量，所述扇区S k的总拥挤度为 所述扇区Sk在时间T内的航班数量之和，所述扇区Sk的最大拥挤度为所述扇区S k在时间T 内一个时刻t的航班数量的最大值。8. 根据权利要求7所述的方法，其特征在于，所述扇区S ,在t时刻的负荷(?)包括： 监视负荷》⑴和协调负荷Ra G)，表示为：其中，w, Φ e [〇，1]为所述监视负荷和所述协调负荷的权重； 所述监视负荷(力，表示为：其中，MsJi)与t时刻在所述扇区&内的飞机数目的平方成正比，(，)表示t时刻 所述扇区Sk的监视负荷阈值； 所述协调负荷(0可以表示为：其中，仏的与七时刻穿越所述扇区Sk边界的飞机数目的平方成正比，（:、（0表示t时 刻所述扇区Sk的协调负荷阈值。9. 根据权利要求1或2所述的方法，其特征在于，所述第二目标函数为所述待调控空域 中所有航班的起飞时刻延误和额外飞行路径的目标函数，所述起飞时刻延误为所述航班的 起飞时刻与所述数据库中所述航班的最早起飞时刻的差值；所述额外飞行路径为所述航班 的飞行路径与所述数据库中所述航班的最短飞行路径的差值； 所述第二目标函数表示为：其中，S (i)为所述航班总的延误，表示为： δ ⑴=δ s(i)+ δ 力） 其中，Ss⑴为所述航班的地面延误，δ力）为所述航班的空中延误。10. 根据权利要求9所述的方法，其特征在于，所述数据库中所述航班包括大、中、小型 航班； 所述待调控空域中所有航班的起飞时刻延误和额外飞行路径的目标函数，具体表示 为：其中為為以分别表示所述大冲^型航班的数量"^人^人次别表示所述大冲、 小型航班对应的权重系数（λ Β> λ Μ> λ s)。
【专利摘要】本发明实施例提供一种空中交通流量调控方法。本发明空中交通流量调控方法通过对每一代种群参与局部搜索的染色体数量进行动态调整，使每一代种群参与局部搜索的染色体数量都不相同，这样就可以加强对解空间的搜索能力，不容易陷入局部最优，提高解集的多样性，能够比传统的遗传算法找到更为满意的结果，保证了在航班安全飞行的前提下尽量兼顾航空公司的经济利益和航班之间的公平性。
【IPC分类】G06N3/12, G08G5/00
【公开号】CN105489066
【申请号】CN201410471476
【发明人】张学军, 管祥民, 雷佳兴
【申请人】北京航空航天大学
【公开日】2016年4月13日
【申请日】2014年9月16日
最新回复(0)