摘要
针对在最少油耗、最快时间和最低成本等目标下的巡航阶段路径优化中,出现的边权重与前续路径的选择密切相关、估值函数计算开销过大等问题,首先构建了GRIB2格式网格气象数据插值、飞机性能参数快速计算流程,然后通过对A*算法估值函数系数和性能计算步长进行改进,提高每步优化时的计算效率;之后针对典型飞行任务,对不同优化目标下的结果进行对比,分析了成本指数、飞机起始质量和飞行高度层等因素的影响。将飞行性能计算融入边权重的A*算法相对于传统最短路算法会增加计算时间,但同样以飞行性能最优为目标的情况下,相较于Dijkstra算法它可以更迅速地找到优化路线。
随着欧洲空域一体化改革的推进,空域使用规则逐渐向更加灵活机动的方向发展,使得航空公司可以更加灵活地选择各个航段,形成一条最佳航路,以降低从国内直飞欧洲航线的燃油消耗和飞行成本。
给定起点以及终点,寻找出一条可行路径的问题在无人
常见的寻路算
康文雄
上述研究所涉及的图模型中的各边权重有些是固定值,有些是针对动态环境不断变化的,但这种外界的变化与寻路过程本身是不相关的,也就是说并不会因为前续路线的选择问题影响图中各边权重变化。但是,在巡航航路优化过程中,边权重(如航段油耗、成本等)与飞机在该边起始点的重量有关,而该重量值又与前续路线的实际油耗有关,也就是说不同的前续路线会造成同一条边的权重不同,因此需要在优化中实时计算边权重和估值函数。再结合计算权重时需要将航路划分成段进行重量迭代计算,每次分段后的计算都需要进行相应的飞机性能参数的积分计算与高空风温数据插值计算,这样的处理过程与传统的权重为距离常值相比,计算资源消耗较
根据二进制的通用规则分布信息版本2(General regularly‑distributed information in binary form, GRIB2)格式原始气象数
(1) |
(2) |
当需要考虑某段航路上的风速时,找到该航段中点,采用双线性插值法得到该中点处的风速,并用此值近似代表整段航路上的风速。该风速矢量在航向上的投影即顺(逆)风分量,直接影响地速和航行时间,是稍后的性能计算中所需的重要参数。中点温度可通过类似的方法进行计算,并用以代表整段航路上的温度。
航油成本在民航运输中所占比重相当高,合理的飞行油耗可以有效地降低成本。在给定飞机质量、飞行高度和气象风温的条件下,燃油流量和飞行速度可根据性能数据库求出,继而飞行时间可求,而飞机油耗由燃油流量和飞行时间共同决定。但是,随着燃油的消耗,飞机质量越来越小,该参数又会对燃油流量和飞行速度的计算带来影响。所以,采取如

图1 性能计算方法
Fig.1 Algorithm of performance calculation
飞行成本指数可以用来衡量航班的总成本,它被定义为小时成本与燃油成本的比值,即
(3) |
式中:Chr为除燃油成本外的每小时使用成本,单位元/时;Clb为每百磅燃油成本,单位元/百磅。与飞行有关的航班总成本由燃油成本和时间成本组成,即
(4) |
式中:t为飞行总时间,单位小时;F为飞行燃油总消耗量,单位千克。整理可得
(5) |
在刚刚计算飞行油耗和飞行时间的基础上,笔者可以计算出航班飞行成本C,单位元。
使用航空无线电通信公司(Aeronautical radio incorporated, ARINC424)格式的航路数据,根据格式规则将数据文件导出整理形成csv文件。其中每行数据代表一个航段,包括航段所属航路名、相对位置、起始航路点、终止航路点经纬度等。分析该航路数据文件,发现其中存在了一些名称相同但经纬度位置不同的航路点。故数据处理前需要进行数据检查,对重名航路点重新进行命名。具体流程如

