基于改进Agent的终端区扇区划设方法、装置、设备和介质

基于改进agent的终端区扇区划设方法、装置、设备和介质
技术领域
1.本发明涉及到航空管理领域，具体为基于改进agent的终端区扇区划设方法、装置、设备和介质。


背景技术：

2.伴随民航运输业的迅速发展，传统基于主观经验人为划设的扇区存在空域资源严重分配不均的问题，无法满足如今空中交通运行需求，需要根据航空器的实际运行情况做出扇区划设方案的优化调整。因此，针对终端区扇区问题，通过探索并改进扇区划设方法，实现扇区形状分布更为合理。
3.管制扇区是空域规划过程中的重要组成部分，作为空中交通管制服务的基础单元，合理有效的扇区划设对于保障空域内航空器的飞行安全、提升空域容量与运行效率、降低管制员的工作负荷等方面都起到了积极关键的作用。
4.在终端区扇区划设过程中，使用何种划设方法对最终划设方案结果有显著影响。扇区划设方法可以分为三类：第一类是计算几何方法研究图形，对于图像建立坐标系，把图形转换成函数，然后用插值和逼近的数学方法分析图形；第二类是加权无向图，将空中交通网络抽象认为是地理空间网络，通过空间网络图，直观描述空域结构中航路分布、关键航路点等关键信息而后转换为图分割问题进行扇区划设；第三类是网格聚类法，基于聚类扇区划设思路下的方法，本质是将空域离散成为若干个包含特定结构和交通流信息的网格单元，然后根据确定的优化目标对网格单元聚类生长，结果最终生成扇区。
5.以上方法中网格聚类法生成扇区方式灵活，适应度强，针对各优化目标效果表现都较好，但不足之处体现在：计算成本较高，生成的扇区结果易违反安全约束，需要后期修正。


技术实现要素：

