基于“兩步法”的飛行沖突解脫問題求解策略①

溫 乾 陳偉鋒

(浙江工業(yè)大學(xué)信息工程學(xué)院 杭州 310023)

0 引 言

隨著全球航空業(yè)的快速發(fā)展，空域資源緊缺與空中交通擁堵的現(xiàn)象日益嚴(yán)重。為應(yīng)對(duì)交通流量的持續(xù)增長、提高航空飛行安全水平、減少航班延誤等問題，空中交通管理(air traffic management,ATM)系統(tǒng)性能亟待提升。為了提高空中交通的安全管理和運(yùn)行效率，一系列空中管制自動(dòng)化方法與智能化優(yōu)化方法成為空中交通管理領(lǐng)域的研究重點(diǎn)[1]，其中之一就是飛行器沖突檢測和解決[2](collision detection and resolution, CDR)。

關(guān)于CDR問題的數(shù)學(xué)優(yōu)化方法，Kuchar和Yang[3]以及Campo和Javier[4]對(duì)沖突檢測方法、沖突解脫方法以及沖突的管理等問題都進(jìn)行了闡述。沖突解脫方法有基于Meng和Qi[5]提出的進(jìn)化算法和Gao等人[6]提出的遺傳算法等元啟發(fā)式方法，以及數(shù)學(xué)模型、動(dòng)態(tài)規(guī)劃方面的方法。其中，Pallottino等人[7]建立了2維平面空間中的飛行沖突解脫模型，使用混合整數(shù)規(guī)劃方法求解，存在求解時(shí)間長、部分問題無法求解的情況。Christodoulou等人[8]建立了3維空域下的飛行沖突解脫模型，使用混合整數(shù)非線性規(guī)劃方法，求解時(shí)間較長，沖突解脫效率較低。Alonso-Ayuso等人[9]提出了一種基于改變飛行速度和飛行高度的混合整數(shù)線性規(guī)劃模型，此模型只適合部分沖突問題，部分沖突情況無法使用此方法解決，例如“頭對(duì)頭”沖突等。Alonso-Ayuso等人[10]提出混合整數(shù)非線性規(guī)劃模型，建立速度隨時(shí)間變化的模型，非線性模型復(fù)雜度高，規(guī)模大，求解較慢，并且針對(duì)此模型當(dāng)時(shí)最先進(jìn)的混合整數(shù)非線性規(guī)劃求解器還無法解決這類大規(guī)模問題，降低了求解效率，增加了求解難度。Omer等人[11]提出了連續(xù)時(shí)間變量離散化的思想，提出了一種混合求解算法，使用混合整數(shù)線性規(guī)劃方法求解出的較好可行解作為非線性模型的初值，不足之處是使用此混合求解算法求解時(shí)間較長，求解成本較高。Alonso-Ayuso等人[12]提出了通過改變飛行速度和飛行高度的優(yōu)化模型，并且將飛行高度范圍增加到多個(gè)水平高度，使用混合整數(shù)線性規(guī)劃方法能夠很好地解決，不足之處是當(dāng)飛行器數(shù)量變多時(shí)，求解成本較高。Alonso-Ayuso等人[13]是在3維空間下，通過改變航向角、速度和飛行高度來實(shí)現(xiàn)沖突解脫，提出了多目標(biāo)折中的混合整數(shù)非線性規(guī)劃方法，使得在不同的環(huán)境下改變不同的目標(biāo)成本來使沖突解脫結(jié)果最優(yōu)。Alonso-Ayuso等人[14]提出了角度范圍離散化，將非線性問題轉(zhuǎn)換成混合整數(shù)線性規(guī)劃問題，與混合整數(shù)非線性規(guī)劃方法相比，混合整數(shù)線性規(guī)劃方法求解速度快、效率高。Cafieri等人[15]提出兩步求解方法，使用混合整數(shù)非線性規(guī)劃方法對(duì)此問題進(jìn)行分步求解，在沖突架數(shù)較少的時(shí)候效果明顯。Mihaela等人[16]將近年來ATM飛行沖突模型進(jìn)行評(píng)估，建立統(tǒng)一的數(shù)學(xué)框架進(jìn)行沖突解脫求解和碰撞概率估計(jì)，促進(jìn)了對(duì)未來ATM數(shù)學(xué)模型能力設(shè)計(jì)評(píng)估的深入了解。

