基于转弯惩罚的机场滑行路径优化及冲突解脱.pdf

引用格式:何康吴红兰宫淑丽等.基于转弯惩罚的机场滑行路径优化及冲突解脱.航空计算技术():.():.基于转弯惩罚的机场滑行路径优化及冲突解脱何 康吴红兰宫淑丽吴 振(南京航空航天大学江苏 南京)摘 要:为了缓解机场滑行道系统运行压力提高航空器运行效率以优化航空器滑行路径降低滑行道占用时间为目标针对机场滑行系统优化问题展开分析建立栅格化机场场面地图并提出基于转弯惩罚和 算法相结合的算法模型 以无锡硕放机场为例进行仿真分析结果表明:与基于冲突等待的传统 算法路径方案相比改进模型在高峰小时航班总运行时间降低 冲突次数降低 次滑行等待时间降低 实验验证所提的路径优化模型是可行的能在提升滑行效率的基础上识别与解脱冲突关键词:滑行路径优化转弯惩罚算法冲突解脱中图分类号:文献标识码:文章编号:()():.:引言随着民航业的发展机场作为航空器运行起讫点和旅客中转点扮演着举足轻重的角色 日益增长的航班量与严重依赖人工分配滑行路径的现状之间存在着不可忽视的矛盾给机场造成了巨大的压力国外学者对航空器滑行路径规划的研究起步较早 一类研究应用了混合整数规划()模型 并在模型中加入了各项个性化指标来精确求解另一类研究应用了遗传算法、蚁群算法等智能优化算法来高效解决滑行路径规划问题 年 等以飞机的油耗和污染物排放最低为目标提出了起飞控制策略 同年 等以平均延误最少和滑行时平均等待时间最少为目标对滑行路线进行了优化近年来国内学者对滑行规划问题进行了算法上的创新 李志龙等通过实时评估单位时间内的冲突等级来选择不同的路径规划策略 张林影基于层次分析法对机场关键点和冲突点拟合降低了冲突频率刘帆等将滑行和冲突解脱的时间代价融入启发函数实现路径的动态搜索 李善梅等将时间代价作为冲突预测和最优路径的启发函数并通过滑动时收稿日期:修订日期:基金项目:国家自然科学基金项目资助()作者简介:何 康()男江苏溧阳人助理工程师第 卷 第 期航 空 计 算 技 术.年 月 .间窗概念把冲突解脱分解成若干子问题来求解 这种方式虽然降低了系统运行压力但限定的窗口大小无法适应大型机场高峰小时运行的复杂情况 姜雨等通过双层规划方法构建了航空器时空协同优化模型有效提升场面调度效率 唐博等结合油耗、滑行时间、污染等多个目标建立了航空器滑行路段的帕累托滑行速度曲线模型目前国内外学者主要基于 算法针对静态场景研究航空器滑行路径规划问题但由于缺乏航空器的动态运行特征难以满足机场场面航空器日渐增多的运行需求 因此以动态优化的方式提出冲突解脱策略改进算法对航空器场面运行的适应度在提升航空器滑行效率降低场面拥堵等方面具有重要意义本文从航空器在不同路径上速度变化入手将转弯时间损耗转化为 算法中启发函数的增量惩罚元素并以滑行和等待时间最短为目标建立冲突动态解脱模型最后使用 仿真平台验证本模型的有效性和优越性 模型建立本文针对航空器滑行路径的动态优化问题构建了一种无冲突且路径平滑的模型.目标函数定义如下变量:第 架进场航空器的预计着陆时间着陆后立即脱离跑道即为开始滑行时间:第 架离场航空器的预计推出时间:第 架航空器整个滑行路径经过的节点数:第 架航空器滑行经过第 个节点:第 架航空器的滑行路径集合:第 架航空器到达 节点的时间:航空器之间的安全滑行间隔时间:第 架航空器基于整个滑行路径总转弯次数的惩罚成本滑行路径优化模型如式()所示()().约束条件模型约束条件如下:()()()()常见的滑行道冲突分为 类分别是追尾冲突、交叉冲突和对头冲突如图 所示 式()是针对交叉冲突和追尾冲突的解脱方式 对于可能发生冲突的节点 由于航空器滑行速度相同只要保证第 架航空器与第 架航空器到达节点 的时间差大于安全间隔时间即可图 种冲突模型式()是针对对头冲突的解脱方式对于第 架航空器与第 架航空器如果它们的滑行路径有共同的路段()航空器 到达节点 的时间早于航空器 到达节点 的时间同时航空器 到达节点 的时间晚于航空器 到达节点 的时间则此时会有对头冲突的情况发生 如果调整两架航空器到达 节点的时间使得航空器 到达 节点的时间早于航空器 到达 节点的时间则可以避免发生对头冲突式()表示进场航空器 的滑行开始时间即预计着陆时间式()表示离场航空器 的滑行开始时间应在预计推出时间之后 算法设计.转弯惩罚函数航空器脱离跑道或推出开车开始滑行时需要由地面管制员根据滑行约束指定一条滑行路径将航空器引导至跑道端或相应的停机位 在李善梅等以算法进行场面滑行路径优化的研究中为简化计算是假定航空器在跑滑系统内以匀速来运动的 但事实上航空器在转弯时由于速度的损耗对比相同滑行距离将占用更多的滑行时间 考虑 算法基于目标函数进行节点评估的特征如果简单地将路段长度作为评估标准将会忽略航空器在转弯处的速度和时间损失 因此为使转弯价值在启发函数中得到体现本文将转弯惩罚函数设为()加入到启发函数的计算中 转弯次数越多惩罚函数值越大为了判断航空器在滑行过程中是否发生转弯可以通过计算相邻两段路径的斜率差异来实现()()()()()()()航 空 计 算 技 术 第 卷第 期 ()式中()为拓展到节点的路径转弯代价总和 为当前节点的父节点坐标()为当前节点坐标()为拓展节点坐标()为()段的斜率 为()段的斜率当两者相等时说明前序节点、当前节点与拓展节点在一条直线上航空器以直线滑行否则航空器进行了转弯()为节点的转弯代价()为当运行到节点时路径中转弯数量 为转弯的平均代价.改进的 算法算法是一种利用启发函数进行启发式搜索的动态规划算法常用于路径规划问题中寻找两点间的最短路径 启发函数提供了向目标点移动的参考信息有效地缩短了路径规划的时间 本文在启发函数中引入转弯代价以减少扩展节点的数量提高寻路性能 对于航空器滑行而言不仅要尽量缩短滑行时间也要尽量减少转弯次数避免转弯过程中频繁加减速带来的旅客不适和耗损时间 因此本文对算法进行了优化实现了降低转弯次数、缩短滑行时间的目标估价函数如下:()()()()()式中()为起点到当前节点的滑行距离代价()为节点到终点的启发值由于大部分机场的滑行道网状结构都以平行滑行道与垂直联络道为主该值选用曼哈顿距离能更接近实际运行方案()的意义在于若在相同时间内航空器以直线滑行速度滑行时可滑行的路径长度比在包含转弯的路径上滑行的长度多出的部分这一部分就是以路径长度衡量的航空器转弯的损耗 通过给定的权重值 来调节转弯因子对 值计算的影响 当 值越大时搜索路径会更多的规避转弯趋向于搜索一条转弯次数少航空器能保持直线滑行速度久进而滑行时间较短的路径.冲突解决方案当场面运行航空器数量不断增加进离港航空器共同运行时滑行调度必然需要考虑到冲突问题 当获得航空器开始滑行的时刻和初始路径时可以在各节点处生成一个航班号与通过时刻的链表 比对节点上时刻差值如不满足安全间隔则说明存在冲突对于优先级较低的航班来说方案一为原地等待冲突消散这将产生一个等待时间代价 方案二为变更滑行路线此时需要回到冲突节点的父节点进行重新寻路生成的新路径将比原路径多耗费一个次优节点时间增量代价 系统将对两者进行评价选择代价较小的方案.求解过程算法流程如图 所示图 模型求解流程:读取航班信息创建并初始化 包含需要访问的节点将航班起点加入 令起点的 值和 值都为 对出港航班而言起点为停机位节点终点为跑道等待点对进港航班而言起点为跑道脱离道口终点为停机位节点 创建 年 月何 康 等:基于转弯惩罚的机场滑行路径优化及冲突解脱 初始为空集 包含已经访问过的节点节点信息中包含转弯次数 对于起点转弯次数初始值为 :将 中 值最小的节点设为 并将其放入 拓展 的联通节点设为并建立指向 节点的指针:根据前续节点、当前节点、拓展节点 三点的坐标计算 与 的斜率判断拓展 节点时是否存在转弯:如有则将 节点的 值替换为 节点的 值加一否则 值不变 计算 节点的 值:如果 节点已经存在于 中则比较新的路径 值是否更小如果更小则更新父节点信息 如果 节点为障碍物、不在地图上或已经存在于 中则忽略该节点否则将其加入 :判断 是否为空和是否已经包含目标节点如果不是则继续上述 如果包含目标节点则输出初始路径按航空器节点时刻判定是否存在冲突 如存在冲突则计算拓展冲突节点的次优节点后产生的新路径滑行时间与初始路径滑行时间的差额将其与原地等待耗时相比较输出代价较小的方案否则直接输出初始路径 算例仿真本文以无锡硕放机场的地面滑行系统为基础选取 年 月典型日高峰小时以 号跑道起降的运行数据进行仿真优化无锡机场设有平滑 条联络道 条快脱 条跑滑结构与代号见图 其中 为进港航空器 为离港航空器进港航班滑行起点为快脱 末端终点为对应机位离港航班滑行起点为所在机位终点为 号跑道等待点 航空器滑行速度设定为直线段 转弯段 加速度.受机坪运行限制 类航空器起飞前 推开推开时间 推开时前后 个机位设为不可通过图 无锡硕放机场滑行结构图航班基础数据见表 由于该时段内运行均为 类飞机地面安全运行距离为 考虑到中小机场航班起飞时刻由中国民航流量管理系统分配一旦错过时刻航班将重新排队增加协调工作量因此优先级设定为离港一律优先于进港离港航班 时间靠前者优先进港航班先到先服务表 无锡机场高峰小时航班基础数据序号航班号机型性质/机位本文在进行路径规划实验时选用 种方案分别计算总运行时间进行对比:)方案 基于传统 算法分配路径冲突时低优先级航班原地等待总运行时间为滑行时间与等待时间总和)方案 基于本文改进 算法分配路径冲突解脱策略同方案)方案 在方案 的基础上优化冲突解脱策略当检测到冲突时进行邻域搜索评价各相邻节点路径变更代价与原地等待代价择优滑行实验所采用的算法仿真参数如表 所示表 仿真及算法参数算法参数取值直线滑行速度/转弯滑行速度/加速度.滑行道宽度/转弯半径/平均转弯角度/()推开时间/惩罚系数.平均转弯代价/安全距离/实验结果如表、图 所示 结果表明:)方案 以航班滑行距离最短为目标路径中转弯较多导致航空器必须进行多次弯道加减速致使滑行时间大大增加 另外运行中序号、的 架进港航空器与其他航空器发生了冲突等待高优先级航班滑至安全间隔后重新开始滑行总等待时间为 )方案 通过转弯惩罚将路径转弯总次数降低了 次虽然滑行距离略有增加但滑行时间总和降低 冲突次数不变冲突等待依然占据较大比值 航 空 计 算 技 术 第 卷第 期)方案 开启了冲突评价机制:原定于 滑上等待 后进机坪滑行次优路径为 滑进机坪运行时间增量为 大于原路径等待时间保留原路径方案 原定于 滑上等待 次优路径为 滑进机坪滑行时间增量为 无冲突等待时间运行总时间远低于原路径方案因此选择次优路径 内滑 原定于 滑上等待 后进机坪滑行次优路径为 滑进机坪滑行时间增量为 等待时间增量为 大于原路径等待时间保留原路径方案方案 较方案 降低总运行时间 转弯次数持平降低冲突次数 次 方案 较方案 降低总运行时间 降低转弯次数 次降低冲突次数 次 各航班在不同方案中总运行时间如图 所示 综上方案 优化效果显著大大提升了场面运行效率表 优化结果对比方案方案 方案 方案 总运行时间/平均运行时间/总等待时间/平均等待时间/冲突次数总转向次数图 方案、滑行时间对比 结束语航空器场面运行受到多方因素影响滑行效率对机场整体运行效率至关重要 本文以航空器场面滑行总滑行时间最短为研究目标提出了基于转弯惩罚和算法相结合的算法模型 案例采用无锡硕放机场地面实际运行的航班滑行数据进行仿真实验结果表明本文模型与传统 算法相比有助于减少航空器总滑行时间降低转弯次数避免滑行冲突可以为管制员提供决策支持参考文献:.:.():.:().:.:.():.():.():.():.:.():.李志龙张建伟.基于强化学习的机场服务机器人动态路径规划.现代计算机():.张林影.机场关键冲突点识别及滑行路径优化研究.广汉:中国民用航空飞行学院.刘帆张学军马国亮等.算法的场面滑行动态规划方法.空军工程大学学报:自然科学版():.李善梅高艺.基于改进 算法的机场场面滑行路径优化.计算机仿真():.姜雨王欢樊卫国等.场面航空器滑行时空协同优化模型.交通运输工程学报():.唐博韩松臣梁斌斌.基于多目标优化的航空器滑行速度曲线生成.现代计算机():.孙梦圆田勇叶博嘉等.飞行冲突探测与解脱方法研究综述.航空计算技术():.万莉莉.面向环境保护的空中交通运行优化方法研究.南京:南京航空航天大学.():.:.年 月何 康 等:基于转弯惩罚的机场滑行路径优化及冲突解脱