基于“两步法”的飞行冲突解脱问题求解策略①

温 乾 陈伟锋

(浙江工业大学信息工程学院 杭州 310023)

0 引 言

随着全球航空业的快速发展，空域资源紧缺与空中交通拥堵的现象日益严重。为应对交通流量的持续增长、提高航空飞行安全水平、减少航班延误等问题，空中交通管理(air traffic management,ATM)系统性能亟待提升。为了提高空中交通的安全管理和运行效率，一系列空中管制自动化方法与智能化优化方法成为空中交通管理领域的研究重点[1]，其中之一就是飞行器冲突检测和解决[2](collision detection and resolution, CDR)。

关于CDR问题的数学优化方法，Kuchar和Yang[3]以及Campo和Javier[4]对冲突检测方法、冲突解脱方法以及冲突的管理等问题都进行了阐述。冲突解脱方法有基于Meng和Qi[5]提出的进化算法和Gao等人[6]提出的遗传算法等元启发式方法，以及数学模型、动态规划方面的方法。其中，Pallottino等人[7]建立了2维平面空间中的飞行冲突解脱模型，使用混合整数规划方法求解，存在求解时间长、部分问题无法求解的情况。Christodoulou等人[8]建立了3维空域下的飞行冲突解脱模型，使用混合整数非线性规划方法，求解时间较长，冲突解脱效率较低。Alonso-Ayuso等人[9]提出了一种基于改变飞行速度和飞行高度的混合整数线性规划模型，此模型只适合部分冲突问题，部分冲突情况无法使用此方法解决，例如“头对头”冲突等。Alonso-Ayuso等人[10]提出混合整数非线性规划模型，建立速度随时间变化的模型，非线性模型复杂度高，规模大，求解较慢，并且针对此模型当时最先进的混合整数非线性规划求解器还无法解决这类大规模问题，降低了求解效率，增加了求解难度。Omer等人[11]提出了连续时间变量离散化的思想，提出了一种混合求解算法，使用混合整数线性规划方法求解出的较好可行解作为非线性模型的初值，不足之处是使用此混合求解算法求解时间较长，求解成本较高。Alonso-Ayuso等人[12]提出了通过改变飞行速度和飞行高度的优化模型，并且将飞行高度范围增加到多个水平高度，使用混合整数线性规划方法能够很好地解决，不足之处是当飞行器数量变多时，求解成本较高。Alonso-Ayuso等人[13]是在3维空间下，通过改变航向角、速度和飞行高度来实现冲突解脱，提出了多目标折中的混合整数非线性规划方法，使得在不同的环境下改变不同的目标成本来使冲突解脱结果最优。Alonso-Ayuso等人[14]提出了角度范围离散化，将非线性问题转换成混合整数线性规划问题，与混合整数非线性规划方法相比，混合整数线性规划方法求解速度快、效率高。Cafieri等人[15]提出两步求解方法，使用混合整数非线性规划方法对此问题进行分步求解，在冲突架数较少的时候效果明显。Mihaela等人[16]将近年来ATM飞行冲突模型进行评估，建立统一的数学框架进行冲突解脱求解和碰撞概率估计，促进了对未来ATM数学模型能力设计评估的深入了解。

本文提出的方法是在2维平面下，基于数学建模方法进行分析，针对解脱成本和解脱时效性进行探究。为了能在最快的时间内解脱冲突，在之前混合整数线性规划(mixed integer linear programming,MILP)方法的基础上，结合Alonso-Ayuso等人[14]提出的角度范围离散化方法，对飞行冲突解脱问题使用分步求解策略。首先，利用角度范围离散化模型将飞行冲突解脱非线性模型线性化，通过混合整数线性规划方法求得一组较好的可行解；其次，将求得的可行解带入飞行冲突解脱非线性模型中，最后使用非线性规划方法寻找更优结果。本文最后通过对多架飞行器的飞行实例来验证该方法的可行性。

1 问题阐述及相关定义

假设给定一组飞行配置，为了解决飞行冲突问题，需要在尽量少的时间内重新规划多架飞行器的飞行配置，以避免冲突情况的发生。在2维空间中，冲突是指两架或多架飞行器违反了飞行必须保持的最小安全距离(5海里)的要求。每架飞机在模型中形成一个半径为2.5海里的圆形保护区域，此飞机处于圆心位置。若有其他飞行器进入该飞行器圆形保护区域，则会发生飞行冲突事件。在2维空间中，解决冲突事件可以考虑以下操作：速度改变(VC)，角度偏转(TC)，用来改变原来飞行器的飞行状态使其以最低成本快速解决检测到的冲突问题。