本文提出的方法是在2維平面下，基于數(shù)學(xué)建模方法進(jìn)行分析，針對(duì)解脫成本和解脫時(shí)效性進(jìn)行探究。為了能在最快的時(shí)間內(nèi)解脫沖突，在之前混合整數(shù)線性規(guī)劃(mixed integer linear programming,MILP)方法的基礎(chǔ)上，結(jié)合Alonso-Ayuso等人[14]提出的角度范圍離散化方法，對(duì)飛行沖突解脫問題使用分步求解策略。首先，利用角度范圍離散化模型將飛行沖突解脫非線性模型線性化，通過混合整數(shù)線性規(guī)劃方法求得一組較好的可行解；其次，將求得的可行解帶入飛行沖突解脫非線性模型中，最后使用非線性規(guī)劃方法尋找更優(yōu)結(jié)果。本文最后通過對(duì)多架飛行器的飛行實(shí)例來驗(yàn)證該方法的可行性。

1 問題闡述及相關(guān)定義

假設(shè)給定一組飛行配置，為了解決飛行沖突問題，需要在盡量少的時(shí)間內(nèi)重新規(guī)劃多架飛行器的飛行配置，以避免沖突情況的發(fā)生。在2維空間中，沖突是指兩架或多架飛行器違反了飛行必須保持的最小安全距離(5海里)的要求。每架飛機(jī)在模型中形成一個(gè)半徑為2.5海里的圓形保護(hù)區(qū)域，此飛機(jī)處于圓心位置。若有其他飛行器進(jìn)入該飛行器圓形保護(hù)區(qū)域，則會(huì)發(fā)生飛行沖突事件。在2維空間中，解決沖突事件可以考慮以下操作：速度改變(VC)，角度偏轉(zhuǎn)(TC)，用來改變原來飛行器的飛行狀態(tài)使其以最低成本快速解決檢測到的沖突問題。

在沖突解脫問題中，Pallottino等人[7]提出，有一組已知飛行器初始配置(初始速度，運(yùn)行航線，初始點(diǎn)坐標(biāo)，終點(diǎn)坐標(biāo))的飛行計(jì)劃。該問題的目的是提供一種新的飛行配置，使空域中的所有飛行器沖突都得以避免。發(fā)生沖突情形時(shí)，即所涉飛行器之間的當(dāng)前距離已小于最小安全距離(5海里)。按照最小安全距離原則，半徑為2.5海里圓形保護(hù)區(qū)域內(nèi)，不允許別的飛行器出現(xiàn)，以此為標(biāo)準(zhǔn)建立飛行沖突解脫模型進(jìn)行求解，為涉及沖突的飛行器提供新的飛行配置。

(1)

因此，需要考慮使用不同的方法改變這種情形，包括改變飛行器飛行速度vi+qi(qi表示飛行器速度改變量)、飛行器飛行航向角θi+pi(pi表示飛行器角度改變量)等。分別定義2條關(guān)于飛行器i、j安全保護(hù)區(qū)的切線，切線角度分別為lij、rij，其中l(wèi)ij≥rij。在以上各種情況下，所在沖突中的飛行器均可以通過及時(shí)調(diào)整飛行配置來避免沖突的情況發(fā)生，通過改變飛行器飛行速度和飛行航向角等方法，用線性/非線性約束和一系列離散變量建立沖突解脫模型，使用混合整數(shù)線性/非線性規(guī)劃方法進(jìn)行求解。本文涉及的方法是在2維平面內(nèi)，通過改變飛行速度和飛行航向角來實(shí)現(xiàn)沖突解脫問題，暫未涉及3維空間中改變飛行高度的方法。在Alonso-Ayuso等人[9]提出的模型中，建立基于飛行速度和飛行航向角同時(shí)改變的數(shù)學(xué)模型，如式(2)、(3)所示：

≥tan(lij) (2)

≤tan(rij) (3)

以上Alonso-Ayuso等人[9]提出的改變速度和航向角相結(jié)合的非線性規(guī)劃模型，考慮并分析了模型空分母情況等特殊情況，解決了單獨(dú)改變速度無法解脫沖突的情況。在涉及空中交通問題時(shí)，快速地解決沖突事件能夠有效提升空域安全管理和運(yùn)行。以上使用非線性優(yōu)化方法求解飛行沖突解脫問題求解效率較低。本文在Alonso-Ayuso等人[14]提出的角度范圍離散化求解模型基礎(chǔ)上進(jìn)一步研究和探索，主要是為了減少?zèng)_突解脫問題的求解時(shí)間，當(dāng)發(fā)生飛行沖突問題的時(shí)候，能夠在求解時(shí)間和沖突成本之間有所權(quán)衡，盡可能以最快的時(shí)間用最低的成本實(shí)現(xiàn)沖突解脫，提高航空飛行的安全性能。

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