6.本发明的目的是针对现有技术存在的问题，提供一种基于改进agent的终端区扇区划设方法、装置、设备和介质，用以解决上述技术问题中的至少一个。
7.基于本发明说明书的一方面，提供一种基于改进agent的终端区扇区划设方法，包括以下步骤：
8.步骤s1：获取终端区空域的空间数据和空域内所有航迹点的航迹数据，并对所述航迹数据进行预处理；
9.步骤s2：对终端区空域进行栅格化处理，并基于航迹数据为每个栅格赋予交通流信息；
10.步骤s3：利用遗传算法确定初始agent解的位置；
11.步骤s4：设置agent的累积工作负载上限，利用生长规则基于初始agent解的位置得到扇区划设栅格结果；
12.步骤s5：基于扇区划设栅格结果，采用空域填充规则进行栅格再分配，得到终端区
扇区划设结果。
13.在上述技术方案中，先将终端区进行栅格化，并基于栅格的交通流信息利用遗传算法得到初始agent的位置，然后在初始agent解的位置的基础上对栅格进行划设，得到扇区划设栅格结果，最后采用空域填充规则进行栅格再分配得到最终的终端区扇区划设结果。
14.agent方法是一种用来模拟具有自主意识的智能体(独立个体或共同群体，例如组织、团队)的行动和相互作用的计算方法，通过图像展示评估agent在系统整体中的作用。具体到发明中为：agent在栅格化的三维空域内移动，使用改进后的行为规则占据空域单元格，最终完成栅格的聚类以形成扇区图形。
15.进一步地，所述步骤s2具体包括：
16.步骤s201：采用三维空域环境离散化将终端区空域分割成若干大小一致的三维空域单元，得到终端区空域所包含的栅格；
17.步骤s202：选取一个栅格作为待赋值栅格，从预处理后的航迹数据中获取位于被选取的栅格内的所有航迹点的航迹数据，并构建得到被选取栅格的航迹数据集p’a
：
18.p’a
＝{p
a1
,p
a2
,...,p
an
}，p
an
∈pi19.pi＝{p
i,1
,p
i,2
,...,p
i,m
}，i∈i
20.p
i,m
＝{x
i,m
,y
i,m
,h
i,m
,d
i,m
,v
i,m
,t
i,m
}
21.其中：a为被选取的栅格的编号，p
an
为栅格a内的航迹点的航迹数据，n为栅格a内的航迹点的总数量；pi为终端区空域内的航迹点，p
i,m
为第i条航线的第m个航迹点，i为终端区空域内的航迹总数；x
i,m
为航迹点p
i,m
的经度，y
i,m
为航迹点p
i,m
的纬度，h
i,m
为航迹点p
i,m
的高度索引，d
i,m
为航迹点p
i,m
对应的航班航向，vi
,m
为航迹点pi
,m
对应的航班速度，v
i,m
为航迹点p
i,m
被雷达捕捉的时间；
22.计算待赋值栅格与相邻栅格的交通共性值，并获取待赋值栅格的交通流量负载，将所述航迹数据集、交通共性值和交通流量负载作为交通流信息赋予待赋值栅格；
23.步骤s203：选取一个未被选择的栅格作为新的待赋值栅格，重复步骤s202；
24.步骤s204：重复步骤s203，直至所有栅格被赋予交通流信息。
25.进一步地，所述交通共性值的计算方法如下：
26.c
a,b
＝tr
a,b
,b∈na,a≠b
27.其中：c
a,b
为栅格a与相邻栅格b的交通共性值，na为栅格a的相邻栅格集合，tr
a,b
为给定时间间隔内航班的轨迹位置从栅格a转移到栅格b的总次数。
28.进一步地，所述步骤s3具体包括：
29.s301：设置初始agent解的数量，基于agent解的数量和空域内栅格的总数量计算得到样本数量ns：
[0030][0031]
其中：m为空域内栅格的总数量，na为agent解的数量；
[0032]
将空域内所有的栅格根据样本数量进行均分，得到ns个样本，每一样本中包含有na个栅格；
[0033]
s302：设置第一优化目标函数：
[0034][0035]
其中：表示样本si中所有栅格的交通流量负载总和，i为样本编号；为栅格a的交通流量负载；
[0036]
设置第二优化目标：
[0037][0038]
其中：为样本si内的栅格间的几何距离之和，d
ab
为样本si所包含的栅格a和栅格b之间的米制距离，h
ab
为栅格a和栅格b之间的高度差绝对值；
[0039]
s303：构建适应度函数：
[0040][0041]
其中，f(si)为si的适应度值，为对样本si的第一优化目标函数值的标准化结果，为对样本si的第二优化目标函数值的标准化结果，k为惩罚函数，当满足约束条件是k为0，不满足约束条件是k为负无穷大；n1和n2为权重；
[0042]
s304：对所有样本进行交叉变异处理，迭代多次，得到优化后的样本；
[0043]
s305：基于适应度函数计算所有优化后的样本的适应度值，得到适应度值最大的样本，将适应度值最大的样本对应的栅格作为初始agent解的位置。
[0044]
进一步地，所述步骤s4包括：
[0045]
s401：针对每一个agent，设置agent的累积工作负载上限，当agent的累积工作负载不超过累积工作负载上限时，执行步骤s402；
[0046]
s402：将每一个初始agent解的位置作为初始栅格，从每一个初始栅格的相邻栅格集合中选定与初始栅格之间交通共性值不为零的栅格，将初始栅格与被选定的相邻栅格作为初始结果；
[0047]
s403：获得初始结果在经纬度面的投影，依照投影与s402中被选定的栅格的层数进行直棱柱的生长，得到每个初始agent解的位置对应的直棱柱；
[0048]
s405：对所有直棱柱进行竖直平面和/或水平平面的扩大，得到扇区划设栅格结果。
[0049]
进一步地，所述步骤s405包括：
[0050]
s4051：设置移动比率的参数；确定每次调用生长规则的低工作负载agent个数；
[0051]
s4052：根据移动比率选取当前累积工作负载低的agent作为目标agent，获取与目标agent所包含的栅格相邻且未被占领的栅格的交通共性值，并选取交通共性值最大的栅格作为目标栅格；
[0052]
s4053：以目标栅格相对目标agent所含栅格的高度位置，产生水平或竖直的栅格几何平面，将栅格几何平面内的栅格添加到目标agent对应的直棱柱中；
[0053]
s4054：将步骤s4053中被添加到直棱柱中的栅格标记为已分配栅格，将已分配栅格的交通流量负载累加到目标agent的累积工作负载中；
[0054]
s4055：重复步骤s4052-s4054，直至完成对所有交通共性值不为零的栅格的分配，将每一个agent包含的所有栅格作为一个扇区，得到扇区划设栅格结果。
[0055]
进一步地，所述步骤s5包括：
[0056]
s501：从终端区空域内选取一个未分配栅格；
[0057]
s502：获取位于未分配栅格上方和下方的agent的数量，若未分配栅格上方agent数量小于未分配栅格下方agent数量，则选定未分配栅格上方累积工作负载最小的agent作为待激活agent；否则，选定未分配栅格下方累积工作负载最小的agent作为待激活agent；将空域填充规则赋予待激活agent，得到激活空域填充规则的agent；
[0058]
s503：选取未分配栅格所在的水平层作为待分配水平层，所述待分配水平层与激活空域填充规则的agent所属扇区里横向水平栅格配置相同，将待分配水平层添加到激活空域填充规则的agent所述扇区内，并将待分配水平层中所有栅格的交通流量负载累加至激活空域填充规则的agent的累积工作负载中；
[0059]
s504：判断未激活空域填充规则的agent对应的扇区是否与待分配水平层发生栅格重合，若是，则将重合的栅格的交通流量负载从对应的agent的累积工作负载中删除；
[0060]
s505：重复步骤s601-s604，直至终端区空域内没有未分配栅格，得到终端区扇区划设结果。
[0061]
基于本发明说明书的另一方面，提供一种基于改进agent的终端区扇区划设装置，包括：
[0062]
数据获取模块：用于获取终端区空域的空间数据和空域内所有航迹点的航迹数据，并对所述航迹数据进行预处理；
[0063]
栅格化模块：用于对终端区空域进行栅格化处理，并基于航迹数据为每个栅格赋予交通流信息；
[0064]
初始agent解确定模块：用于构建适应度函数，对于包含有交通流信息的栅格，利用遗传算法确定初始agent解的位置；
[0065]
扇区划设模块：用于设置agent的累积工作负载上限，利用生长规则基于初始agent解的位置得到的扇区划设栅格结果；
[0066]
再分配模块：用于基于扇区划设栅格结果，采用空域填充规则进行栅格再分配，得到终端区扇区划设结果。
[0067]
在上述技术方案中，采用数据获取模块获取终端区空域的空间数据和航迹数据，栅格化模块将终端区空域栅格化得到所有的栅格，并基于航迹数据赋予每个栅格交通流信息，初始agent解确定模块基于栅格和交通流信息采用遗传算法计算得到初始agent解的位置，扇区划设模块基于初始agent解的位置利用生长规则得到扇区划设栅格结果，再分配模块在扇区划设栅格结果的基础上，采用空域填充规则进行栅格再分配，得到终端区扇区划设结果。
[0068]
基于本发明说明书的又一方面，提供一种计算机设备，所述计算机设备包括处理器、存储器，以及存储在所述存储器上并可被所述处理器执行的计算机程序，其中所述计算机程序被所述处理器执行时，实现所述的基于改进agent的终端区扇区划设方法的步骤。
[0069]
基于本发明说明书的又一方面，提供一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，其中所述计算机程序被处理器执行时，实现所述的基于改
进agent的终端区扇区划设方法的步骤。
[0070]
与现有技术相比，本发明的有益效果是：
[0071]
(1)本发明提供的基于改进agent的终端区扇区划设方法，使用agent方法对栅格进行聚类，通过调参可以获得不同的栅格聚类结果，灵活性与可操控性很强，并且能够识别条数较少的雷达引导航迹。引入遗传算法优化agent初始解的位置，提高了方法划设扇区的时间效率与避免了后续扇区划设方案优化效果不佳的情况发生；相较于传统基于agent的扇区划设方法，本发明的生长规则与空域填充规则可将方法的时间复杂度降低，提高了面对终端区内多机场运行情况下求解模型的效率，并且解决了传统agent方法划设出的扇区结果易违反民航运行安全约束的不足；设置移动比率实现各agent所属扇区结果的均衡增长，保证终端区内扇区工作负载的均衡，并空域填充规则对存在矛盾的栅格进行再分配与聚类，可以优化结果，使得聚类结果更加精细并具有严谨性。
[0072]
(2)本发明提供的基于改进agent的终端区扇区划设装置，采用数据获取模块获取终端区空域的空间数据和航迹数据，栅格化模块将终端区空域栅格化得到所有的栅格，并基于航迹数据赋予每个栅格交通流信息，初始agent解确定模块基于栅格和交通流信息采用遗传算法计算得到初始agent解的位置，扇区划设模块基于初始agent解的位置利用生长规则得到扇区划设栅格结果，再分配模块在扇区划设栅格结果的基础上，采用空域填充规则进行栅格再分配，得到终端区扇区划设结果。
附图说明
[0073]
图1为本发明实施例的方法流程图；
[0074]
图2为本发明实施例的扇区划设结果立体图；
[0075]
图3为本发明实施例的扇区划设结果仰视图；
[0076]
图4为本发明实施例的扇区划设结果俯视图；
[0077]
图5为本发明实施例的各扇区分离后的立体图；
[0078]
图6为本发明实施例的平均飞跃扇区时间箱线图；
[0079]
图7为本发明实施例的各扇区动态密度分布图；
[0080]
图8为本发明实施例的求解时间折线图；
[0081]
图9为本发明实施例的一种栅格几何平面示意图；
[0082]
图10为本发明实施例的另一种栅格几何平面示意图。
具体实施方式
[0083]
下面将结合本发明中的附图，对本发明的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动条件下所获得的所有其它实施例，都属于本发明保护的范围。
[0084]
如图1所示，本实施例提供一种基于改进agent的终端区扇区划设方法，包括以下步骤：
[0085]
步骤s1：获取终端区空域的空间数据和空域内所有航迹点的航迹数据，并对所述航迹数据进行预处理。
[0086]
终端区空域的空间数据包括终端区空域对应的经纬度和高度(通常为0-6300m)。
[0087]
航迹数据包括进场、离场和飞越的航迹数据。
[0088]
在本实施例的示例中，选择上海终端区空域作为扇区划设对象，从华东空管局空中交通管制中心流量管理室获得2021年6月15日至6月17日高峰段内雷达记录的航迹数据，航迹数据包括多条航迹，每条航迹上包含多个航迹点，每个航迹点包括对应的时间、三维坐标(经度、维度和高度)、航向角及速度。
[0089]
对航迹数据进行预处理包括数据清洗和重采样，其中数据清洗包括：
[0090]
(1)删除缺失航班号字段的雷达航迹；
[0091]
(2)删除水平范围或垂直范围不在终端区内的雷达航迹数据；
[0092]
(3)删除飞机落地速度减为0后，在同一位置仍不断记录航迹；
[0093]
(4)删除一个架次的航班在相同记录时间内有多条位置高度等完全不相同的记录；
[0094]
(5)删除航迹任意两点间出现不规则变化，该航迹明显异于相邻时段的正常航迹；
[0095]
重采样包括：采用等间隔采样法对数据进行重采样，确定采样间隔为5s，从完整航迹的起点至终点，每5s中更新一次航迹。
[0096]
删除缺失航班号字段的数据并筛除异常数据，针对记录的雷达数据点时间间隔过短，以及在短时间内航空器位置不会出现大幅度变化所导致的航迹数据冗余，使用采样间隔为5s的等间隔采样法，本发明不仅考虑了航迹数据的准确性，还考虑了航迹坐标点的数量规模，避免将同一航班短时间内过多的航迹坐标点进行输入，保证栅格聚类准确性的同时提升了效率。
[0097]
步骤s2：对终端区空域进行栅格化处理，并基于航迹数据为每个栅格赋予交通流信息。步骤s2具体包括：
[0098]
步骤s201：采用三维空域环境离散化将终端区空域分割成若干大小一致的三维空域单元，每一三维空域单元包含部分雷达航迹，得到终端区空域所包含的栅格；得到的所有栅格可以分为两类栅格，含有航迹点的栅格和不含有航迹点的栅格；
[0099]
通过定义栅格数据，选择栅格边长、栅格边数、高度层数后，依次生成大小相等的栅格。根据终端区300m飞行安全间隔，取其因数设置栅格高度间隔为100m，栅格形状为底面为正方形的长方体，所述长方体的高为100m；其边长尺寸直接影响到栅格大小，栅格过大会导致栅格内包含的航迹点过多，分割精度不够，而栅格过小会导致栅格数量急剧增加，导致计算成本过高，因此，需要对边长参数进行调节，最终选择6.66km作为边长参数，即将栅格的尺寸设置为6.66km
×
6.66km
×
300m(长
×
宽
×
高)。
[0100]
步骤s202：选取一个栅格作为待赋值栅格，从预处理后的航迹数据中获取位于被选取的栅格内的所有航迹点的航迹数据，并构建得到被选取栅格的航迹数据集p’a
：
[0101]
p’a
＝{p
a1
,p
a2
,...,p
an
}，p
an
∈pi[0102]
pi＝{p
i,1
,p
i,2
,...,p
i,m
}，i∈i
[0103]
p
i,m
＝{x
i,m
,y
i,m
,h
i,m
,d
i,m
,v
i,m
,t
i,m
}
[0104]
其中：a为被选取的栅格的编号，p
an
为栅格a内的航迹点的航迹数据，n为栅格a内的航迹点的总数量；pi为终端区空域内的航迹点，p
i,m
为第i条航线(航迹)的第m个航迹点，i为终端区空域内的航迹总数；x
i,m
为航迹点p
i,m
的经度，y
i,m
为航迹点p
i,m
的纬度，h
i,m
为航迹点
p
i,m
的高度索引，d
i,m
为航迹点p
i,m
对应的航班航向，v
i,m
为航迹点p
i,m
对应的航班速度，v
i,m
为航迹点p
i,m
被雷达捕捉的时间。
[0105]
计算待赋值栅格与相邻栅格的交通共性值，并获取待赋值栅格的交通流量负载，将所述航迹数据集、交通共性值和交通流量负载作为交通流信息赋予待赋值栅格；
[0106]
交通共性值的计算方法如下：
[0107]ca,b
＝tr
a,b
,b∈na,a≠b
[0108]
其中：c
a,b
为栅格a与相邻栅格b的交通共性值，na为栅格a的相邻栅格集合，tr
a,b
为给定时间间隔内航班的轨迹位置从栅格a转移到栅格b的总次数。
[0109]
针对于每一栅格，在计算交通共性值时，所说的相邻栅格包括与该栅格共面、共线或共点的所有栅格，即每一个栅格拥有26个相邻栅格，则每个栅格含有26个共性值。
[0110]
为通过栅格量化体现扇区形状特征与主要交通流走向保持齐平，基于每个栅格的交通共性值可以计算扇区s内航班累积交通共性值ccs：
[0111][0112]
其中：栅格a和栅格b是扇区s中的栅格，且栅格a与栅格b相邻，scs表示属于扇区s的栅格的集合。
[0113]
为了通过栅格层面体现扇区管制工作负荷，定义空域内每一个栅格都有一个相关的交通流量负载，该值表示空域内经过栅格的航班数，可以通过对给定时间间隔内的历史雷达航迹数据的分析来确定。所有栅格的交通流量负荷之和决定了空域的总交通流量负载w：
[0114][0115]
其中：m为空域内栅格的总数量，q'a为栅格a的交通流量负载。
[0116]
分配给扇区s的累积工作负载cws计算公式如下：
[0117][0118]
步骤s203：选取一个未被选择的栅格作为新的待赋值栅格，重复步骤s202；
[0119]
步骤s204：重复步骤s203，直至所有栅格被赋予交通流信息。对于不包含航迹点的栅格，其交通流信息中航迹数据集为空集，即这些不包含航迹点的栅格的交通流信息只包含交通流量负载和交通共性值。
[0120]
步骤s3：构利用遗传算法确定初始agent解的位置。具体包括以下步骤：
[0121]
s301：设置初始agent解的数量，基于agent解的数量和空域内栅格的总数量计算得到样本数量ns：
[0122][0123]
其中：m为空域内栅格的总数量，na为agent解的数量；
[0124]
将空域内所有的栅格根据样本数量进行均分，得到ns个样本，每一样本中包含有na个栅格；
[0125]
在本实施例的示例中，空域内栅格的总数量为1100个，设置初始agent解的数量为11个，则样本数量为1100/11＝100(个)。然后将这1100个栅格按照11个一组随机分成100组，即得到100个样本(s1,s2,...,s
100
)，每个样本中包含有11个栅格(为样本编号)。
[0126]
s302：设置第一优化目标函数：
[0127][0128]
其中：表示样本si中所有栅格的交通流量负载总和，i为样本编号；为栅格a(栅格a属于样本si)的交通流量负载；
[0129]
设置第二优化目标：
[0130][0131]
其中：为样本si内的栅格间的几何距离之和，d
ab
为样本si所包含的栅格a和栅格b之间的米制距离，h
ab
为栅格a和栅格b之间的高度差绝对值。
[0132]
米制距离的计算公式如下：
[0133][0134]
其中：d
ab
为栅格a和栅格b之间的米制距离，r为地球半径，和分别为栅格a的中心点和栅格b的中心点的纬度，βa和βb分别为栅格a的中心点和栅格b的中心点的经度。s303：构建适应度函数：
[0135][0136]
其中，f(si)为si的适应度值，为对样本si的第一优化目标函数值的标准化结果，为对样本si的第二优化目标函数值的标准化结果，k为惩罚函数，当满足约束条件是k为0，不满足约束条件是k为负无穷大；n1和n2为权重。
[0137]
本实施例中采用z-score对每一个样本的第一优化目标函数值和第二优化目标函数值进行标准化处理：
[0138][0139][0140]
其中：μw和σw为所有样本的第一优化目标函数值均值和标准差，μd和σd为所有样本的第二优化目标函数值均值和标准差。
[0141]
s304：对所有样本进行交叉变异迭代处理，迭代多次(本实施例迭代800次)，得到优化后的样本；
[0142]
s305：基于适应度函数计算所有优化后的样本的适应度值，得到适应度值最大的样本，将适应度值最大的样本对应的栅格作为初始agent解的位置。
[0143]
在本实施例的示例中，计算得到优化后的样本s
10
的适应度值最大，则将优化后的样本s
10
中的11个栅格作为初始agent解的位置，样本s
10
中的每一个栅格对应着一个agent。
[0144]
步骤s4：设置agent的累积工作负载上限，利用生长规则基于初始agent解的位置得到扇区划设栅格结果。具体包括：
[0145]
s401：针对每一个agent，设置agent的累积工作负载上限，当agent的累积工作负载不超过累积工作负载上限时，执行步骤s402；
[0146]
s402：将初始agent解的位置作为初始栅格，从初始栅格的相邻栅格集合(共计26个相邻栅格)中选定与初始栅格之间交通共性值不为零的栅格，将初始栅格和被选定的相邻栅格作为初始结果；
[0147]
s403：获得初始结果在经纬度面的投影，依照投影与s402中选定的栅格的层数进行直棱柱的生长，得到每个初始agent解的位置对应的直棱柱；
[0148]
在本实施例的示例中，得到了11个初始agent解的位置，分别设置这11个agent(agent1,agent2,...,agent11)的累积工作负载上限。本示例中以agent1为例，当判断出agent1的当前累积工作负载不超过设定的累积工作负载上限时，以agent1对应的初始解的位置所在的栅格作为初始栅格1，获取初始栅格1与相邻栅格之间的交通共性值并判断是否为零，将交通共性值不为零对应的相邻栅格选定，将选定的栅格与初始栅格1作为初始结果1；将初始结果1投影到经纬度面，得到初始结果1对应的投影图，假设获取初始结果1中共包含3层栅格，将初始结果1的投影图在竖直平面上延伸三层，得到一个以投影图为底面，以3层栅格高度为高的直棱柱1，初始结果1包含的栅格均位于直棱柱1中。以相同的方式对剩余的agent进行操作，得到另外的10个直棱柱，共计得到的11个直棱柱即为每个初始agent解的初始位置对应的直棱柱。
[0149]
s405：对所有直棱柱进行竖直平面和/或水平平面的扩大，得到扇区划设栅格结果。
[0150]
s4051：设置移动比率的参数，确定每次调用生长规则的低工作负载agent个数；
[0151]
s4052：根据移动比率选取当前累积工作负载低的agent作为目标agent，获取与目标agent所包含的栅格相邻(此处的相邻指共面，此时每个栅格有六个相邻的栅格)且未被占领的栅格(即当前时刻下不属于任何直棱柱的栅格)的交通共性值，并选取交通共性值最大的栅格作为目标栅格；
[0152]
s4053：以目标栅格相对目标agent所含栅格的高度位置，产生水平或竖直的栅格几何平面，将栅格几何平面内的栅格添加到目标agent对应的直棱柱中；
[0153]
当目标栅格位于目标agent对应的直棱柱的上方或下方，则在该直棱柱的上方或下方产生一个高度为一层、底面与直棱柱底面相同的栅格几何平面，并将该平面并入到该直棱柱的上方或下方形成新的直棱柱(如图9所示)。
[0154]
当目标栅格位于目标agent对应的直棱柱的侧面(与直棱柱侧面相邻)，则在该直棱柱的侧面产生一个高度与直棱柱高度相同且侧面形状与直棱柱侧面形状相同的栅格几何盘平面，并将该平面并入至该直棱柱的侧面形成新的直棱柱(如图10所示)。
[0155]
s4054：将步骤s4053中被添加到直棱柱中的栅格标记为已分配栅格，将已分配栅格的交通流量负载累加到目标agent的累积工作负载中；
[0156]
s4055：重复步骤s4052-s4054，直至完成对所有交通共性值不为零的栅格的分配，将每一个agent包含的所有栅格作为一个扇区，得到扇区划设栅格结果。
[0157]
步骤s5：基于扇区划设栅格结果，采用空域填充规则进行栅格再分配，得到终端区扇区划设结果，具体包括：
[0158]
s501：从终端区空域内选取一个未分配栅格(即当前时刻下不属于任何直棱柱的栅格)；
[0159]
s502：获取位于未分配栅格上方和下方的agent的数量，若未分配栅格上方agent数量小于未分配栅格下方agent数量，则选定未分配栅格上方累积工作负载最小的agent作为待激活agent；否则，选定未分配栅格下方累积工作负载最小的agent作为待激活agent；将空域填充规则赋予待激活agent，得到激活空域填充规则的agent；
[0160]
s503：选取未分配栅格所在的水平层作为待分配水平层，所述待分配水平层与激活空域填充规则的agent所属扇区里横向水平栅格配置相同(即待分配水平层的底面与扇区的底面形状相同)，将待分配水平层添加到激活空域填充规则的agent所述扇区内，并将待分配水平层中所有栅格的交通流量负载累加至激活空域填充规则的agent的累积工作负载中；
[0161]
s504：判断未激活空域填充规则的agent对应的扇区是否与待分配水平层发生栅格重合，若是，则将重合的栅格的交通流量负载从对应的agent的累积工作负载中删除；
[0162]
s505：重复步骤s601-s604，直至终端区空域内没有未分配栅格，得到终端区扇区划设结果(如图5所示)。
[0163]
本实施例对终端区扇区划设结果的评价通过以下方式实现：
[0164]
根据优化目标选择航空器平均飞越扇区时间，航空器在扇区内的平均飞行时间越长，扇区的容量越大，公式为：
[0165][0166]
式中，ni为处在扇区内的航空器架次，分别为航空器i进入与离开扇区的时刻。为挖掘航空器在扇区内运行时间特征，需要针对扇区与航空器，对飞越扇区时间分布进行描述。在统计学中，四分位数作为分位数的一种形式，能够较好的对数据分布进行描述，因此研究计算四分位数并采用箱线图的形式对平均飞越扇区时长进行分析。
[0167]
数值按照从小到大排列并分成四等份，这些等分的数称为四分位数，即每一个部分都包含有25％的数据项。四分位数是处于三个分割点位置的数值。其中，q1代表第一四分位数(即上四分位数)，第一四分位数为较小的四分位数；q2表示第二四分位数，即中位数；q3代表第三四分位数(即下四分位数)，第三四分位数即为较大的四分位数；且q1《q3。上、下边缘计算方法则为数据样本中最大与最小值。
[0168]
这种划分的临界点即为四分位数。在q1与q3之间，包含了整个数据集中50％的数据，由此可以得到各扇区粗略的平均飞越时间的聚集区间。
[0169]
基于空域复杂度因素加权组成各扇区动态密度与标准差(如图7所示)，动态密度的计算公式为：
[0170][0171]
其中n为给定时间在单个扇区内的航空器架次；nh为航向变化大于15
°
的航空器架次；ns为速度变化大于18km/h的航空器架次；na为高度变化大于250m的航空器架次；c
p
为存在冲突可能的航空器数量，认为航空器间横向距离小于10km、垂直距离小于300m的航空器是有冲突可能的；w1,w2,w3,w4,w5为需要预先确定的主观权重，研究分别取1、2.40、2.45、2.94、8。
[0172]
扇区动态密度的标准差，公式为：
[0173]
f(x)＝min[sd(w
orkload,i
)]
[0174]
划设方法的计算成本对扇区划设问题求解效率起着决定性作用。对该优化目标的量化可从方法的求解时间入手。
[0175]
假设算法在处理规模为n的输入数据时，需要消耗的时间为t(n)，则以o(f(n))表示该算法时间复杂度。通常情况下，时间复杂度的计算方法是统计算法执行次数的上限，即最坏时间复杂度。因此，求解时间的数学量化公式可以表示为：
[0176]
t(n)＝o(f(n))
[0177]
本实施例中求解时间折线图如图8所示。
[0178]
本实施例中使用改进agent方法得到的扇区划设方案评估结果如表3所示。
[0179]
表3a扇区划设方案平均飞越扇区时间指标结果值
[0180]
扇区划设方案q1q2q3改进后的agent方法307.18331.44367.41
[0181]
表3b扇区划设方案动态密度与标准差结果值
[0182][0183]
表3c扇区划设方案求解时间指标结果值
[0184]
行动规则生长规则空域填充规则时间(ms)47903.156096.85调用次数285155每次调用时间(ms)16.80110.85
[0185]
图2-图4分别为三种视角下的改进agent扇区划设方法得到栅格聚类结果图。图中坐标系取自上海终端区实际的经纬度坐标与高度范围，终端区高度范围为0至6300米。由于使用的数据为终端区内北向运行的进离场航空器与少部分飞越航空器，因此存在扇区内缺乏航迹坐标点情况，导致计算平均飞越扇区时间时，箱线图出现异常点，图6中已用黑色点标注。
[0186]
综上实例，可以看出本发明考虑了扇区形状同交通流相适应、管制工作负荷和扇区划设方法的时间成本三个方面进行终端区扇区划设，能够提升终端区扇区划设结果的合理性，降低扇区划设方法的时间复杂度。
[0187]
本实施例还提供一种基于改进agent的终端区扇区划设装置，用于实现本实施例中的基于改进agent的终端区扇区划设方法的步骤，包括：
[0188]
数据获取模块：用于获取终端区空域的空间数据和空域内所有航迹点的航迹数据，并对所述航迹数据进行预处理；
[0189]
栅格化模块：用于对终端区空域进行栅格化处理，并基于航迹数据为每个栅格赋予交通流信息；栅格化模块具体用于完成以下步骤：
[0190]
步骤s201：采用三维空域环境离散化将终端区空域分割成若干大小一致的三维空域单元，得到终端区空域所包含的栅格；
[0191]
步骤s202：选取一个栅格作为待赋值栅格，从预处理后的航迹数据中获取位于被选取的栅格内的所有航迹点的航迹数据，并构建得到被选取栅格的航迹数据集p’a
：
[0192]
p’a
＝{p
a1
,p
a2
,...,p
an
}，p
an
∈pi[0193]
pi＝{p
i,1
,p
i,2
,...,p
i,m
}，i∈i
[0194]
p
i,m
＝{x
i,m
,y
i,m
,h
i,m
,d
i,m
,v
i,m
,t
i,m
}
[0195]
其中：a为被选取的栅格的编号，p
an
为栅格a内的航迹点的航迹数据，n为栅格a内的航迹点的总数量；pi为终端区空域内的航迹点，p
i,m
为第i条航线的第m个航迹点，i为终端区空域内的航迹总数；x
i,m
为航迹点p
i,m
的经度，y
i,m
为航迹点p
i,m
的纬度，h
i,m
为航迹点p
i,m
的高度索引，d
i,m
为航迹点p
i,m
对应的航班航向，v
i,m
为航迹点p
i,m
对应的航班速度，v
i,m
为航迹点p
i,m
被雷达捕捉的时间；
[0196]
计算待赋值栅格与相邻栅格的交通共性值，并获取待赋值栅格的交通流量负载，将所述航迹数据集、交通共性值和交通流量负载作为交通流信息赋予待赋值栅格；
[0197]
步骤s203：选取一个未被选择的栅格作为新的待赋值栅格，重复步骤s202；
[0198]
步骤s204：重复步骤s203，直至所有栅格被赋予交通流信息。
[0199]
初始agent解确定模块：用于构建适应度函数，对于包含有交通流信息的栅格，利用遗传算法确定初始agent解的位置；初始agent解确定模块具体用于实现以下步骤：
[0200]
s301：设置初始agent解的数量，基于agent解的数量和空域内栅格的总数量计算得到样本数量ns：
[0201][0202]
其中：m为空域内栅格的总数量，na为agent解的数量；
[0203]
将空域内所有的栅格根据样本数量进行均分，得到ns个样本，每一样本中包含有na个栅格；
[0204]
s302：设置第一优化目标函数：
[0205][0206]
其中：表示样本si中所有栅格的交通流量负载总和，i为样本编号；为栅格a的交通流量负载；
[0207]
设置第二优化目标：
[0208][0209]
其中：为样本si内的栅格间的几何距离之和，d
ab
为样本si所包含的栅格a和栅格b之间的米制距离，h
ab
为栅格a和栅格b之间的高度差绝对值；
[0210]
s303：构建适应度函数：
[0211][0212]
其中，f(si)为si的适应度值，为对样本si的第一优化目标函数值的标准化结果，为对样本si的第二优化目标函数值的标准化结果，k为惩罚函数，当满足约束条件是k为0，不满足约束条件是k为负无穷大；n1和n2为权重。
[0213]
s304：对所有样本进行交叉变异处理，迭代多次，得到优化后的样本；
[0214]
s305：基于适应度函数计算所有优化后的样本的适应度值，得到适应度值最大的样本，将适应度值最大的样本对应的栅格作为初始agent解的位置。
[0215]
扇区划设模块：用于设置agent的累积工作负载上限，利用生长规则基于初始agent解的位置得到的扇区划设栅格结果；扇区划设模块具体用于完成以下步骤：
[0216]
s401：针对每一个agent，设置agent的累积工作负载上限，当agent的累积工作负载不超过累积工作负载上限时，执行步骤s402；
[0217]
s402：将每一个初始agent解的位置作为初始栅格，从每一个初始栅格的相邻栅格集合中选定与初始栅格之间交通共性值不为零的栅格，将初始栅格与被选定的相邻栅格作为初始结果；
[0218]
s403：获得初始结果在经纬度面的投影，依照投影与s402中被选定的栅格的层数进行直棱柱的生长，得到每个初始agent解的位置对应的直棱柱；
[0219]
s405：对所有直棱柱进行竖直平面和/或水平平面的扩大，得到扇区划设栅格结果。
[0220]
再分配模块：用于基于扇区划设栅格结果，采用空域填充规则进行栅格再分配，得到终端区扇区划设结果。再分配模块具体用于完成以下步骤：
[0221]
s501：从终端区空域内选取一个未分配栅格；
[0222]
s502：获取位于未分配栅格上方和下方的agent的数量，若未分配栅格上方agent数量小于未分配栅格下方agent数量，则选定未分配栅格上方累积工作负载最小的agent作为待激活agent；否则，选定未分配栅格下方累积工作负载最小的agent作为待激活agent；将空域填充规则赋予待激活agent，得到激活空域填充规则的agent；
[0223]
s503：选取未分配栅格所在的水平层作为待分配水平层，所述待分配水平层与激
活空域填充规则的agent所属扇区里横向水平栅格配置相同，将待分配水平层添加到激活空域填充规则的agent所述扇区内，并将待分配水平层中所有栅格的交通流量负载累加至激活空域填充规则的agent的累积工作负载中；
[0224]
s504：判断未激活空域填充规则的agent对应的扇区是否与待分配水平层发生栅格重合，若是，则将重合的栅格的交通流量负载从对应的agent的累积工作负载中删除；
[0225]
s505：重复步骤s601-s604，直至终端区空域内没有未分配栅格，得到终端区扇区划设结果。
[0226]
本实施例还提供一种计算机设备，该计算机设备可以为工控机、服务器或计算机终端。
[0227]
所述计算机设备包括处理器、存储器，以及存储在所述存储器上并可被所述处理器执行的计算机程序，其中所述计算机程序被所述处理器执行时，实现所述的基于改进agent的终端区扇区划设方法的步骤。
[0228]
该计算机设备包括通过系统总线连接的处理器、存储器和网络接口，其中，存储器可以包括非易失性存储介质和内存储器。
[0229]
非易失性存储介质可存储操作系统和计算机程序。该计算机程序包括程序指令，该程序指令被执行时，可使得处理器执行任意一种基于改进agent的终端区扇区划设方法。
[0230]
处理器用于提供计算和控制能力，支撑整个计算机设备的运行。
[0231]
内存储器为非易失性存储介质中的计算机程序的运行提供环境，该计算机程序被处理器执行时，可使得处理器执行任意一种基于改进agent的终端区扇区划设方法。
[0232]
该网络接口用于进行网络通信，如发送分配的任务等。
[0233]
应当理解的是，处理器可以是中央处理单元(central processing unit，cpu)，该处理器还可以是其他通用处理器、数字信号处理器(digital signal processor，dsp)、专用集成电路(application specific integrated circuit，asic)、现场可编程门阵列(field-programmable gate array，fpga)或者其他可编程逻辑器件、分立门或者晶体管逻辑器件、分立硬件组件等。其中，通用处理器可以是微处理器或者该处理器也可以是任何常规的处理器等。
[0234]
其中，在一个实施例中，所述处理器用于运行存储在存储器中的计算机程序，以实现如下步骤：
[0235]
步骤s1：获取终端区空域的空间数据和空域内所有航迹点的航迹数据，并对所述航迹数据进行预处理；
[0236]
步骤s2：对终端区空域进行栅格化处理，并基于航迹数据为每个栅格赋予交通流信息；
[0237]
步骤s3：利用遗传算法确定初始agent解的位置；
[0238]
步骤s4：设置agent的累积工作负载上限，利用生长规则基于初始agent解的位置得到扇区划设栅格结果；
[0239]
步骤s5：基于扇区划设栅格结果，采用空域填充规则进行栅格再分配，得到终端区扇区划设结果。
[0240]
本实施例还提供一种计算机可读存储介质，所述存储介质上存储有计算机程序，其中所述计算机程序被处理器执行时，实现所述的基于改进agent的终端区扇区划设方法
的步骤。
[0241]
其中，所述计算机可读存储介质可以是前述实施例所述的计算机设备的内部存储单元，例如所述计算机设备的硬盘或内存。所述计算机可读存储介质也可以是所述计算机设备的外部存储设备，例如所述计算机设备上配备的插接式硬盘，智能存储卡(smartmedia card，smc)，安全数字(secure digital，sd)卡，闪存卡(flash card)等。
[0242]
尽管已经示出和描述了本发明的实施例，对于本领域的普通技术人员而言，可以理解在不脱离本发明的原理和精神的情况下可以对这些实施例进行多种变化、修改、替换和变型，本发明的范围由所附权利要求及其等同物限定。

