2. 航空工业航空所 飞行控制航空科技重点实验室, 西安 710065
2. Aviation Key Laboratory of Science and Technology on Aircraft Control, FACRI, Xi'an 710065, China
机场地面运动是影响场面运行安全和效率的重要环节。随着场面移动目标引导与控制技术的不断发展,机场地面运动开始由传统的人工操作模式向以四维轨迹为基础的新型操作模式转变[1-5]。四维轨迹明确了移动目标的地面运行路径和路点到达时间,提高了地面运动过程的可预测性,有利于实现场面操作的协同优化。近年来,针对航空器滑行规划问题的研究取得较大进展[6]。其中,基于混合整数规划的滑行轨迹分配方法从优化角度对滑行规划问题进行建模,能够处理复杂的约束条件和目标函数,显著提高运行效率[7-11]。尽管如此,在实际场面运行过程中仍然可能出现操作失误、设备故障、非合作目标侵入等多种干扰事件,使得移动目标无法按照计划轨迹运行。为确保干扰事件出现后地面运动能够及时恢复安全有序状态,还需要进一步构建有效的扰动恢复机制,针对干扰情况对受影响的计划轨迹进行动态调整[12]。
扰动恢复与场面监视及滑行规划系统之间有着密切联系[1]。当地面运动过程出现干扰事件时,扰动恢复应根据监视系统提供的扰动信息和航空器运行状态信息,以及滑行规划系统提供的航空器初始计划轨迹,对受影响航空器的计划轨迹进行优化调整,使场面交通恢复安全有序状态[13-14]。同时,扰动恢复还应尽量减少计划路径的变化以及目标位置到达时间与计划时间的偏差,以降低扰动对跑道调度和停机位操作的影响[15]。
根据不同成因,机场地面运动的干扰事件可分为2类:一类起因于航空器自身的计划执行偏差,例如实际的路点到达时间与计划不符、运动轨迹偏离计划路径等;另一类起因于外部事件,例如滑行道关闭、非合作目标侵入、设备故障等,通常导致部分滑行道区域在一段时间内不可用。文献[16]针对不同干扰事件对地面运动的影响程度进行了仿真研究。实验结果表明,滑行道临时关闭和机场配置变化对地面运动的影响最为显著。但该研究没有探讨航空器偏离计划轨迹的情况;仿真实验中也未完全规避滑行冲突[17]。文献[18-20]对航空器出现延误(即未按时到达指定位置)时的计划轨迹调整问题进行了研究。文献[18, 20]提出利用计划步骤优先次序图调整未出现延误的航空器在受影响区域的访问优先级。这种局部优先级调整策略能够确保无冲突场面运行,但会对场面运行效率造成不利影响[18]。文献[19]提出一种基于计划步骤优先次序图的延误传播算法,在某架航空器出现延误后调整其他航空器在受影响区域的到达时间。该方法能够确保无冲突场面运行,但轨迹调整过程中缺少对运行效率的优化;调整后的运行轨迹会出现较大的总体延误。
综上所述,现有扰动恢复研究仅针对航空器延误问题提出了局部调整方案,未考虑轨迹调整过程对整体运行效率的影响。为进一步实现对滑行道关闭、路径偏离等其他干扰事件的有效处理,本文根据现有滑行轨迹优化分配模型提出一种基于混合整数规划的扰动恢复方法。针对外部扰动造成的滑行道关闭问题,构建区域可用性约束,使航空器避开扰动影响范围。针对航空器偏离计划路径问题,根据航空器实际位置对计划轨迹进行调整,构建冲突规避约束,确保场面运行安全。与现有局部调整策略不同,本文方法从优化角度对扰动恢复问题进行建模和求解,充分利用混合整数规划方法的复杂约束建模和指标优化能力,统一处理受扰动影响的航空器,实现最优计划轨迹调整;并通过在目标函数中引入对轨迹变化的惩罚,降低扰动对其他场面操作的影响。
1 问题描述为确保运行安全,分区域控制滑行道的使用,每个区域在任意时刻只允许一架航空器占用[9]。如图 1所示,每个交叉口将作为一个单独区域;较长的路段将被进一步分割为若干单元区域,以提高滑行道使用效率。航空器的滑行路径通常贯穿多个区域。航空器到达各区域边界与运行路径交点的时间称为路点到达时间。
在着陆或推出后,航空器将按照已分配的计划轨迹开始滑行。计划轨迹明确了航空器从起始位置到目标位置的滑行路径以及各路点的期望到达时间。扰动恢复应确保调整后的航空器计划轨迹符合滑行道的物理布局,航空器在各区域的通行时间与实际滑行速度相符,不同航空器的计划轨迹之间不会出现冲突。同时,扰动恢复过程中还应解决以下问题:
1) 根据每架航空器a的当前位置,预测其到达下一路点i的时间范围[AaS, AaE]。在新的计划轨迹中,航空器a在路点i的到达时间ti应当满足AaS≤ti≤AaE。为规避冲突,其他航空器在路点i的到达时间均应大于ti。
2) 当出现滑行道临时关闭的情况时,航空器a应当在滑行道重新开放后使用相关区域。记区域p重新开放时间为TpR,则航空器a在区域p任意路点j的到达时间tj应满足tj≥TpR。
3) 在轨迹调整过程中,航空器a对任一滑行道区域p的占用不能与其他航空器在该区域的预留时间窗发生冲突。例如,若航空器b在区域p的预留时间窗为[Wb, pS, Wb, pE],则航空器a应当在Wb, pE之后进入区域p,或在Wb, pS之前离开区域p。
4) 当有多种轨迹调整方案满足上述约束条件时,扰动恢复应当在计算时间允许的范围内选出总体运行效率最高且对其他场面操作影响最小的轨迹调整方案。
2 混合整数规划模型 2.1 决策变量扰动恢复的决策变量主要包括路由相关变量和时间相关变量2部分。根据文献[8-9]的混合整数建模方法,将航空器滑行轨迹描述为若干连续滑行步骤。在滑行步骤k中,航空器在区域p中从路点i向路点j运动,并经由路点j进入下一区域。定义0-1变量r和n分别表示航空器在每个滑行步骤的区域和路点路由方式:ra, p, q, k=1表明航空器a在滑行步骤k的所在区域为p,并将通过区域p进入下一区域q;na, i, j, k=1表明航空器a在滑行步骤k的运行路线为路点i到路点j。为确保计划轨迹有效,变量r、n的取值应分别与区域、路点的物理连通性相符。区域p、q的连通性由参数Cp, qR描述:若区域p、q邻接,则Cp, qR=1,否则Cp, qR=0。类似地,路点i、j的连通关系由参数Ci, jN描述:若路点i与路点j连通,则Ci, jN=1,否则Ci, jN=0。
定义变量ta, k为航空器a完成滑行步骤k的时间。假设航空器a在滑行步骤k从路点i向路点j运动,则航空器到达路点i的时间与到达路点j的时间之差为ta, k-ta, k-1。为确保计划轨迹的可行性,ta, k-ta, k-1应满足由最大和最小滑行速度决定的通行时间下限τi, jL和上限τi, jU约束。
2.2 目标函数机场地面运动扰动恢复的主要目标为减少干扰事件对场面运行效率及其他相关场面操作的影响。为此,定义目标函数为
(1) |
式中:ta, Ka、ya与ra, p, q, k为待定变量,其余参数均为已知量。w1、w2和w3分别为滑行时间、目标位置到达时间变化量和路径变化量的权重;参数Ka为航空器a的滑行步骤总数;T0为扰动恢复的开始时间;
式(1)通过最小化航空器的滑行时间,确保轨迹调整后仍有较高的场面运行效率;通过最小化目标位置到达时间及滑行路径变化量,降低干扰事件对跑道、停机位相关操作的影响。
辅助变量y用于线性化目标位置到达时间变化量,满足以下条件:
(2) |
(3) |
式中:参数
根据第1节的分析与第2.1节的决策变量定义,区域路由变量r应满足以下约束:
(4) |
(5) |
(6) |
(7) |
式(4)表示每架航空器在每个滑行步骤中有且仅有一个区域路由变量取非零值,即航空器不能同时出现在2个不同位置。式(5)表示区域路由变量取值与区域连通性相符,以确保航空器不会按实际中并不存在的路径运行。式(6)表示区域路由变量取值具有连续性,以避免出现航空器位置跳变的情况。式(7)表示航空器不能在到达区域终点后直接折返。
与区域路由变量类似,路点路由变量n应满足以下约束:
(8) |
(9) |
(10) |
为关联区域路由变量r与路点路由变量n,定义辅助变量η描述航空器在每个滑行步骤的目标路点。变量r、n与η满足以下关系:
(11) |
(12) |
(13) |
式中:Vp, q为位于区域p、q公共边界上的路点。
变量t与变量n、r应满足以下关系:
(14) |
(15) |
(16) |
(17) |
式(14)表示航空器a在滑行步骤k的滑行时间满足路点间的通行时间要求。式(15)表示航空器进入任意区域的时间应大于该区域在扰动后重新开放的时间。式(16)和式(17)中定义0-1辅助变量x构建预留时间窗约束:xa, b, q=1表示航空器a先于航空器b经过区域q;xa, b, q=0时表示航空器b先于航空器a经过区域q。M为足够大的正常数。若航空器b在区域q有预留时间窗[Wb, qS, Wb, qE],式(16)和式(17)利用大M方法确保了航空器a不会在预留时间窗内占用区域q。δ为一个较小的正常数,用于避免两架航空器沿相反方向同时经过同一路点(同时资源交换)[9]。
为规避滑行冲突,定义0-1辅助变量f:fa, b, p, k, l=1表示航空器a、b分别在滑行步骤k、l占用区域p,且航空器a先于航空器b占用区域p。容易验证,为实现冲突规避,变量f与变量t、r之间应满足以下关系:
(18) |
(19) |
(20) |
(21) |
此外,扰动恢复还应满足以下边界条件:
(22) |
(23) |
(24) |
(25) |
(26) |
式中:NaH为扰动恢复时航空器a即将到达的下一路点。式(22)表示航空器a在第一个滑行步骤结束时应到达的路点NaH。式(23)表示航空器a应在期望的时间范围[AaS, AaE]内到达路点NaH,完成第一个滑行步骤。式(24)表示航空器a能够到达目标区域DaR。式(25)表示若航空器a在滑行步骤k由某区域向目标区域DaR运行,则在滑行步骤k结束时应当到达目标节点DaN。式(26)表示航空器a在到达目标区域后不再向其他区域运动。
2.4 求解方法式(1)~式(26)描述的混合整数规划模型可直接利用CPLEX等通用求解器求解。但由于模型变量较多、约束较为复杂,通用求解器有时无法在有限的计算时间内得到可行解[12]。为此,可利用迭代冲突规避策略[8, 21]减少变量和约束数量、提高求解效率。本文采用以下迭代冲突规避求解策略:
步骤1 不考虑航空器之间的冲突,式(1)~式(26)描述的模型可按航空器分解,分别确定每架航空器的最优滑行轨迹。
步骤2 检查所得轨迹是否存在冲突。若存在冲突,则引入对应的变量和约束,转到步骤3;否则,转到步骤4。
步骤3 对更新后的模型进行求解,得到一组新的计划轨迹,转到步骤2。
步骤4 输出当前结果,求解结束。
在步骤2中,若航空器a、b分别在各自的滑行步骤k、l占用区域p,且二者在区域p的占用时间窗存在冲突,则在模型中引入变量fa, b, p, k, l与fb, a, p, l, k,同时引入与变量fa, b, p, k, l、fb, a, p, l, k相关的约束。
以上基于迭代冲突规避策略的求解方法仅在扰动恢复模型中引入必要的冲突规避变量和约束,大大降低了问题的复杂度。所有简化问题的求解时间之和一般远小于原问题的求解时间。
3 算例分析针对路径偏离和滑行道关闭2种情况,通过仿真实验算例对本文扰动恢复方法的有效性进行了验证。场面运行环境基于南京禄口机场布局构建,实验平台为配备i7处理器和8 GB内存的个人计算机。利用MATLAB完成输入输出数据处理,基于AMPL实现混合整数规划建模,利用CPLEX 12.7.1对混合整数规划模型进行求解。目标函数式(1)中的权重系数取w1=1,w2=50,w3=20。
算例1 路径偏离
在该算例中,初始阶段有2架航空器a、b同时在场面滑行,计划路径如图 2(a)所示。某时刻,系统检测到航空器a未能在区域41按计划路径转向进入区域42,而将进入区域9,如图 2(b)所示。与此同时,航空器b正沿另一路径向区域9运行。
为避免航空器a、b发生冲突,在检测到航空器a偏离计划路径后,系统立即对航空器a、b的计划轨迹进行调整。利用本文扰动恢复方法得到如图 2(c)和图 2(d)所示结果。其中,航空器a在进入区域9后转向进入区域8,沿新路径运动到达目标位置。为避免与航空器a发生对头冲突,航空器b在区域8转向并进入区域42,再经过区域41进入区域9,重新回到初始的计划路径。本算例的求解时间约为0.4 s。
算例2 滑行道关闭
在该算例中,某时刻滑行道区域11需临时关闭5 min。此时,有7架航空器a1~a7正在滑行或即将开始按计划轨迹滑行。图 3(a)展示了航空器a1~a7初始计划轨迹在各区域的占用时间窗,以及区域11将要关闭的时间段。若按初始计划轨迹滑行,航空器a3、a5、a2将会在区域11关闭期间依次经过该区域。因此,必须对航空器a3、a5、a2的计划轨迹进行调整。由于航空器a3、a5、a2与另外4架航空器的计划轨迹之间存在相互影响,扰动恢复时将对所有7架航空器的计划轨迹进行调整。轨迹调整后,航空器a1~a7在各区域的占用时间窗如图 3(b)所示,均避开了扰动影响范围。
图 4(a)~(c)进一步对比了轨迹调整前后航空器a3、a5、a2的区域占用时间窗。由此可以看到航空器a3、a5、a2的计划轨迹变化情况(滑行道区域布局见图 2):在新的计划轨迹中,航空器从区域12进入区域10,绕过了区域11,然后经过区域8进入区域9,回到初始计划路径;航空器在区域12等待一段时间后进入区域10,然后经过区域8、9进入区域6,回到初始计划路径;航空器为了绕过区域11,从区域41进入区域9,然后经过区域8、10、13、14进入区域16,回到初始计划路径。
另外,扰动恢复过程未改变另外4架航空器的计划路径,仅对部分航空器的路点到达时间进行了适当调整,如图 4(d)~(g)所示。其中,航空器a1的计划轨迹未发生变化,航空器a4和a6在部分区域的占用时间窗出现一定程度的变化,航空器a7的计划轨迹变化也较小。
轨迹调整后,航空器的目标位置到达时间变化情况如表 1所示。除航空器a2、a4、a7的目标位置到达时间略有增加外,其余航空器的目标位置到达时间均与初始值相同,从而有效降低了扰动对跑道、停机位等其他场面操作的影响。
s | |||
航空器 | 初始值 | 调整后 | 变化量 |
a1 | 382 | 382 | 0 |
a2 | 369 | 388 | 19 |
a3 | 482 | 482 | 0 |
a4 | 395 | 403 | 8 |
a5 | 582 | 582 | 0 |
a6 | 501 | 501 | 0 |
a7 | 779 | 782 | 3 |
由于本算例中航空器数量较多,直接利用求解器求解所需计算时间为139.8 s。应用迭代冲突规避策略后,计算时间下降至26.5 s。为进一步提高求解效率,可分组对航空器进行调整,并通过在混合整数规划模型中增加相应的预留时间窗约束,避免不同组航空器的计划轨迹发生冲突。不同的分组方式和分组大小均会对计算结果产生影响。实验发现,按跑道占用优先次序对航空器进行分组能够有效减少计算时间,同时对求解质量影响也较小。本算例中,航空器的跑道占用优先次序为a2>a4>a6>a1>a3>a5>a7。将航空器分为{a2, a4, a6, a1}和{a3, a5, a7}2组进行轨迹调整,能够在不影响求解质量的情况下将计算时间减少至4.9 s。
4 结论本文针对机场地面运动扰动恢复问题提出一种基于混合整数规划的轨迹调整方法。
1) 本文方法能够有效处理复杂的约束条件和目标函数,实现对计划轨迹的优化调整。
2) 本文方法保证了轨迹可行性和运行效率,并通过最小化目标位置到达时间和路径变化量,降低了轨迹调整对其他场面操作的影响。
3) 实验结果表明,本文方法能够在航空器偏离计划路径和滑行道临时关闭等干扰事件出现后,实现快速、有效的扰动恢复。
[1] |
OKUNIEK J N, GERDES I, JAKOBI J, et al.A concept of operations for trajectory-based taxi operations[C]//16th AIAA Aviation Technology, Integration, and Operations Conference.Reston: AIAA, 2016: 3753. http://www.researchgate.net/publication/303902508_A_Concept_of_Operations_for_Trajectory-based_Taxi_Operations
|
[2] |
BAKOWSKI D L, HOOEY B L, FOYLE D C, et al.NextGen surface trajectory-based operations: Contingency-hold clearances[C]//IEEE/AIAA 32nd Digital Avionics Systems Conference (DASC).Piscataway, NJ: IEEE Press, 2013: 1B6-1-1B6-11. http://www.researchgate.net/publication/261266244_NextGen_surface_trajectory-based_operations_Contingency-hold_clearances
|
[3] |
CARSTENGERDES N, SCHAPER M, SCHIER S, et al.Controller support for time-based surface management-first results from a feasibility workshop[C]//Proceedings of the 3rd SESAR Innovation Days.Stockholm: KTH Royal Institute of Technology, 2013: 1-8.
|
[4] |
HOOEY B L, CHENG V H, FOYLE D C.A concept of operations for far-term surface trajectory-based operations (STBO): NASA/TM-2014-218354[R].Hanover: NASA Center for Aerospace Information, 2014: 1-51.
|
[5] |
FOYLE D C, HOOEY B L, BAKOWSKI D L, et al. Flight-deck surface trajectory-based operations[J]. The International Journal of Aviation Psychology, 2015, 25(2): 77-96. DOI:10.1080/10508414.2015.1097090 |
[6] |
ATKIN J A, BURKE E K, RAVIZZA S.The airport ground movement problem: Past and current research and future directions[C]//Proceedings of the 4th International Conference on Research in Air Transportation (ICRAT).Budapest: Budapest University of Technology and Economics, 2010: 131-138.
|
[7] |
MARÍN G. Airport management:Taxi planning[J]. Annuals of Operations Research, 2006, 143(1): 191-202. DOI:10.1007/s10479-006-7381-2 |
[8] |
CLARE G L, RICHARDS A G. Optimization of taxiway routing and runway scheduling[J]. IEEE Transactions on Intelligent Transportation Systems, 2011, 12(4): 1000-1013. DOI:10.1109/TITS.2011.2131650 |
[9] |
张天慈, 丁萌, 左洪福, 等. 基于区域控制的航空器滑行轨迹优化模型[J]. 系统工程与电子技术, 2016, 38(1): 136-141. ZHANG T C, DING M, ZUO H F, et al. Zone control based aircraft ground movement trajectory optimization model[J]. System Engineering and Electronics, 2016, 38(1): 136-141. (in Chinese) |
[10] |
GARCÍA J, BERLANGA A, MOLINA J M, et al. Methods for operations planning in airport decision support systems[J]. Applied Intelligence, 2005, 22(3): 183-206. DOI:10.1007/s10791-005-6618-z |
[11] |
PESIC B, DURAND N, ALLIOT J-M.Aircraft ground traffic optimisation using a genetic algorithm[C]//Proceedings of the 3rd Annual Conference on Genetic and Evolutionary Computation. San Francisco: Morgan Kaufmann, 2001: 1397-1404. http://dl.acm.org/citation.cfm?id=2955476
|
[12] |
ICAO.Advanced surface movement guidance and control systems (A-SMGCS) manual: Doc 9830 AN/452[R].Montreal: International Civil Aviation Organization, 2004: 1-83.
|
[13] |
CHENG V, VADDI V, SWERIDUK G, et al.Surface conflict detection and resolution with emphasis on trajectory-based operations: NRA NNA10DE59C[R].Moffett Field: NASA AMES Research Center, 2011.
|
[14] |
VADDI S, SWERIDUK G, KWAN J, et al.Concept and requirements for airport surface conflict detection and resolution[C]//11th AIAA Aviation Technology, Integration, and Operations (ATIO) Conference.Reston: AIAA, 2011: 7050. http://arc.aiaa.org/doi/pdf/10.2514/6.2011-7050
|
[15] |
RAVIZZA S, ATKIN J A, BURKE E K. A more realistic approach for airport ground movement optimisation with stand holding[J]. Journal of Scheduling, 2014, 17(5): 507-520. DOI:10.1007/s10951-013-0323-3 |
[16] |
RAFAL K, MOEIN G, JIT-TAT C, et al.Co-evolutionary approach to improve robustness of routing algorithms against disruptive events on the airport surface[C]//AIAA Guidance, Navigation, and Control Conference.Reston: AIAA, 2014: 1466. http://www.researchgate.net/publication/269249412_Co-evolutionary_Approach_to_Improve_Robustness_of_Routing_Algorithms_against_Disruptive_Events_on_the_Airport_Surface
|
[17] |
TANG X, AN H, WANG C. Conflict-avoidance-oriented airport surface-taxiing guidance lights system model[J]. Journal of Guidance, Control, and Dynamics, 2012, 35(2): 674-681. DOI:10.2514/1.54693 |
[18] |
TER MORS A, WITTEVEEN C.Plan repair in conflict-free routing[C]//International Conference on Industrial, Engineering and Other Applications of Applied Intelligent Systems.Berlin: Springer, 2009: 46-55. http://www.springerlink.com/content/3707836340276378
|
[19] |
TER MORS A W.Conflict-free route planning in dynamic environments[C]//2011 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).Piscataway, NJ: IEEE Press, 2011: 2166-2171. http://www.researchgate.net/publication/221063712_Conflict-free_route_planning_in_dynamic_environments
|
[20] |
唐勇, 胡明华, 黄荣顺, 等. A-SMGCS航空器场面滑行路由实时调整策略[J]. 西南交通大学学报, 2014, 49(4): 734-740. TANG Y, HU M H, HUANG R S, et al. Real-time adjustment strategy of aircraft taxiing routes for A-SMGCS[J]. Journal of Southwest Jiaotong University, 2014, 49(4): 734-740. DOI:10.3969/j.issn.0258-2724.2014.04.027 (in Chinese) |
[21] |
EARL M G, D'ANDREA R. Iterative MILP methods for vehicle-control problems[J]. IEEE Transactions on Robotics, 2005, 21(6): 1158-1167. DOI:10.1109/TRO.2005.853499 |