針對(duì)以上使用混合整數(shù)線性規(guī)劃方法求解飛行沖突解脫效率低的問題，秉承航空運(yùn)輸安全第一的原則，本文提出了基于元啟發(fā)式算法的低成本快速解決飛行沖突問題的“兩步法”模型求解策略，在求解時(shí)間和解脫成本之間尋找一個(gè)折中點(diǎn)，用更短的時(shí)間求解出可行的沖突解脫策略。

本文在Raghunathan等人[17]提出的“三步法”初始化策略和顏豐琳[18]提出的遞歸思想的基礎(chǔ)上，提出“兩步法”模型求解策略。首先，在Alonso-Ayuso等人[14]提出的角度范圍離散化求解模型基礎(chǔ)上加入遞歸求解策略，使用MILP求解方法求解出一個(gè)較好的可行解，以此可行解作為“兩步法”第2部分的初始解，然后第2部分使用NLP求解方法進(jìn)行求解，得到一個(gè)更好的結(jié)果。

2.1 混合整數(shù)線性規(guī)劃求解

混合整數(shù)線性規(guī)劃求解作為“兩步法”求解策略的第1步，提出一種加入沖突解脫模型飛行器序列的方法，在Alonso-Ayuso等人[14]提出的角度范圍離散化、將非線性問題轉(zhuǎn)換成混合整數(shù)線性規(guī)劃問題基礎(chǔ)上稍做改進(jìn)，使用改進(jìn)的遞歸求解思想進(jìn)行求解。

2.1.1 飛行配置初始化

在將多架飛行器加入沖突解脫模型時(shí)，將飛行器在模型中的編排序列考慮進(jìn)去，提出一種航向角遞增排序方法。其中，航向角遞增排序方法指飛行器加入沖突解脫模型的排列順序按照各飛行器航向角的角度由小到大進(jìn)行排序，根據(jù)飛行航向角角度大小順序作為飛行沖突模型中飛行器的添加順序。航向角θi范圍是[0, 2π)。

以4架飛行器為例，坐標(biāo)分別為:A初始坐標(biāo)(-100,0)，終點(diǎn)坐標(biāo)(100,0)，B初始坐標(biāo)(0,-100)，終點(diǎn)坐標(biāo)(0,100)，C初始坐標(biāo)(100,0)，終點(diǎn)坐標(biāo)(-100,0)，D初始坐標(biāo)(0,100)，終點(diǎn)坐標(biāo)(0,-100)。

根據(jù)飛行器初始配置可知，各飛行器的飛行航向角為：θA=0，θB=π/2，θC=π，θD=3π/2，根據(jù)航向角遞增排序方法，確定飛行器A,B,C,D沖突解脫模型中的飛行配置順序?yàn)锳,B,C,D。

2.1.2 引入遞歸思想

確定以上飛行配置順序后，在顏豐琳提出的遞歸思想初始化策略[18]基礎(chǔ)上，為了進(jìn)一步降低求解時(shí)間，將此遞歸模型進(jìn)行擴(kuò)展，將飛行器數(shù)量一架一架逐漸增加的沖突解脫問題擴(kuò)展為飛行器增加數(shù)量為多架增加方式的沖突解脫問題(以下飛行器增加數(shù)量設(shè)為2)?；跀U(kuò)展的遞歸思想的初始化策略步驟如下：

步驟1將N(N>2)架飛行器的飛行沖突解脫問題分為2部分，第1部分是N-2架飛行器的飛行沖突解脫問題，第2部分是將以上N-2架飛行器沖突解脫最優(yōu)解固定，加入另外2架飛行器再次進(jìn)行沖突解脫；

步驟2對(duì)N-2架飛行器依次根據(jù)步驟1進(jìn)行分解，直至最后分解為2架(N為偶數(shù)架時(shí)最后分解為2架)或3架(N為奇數(shù)時(shí)最后分解為3架)飛行器的飛行沖突解脫問題；

步驟3將已經(jīng)優(yōu)化求解成功的N-2架飛行器的最優(yōu)飛行配置固定，再與加入的2架飛行器一同再次進(jìn)行飛行沖突解脫求解，如圖1所示；

步驟4合并。遞歸求解各個(gè)子問題，最終優(yōu)化求解N架飛行器的沖突解脫問題。

2.1.3 MILP模型求解

圖1 飛行沖突解脫遞歸思路

圖2 飛行器i角度可行域