在冲突解脱问题中，Pallottino等人[7]提出，有一组已知飞行器初始配置(初始速度，运行航线，初始点坐标，终点坐标)的飞行计划。该问题的目的是提供一种新的飞行配置，使空域中的所有飞行器冲突都得以避免。发生冲突情形时，即所涉飞行器之间的当前距离已小于最小安全距离(5海里)。按照最小安全距离原则，半径为2.5海里圆形保护区域内，不允许别的飞行器出现，以此为标准建立飞行冲突解脱模型进行求解，为涉及冲突的飞行器提供新的飞行配置。

(1)

因此，需要考虑使用不同的方法改变这种情形，包括改变飞行器飞行速度vi+qi(qi表示飞行器速度改变量)、飞行器飞行航向角θi+pi(pi表示飞行器角度改变量)等。分别定义2条关于飞行器i、j安全保护区的切线，切线角度分别为lij、rij，其中lij≥rij。在以上各种情况下，所在冲突中的飞行器均可以通过及时调整飞行配置来避免冲突的情况发生，通过改变飞行器飞行速度和飞行航向角等方法，用线性/非线性约束和一系列离散变量建立冲突解脱模型，使用混合整数线性/非线性规划方法进行求解。本文涉及的方法是在2维平面内，通过改变飞行速度和飞行航向角来实现冲突解脱问题，暂未涉及3维空间中改变飞行高度的方法。在Alonso-Ayuso等人[9]提出的模型中，建立基于飞行速度和飞行航向角同时改变的数学模型，如式(2)、(3)所示：

≥tan(lij) (2)

≤tan(rij) (3)

以上Alonso-Ayuso等人[9]提出的改变速度和航向角相结合的非线性规划模型，考虑并分析了模型空分母情况等特殊情况，解决了单独改变速度无法解脱冲突的情况。在涉及空中交通问题时，快速地解决冲突事件能够有效提升空域安全管理和运行。以上使用非线性优化方法求解飞行冲突解脱问题求解效率较低。本文在Alonso-Ayuso等人[14]提出的角度范围离散化求解模型基础上进一步研究和探索，主要是为了减少冲突解脱问题的求解时间，当发生飞行冲突问题的时候，能够在求解时间和冲突成本之间有所权衡，尽可能以最快的时间用最低的成本实现冲突解脱，提高航空飞行的安全性能。

2 “两步法”模型求解策略

针对以上使用混合整数线性规划方法求解飞行冲突解脱效率低的问题，秉承航空运输安全第一的原则，本文提出了基于元启发式算法的低成本快速解决飞行冲突问题的“两步法”模型求解策略，在求解时间和解脱成本之间寻找一个折中点，用更短的时间求解出可行的冲突解脱策略。

本文在Raghunathan等人[17]提出的“三步法”初始化策略和颜丰琳[18]提出的递归思想的基础上，提出“两步法”模型求解策略。首先，在Alonso-Ayuso等人[14]提出的角度范围离散化求解模型基础上加入递归求解策略，使用MILP求解方法求解出一个较好的可行解，以此可行解作为“两步法”第2部分的初始解，然后第2部分使用NLP求解方法进行求解，得到一个更好的结果。

2.1 混合整数线性规划求解

混合整数线性规划求解作为“两步法”求解策略的第1步，提出一种加入冲突解脱模型飞行器序列的方法，在Alonso-Ayuso等人[14]提出的角度范围离散化、将非线性问题转换成混合整数线性规划问题基础上稍做改进，使用改进的递归求解思想进行求解。

2.1.1 飞行配置初始化

在将多架飞行器加入冲突解脱模型时，将飞行器在模型中的编排序列考虑进去，提出一种航向角递增排序方法。其中，航向角递增排序方法指飞行器加入冲突解脱模型的排列顺序按照各飞行器航向角的角度由小到大进行排序，根据飞行航向角角度大小顺序作为飞行冲突模型中飞行器的添加顺序。航向角θi范围是[0, 2π)。

以4架飞行器为例，坐标分别为:A初始坐标(-100,0)，终点坐标(100,0)，B初始坐标(0,-100)，终点坐标(0,100)，C初始坐标(100,0)，终点坐标(-100,0)，D初始坐标(0,100)，终点坐标(0,-100)。

根据飞行器初始配置可知，各飞行器的飞行航向角为：θA=0，θB=π/2，θC=π，θD=3π/2，根据航向角递增排序方法，确定飞行器A,B,C,D冲突解脱模型中的飞行配置顺序为A,B,C,D。