图2 重名航路点处理流程
Fig.2 Process of duplicated name waypoints
基于已经转换成连通图的航路网络结构,不同目标下的航路优化问题可看作是基于图论的最短路径问题。该问题的一般提法如下:设G=(V, E)为连通图,图中各边(,)有权 (表示、间无边),、为图中任意两点,求一条道路,使它是从到的所有路中总权最小的路,即
(6) |
最小(考虑单源点的最短路径问题)。式中、分别为航路的起点和终点,连通图G即航路网络。各边的权重根据航路优化目标的不同,可以是两航路点间的距离、飞过两航路点所需的油耗、飞行时间、飞行成本。
航路网络图中的航路点密集程度很高,在这种情况下,寻找起点和终点间的最优路线对计算量的需求相当大。考虑到制定航线的实际情况,起点和终点间的大圆航线几何距离最短,根据不同目标寻找到的最优路线会有一定程度的偏离但不会偏离过多。因此,在进行航路优化时,研究范围被缩减在以起点和终点为焦点的椭圆内,椭圆长轴的长度控制可变,通过适当选取起点和终点间距离的倍数确定(见

图3 航路网络计算域的椭圆形裁剪
Fig.3 Ellipse cropping of the computational domain of route network
Dijkstra算法虽然可以得到准确的最优解,但全局搜索耗时较久,此处采用启发式A*算法进行加速。A*算法中涉及的估值函数h是在考虑气象条件的情况下,基于当前点与结束点间的大圆航线对飞行油耗、时间、成本等性能进行计算,由于它本身是一种估计值,可以设计对h乘以一个系数k来表征所选估值函数的变化程度,然后选取合适的参数使得在计算代价相对较小的情况下得到满意的目标路径。
前面介绍的算法部分适用于飞机性能允许范围内的任意飞机初始质量、成本指数、飞行高度值,这些参数的变化虽然直接影响优化结果,但通过大量的算例分析,发现他们的变化趋势是一致的。所以,为了使计算结果的呈现更加简洁清晰,本部分从一到两个具体的飞行任务案例出发,分析算法涉及的相关参数以及不同的优化目标(最短飞行路径min s,最少飞行油耗min F,最快飞行时间min t,最低飞行成本min C)带来的优化结果。
本部分的案例涉及的气象数据来自某航空公司2020年5月7日0时的高空气象GRIB2文件,通过飞过航路点的经纬度位置以及飞行高度层可以确定出当地的国际标准大气(International standard atmosphere,ISA)温度偏差。
当A*算法中估值函数h的系数k等于零时,正是Dijkstra算法的实现步骤。因为Dijkstra算法是可以给出准确的目标路径的,变化估值函数的系数k,在全球航路网络中选取起点ITE,终点OK,按照成本指数50、飞机起始质量295 000 kg、飞行高度层9 500 m的计算条件,以min F为目标进行航路优化。对比优化结果、运算时间(以Dijkstra算法得到准确解的时间为基准1,计算运算时间比值)、累计访问航路点数目,具体如
k | 油耗/kg | 运算时间 | 累计访问航路点数目 |
---|---|---|---|
0.0 | 60 124 | 1.000 0 | 27 152 |
0.1 | 60 124 | 0.971 0 | 25 970 |
0.2 | 60 135 | 0.904 3 | 24 438 |
0.3 | 60 135 | 0.817 8 | 22 054 |
0.6 | 60 135 | 0.573 2 | 15 636 |
0.9 | 60 135 | 0.195 4 | 5 255 |
实际上,k=0和k=0.1情况下得到的优化路线是完全一致的:ITE—SANDA—ROKKO—CUE40—TOZAN—TSUNO—JEC—BOKSA—NAMER-OK,该路线下的飞行油耗是60 124 kg;当k取其他值时,会得到稍区别于上一条优化路线的另一条路线:ITE—SANDA—ROKKO—CUE40—TOZAN—RAKDA—JEC—BOKSA—NAMER—OK,该路线下的飞行油耗是60 135 kg,比准确解多消耗了0.02%的燃油。与此同时,观察运算时间和累计访问航路点数目可以看到,随着k值的增加,计算开销显著减小,选取较大的k值可以在保证准确性的基础上提高计算效率,接下来的计算过程取k=0.9。
另外,涉及性能计算的质量迭代问题,原则上令计算中涉及的每段航路距离尽可能小,这样飞机质量值能够得及时更新,结果会更加准确。实际上考虑到航程距离和计算代价,选取固定的计算步长,每次计算时取该步长与它和下一航路点间的距离中的较小值作为计算步长。与前文研究估计代价函数系数对优化结果的影响类似,变化该计算步长,在全球航路网络中选取起点ITE,终点OK,按照成本指数50、飞机起始质量295 000 kg、飞行高度层9 500 m的计算条件,以min F为目标进行航路优化。对比优化结果、运算时间(以固定步长等于20 km时的所需运算时间为基准1,计算运算时间比值)、累计访问航路点数目,具体如
步长/km | 油耗/kg | 运算时间 | 累计访问航路点数目 |
---|---|---|---|
20 | 60 146 | 1.000 0 | 5 283 |
100 | 60 135 | 0.857 4 | 5 255 |
200 | 60 131 | 0.847 7 | 5 271 |
实际上,表格中的3种情况下得到的优化路线是完全一致的:ITE—SANDA—ROKKO—CUE40—TOZAN-RAKDA—JEC—BOKSA—NAMER—OK,取不同的固定步长导致最终计算得到的飞行油耗有细微区别。前面已经提到固定步长越短,质量迭代越精确,此处以20 km固定步长所对应的运算时间作为基准,可以发现随着步长的进一步提高运算时间的减少并不明显,但计算油耗值却越来越偏离准确值,接下来的计算过程取固定步长等于100 km。
在全国航路网络中,选取起点BUNTA,终点P13,按照成本指数50、飞机起始质量255 000 kg、飞行高度层9 500 m的计算条件,分别以min s、min F、min t、min C为目标进行航路优化,结果见
优化目标 | 油耗/kg | 距离/m | 时间/s | 成本/元 |
---|---|---|---|---|
min s | 21 948 | 2 621 769 | 11 008 | 144 413 |
min F | 21 651 | 2 673 031 | 10 855 | 142 446 |
min t | 21 651 | 2 673 031 | 10 855 | 142 446 |
min C | 21 651 | 2 673 031 | 10 855 | 142 446 |
根据前面的优化结果可知,以min F、min t和min C为优化目标时会得到相同的航路优化结果。所以接下来选定min C和最短路径为优化目标,考虑由成本指数带来的影响,分别选取成本指数等于20、50、80和110,按照飞机起始质量255 000 kg、飞行高度层9 500 m的计算条件,在全国航路网络中选取起点BUNTA、终点P13进行航路优化(见

图4 不同成本指数对BUNTA至P13(全国航路)的航路优化的影响
Fig.4 Impact of different cost indices on optimization from BUNTA to P13 (national airways)
类似地,选定min C和最短路径为优化目标,考虑由飞机起始质量带来的影响。分别选取飞机起始质量等于215 000、235 000、255 000和275 000 kg,按照成本指数50、飞行高度层9 500 m的计算条件,在全国航路网络中选取起点BUNTA、终点P13进行航路优化(见

图5 不同飞机起始质量对BUNTA至P13(全国航路)的航路优化的影响
Fig.5 Impact of different aeroplane masses on optimization from BUNTA to P13 (national airways)
最后,选定min C和最短路径为优化目标,考虑由飞行高度层带来的影响。分别选取飞行高度层等于8 900、9 500、10 100和10 700 m,按照成本指数50、飞机起始质量255 000 kg的计算条件,在全国航路网络中选取起点BUNTA、终点P13进行航路优化(见

图6 不同飞行高度层对BUNTA至P13(全国航路)的航路优化的影响
Fig.6 Impact of different flight altitudes on optimization from BUNTA to P13 (national airways)
分别以min s、min F、min t、min C为目标进行高空巡航航路优化,讨论了经过改进的A*算法在大规模航路图中的适用性。优化目标不同,所得优化路径不一致,其中以飞行性能为目标min F、min t、min C可以得到相同的优化路线,而以传统最短路min s为目标得到的优化路线是不同于其他情况的,此结果与预期相符,一方面改进A*算法相对于传统最短路算法会增加计算时间,另一方面同样以飞行性能最优为目标的情况下,相较于Dijkstra算法它可以更迅速地找到优化路线。
成本指数不同决定优化路线时,是燃油成本的影响更大还是时间成本的影响更大,在相同的某种优化目标下,对于得到的优化路线,成本指数越高,油价影响越小,飞行油耗越高,时间影响越大,飞行时间越短;而飞机起始质量越大、飞行高度层越低时,飞行油耗越高。可以看出,以飞机性能和气象数据为基础的航路优化算法的影响因素较多,最低成本优化结果与传统最短路径优化相比,可减少燃油消耗,减少飞行时间,降低成本,产生不错的经济效益。
由于各地区实际运行情况并不相同,本文的研究内容没有涉及当地的相关运行规则以及实际可能会碰到的相关管制情况,而是选择使用了单一简单图模型来作为研究基准对象,目的是为了保证算法的普适性。后续可根据研究的具体区域在该基准模型的框架下进行相应的限制修改,为后续研究服务。
参考文献
SATHYARAJ B M, JAIN L C, FINN A, et al. Multiple UAVs path planning algorithms: A comparative study[J]. Fuzzy Optimization and Decision Making, 2008, 7(3): 257-267. [百度学术]
RADMANESH M, KUMAR M, GUENTERT P H, et al. Overview of path-planning and obstacle avoidance algorithms for UAVs: A comparative study[J]. Unmanned Systems, 2018, 6(2): 95-118. [百度学术]
MAC T T, COPOT C, TRAN D T, et al. Heuristic approaches in robot path planning: A survey[J]. Robotics and Autonomous Systems, 2016, 86: 13-28. [百度学术]
HUSSEIN A, MOSTAFA H, BADREL-DIN M, et al. Metaheuristic optimization approach to mobile robot path planning[C]//Proceedings of 2012 International Conference on Engineering and Technology (ICET). Cairo, Egypt: IEEE, 2012: 1-6. [百度学术]
NAZARAHARI M, KHANMIRZA E, DOOSTIE S. Multi-objective multi-robot path planning in continuous environment using an enhanced genetic algorithm[J]. Expert Systems with Applications, 2019, 115: 106-120. [百度学术]
CAZENAVE T. Optimizations of data structures, heuristics and algorithms for path-finding on maps[C]//Proceedings of 2006 IEEE Symposium on Computational Intelligence and Games. Reno, USA: IEEE, 2006: 27-33. [百度学术]
LEIGH R, LOUIS S J, MILES C. Using a genetic algorithm to explore A*-like pathfinding algorithms[C]//Proceedings of 2007 IEEE Symposium on Computational Intelligence and Games. Honolulu,USA: IEEE, 2007: 72-79. [百度学术]
LI D, LEE D L. A lattice-based semantic location model for indoor navigation[C]//Proceedings of the Ninth International Conference on Mobile Data Management (MDM 2008). Beijing, China: IEEE, 2008: 17-24. [百度学术]
BECKER C, DUERR F. On location models for ubiquitous computing[J]. Personal and Ubiquitous Computing, 2005, 9(1): 20-31. [百度学术]
LI D, DIK L L. A topology-based semantic location model for indoor applications[C]//Proceedings of the 16th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems. Irvine, USA: ACM, 2008. [百度学术]
JENSEN C S, LU H, YANG B. Graph model based indoor tracking[C]//Proceedings of 2009 Tenth International Conference on Mobile Data Management: Systems, Services and Middleware. Taipei, China: IEEE, 2009: 122-131. [百度学术]
NAM H, HONG S, HAN B. Online graph-based tracking[C]//Proceedings of Computer Vision— ECCV 2014. Zurich, Switzerland: Springer International Publishing, 2014: 112-126. [百度学术]
ROBERGE V, TARBOUCHI M, LABONTE G. Comparison of parallel genetic algorithm and particle swarm optimization for real-time UAV path planning[J]. IEEE Transactions on Industrial Informatics, 2013, 9(1): 132-141. [百度学术]
SAHINGOZ O K. Flyable path planning for a multi-UAV system with genetic algorithms and Bezier curves[C]//Proceedings of 2013 International Conference on Unmanned Aircraft Systems (ICUAS). Atlanta, USA: IEEE, 2013: 41-48. [百度学术]
SONMEZ A, KOCYIGIT E, KUGU E. Optimal path planning for UAVs using genetic algorithm[C]//Proceedings of 2015 International Conference on Unmanned Aircraft Systems (ICUAS). Denver, USA: IEEE, 2015: 50-55. [百度学术]
康文雄, 许耀钊. 节点约束型最短路径的分层Dijkstra算法[J]. 华南理工大学学报(自然科学版), 2017, 45(1): 66-73. [百度学术]
KANG Wenxiong, XU Yaozhao. A hierarchical Dijkstra algorithm for solving shortest path from constrained nodes[J]. Journal of South China University of Technology (Natural Science Edition), 2017, 45(1): 66-73. [百度学术]
薛双飞, 谢磊, 王树武, 等. 海上风电场区船舶A~*避碰寻路算法[J]. 中国航海, 2018, 41(2): 21-25. [百度学术]
XUE Shuangfei, XIE Lei, WANG Shuwu, et al. A~* algorithm for ships avoiding offshore wind farm facility[J]. Navigation of China, 2018, 41(2): 21-25. [百度学术]
黄冬梅, 杨建, 何盛琪, 等. 基于权重的改进A~*算法航线规划研究[J]. 海洋信息, 2018, 33(2): 16-22. [百度学术]
HUANG Dongmei, YANG Jian, HE Shengqi, et al. Weight based A~* algorithm improved for ship route planning[J]. Marine Information, 2018, 33(2): 16-22. [百度学术]
魏志强, 张文秀, 韩博. 考虑飞机排放因素的飞机巡航性能参数优化方法[J]. 航空学报, 2016, 37(11): 3485-3493. [百度学术]
WEI Zhiqiang, ZHANG Wenxiu, HAN Bo. Optimization method of aircraft cruise performance parameters considering pollution emissions[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(11): 3485-3493. [百度学术]