考虑航线交叉的救援直升机起飞时序规划方法*
2015-02-02张家铭石建迈贺云岳王一杉
张家铭，刘 忠，石建迈，贺云岳，王一杉，陈 超
(1.国防科技大学 信息系统与管理学院， 湖南 长沙 410073； 2.中国人民解放军63796部队， 四川 西昌 615000)
考虑航线交叉的救援直升机起飞时序规划方法*
张家铭1，刘忠1，石建迈1，贺云岳1，王一杉2，陈超1
(1.国防科技大学 信息系统与管理学院， 湖南 长沙410073； 2.中国人民解放军63796部队， 四川 西昌615000)
摘要：为解决多架救援直升机的起飞时序规划问题，以最小化最后一架救援直升机的起飞时间为优化目标，建立多直升机多起降点的数学规划模型。设计了基于任务优先级的快速启发式算法，提出航线交叉点的处理方案，给出起飞时间求解算法。以云南鲁甸6.8级地震的灾后救援为背景，设计了包含24架直升机和12个起飞点的起飞时序规划案例，对模型和算法进行了仿真验证，并对航线交叉的影响与处理措施进行了深入讨论。实验结果表明该模型和方法能有效解决多架救援直升机的起飞时序规划问题。
关键词：灾害救援；救援直升机；任务规划；航线交叉
中国是自然灾害多发的国家，近年来发生的地震、塌方、泥石流等重大自然灾害，给国家和人民生命财产带来了巨大损失。以地震灾害为例，据中国地震局统计，中国大陆地震约占世界大陆地震总数的1/3，而死亡人数约占世界地震死亡人数的1/2[1]。导致地震等自然灾害中死亡人数居高不下的一个重要原因就是灾后交通受阻以致救援不及时[2]。直升机可以垂直起降，可以更快到达水、陆路不可通达的作业现场和受灾严重地区，因而成为灾害救援的核心装备。因此，为了进一步提高救援效率，保障飞行安全，缩短救援时间，为各航路的救援直升机合理地规划起飞时序意义重大。相关研究主要集中在以下两方面的问题。
直升机的航路规划问题。主要是研究在满足一定约束条件下，如何寻找直升机从初始点到目标点的最优运动轨迹[1]。常用的优化目标有运动时间最短[3]、离地高度最低[1]等。航路规划问题本质是路径搜索问题，根据对搜索状态空间的划分和搜索算法的特点，文献[1]将航路规划方法归纳为三种：一是基于概略图的规划方法，常用的有泰森多边形法[4]、随机路线图法[5]；二是基于单元分解的规划方法，常用的求解算法有A*算法[6]和动态规划算法[7-8]等；三是基于类比的航路规划方法，典型的算法有人工势场法[9]、神经网络算法[10]、蚁群算法[11-13]、遗传算法[14]等。
直升机的任务规划问题。主要是研究直升机在执行医疗物资投放、抢险力量输送、受伤民众疏散等救援任务过程中，满足救援时间窗口和飞行时间等约束的前提下，寻求最优的资源调配方案[15]。常用的优化目标有执行救援任务的总时间最短[16]、物资分发后的最小获得物资量最大[17]。相关研究对于灾害救援过程中直升机等救援装备的合理调配具有指导意义。
此外，飞行器的自身安全也是一个不容忽视的问题，尤其是近年来世界多地发生的直升机相撞事故使得直升机的飞行安全再度引起人们的关注。2012年2月22日，美海军陆战队两架直升机在亚利桑那州尤马县训练基地演习时相撞，事故造成七名海军陆战队员身亡[18]。2013年3月21日，德国两架警用直升机在柏林上空相撞坠毁，造成至少一名飞机驾驶员死亡，多人受伤[19]。类似的直升机相撞事故进一步表明，尽管直升机具备垂直起降、空中悬停等特殊性能，但假如操作不当，航线交叉的多架直升机依然有较大可能发生相撞，造成不可挽回的灾难。因此，“航线交叉”既是实际飞行中必须重视的安全因素，也是当前相关研究中不容忽视的重点问题。
1问题描述
1.1 基本概念
为便于问题描述及模型理解，先将相关概念解释如下。
通用航空器(generic aircraft)又称通用航空飞行器，它是指除用于军事、警务、海关缉私飞行和公共航空运输飞行以外的航空活动所使用的航空器[20]。本文所指的救援直升机属于通用航空器的范畴。
航路(air route)是由民航主管当局等机构批准建立的一条由导航系统划定空域构成的空中飞行通道[21]。
航线(airway)是航空器预定要飞行的路线，航空器在任何两个地点间确定的飞行线路就是航线[21]。
交叉点(intersection)是指两条(含)以上的航线相交的点[22]。
巡航高度层(cruising level)是指飞行器飞行的大部分时间所保持的高度层[22]。
1.2 航线交叉处理策略
一般而言，空间上的巡航高度层分离、时间上的起飞时间错开，都是解决航空器航线交叉的重要措施。因此，为保证航空器在航线交叉点处的飞行安全，可灵活采用空间调整或时间分配的方法[22]。而对于执行灾害救援的直升机而言，通过空间调整的方法保证交叉点处的飞行安全，存在以下局限和不足：一是直升机飞行空域受限，灾区多为山区，可供直升机调整的飞行空间十分有限，往往不允许直升机做大幅度的爬升动作；二是直升机操纵性受限，在高海拔地区执行救援任务时，随着飞行高度的增加，空气密度减小，直升机发动机的可用功率和旋翼的效率会降低，直升机的操纵性也会变差[23]。因此，在不影响救援任务的前提下，侧重研究了时间维度的优化，即为直升机合理分配起飞时间，而高度层和起飞时间同时优化将是后续研究的重要扩展方向。
1.3 问题假设
为便于研究，在不影响直升机起飞时序规划主要需求的前提下，进行如下假设：
1)采用直升机的平均飞行速度来计算其飞行用时。
2)所指的救援是指直升机安全到达降落点的单向飞行，并非是直升机的往返飞行，实际救援过程中运用本文的模型和算法时，可将直升机返航过程视为新的飞行任务。
3)研究的救援直升机均沿救援指挥部及空管部门规划的航路飞行。
2模型构建
2.1 符号定义
I表示起飞点集合，且i=1,2,…,I。
Ji表示从起飞点i起飞的第j架直升机，且j=1,2,…,J。
K表示救援目标区集合，且k=1,2,…,K。
Lk表示救援目标区k的第l个降落点，且l=1,2,…,L。
tij_fly：起飞点i的第j架直升机飞抵目标区的飞行用时。
tij_end：起飞点i的第j架直升机飞抵目标区的时刻。
ΔTi_take-off：起飞点i连续起飞两架直升机时的最短时间间隔。
ΔTi_safe：起飞点i连续起飞多架直升机时的安全时间范围。
tij×i′j′：起飞点i起飞的第j架直升机飞抵航线交叉点处的飞行用时，该交叉点由起飞点i起飞的第j架直升机的航线与起飞点i′起飞的第j′架直升机的航线相交产生。
ti′j′×ij：起飞点i′起飞的第j′架直升机飞抵航线交叉点的飞行用时，该交叉点由起飞点i′起飞的第j′架直升机的航线与起飞点i起飞的第j架直升机的航线相交产生。
ΔTij×i′j′_cross：起飞点i起飞的第j架直升机与起飞点i′起飞的第j′架直升机飞经航线交叉点的安全飞行交会时间差。
tij_start：起飞点i的第j架直升机的起飞时刻，且tij_end=tij_start+tij_fly。
2.2 数学模型
约束条件包括：
1)同一起飞点的两架直升机的起飞时刻间隔约束，即同一起飞点连续起飞两架直升机之间的时间间隔必须超过某一规定的安全间隔ΔTi_take-off，如式(1)所示。
tij+1_start-tij_start≥ΔTi_take-off
(1)
2)多架直升机从起飞点起飞的安全时间窗口约束，即同一起飞点的多架直升机必须在某一规定时间范围内起飞完毕，如式(2)所示。
tiJ_start-ti1_start≤ΔTi_safe
(2)
(3)
4)直升机到达每个降落点的时段约束，如某架次直升机必须在某一规定时间段内降落到目标区k，如式(4)所示。
(4)
5)两架直升机在飞行过程中，可能存在航线交叉的情况，为了飞行安全，两架直升机到达航线交叉点的时间之差不能小于某一规定的时间间隔ΔTij×i′j′_cross,如式(5)所示。
(5)
3算法设计
3.1 起飞时刻求解策略
若将起飞点和目标区抽象为有向图中的顶点，将起飞点与目标区的匹配关系看作有向图中的边，则救援任务集合就可以表示成有向图的形式。假设某救援任务有I个起飞点，每个起飞点有J架直升机，所有直升机需飞往K个救援目标区展开灾害救援，每个目标区有L个降落点，整个救援任务共设有C条飞行航线。因此，可将I个起飞点和K个救援目标区抽象成有向图G1的顶点集合V(G1)={v1,v2,…,vI+K}，将飞行航线抽象成有向图G1的边集合E(G1)={e1,e2,…,eC}。如前所述，航线的起飞时间受到众多约束条件的限制，各条航线的起飞时间相互制约相互影响，当确定了某条航线的起飞时间后，其他航线起飞时间的取值范围也可以逐步确定。
因此，本文设计了基于任务优先级的起飞时间求解策略：
首先，根据任务紧急程度选定第c条航线(其中c=1,2,…,C)作为优先级最高的任务最先起飞，则tc_start=0，且tc_end=0+tc_fly。
随后，依据航线网络，找出与第c条航线到达目标区相同的第c′条航线(其中c′=1,2,…,C)，受式(3)的约束，第c′条航线的到达时刻范围可以确定，再根据到达时刻和起飞时刻的关系式tij_end=tij_start+tij_fly，可求出第c′条航线的起飞时刻范围。
然后，根据式(1)和式(2)的约束，可以得到与第c′条航线起飞点相同航线的起飞时刻范围。反复运用航线间的起降点关系和约束条件，最终可以求出所有航线的起飞时刻。
在实际的救援任务中，还可能出现从某个任务开始求解，不能完全遍历所有任务的情况，即航线网络是一个非连通有向图，此时可选定所包含的子图分别在零时刻开始执行，再利用各子图所示的任务间的求解顺序逐步求解。
3.2 算法流程
步骤1：信息采集，数据预处理。通过地理信息系统快速计算直升机飞抵目标区的飞行用时。标注航线交叉点，构建航线交叉矩阵。
步骤2：按照起飞时刻的求解策略逐步求解各任务的起飞时刻。
步骤3：将航线交叉矩阵与步骤2计算所得数据一同进行约束判断，符合约束的解便构成了起飞时序的可行解集合。
步骤4：从可行解中选出各组解中最大值最小的那一组，即满足约束的所有飞行计划中最优的起飞时序。
算法流程如图1所示。
图1 算法流程图Fig.1 Algorithm flow chart
4仿真实验及结果分析
4.1 仿真算例设定
以云南鲁甸6.8级地震的灾害救援为背景。设有24架属同一型号的救援直升机被配置在昭通市的医院、救援物资仓库等12个起飞点，每个起飞点配置2架救援直升机，所有直升机需飞往震中的学校、堰塞湖等12个降落点展开救援，每个降落点有2架直升机先后降落，即共有24条飞行航线。设直升机的平均飞行速度为240km/h，由此便可得到各架直升机飞抵降落点的飞行用时。为保证基本的飞行安全及任务的尽快完成，做如下要求：
1)同一起飞点的2架直升机起飞时间间隔至少大于0.5min，且不多于20min；
2)同一降落点先后降落的2架直升机降落时间间隔至少大于5min，且不多于20min；
3)对于存在交叉的飞行航线，2架直升机先后飞经交叉点的时间间隔至少大于0.5min。
为便于分析与求解，将飞行航线抽象为有向图G2，图中顶点v1,v2,…,v12表示起飞点，顶点v13,v14,…,v24表示降落点，如图2所示。
图2 飞行航线有向图G2Fig.2 Flight line digraph G2
4.2 仿真实验分析
4.2.1仿真结果分析
经过仿真计算，共得到14组最优的起飞时序，结果列于表1中。
表1中第2栏的数字表示航线编号，如，数字“7”指代第7条航线，它具体代表航线
图3 第14组起飞时序散点图Fig.3 Scatter diagram of 14th take-off sequence
表1 最优起飞时序表
为验证上述结果是否满足航线交叉约束，可将各航线的出发时间与相应交叉点的时间属性相结合，计算出直升机在相应交叉点的交会时间差，检验结果以高低图(high-low chart)形式展示，如图4所示。
图4 航线交叉点的交会时间高低图Fig.4 High-low chart of meeting time
图4中的条形(bar)表示先后飞经某交叉点的两架直升机的飞行时间差，条形的低值(low)表示某架直升机先飞经该交叉点的时刻，高值(high)表示另一架直升机后飞经该交叉点的时刻。条形长度越长说明航线交叉的两架直升机经过交叉点的时间间隔越长；反之则说明两架直升机经过交叉点的时间间隔越短，即在交叉点发生相撞的可能性越大。因此，要验证某组起飞时序的安全性，只用检验长度最短的条形即可。由图4可知，第12号交叉点对应条形长度最短，该条形高、低值分别为22.17min和21.27min，两者差值0.9min大于规定的安全交会时间间隔0.5min，说明航线交叉的两架直升机在第12号交叉点处可安全通行，进而验证了整组起飞时序的安全性。
4.2.2进一步讨论
由图2可知，航线交叉点的分布极不均匀。有的航线和其他航线不存在任何交叉点，如航线
步骤1：包含所有航线交叉点约束时，计算得最优解(27.29min)，并统计可行解数量(1198组)。
步骤2：不包含任何航线交叉点约束时，计算得最优解(23.51min)，并统计可行解数量(2584组)。
步骤3：分别考虑各条航线与其他航线存在交叉时，计算最优解及可行解数量。
步骤4：将上述步骤得到的数据进行汇总处理。
步骤5：对步骤4得到的数据文件进行统计分析，统计描述结果如图5所示。
由图5(a)可知，当不包含航线交叉约束时，最后一架直升机的起飞时刻为第23.51min，而考虑了23个航线交叉点的约束后，最后一架直升机的起飞时刻推后到第27.29min。此外，随着交叉点数量的增加，最优解逐渐变大，特别是当单条航线与5条(含)以上航线存在交叉时，最优解变化趋势明显。由图5(b)可知，随着交叉点数量的增加，可行解数量总体呈逐渐递减趋势，当单条航线与5条(含)以上航线存在交叉时，可行解数量急剧减少。
综上，可以得到如下结论：在规划飞行航线时，应尽量避免航线交叉，当交叉难以避免时，应尽量将单条航线与其他航线的交叉次数控制在5次以内。
(a)交叉点约束与最优解的关系(a) The relationship between intersection constraint and optimal solution
(b) 交叉点约束与可行解数量的关系(b) The relationship between intersection constraint and the number of feasible solution图5 航线交叉约束对时序规划的影响Fig.5 Intersection constraint’s effects on scheduling
5结论
针对救援直升机起飞时序规划问题构建了数学模型，并结合问题的具体特点，设计了启发式算法进行问题求解，后以24架直升机参与地震救援为算例，对模型和算法进行了测试，并就航线交叉对于时序规划的影响进行了分析，实验结果显示，本文的模型和算法能得到满意的时序规划方案。
下一步，将从以下方面展开进一步研究：一是在航线交叉处理策略中，加入空间调整的方法；二是在问题求解过程中，将考虑无可行解时如何给出不同约束的调整策略。
参考文献(References)
[1]陈通. 救援直升机航迹规划研究[D]. 广汉：中国民用航空飞行学院， 2011.
CHEN Tong. Research on rescue helicopter route planning[D]. Guanghan: Civil Aviation Flight University of China, 2011. (in Chinese)
[2]Fiedrich F, Gehbauer F, Rickers U. Optimized resource allocation for emergency response after earthquake disasters[J]. Safety Science, 2000, 35(1/2/3): 41-57.
[3]Özdamar L, Ekinci E, Küçükyazici B. Emergency logistics planning in natural disasters[J]. Annals of Operations Research, 2004, 129(1): 217-245.
[4]何兵, 刘刚, 闫建静, 等. 基于Voronoi图和量子遗传算法的飞行器航迹规划方法[J]. 电光与控制, 2013, 20(1): 5-8.
HE Bing, LIU Gang, YAN Jianjing, et al. A UAV route planning method based on Voronoi diagram and quantum genetic algorithm [J]. Electronics Optics & Control, 2013, 20(1): 5-8. (in Chinese)
[5]Pettersson P O, Doherty P. Probabilistic roadmap based path planning for an autonomous unmanned helicopter[J]. Journal of Intelligent and Fuzzy Systems, 2006, 17(4) : 395-405.
[6]王志科, 朱凡, 彭建亮. 基于启发式A*算法的飞行器三维航路规划[J]. 电光与控制, 2009, 16(6):30-33,65.
WANG Zhike, ZHU Fan，PENG Jianliang. On 3-D path planning for air vehicle based on heuristic A*algorithm[J]. Electronics Optics & Control, 2009, 16(6): 30-33,65. (in Chinese)
[7]谢燕武, 王伟, 李爱军. 基于有向图的动态最优航迹规划算法[J]. 测控技术, 2006, 25 (10) :78-81.
XIE Yanwu, WANG Wei, LI Aijun.Dynamic programming algorithm based on directed graph for optimal flight trajectory planning [J]. Measurement & Control Technology, 2006, 25(10): 78-81. (in Chinese)
[8]Yi W, Özdamar L. A dynamic logistics coordination model for evacuation and support in disaster response activities[J]. European Journal of Operational Research, 2007, 179(3): 1177-1193.
[9]王强, 张安, 吴忠杰. 改进人工势场法与模拟退火算法的无人机航路规划[J]. 火力与指挥控制, 2014, 39(8): 70-73.
WANG Qiang, ZHANG An, WU Zhongjie.UCAV path planning based on improved artificial potential field and simulated annealing[J]. Fire Control & Command Control, 2014, 39(8): 70-73. (in Chinese)
[10]张岳平, 朱力超, 孙涛. 用Hopfield神经网络与模拟退火算法求解UAV航路规划问题[J]. 海军航空工程学院学报, 2007, 22(4): 451-453, 466.
ZHANG Yueping, ZHU Lichao, SUN Tao. UAV route planning using Hopfield neural network and simulated annealing[J]. Journal of Naval Aeronautical Engineering Institute, 2007, 22(4): 451-453, 466. (in Chinese)
[11]税薇, 葛艳, 韩玉, 等. 基于混合蚁群算法的无人机航路规划[J]. 系统仿真学报, 2011, 23(3): 574-576, 597.
SHUI Wei, GE Yan, HAN Yu, et al. Path planning for UAV based on mixed ant colony algorithm[J]. Journal of System Simulation, 2011, 23(3): 574-576, 597. (in Chinese)
[12]Balseiro S R, Loiseau I, Ramonet J. An ant colony algorithm hybridized with insertion heuristics for the time dependent vehicle routing problem with time windows[J]. Computers & Operations Research, 2011, 38(6): 954-966.
[13]Yi W, Kumar A. Ant colony optimization for disaster relief operations[J]. Transportation Research Part E: Logistics and Transportation Review, 2007, 43(6): 660-672.
[14]Shima T, Rasmussen S, Sparks A G, et al. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research, 2006, 33(11): 3252-3269.
[15]Özdamar L. Planning helicopter logistics in disaster relief[J]. Operational Research, 2011, 33(3): 655-672.
[17]祁明亮, 秦凯杰, 赵琰. 雪灾救援物资车辆-直升机联合运送的调度问题研究[J].中国管理科学, 2014, 22(3):59-67.
QI Mingliang, QIN Kaijie, ZHAO Yan. Research on problem of scheduling of helicopter coordinated with vehicle for resources distribution in snowstorm[J]. Chinese Journal of Management Science, 2014, 22(3): 59-67. (in Chinese)
[18]德永建.美海军陆战队两架直升机相撞七人身亡[EB/OL].(2012-02-24)[2014-12-12].http://www.chinanews.com/gj/2012-02-24/3694154.shtml.
DE Yongjian. The U.S. marine corps′ two helicopters collided and seven marines were killed[EB/OL].(2012-02-24)[2014-12-12]. http://www.chinanews.com/gj/2012-02-24/3694154.shtml. (in Chinese)
[19]杨彦宇.德国两架警用直升机相撞坠毁[EB/OL]. (2013-03-21)[2014-12-12].http://www.chinanews.com/tp/hd2011/2013/03-21/186470.shtml.
YANG Yanyu. Two German police helicopters crashed collided[EB/OL]. (2013-03-21)[2014-12-12]. http://www.chinanews.com/tp/hd2011/2013/03-21/186470.shtml. (in Chinese)
[20]耿建华, 王霞, 谢钧, 等. 通用航空概论[M]. 北京：航空工业出版社， 2007.
GENG Jianhua, WANG Xia, XIE Jun, et al. An introduction to general aviation[M]. Beijing: Aviation Industry Press， 2007. (in Chinese)
[21]江群， 王春. 民航基础知识应用[M]. 北京：国防工业出版社， 2011.
JIANG Qun，WANG Chun. Basics and application of civil aviation [M]. Beijing: National Defense Industry Press，2011. (in Chinese)
[22]朱金福. 航空运输规划[M]. 西安：西北工业大学出版社， 2008.
ZHU Jinfu. Planning of air transportation[M]. Xi’an: Northwestern Polytechnical University Press，2008. (in Chinese)
[23]廖瑛, 庄景钊, 梁加红. 直升机工作特性建模与飞行性能仿真[J]. 国防科技大学学报, 2004, 26(5):5-8.
LIAO Ying, ZHUANG Jingzhao, LIANG Jiahong. The modeling of the working characteristics and simulation of the flying performance of helicopters[J]. Journal of National University of Defense Technology, 2004, 26(5):5-8. (in Chinese)
http://journal.nudt.edu.cn
Schedule of rescue helicopter departure time considering airway intersection
ZHANGJiaming1,LIUZhong1,SHIJianmai1,HEYunyue1,WANGYishan2,CHENChao1
(1. College of Information System and Management, National University of Defense Technology, Changsha 410073, China;
2. The PLA Unit 63796, Xichang 615000, China)
Abstract：Aiming at minimizing the departure time of the last helicopter, a mathematical programming model for multiple helicopters in multiple airports was set up to solve the departure time scheduling problem of multiple helicopters. A heuristic algorithm based on task priority was designed to solve the model, a scheme to deal with the airway intersection was put forward and an algorithm to solve the departure time was also established. Basing on the disaster rescue of the 6.8 magnitude earthquake in Yunnan Ludian, a departure time scheduling case which includes 24 helicopters in 12 airports was designed to validate the model and algorithms. The influence of airway intersection and the treatment measures were deeply discussed. The results demonstrate the efficiency of the model and algorithms in dealing with the scheduling problem of multiple helicopters.
Key words：disaster rescue; rescue helicopter; mission scheduling; airway intersection
中图分类号：TP316
文献标志码：A
文章编号：1001-2486(2015)06-103-07
作者简介：张家铭(1982—)，男，云南曲靖人，博士研究生，E-mail：zjm08091018@163.com;刘忠(通信作者)，男，教授，博士，博士生导师，E-mail：phillipliu@263.net
基金项目：国家自然科学基金资助项目(71201169，70771109，71471174)
收稿日期：*2015-01-07
doi:10.11887/j.cn.201506020