2.1.2 引入递归思想

确定以上飞行配置顺序后，在颜丰琳提出的递归思想初始化策略[18]基础上，为了进一步降低求解时间，将此递归模型进行扩展，将飞行器数量一架一架逐渐增加的冲突解脱问题扩展为飞行器增加数量为多架增加方式的冲突解脱问题(以下飞行器增加数量设为2)。基于扩展的递归思想的初始化策略步骤如下：

步骤1将N(N>2)架飞行器的飞行冲突解脱问题分为2部分，第1部分是N-2架飞行器的飞行冲突解脱问题，第2部分是将以上N-2架飞行器冲突解脱最优解固定，加入另外2架飞行器再次进行冲突解脱；

步骤2对N-2架飞行器依次根据步骤1进行分解，直至最后分解为2架(N为偶数架时最后分解为2架)或3架(N为奇数时最后分解为3架)飞行器的飞行冲突解脱问题；

步骤3将已经优化求解成功的N-2架飞行器的最优飞行配置固定，再与加入的2架飞行器一同再次进行飞行冲突解脱求解，如图1所示；

步骤4合并。递归求解各个子问题，最终优化求解N架飞行器的冲突解脱问题。

2.1.3 MILP模型求解

图1 飞行冲突解脱递归思路

图2 飞行器i角度可行域

图3 飞行器i航向角离散化

然后按照以上步骤1中的扩展递归求解方法，将飞行冲突所需数据带入以上MILP模型中，使用混合整数线性规划方法进行求解，得到一个较好的可行解Z1。

2.2 非线性规划求解

在非线性规划问题求解过程中，有个好的初始解是求解非线性问题的关键，不同的初始解可能会得到不同的局部最优解。在此部分的非线性规划求解中，将2.1节混合整数线性规划模型中求解得到的较好的可行解Z1作为此部分非线性规划问题的初始解，然后使用非线性规划方法进一步求解。

2.2.1 初始解与非线性约束条件

在2.1节中，Alonso-Ayuso等人[14]提出的角度范围离散化模型也是在原始非线性规划模型的基础上进行优化得到的，所以求解得到的可行解Z1依然满足原始非线性规划求解模型的约束。

根据以上飞行冲突非线性求解模型可知，任意2架飞行器i,j在冲突解决过程中，满足式(2)和(3) 2条约束条件中的任意一条即可解决冲突问题。

因此，将2.1节中求得的可行解Z1带入以上非线性约束条件式(2)和式(3)中进行验证，每对飞行器只存在一条满足的约束条件。

2.2.2 联立非线性约束条件

由式(1)可知，任意2架飞行器i,j都已验证得到对应的约束条件(约束条件式(2)或式(3))。对N架飞行器冲突解脱，联立所有飞行器的约束条件，如式(4)所示：

(4)

2.2.3 非线性化求解

角度变量和速度变量相结合的目标函数使用归一化处理，目标函数如式(5)所示：

(5)

使用非线性规划方法对以上联立的飞行冲突解脱非线性模型式(2)、(3)使用非线性规划方法进行求解，得到“两步法”模型求解策略的最终优化结果。

3 运行结果与分析

本次实验是基于AMD Ryzen 5 2500U和Radeon Vega Mobile Gfx处理器，2.00 GHz, 8 G内存的计算机进行的。

为了评估本文提出的新型求解飞行冲突解脱问题方法，实验分别对13、15、17、19、21架飞行器的数据进行了验证，来保证此方法的可行性和实验结果的可靠性，并且与Alonso-Ayuso等人[14]提出的离散模型进行数据对比，结果如图4、图5所示。其中，Z表示目标函数，即最终运行结果，N表示参与飞行冲突解脱的飞行器架数，t表示冲突解脱问题的求解时间。

图4 2模型运行结果对比示意图

图5 2模型运行时间对比示意图

由图4可见，在同一目标函数下，“两步法”求解策略最优解与原离散模型求解策略最优解相比结果更优，即解脱成本更低。从图5中也可看出“两步法”模型比原离散模型求解效率更高。

4 结 论

飞行冲突解脱问题一直以来都是航空空域飞行至关重要的一环，如何提高求解效率，降低飞行成本是研究的重点。本文提出了先通过MILP方法在混合整数线性规划模型中求得一个较好可行解，再使用NLP方法进一步求得更优结果的“两步法”求解策略，以13、15、17、19、21架飞行器冲突解脱实例验证了该方法的可行性。结果表明，本文提出的“两步法”求解策略对于2维平面中的飞行冲突解脱问题可行，效果良好。