基于混合整数规划的机场地面运动扰动恢复

张天慈， 丁萌，*， 左洪福

(1. 南京航空航天大学民航学院, 南京 211106； 2. 航空工业航空所飞行控制航空科技重点实验室， 西安 710065)

机场地面运动是影响场面运行安全和效率的重要环节。随着场面移动目标引导与控制技术的不断发展，机场地面运动开始由传统的人工操作模式向以四维轨迹为基础的新型操作模式转变[1-5]。四维轨迹明确了移动目标的地面运行路径和路点到达时间，提高了地面运动过程的可预测性，有利于实现场面操作的协同优化。近年来，针对航空器滑行规划问题的研究取得较大进展[6]。其中，基于混合整数规划的滑行轨迹分配方法从优化角度对滑行规划问题进行建模，能够处理复杂的约束条件和目标函数，显著提高运行效率[7-11]。尽管如此，在实际场面运行过程中仍然可能出现操作失误、设备故障、非合作目标侵入等多种干扰事件，使得移动目标无法按照计划轨迹运行。为确保干扰事件出现后地面运动能够及时恢复安全有序状态，还需要进一步构建有效的扰动恢复机制，针对干扰情况对受影响的计划轨迹进行动态调整[12]。

扰动恢复与场面监视及滑行规划系统之间有着密切联系[1]。当地面运动过程出现干扰事件时，扰动恢复应根据监视系统提供的扰动信息和航空器运行状态信息，以及滑行规划系统提供的航空器初始计划轨迹，对受影响航空器的计划轨迹进行优化调整，使场面交通恢复安全有序状态[13-14]。同时，扰动恢复还应尽量减少计划路径的变化以及目标位置到达时间与计划时间的偏差，以降低扰动对跑道调度和停机位操作的影响[15]。

根据不同成因，机场地面运动的干扰事件可分为2类：一类起因于航空器自身的计划执行偏差，例如实际的路点到达时间与计划不符、运动轨迹偏离计划路径等；另一类起因于外部事件，例如滑行道关闭、非合作目标侵入、设备故障等，通常导致部分滑行道区域在一段时间内不可用。文献[16]针对不同干扰事件对地面运动的影响程度进行了仿真研究。实验结果表明，滑行道临时关闭和机场配置变化对地面运动的影响最为显著。但该研究没有探讨航空器偏离计划轨迹的情况；仿真实验中也未完全规避滑行冲突[17]。文献[18-20]对航空器出现延误(即未按时到达指定位置)时的计划轨迹调整问题进行了研究。文献[18,20]提出利用计划步骤优先次序图调整未出现延误的航空器在受影响区域的访问优先级。这种局部优先级调整策略能够确保无冲突场面运行，但会对场面运行效率造成不利影响[18]。文献[19]提出一种基于计划步骤优先次序图的延误传播算法，在某架航空器出现延误后调整其他航空器在受影响区域的到达时间。该方法能够确保无冲突场面运行，但轨迹调整过程中缺少对运行效率的优化；调整后的运行轨迹会出现较大的总体延误。

综上所述，现有扰动恢复研究仅针对航空器延误问题提出了局部调整方案，未考虑轨迹调整过程对整体运行效率的影响。为进一步实现对滑行道关闭、路径偏离等其他干扰事件的有效处理，本文根据现有滑行轨迹优化分配模型提出一种基于混合整数规划的扰动恢复方法。针对外部扰动造成的滑行道关闭问题，构建区域可用性约束，使航空器避开扰动影响范围。针对航空器偏离计划路径问题，根据航空器实际位置对计划轨迹进行调整，构建冲突规避约束，确保场面运行安全。与现有局部调整策略不同，本文方法从优化角度对扰动恢复问题进行建模和求解，充分利用混合整数规划方法的复杂约束建模和指标优化能力，统一处理受扰动影响的航空器，实现最优计划轨迹调整；并通过在目标函数中引入对轨迹变化的惩罚，降低扰动对其他场面操作的影响。

1 问题描述

为确保运行安全，分区域控制滑行道的使用，每个区域在任意时刻只允许一架航空器占用[9]。如图1所示，每个交叉口将作为一个单独区域；较长的路段将被进一步分割为若干单元区域，以提高滑行道使用效率。航空器的滑行路径通常贯穿多个区域。航空器到达各区域边界与运行路径交点的时间称为路点到达时间。

在着陆或推出后，航空器将按照已分配的计划轨迹开始滑行。计划轨迹明确了航空器从起始位置到目标位置的滑行路径以及各路点的期望到达时间。扰动恢复应确保调整后的航空器计划轨迹符合滑行道的物理布局，航空器在各区域的通行时间与实际滑行速度相符，不同航空器的计划轨迹之间不会出现冲突。同时，扰动恢复过程中还应解决以下问题：

图1 滑行道受控区域、路点与滑行路径示意图Fig.1 Schematic of taxiway controlled zones, waypoints and taxiing route

