考虑优先级的交叉口航班汇聚排序问题研究.pdf

考虑优先级的交叉口航班汇聚排序问题研究 周娟，王莉莉 （中国民航大学 天津市空管运行规划与安全技术重点实验室，天津 ） 摘要：为了有效地利用航路资源，减少飞行延误总成本，建立了改进的航路交叉口汇聚排序模型。 为加快求解速 度，分析了影响航班延误成本的因素，给出了权重赋值表，改进了现有算法，并用 算法与改进算法进行了算例 分析。 仿真结果表明，改进算法通过对交叉口航班各属性赋权值可有效进行优先等级划分，完成时隙分配和航班 排序的快速计算。 采用改进给出的优化排序策略可减少延误飞行的总成本，具有一定的实用性。 关键词：空中交通管理；航路交叉口；航班排序；时隙分配；优先级 中图分类号：文献标识码：文章编号：桘 （）桘 桘 Research on Scheduling Problem of Intersection Flight Considering Priority ， 桘 （Tianjin Key Lab of Operation Programming and Safety Technology of Air Traffic Management，CAUC，Tian Jing ，China） Abstract： ， ， ， - - Key words： ； ； ； ； 引言 由于我国空域资源有限，且空中交通流量日益增 加，使得航路交叉点交通十分拥挤，研究科学合理的交 叉口汇聚排序方法，降低航班延误成本，已成为空中交 通流量管理中的一个热点问题。 目前国内外航班排序 的研究主要集中在进场 着陆到达航班排序或终端区 进离场排序和时隙分配方面。 黄政等 针对机场到达 航班的排序与调度（）问题，建立了以航班总延误 时间为目标函数的排序模型，提出了基于格里芬斯塔 特编码和滚动时域优化策略的遗传算法。 杨姝等 将 飞行程序与终端区进场航班排序优化问题结合分析， 重点研究区域导航飞行程序下终端区进场航班排序的 空管特性。 等 使用多目标进化算法提出了 解决飞机着陆排序问题（），同时考虑了总到达排 序时间和总成本最小的目标，提出了排序方案以确定 最佳的着陆顺序。 王飞等 基于人工鱼群算法的单机 场地面等待优化策略，通过分配时隙并进行仿真。 王 飞等 利用模糊聚类方法对航班进行分组分配时隙计 算相应的延误损失费用。 赵嶷飞等 新增加了飞行高 度层这一决策变量，提出的时隙航线分配模型。 本文 主要考虑两交叉航路在交叉口前至少 的航班 汇聚排序。 给到达交叉口的航班各属性赋权值，进行 优先等级划分，按优先等级顺序分配时隙进行排序，使 各航班按此排序通过交叉口，在避免飞行冲突前提下， 尽量减少延误总成本。 模型建立与分析 航班优先等级和延误损失系数 为使延误总成本尽可能小，需优先考虑延误较大 的航班，因此需进行优先等级划分。本文主要考虑机 收稿日期： 修订日期： 基金项目：国家自然科学基金与中国民用航空基金联合项目资助（）；中央高校基本科研业务费资助（ ） 作者简介：周娟（ ），女，湖南永州人，硕士研究生，主要研究方向为航班排序。 第 卷第 期航 空 计 算 技 术 年 月 型、实际载客人数、连续航班、飞行任务的性质等属性， 根据各属性对航班的影响程度，分别对各属性 s 赋一 定的权值 s（ s），飞行时应是所有属性综合 影响的结果，因此对于每个航班 f 应考虑总权值 f，其 满足：f s s。 总权值越大，表明该航班越重要， 因此优先等级越高，对于总权值相等的航班，则按照 原则进行优先等级划分。 设定第 等级为最高 等级，后续等级依次往后排列，优先等级高的应排序在 前，可优先分配预计到达时间之后满足约束条件的最 早时隙。 可见总权值越大的航班在相同延误时间内造 成的延误成本越大，对应的延误损失系数 f越大，因 此延误损失系数 f与总权值 f成正比，可按 f kf 计算，k 为常数。 模型建立 模型假设 为保证各航班安全有序通过交叉口，需要给出排 序分配建立模型的前提假设： ）假设所研究的航路交叉口周围天气状况良好， 同时没有军航活动对其影响，由于航路不同飞行方向 上排序方法相同，在这里只考虑单方向飞行。 ）进入航路交叉点的航空器数量不超过区域管制 员所能指挥的最大架次。 ）航班间非雷达间隔的尾流间隔时间不得少于 。 ）任意一条航路中的飞机飞离交叉口，可由保持 侧向间隔距离等方法与飞离交叉口的航路上的飞机保 持安全间隔，这里不予考虑。 ）为简便计算，设各容量为定值，不随时间变化。 目标函数及约束条件 交叉口汇聚航班排序的目的是对来自于交叉航路 上的不同时刻到达交叉口的航班进行重新排序，在满 足一定飞行间隔规定的基础上，使航班以分配时隙有 序在交叉口汇聚，以减少交叉口航班的总延误成本，保 证航路容量与流量之间的平衡。 因此以总延误成本为 最小值目标函数可表示如下： n f N t f（SLfESf）Xf，t 其中，f为航班 f 单位时间的延误损失系数；SLf ESf 表示航班 f 实际分配的时隙与预计到达时间的差值， 即该航班的延误时间；Xf，x表示航班 f 是否分配时隙 t。 约束条件如下： LRCR（） LsCs（） N t Xf，t（） n f Xf，t（） SLfESf（） SLf SLfTs，（） SLf ESfdf，（） Xf，t（，）， f，n，t，N（） 其中：式（）表示交叉航路上的流量不超过其容量；式 （）表示航路交叉口 i 的流量不超过其容量；式（）限 制一个航班 f 只能分配一个时隙 t；式（）表示一个时 隙 t 只能分配给一个航班 f；式（）表示时隙分配的时 间不能早于预计的进入交叉口的时间；式（）满足最 小安全间隔：相邻两个航班通过航路交叉口的时间间 隔不能小于规定的最小安全间隔；式（）表示连续航 班和非连续航班的延误时间不超过相应最大延误时 间；式（）表示变量 xf，t的取值，取值为 时表示时隙 t 分配给航班 f，否则表示此时隙不分配给该航班。 算法分析 根据模型建立思路，则交叉口汇聚航班排序算法 步骤如下： ）初始参数的确定：包括预计通过航路交叉口的 时间 ESTESt，ESt，ESm， 分配时隙 SLT SLt，SLt，SLm，航路 R上航班 f f，f， fNI，容量为 C，航路 R航班 f f，f，fNI，容 量为 C，交叉口 s 的容量为 Cs，航班机型集合 A，各航 班属性权值 s，连续航班和非连续航班的最大可延误 时间分别为 df， d，d。 ）求各航班的总权值，并确定各航班的单位时间 延误损失系数 f kf。 ）根据航班优先等级划分方法，确定航班优先等 级序列 f f，f，fNN。 ）给航班 fi分配时隙 SLtj，即求 SLfi： ）检验时隙 SLij是否满足式（）和式（），若满足 执行 ）；若不满足式（），表明该航班已有时隙，令 i i ，iN N，返回步骤 ）；若不满足式（），表明 时隙 SLtj已分配，令 j j ，jm，返回步骤 ）。 ）判断其是否满足式（）、（）、（），若满足则 SLfi SLtj，xfi，tj 否则 xfi，ti ，令 j j ，jm，返回 步骤）。 ）令 i i ，若 iN N，返回步骤 ）。 否则， 完成排序和分配，算法结束。 算例仿真 所用航班相关数据为北京首都机场某日 ： ： 的部分航班数据。 年 月周娟 等：考虑优先级的交叉口航班汇聚排序问题研究 R上航班 f f，f，f，C ，R上航班 f f，f，f，C ；R预计到达交叉口的时 间为 EST ：，：，：，：，：，：，：， ：，：，：；R预计到达交叉口时间为 EST ：，：，：，：，：，：，：，：，：， ：，设连续航班和非连续航班的最大可延误时间分 别为 df， ， ，航班各属性相关参数如 表所示，各属性权值赋值表如表 所示。 时隙为 SLT ：，：，：，：，：，：，：，：， ：，：，：，：，：，：，：，：，：， ：，：，：，根据预计到达时间先后排序机型 A ， ，。 表航班各属性相关参数 航班 属性 机型实际载客人数连续航班 飞行任务的性质 H枛否定期航班 H枛否包机 H否专机 Hi是调机 H枛否定期航班 H枛否包机 H枛否定期航班 H枛是定期航班 H否专机 H枛是包机 H枛否定期航班 H枛否定期航班 H是包机 H枛是定期航班 Hi是调机 H枛是定期航班 H枛是包机 H枛否定期航班 枛是定期航班 枛是包机 表 各属性权值赋值表 机型 权值 实际载客 人数 权值 飞行任务的 性质 权值 连续 航班 权值 热 篌北 调机櫃 是揶 热 北 定期民用櫃 否揶 热 热 包机櫃 北 专机櫃 葺北 为简便计算，取 k ，则 f f。 由 原则和 本文算法得到的排序结果如表 所示，时间单位为 。 可知，两算法的总延误时间基本差不多，但利用 原则分配时总延误成本为 ，本文算法总 延误成本 ，飞行延误的总成本大大减少，可有效 进行优先等级划分和航班排序。 表 原则和本文算法得到的排序结果 航班信息 航 班 预计到 达时间 原则排序结果 时隙 分配 延误 时间 损失 系数 延误 成本 本文算法排序结果 时隙 分配 延误 时间 损失 系数 延误 成本 牋：揪：煙 煙： f 拻 牋：揪：煙G ： Q Q 牋：揪：煙 s ： f f 牋：揪：煙G ： Q 拻 牋：揪：煙 s ： f f 牋：揪：煙G ： 靠Q f 牋：揪：煙G s ： Q f 牋：揪：煙 s ： f f 牋：揪：煙 s ： f f 牋：揪 ：煙G ： Q Q 牋：揪：煙 s ： 靠f 牋：揪：煙G s ： Q 拻 牋：揪：煙G ： Q 拻 牋：揪：煙 煙： f f 牋：揪：煙G ： Q Q 牋 ： 揪：煙G s ： Q Q 牋：揪：煙G ： Q Q 牋：揪：煙G s ： Q f 抖：揪：煙 墘： f f 抖：揪：煙G ： Q Q 总延误 时间 档 总延误 成本 墘 总延误 时间 靠 总延误 成本 i 结束语 针对航路交叉口汇聚航班排序问题，建立了相关 模型，考虑了航班属性的影响，改进了现有算法，用 算法和本文算法分别进行算例分析。 仿真结果 表明，本文算法较 算法有优势，可以大大减少飞 行延误的总成本，且计算速度加快。 （下转第 页） 航 空 计 算 技 术第 卷第 期 参考文献： 蒋祖国，田丁栓，周占廷 飞机结构载荷 环境谱 北 京 ：电子工业出版社，： ， 刘文廷，王智，隋福成，等 单机寿命监控技术指南 北京：国防工业出版社，： 刘树元，贾国荣，唐永岩，等 单机疲劳寿命监控技术研究 中国航空工业总公司科学技术委员会，飞机结构疲 劳定寿文集（第 集）， 桘 桘 - ，（）： - - ， ，： ， ， ： ： ，： ， 高新波，谢维信 模糊聚类理论发展及应用的研究进展 科学通报 ， ：（）： ， - ， - ，： ， ， ： ， - ， ，（）： - ： ： - ，： ， ： - 桘 ， ， ： 史峰，王小川，郁磊，等 神经网络 个案例分析 北京：北京航空航天大学出版社，： ， ， ， 桘 - ，（）： ， ， ， ： ， 付梦印，邓志红，闫莉萍，等 滤波理论及其在导 航系统中的应用 北京：科学出版社，： ， ， 桘 桘 - ，（）： 哈斯巴干，马建文，李启青，等 模糊 均值算法改进及 其对卫星遥感数据聚类的对比 计算机工程， （）： （上接第 页） 参考文献： 黄政，白存儒，张伟 到达航班排序与调度优化的遗传算 法研究 航空工程进展 ，（）： 杨姝 基于区域导航飞行程序的进场航班排序优化策略 天津：中国民航大学， ， ， ， 桘 - ，： 王飞，徐肖豪，张静基于人工鱼群算法的单机场地面等 待优化策略 南京航空航天大学学报 ，（）： 王飞，徐肖豪，张静 基于航班模糊聚类的时隙分配均衡 模型 系统工程理论与实践，（）： 赵嶷飞 管制区短期空中交通流量管理的时隙 航线分 配模型及算法 航空学报，（）： 中国航班航空局 桘 中国航班航空空中 交通管理规则 北京：中国航班航空局， ： 年 月马凯超 等 ：基于神经网络的飞行科目模板样本集建立方法