圖3 飛行器i航向角離散化

然后按照以上步驟1中的擴(kuò)展遞歸求解方法，將飛行沖突所需數(shù)據(jù)帶入以上MILP模型中，使用混合整數(shù)線性規(guī)劃方法進(jìn)行求解，得到一個(gè)較好的可行解Z1。

2.2 非線性規(guī)劃求解

在非線性規(guī)劃問題求解過程中，有個(gè)好的初始解是求解非線性問題的關(guān)鍵，不同的初始解可能會(huì)得到不同的局部最優(yōu)解。在此部分的非線性規(guī)劃求解中，將2.1節(jié)混合整數(shù)線性規(guī)劃模型中求解得到的較好的可行解Z1作為此部分非線性規(guī)劃問題的初始解，然后使用非線性規(guī)劃方法進(jìn)一步求解。

2.2.1 初始解與非線性約束條件

在2.1節(jié)中，Alonso-Ayuso等人[14]提出的角度范圍離散化模型也是在原始非線性規(guī)劃模型的基礎(chǔ)上進(jìn)行優(yōu)化得到的，所以求解得到的可行解Z1依然滿足原始非線性規(guī)劃求解模型的約束。

根據(jù)以上飛行沖突非線性求解模型可知，任意2架飛行器i,j在沖突解決過程中，滿足式(2)和(3) 2條約束條件中的任意一條即可解決沖突問題。

因此，將2.1節(jié)中求得的可行解Z1帶入以上非線性約束條件式(2)和式(3)中進(jìn)行驗(yàn)證，每對(duì)飛行器只存在一條滿足的約束條件。

2.2.2 聯(lián)立非線性約束條件

由式(1)可知，任意2架飛行器i,j都已驗(yàn)證得到對(duì)應(yīng)的約束條件(約束條件式(2)或式(3))。對(duì)N架飛行器沖突解脫，聯(lián)立所有飛行器的約束條件，如式(4)所示：

(4)

2.2.3 非線性化求解

角度變量和速度變量相結(jié)合的目標(biāo)函數(shù)使用歸一化處理，目標(biāo)函數(shù)如式(5)所示：

(5)

使用非線性規(guī)劃方法對(duì)以上聯(lián)立的飛行沖突解脫非線性模型式(2)、(3)使用非線性規(guī)劃方法進(jìn)行求解，得到“兩步法”模型求解策略的最終優(yōu)化結(jié)果。

3 運(yùn)行結(jié)果與分析

本次實(shí)驗(yàn)是基于AMD Ryzen 5 2500U和Radeon Vega Mobile Gfx處理器，2.00 GHz, 8 G內(nèi)存的計(jì)算機(jī)進(jìn)行的。

為了評(píng)估本文提出的新型求解飛行沖突解脫問題方法，實(shí)驗(yàn)分別對(duì)13、15、17、19、21架飛行器的數(shù)據(jù)進(jìn)行了驗(yàn)證，來保證此方法的可行性和實(shí)驗(yàn)結(jié)果的可靠性，并且與Alonso-Ayuso等人[14]提出的離散模型進(jìn)行數(shù)據(jù)對(duì)比，結(jié)果如圖4、圖5所示。其中，Z表示目標(biāo)函數(shù)，即最終運(yùn)行結(jié)果，N表示參與飛行沖突解脫的飛行器架數(shù)，t表示沖突解脫問題的求解時(shí)間。

圖4 2模型運(yùn)行結(jié)果對(duì)比示意圖

圖5 2模型運(yùn)行時(shí)間對(duì)比示意圖

由圖4可見，在同一目標(biāo)函數(shù)下，“兩步法”求解策略最優(yōu)解與原離散模型求解策略最優(yōu)解相比結(jié)果更優(yōu)，即解脫成本更低。從圖5中也可看出“兩步法”模型比原離散模型求解效率更高。

4 結(jié) 論

飛行沖突解脫問題一直以來都是航空空域飛行至關(guān)重要的一環(huán)，如何提高求解效率，降低飛行成本是研究的重點(diǎn)。本文提出了先通過MILP方法在混合整數(shù)線性規(guī)劃模型中求得一個(gè)較好可行解，再使用NLP方法進(jìn)一步求得更優(yōu)結(jié)果的“兩步法”求解策略，以13、15、17、19、21架飛行器沖突解脫實(shí)例驗(yàn)證了該方法的可行性。結(jié)果表明，本文提出的“兩步法”求解策略對(duì)于2維平面中的飛行沖突解脫問題可行，效果良好。