4) 当有多种轨迹调整方案满足上述约束条件时，扰动恢复应当在计算时间允许的范围内选出总体运行效率最高且对其他场面操作影响最小的轨迹调整方案。

2 混合整数规划模型

2.1 决策变量

2.2 目标函数

机场地面运动扰动恢复的主要目标为减少干扰事件对场面运行效率及其他相关场面操作的影响。为此，定义目标函数为

(1)

式(1)通过最小化航空器的滑行时间，确保轨迹调整后仍有较高的场面运行效率；通过最小化目标位置到达时间及滑行路径变化量，降低干扰事件对跑道、停机位相关操作的影响。

辅助变量y用于线性化目标位置到达时间变化量，满足以下条件：

(2)

(3)

2.3 约束条件

根据第1节的分析与第2.1节的决策变量定义，区域路由变量r应满足以下约束：

(4)

(5)

(6)

ra,p,q,k+ra,q,p,k+1≤1 ∀a,k,p,q

(7)

式(4)表示每架航空器在每个滑行步骤中有且仅有一个区域路由变量取非零值，即航空器不能同时出现在2个不同位置。式(5)表示区域路由变量取值与区域连通性相符，以确保航空器不会按实际中并不存在的路径运行。式(6)表示区域路由变量取值具有连续性，以避免出现航空器位置跳变的情况。式(7)表示航空器不能在到达区域终点后直接折返。

与区域路由变量类似，路点路由变量n应满足以下约束：

(8)

(9)

(10)

为关联区域路由变量r与路点路由变量n，定义辅助变量η描述航空器在每个滑行步骤的目标路点。变量r、n与η满足以下关系：

ra,p,q,k=1⟹ηa,k=Vp,q∀a,p,q,k

(11)

na,i,j,k=1⟹ηa,k=j∀a,i,j,k

(12)

na,i,j,k=1⟹ηa,k-1=i∀a,i,j,k

(13)

式中：Vp,q为位于区域p、q公共边界上的路点。

(14)

(15)

∀a,b,p,q,k

(16)

M(1-xa,b,q) ∀a,b,p,q,k

(17)

为规避滑行冲突，定义0-1辅助变量f：fa,b,p,k,l=1表示航空器a、b分别在滑行步骤k、l占用区域p，且航空器a先于航空器b占用区域p。容易验证，为实现冲突规避，变量f与变量t、r之间应满足以下关系：

fa,b,p,k,l=1⟹tb,l-1≥ta,k+δ∀a,b,p,k,l

1) 四季竹和少穗竹2种竹笋的含水量均超过90%，表明2种竹笋的口感均较好；四季竹笋的灰分和粗脂肪含量均高于少穗竹，但蛋白质含量低于少穗竹。

(18)

(19)

(20)

fb,a,p,l,k)≤1 ∀a,b,p,k,l

(21)

此外，扰动恢复还应满足以下边界条件：

(22)

(23)

(24)

(25)

(26)

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)所示，均避开了扰动影响范围。

图2 路径偏离扰动恢复结果Fig.2 Disruption recovery result for route deviation

图3 初始与调整后轨迹的区域占用时间窗Fig.3 Zone occupancy time windows for original and recovered trajectories

图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的目标位置到达时间略有增加外，其余航空器的目标位置到达时间均与初始值相同，从而有效降低了扰动对跑道、停机位等其他场面操作的影响。

图4 扰动恢复前后各航空器的区域占用时间窗对比Fig.4 Comparison of zone occupancy time windows for individual aircraft before and after disruption recovery

由于本算例中航空器数量较多，直接利用求解器求解所需计算时间为139.8 s。应用迭代冲突规避策略后，计算时间下降至26.5 s。为进一步提高求解效率，可分组对航空器进行调整，并通过在混合整数规划模型中增加相应的预留时间窗约束，避免不同组航空器的计划轨迹发生冲突。不同的分组方式和分组大小均会对计算结果产生影响。实验发现，按跑道占用优先次序对航空器进行分组能够有效减少计算时间，同时对求解质量影响也较小。本算例中，航空器的跑道占用优先次序为a2>a4>a6>a1>a3>a5>a7。将航空器分为{a2,a4,a6,a1}和{a3,a5,a7}2组进行轨迹调整，能够在不影响求解质量的情况下将计算时间减少至4.9 s。

表1 航空器目标位置到达时间变化Table 1 Change of aircraft destination arrival time s

4 结 论

本文针对机场地面运动扰动恢复问题提出一种基于混合整数规划的轨迹调整方法。

1) 本文方法能够有效处理复杂的约束条件和目标函数，实现对计划轨迹的优化调整。

2) 本文方法保证了轨迹可行性和运行效率，并通过最小化目标位置到达时间和路径变化量，降低了轨迹调整对其他场面操作的影响。

3) 实验结果表明，本文方法能够在航空器偏离计划路径和滑行道临时关闭等干扰事件出现后，实现快速、有效的扰动恢复。