技术特征：
1.基于改进agent的终端区扇区划设方法，其特征在于，包括以下步骤：步骤s1：获取终端区空域的空间数据和空域内所有航迹点的航迹数据，并对所述航迹数据进行预处理；步骤s2：对终端区空域进行栅格化处理，并基于航迹数据为每个栅格赋予交通流信息；步骤s3：利用遗传算法确定初始agent解的位置；步骤s4：设置agent的累积工作负载上限，利用生长规则基于初始agent解的位置得到扇区划设栅格结果；步骤s5：基于扇区划设栅格结果，采用空域填充规则进行栅格再分配，得到终端区扇区划设结果。2.根据权利要求1所述的基于改进agent的终端区扇区划设方法，其特征在于，所述步骤s2具体包括：步骤s201：采用三维空域环境离散化将终端区空域分割成若干大小一致的三维空域单元，得到终端区空域所包含的栅格；步骤s202：选取一个栅格作为待赋值栅格，从预处理后的航迹数据中获取位于被选取的栅格内的所有航迹点的航迹数据，并构建得到被选取栅格的航迹数据集p
′
a
：p
′
a
＝{p
a1
，p
a2
，
…
，p
an
}，p
an
∈p
i
p
i
＝{p
i，1
，p
i,2
，...，p
i,m
}，i∈ip
i,m
＝{x
i,m
,y
i,m
，h
i,m
，d
i，m
，v
i,m
，t
i,m
}其中：a为被选取的栅格的编号，p
an
为栅格a内的航迹点的航迹数据，n为栅格a内的航迹点的总数量；p
i
为终端区空域内的航迹点，p
i,m
为第i条航线的第m个航迹点，i为终端区空域内的航迹总数；x
i,m
为航迹点p
i,m
的经度，y
i,m
为航迹点p
i,m
的纬度，h
i，m
为航迹点p
i,m
的高度索引，d
i，m
为航迹点p
i,m
对应的航班航向，v
i,m
为航迹点p
i,m
对应的航班速度，v
i,m
为航迹点p
i,m
被雷达捕捉的时间；计算待赋值栅格与相邻栅格的交通共性值，并获取待赋值栅格的交通流量负载，将所述航迹数据集、交通共性值和交通流量负载作为交通流信息赋予待赋值栅格；步骤s203：选取一个未被选择的栅格作为新的待赋值栅格，重复步骤s202；步骤s204：重复步骤s203，直至所有栅格被赋予交通流信息。3.根据权利要求2所述的基于改进agent的终端区扇区划设方法，其特征在于，所述交通共性值的计算方法如下：c
a,b
＝tr
a,b
，b∈n
a
,a≠b其中：c
a,b
为栅格a与相邻栅格b的交通共性值，n
a
为栅格a的相邻栅格集合，tr
a，b
为给定时间间隔内航班的轨迹位置从栅格a转移到栅格b的总次数。4.根据权利要求1所述的基于改进agent的终端区扇区划设方法，其特征在于，所述步骤s3具体包括：s301：设置初始agent解的数量，基于agent解的数量和空域内栅格的总数量计算得到样本数量n
s
：其中：m为空域内栅格的总数量，n
a
为agent解的数量；
将空域内所有的栅格根据样本数量进行均分，得到n
s
个样本，每一样本中包含有n
a
个栅格；s302：设置第一优化目标函数：其中：表示样本s
i
中所有栅格的交通流量负载总和，i为样本编号；为栅格a的交通流量负载；设置第二优化目标：其中：为样本s
i
内的栅格间的几何距离之和，d
ab
为样本s
i
所包含的栅格a和栅格b之间的米制距离，h
ah
为栅格a和栅格b之间的高度差绝对值；s303：构建适应度函数：其中，f(s
i
)为s
i
的适应度值，为对样本s
i
的第一优化目标函数值的标准化结果，为对样本s
i
的第二优化目标函数值的标准化结果，k为惩罚函数，当满足约束条件是k为0，不满足约束条件是k为负无穷大；n1和n2为权重；s304：对所有样本进行交叉变异处理，迭代多次，得到优化后的样本；s305：基于适应度函数计算所有优化后的样本的适应度值，得到适应度值最大的样本，将适应度值最大的样本对应的栅格作为初始agent解的位置。5.根据权利要求1所述的基于改进agent的终端区扇区划设方法，其特征在于，所述步骤s4包括：s401：针对每一个agent，设置agent的累积工作负载上限，当agent的累积工作负载不超过累积工作负载上限时，执行步骤s402；s402：将每一个初始agent解的位置作为初始栅格，从每一个初始栅格的相邻栅格集合中选定与初始栅格之间交通共性值不为零的栅格，将初始栅格与被选定的相邻栅格作为初始结果；s403：获得初始结果在经纬度面的投影，依照投影与s402中被选定的栅格的层数进行直棱柱的生长，得到每个初始agent解的位置对应的直棱柱；s405：对所有直棱柱进行竖直平面和/或水平平面的扩大，得到扇区划设栅格结果。6.根据权利要求5所述的基于改进agent的终端区扇区划设方法，其特征在于，所述步骤s405包括：s4051：设置移动比率的参数，确定每次调用生长规则的低工作负载agent个数；s4052：选根据移动比率选取当前累积工作负载低的agent作为目标agent，获取与目标agent所包含的栅格相邻且未被占领的栅格的交通共性值，并选取交通共性值最大的栅格作为目标栅格；s4053：以目标栅格相对目标agent所含栅格的高度位置，产生水平或竖直的栅格几何
平面，将栅格几何平面内的栅格添加到目标agent对应的直棱柱中；s4054：将步骤s4053中被添加到直棱柱中的栅格标记为已分配栅格，将已分配栅格的交通流量负载累加到目标agent的累积工作负载中；s4055：重复步骤s4052-s4054，直至完成对所有交通共性值不为零的栅格的分配，将每一个agent包含的所有栅格作为一个扇区，得到扇区划设栅格结果。7.根据权利要求1所述的基于改进agent的终端区扇区划设方法，其特征在于，所述步骤s5包括：s501：从终端区空域内选取一个未分配栅格；s502：获取位于未分配栅格上方和下方的agent的数量，若未分配栅格上方agent数量小于未分配栅格下方agent数量，则选定未分配栅格上方累积工作负载最小的agent作为待激活agent；否则，选定未分配栅格下方累积工作负载最小的agent作为待激活agent；将空域填充规则赋予待激活agent，得到激活空域填充规则的agent；s503：选取未分配栅格所在的水平层作为待分配水平层，所述待分配水平层与激活空域填充规则的agent所属扇区里横向水平栅格配置相同，将待分配水平层添加到激活空域填充规则的agent所述扇区内，并将待分配水平层中所有栅格的交通流量负载累加至激活空域填充规则的agent的累积工作负载中；s504：判断未激活空域填充规则的agent对应的扇区是否与待分配水平层发生栅格重合，若是，则将重合的栅格的交通流量负载从对应的agent的累积工作负载中删除；s505：重复步骤s601-s604，直至终端区空域内没有未分配栅格，得到终端区扇区划设结果。8.基于改进agent的终端区扇区划设装置，用于实现如权利要求1-7任一项所述的基于改进agent的终端区扇区划设方法的步骤，其特征在于，包括：数据获取模块：用于获取终端区空域的空间数据和空域内所有航迹点的航迹数据，并对所述航迹数据进行预处理；栅格化模块：用于对终端区空域进行栅格化处理，并基于航迹数据为每个栅格赋予交通流信息；初始agent解确定模块：用于构建适应度函数，对于包含有交通流信息的栅格，利用遗传算法确定初始agent解的位置；扇区划设模块：用于设置agent的累积工作负载上限，利用生长规则基于初始agent解的位置得到的扇区划设栅格结果；再分配模块：用于基于扇区划设栅格结果，采用空域填充规则进行栅格再分配，得到终端区扇区划设结果。9.一种计算机设备，其特征在于，所述计算机设备包括处理器、存储器，以及存储在所述存储器上并可被所述处理器执行的计算机程序，其中所述计算机程序被所述处理器执行时，实现如权利要求1至7中任一项所述的基于改进agent的终端区扇区划设方法的步骤。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，其中所述计算机程序被处理器执行时，实现如权利要求1至7中任一项所述的基于改进agent的终端区扇区划设方法的步骤。

技术总结
本发明公开一种基于改进Agent的终端区扇区划设方法、装置、设备和介质，划设方法包括以下步骤：步骤S1：获取终端区空域的空间数据和空域内所有航迹点的航迹数据，并对所述航迹数据进行预处理；步骤S2：对终端区空域进行栅格化处理，并基于航迹数据为每个栅格赋予交通流信息；步骤S3：利用遗传算法确定初始Agent解的位置；步骤S4：设置Agent的累积工作负载上限，利用生长规则基于初始Agent解的位置得到扇区划设栅格结果；步骤S5：基于扇区划设栅格结果，采用空域填充规则进行栅格再分配，得到终端区扇区划设结果。扇区划设结果。扇区划设结果。


技术研发人员：田勇 支博 万莉莉 梁满佳 黄潇 吕越
受保护的技术使用者：南京航空航天大学
技术研发日：2023.05.31
技术公布日：2023/9/6