基于軍民融合的全局飛行流量協(xié)同優(yōu)化方法

吳文浩， 張學(xué)軍， 顧博， 朱曉輝

(1. 北京航空航天大學(xué)電子信息工程學(xué)院, 北京 100083； 2. 國家空域管理中心, 北京 100094)

空中交通管理部門根據(jù)航路航線、機(jī)場和通信導(dǎo)航監(jiān)視等設(shè)施設(shè)備布局，將空域劃分成若干個(gè)管制扇區(qū)，以扇區(qū)為單位向各類飛行活動(dòng)提供管制指揮、告警、氣象等服務(wù)，以確保飛行流量的安全、高效、有序運(yùn)行。隨著中國民用航空和軍事航空飛行量的持續(xù)快速增長，有限的空域資源導(dǎo)致軍民航間飛行矛盾日益凸顯，產(chǎn)生了大量的航班延誤、空中擁堵和額外的管制負(fù)荷。隨著軍民融合發(fā)展上升為國家戰(zhàn)略，如何統(tǒng)一組織、全局優(yōu)化、兼顧軍民航飛行活動(dòng)各自特點(diǎn)實(shí)施飛行流量協(xié)同調(diào)控，最大限度降低擁堵、減少延誤、提高空域資源利用率，已成為空中交通管理領(lǐng)域的一個(gè)熱點(diǎn)和焦點(diǎn)問題。

全局飛行流量協(xié)同優(yōu)化是一類典型的面向?qū)嶋H應(yīng)用的工程優(yōu)化問題，由于緩解空中交通擁堵與減少飛行延誤在實(shí)際中往往是相互沖突的，因此該問題實(shí)質(zhì)上是一個(gè)多目標(biāo)優(yōu)化問題。求解此類問題的難點(diǎn)主要是：一方面，由于扇區(qū)網(wǎng)絡(luò)中同時(shí)運(yùn)行著幾千個(gè)航班，每個(gè)航班至少包括飛行路徑和起飛時(shí)間2個(gè)變量，因此該問題是一個(gè)大規(guī)模優(yōu)化問題；另一方面，表征扇區(qū)網(wǎng)絡(luò)擁堵的目標(biāo)函數(shù)是不可微且難分解的，傳統(tǒng)優(yōu)化算法難以處理，這將在后續(xù)詳細(xì)介紹。

20世紀(jì)90年代以來，歐美等地區(qū)學(xué)者就開展了空中交通流量網(wǎng)絡(luò)運(yùn)行優(yōu)化問題研究，將地面等待、空中等待、空中改航、航班取消等策略覆蓋到每個(gè)航班所有階段，提出了0-1整型規(guī)劃[1-3]、混合0-1整數(shù)規(guī)劃、BLO等模型[4-7]，馬正平等提出了短期空中交通流量管理問題的整數(shù)規(guī)劃模型[8]，蔡開泉、管祥民、肖明明等提出了航班飛行路徑與起降時(shí)隙的協(xié)同分配、飛行流量魯棒優(yōu)化等模型算法[9-11]，有效解決了民用航空特別是同質(zhì)化飛行活動(dòng)條件下飛行流量優(yōu)化問題。

軍事航空飛行活動(dòng)主要包括戰(zhàn)斗飛行、任務(wù)飛行、訓(xùn)練飛行等，由于其在活動(dòng)范圍、飛行路徑、管制間隔等方面有著區(qū)別于民用航空的特殊要求，特別是由于政治、軍事、外交等方面因素導(dǎo)致延誤、改航等措施對(duì)其飛行活動(dòng)影響的代價(jià)也遠(yuǎn)遠(yuǎn)高于民用航空飛行活動(dòng)。統(tǒng)籌民用航空和軍事航空需求實(shí)施全局飛行流量調(diào)控，將是一種在異質(zhì)化飛行活動(dòng)條件下的飛行流量協(xié)同優(yōu)化問題，傳統(tǒng)的同質(zhì)化飛行流量協(xié)同優(yōu)化模型將在目標(biāo)函數(shù)設(shè)置、條件約束等方面難以滿足異質(zhì)化飛行流量調(diào)控要求。同時(shí)，傳統(tǒng)遺傳算法在處理高維問題時(shí)，容易過早陷入局部最優(yōu)，產(chǎn)生“維數(shù)詛咒”，實(shí)際應(yīng)用效果往往不太理想。

本文貫徹軍民融合發(fā)展思想，首先設(shè)計(jì)了全局飛行流量多目標(biāo)協(xié)同優(yōu)化模型——CMI模型；其次，提出了動(dòng)態(tài)自適應(yīng)多目標(biāo)遺傳算法(DA-MOGA)和基于聚集距離與種群多樣性的交叉變異概率動(dòng)態(tài)調(diào)整機(jī)制；最后，通過實(shí)際數(shù)據(jù)對(duì)DA-MOGA的有效性進(jìn)行驗(yàn)證。

1 全局飛行流量協(xié)同優(yōu)化模型

在飛行活動(dòng)中，航空器一般沿著各自規(guī)劃的航線從起飛機(jī)場飛往目的機(jī)場，管制員以空域扇區(qū)為單元實(shí)施飛行管制，保證飛行活動(dòng)安全、高效、有序運(yùn)行。機(jī)場、扇區(qū)構(gòu)成了空域運(yùn)行的基本單元。由于機(jī)場運(yùn)行能力和管制員工作負(fù)荷等原因，機(jī)場和扇區(qū)的容量是有限的?？罩薪煌髁烤W(wǎng)絡(luò)優(yōu)化主要是對(duì)飛行活動(dòng)中的起降時(shí)間和飛行路徑進(jìn)行調(diào)控，以達(dá)到網(wǎng)絡(luò)運(yùn)行經(jīng)濟(jì)性和安全性的整體最優(yōu)。

1.1 目標(biāo)函數(shù)

全局飛行流量協(xié)同優(yōu)化在空域扇區(qū)網(wǎng)絡(luò)多目標(biāo)優(yōu)化模型基礎(chǔ)上，考慮了軍民航異質(zhì)化飛行活動(dòng)管制要求和差異化調(diào)配方法與代價(jià)，兼顧了軍民航管制員各自工作特點(diǎn)，決策變量采用飛行計(jì)劃的起飛時(shí)刻和飛行路徑，目標(biāo)函數(shù)則是扇區(qū)網(wǎng)絡(luò)的空中交通擁堵和總體飛行延誤代價(jià)。

1.1.1 空中交通擁堵

空中交通擁堵通過對(duì)負(fù)責(zé)空域扇區(qū)的管制員工作負(fù)荷進(jìn)行量化，對(duì)扇區(qū)網(wǎng)絡(luò)的所有扇區(qū)的管制員工作負(fù)荷進(jìn)行累加，綜合考慮各扇區(qū)的最大擁堵水平和平均擁堵水平，引用經(jīng)典方法[6]得到以下目標(biāo)函數(shù)：

(1)

式中：φ∈[0,1]為最大擁堵和平均擁堵間的權(quán)重；n為空域內(nèi)扇區(qū)總數(shù)；T為空域扇區(qū)網(wǎng)絡(luò)優(yōu)化時(shí)間區(qū)間；ωi(t)為扇區(qū)i在第t個(gè)時(shí)隙的管制員工作負(fù)荷。

(2)

其中：ni(t)為扇區(qū)i在第t個(gè)時(shí)隙的飛機(jī)數(shù)。

其中：Ci(t)為扇區(qū)i在第t個(gè)時(shí)隙的容量。

1.1.2 總體飛行延誤代價(jià)

總體飛行延誤代價(jià)由起飛延誤導(dǎo)致的地面延誤代價(jià)和由空中等待、減速或飛行路徑變更產(chǎn)生的空中延誤代價(jià)組成。

(3)

式中：f2為總體飛行延誤代價(jià)；gf為飛行活動(dòng)f的延誤代價(jià)；模型中設(shè)計(jì)了ni和nc分別為相應(yīng)類別軍航飛行活動(dòng)FMi和民航飛行FC的延誤代價(jià)權(quán)重。

飛行活動(dòng)F包括民航飛行FC和軍航飛行FM，F(xiàn)M主要包括了戰(zhàn)斗飛行、專機(jī)和重要任務(wù)飛行、一般任務(wù)飛行、轉(zhuǎn)場飛行、場內(nèi)場外飛行等。軍航本場訓(xùn)練飛行(含場內(nèi)場外)因大都不涉及跨扇區(qū)飛行，戰(zhàn)斗飛行因其特殊凈空要求，因此不納入扇區(qū)網(wǎng)絡(luò)流量優(yōu)化范疇。其他軍航飛行計(jì)劃劃分為專機(jī)飛行計(jì)劃FM1、重要任務(wù)飛行計(jì)劃FM2、一般任務(wù)飛行計(jì)劃FM3和轉(zhuǎn)場飛行計(jì)劃FM4。

1.2 約束條件

考慮扇區(qū)網(wǎng)絡(luò)運(yùn)行實(shí)際，還需要對(duì)模型中的空域容量、起飛時(shí)間、軍航特殊間隔要求和飛行距離等進(jìn)行約束。

1.2.1 空域容量約束

空域扇區(qū)網(wǎng)絡(luò)中的各機(jī)場和扇區(qū)節(jié)點(diǎn)應(yīng)全程滿足容量要求，即

(4)

1.2.2 起飛時(shí)間約束

(5)

1.2.3 軍航特殊任務(wù)約束

根據(jù)中國飛行管制有關(guān)規(guī)定，專機(jī)飛行活動(dòng)由于極端安全要求須執(zhí)行特殊間隔規(guī)定，即加大橫向、縱向與水平飛行間隔。模型中，通過控制同一機(jī)場起飛時(shí)間間隔予以保證(即在專機(jī)起飛機(jī)場前后10 min內(nèi)應(yīng)無其他飛機(jī)起飛)。

(6)

1.2.4 飛行距離約束

(7)

2 動(dòng)態(tài)自適應(yīng)多目標(biāo)遺傳算法

從第1節(jié)問題模型可知，扇區(qū)網(wǎng)絡(luò)飛行流量協(xié)同優(yōu)化問題是一個(gè)目標(biāo)函數(shù)不可微、決策變量難分解的大規(guī)模優(yōu)化問題，包含2個(gè)強(qiáng)耦合的子問題，即同時(shí)優(yōu)化起飛時(shí)間和飛行路徑。由于所有飛行計(jì)劃均在同一時(shí)空范圍內(nèi)活動(dòng)，同一飛行計(jì)劃內(nèi)起飛時(shí)間與飛行路徑相互影響，不同飛行計(jì)劃之間起飛時(shí)間和飛行路徑也存在著相互耦合關(guān)系。

2.1 算法框架

Pi={η1,η2,…,ηs}

(8)

(9)

式中：|F|為飛行活動(dòng)總數(shù)。

首先，在決策空間隨機(jī)生成個(gè)體構(gòu)建初始種群，個(gè)體解碼后計(jì)算其目標(biāo)函數(shù)并對(duì)種群個(gè)體進(jìn)行排序；其次，進(jìn)行“選擇”操作，基于擁擠錦標(biāo)賽選擇法構(gòu)建“交配池”；再次，進(jìn)行“遺傳”操作，對(duì)種群實(shí)施交叉和變異，交叉和變異概率將根據(jù)種子聚集距離和種群多樣性進(jìn)行動(dòng)態(tài)調(diào)整，并進(jìn)行約束處理；最后，計(jì)算新的種群個(gè)體目標(biāo)函數(shù)后，進(jìn)行種族重組、選擇和更新，種群中的非支配解即構(gòu)成Pareto最優(yōu)解集。

2.2 動(dòng)態(tài)自適應(yīng)算子

2.2.1 種群平均聚集距離

進(jìn)化第n代種群平均聚集距離為

(10)

式中：di為種群中第i個(gè)種子與第i+1個(gè)種子間的歐氏距離。

2.2.2 種群多樣性

種群多樣性為

(11)

2.3 交叉變異概率動(dòng)態(tài)調(diào)整機(jī)制

遺傳過程中，交叉和變異概率決定了種群進(jìn)化搜索方向。在進(jìn)化之初，較高的交叉概率Pc和較低的變異概率Pv可使種群有效擴(kuò)大搜索范圍，增強(qiáng)種群多樣性。

進(jìn)化過程中，如種群平均聚集距離過大，意味著種子周圍的搜索空間沒有被充分搜索，往往不容易收斂，此時(shí)應(yīng)盡快縮小搜索范圍(迅速降低交叉概率Pc、增大變異概率Pv)，使種群加快聚焦。如種群平均聚集距離過小，意味著種群“早熟”或陷入局部最優(yōu)，則應(yīng)擴(kuò)大搜索范圍(增大交叉概率Pc，降低變異概率Pv)，避免過快聚焦。

進(jìn)化過程中，如種群平均聚集距離適中，若種子間隔也適中，即多樣性較好，則應(yīng)保持交叉變異概率繼續(xù)進(jìn)化；若種子間隔有大有小，不夠均勻，即多樣性分布不佳，意味著種子周圍空間沒有被充分搜索，則應(yīng)縮小搜索范圍(降低交叉概率Pc、增大變異概率Pv)；如多樣性過差，則應(yīng)盡快縮小搜索范圍(迅速降低交叉概率Pc、增大變異概率Pv)，以調(diào)整多樣性分布。具體為

(12)

(13)

(14)

(15)

3 實(shí)驗(yàn)驗(yàn)證

為了評(píng)價(jià)全局飛行流量協(xié)同優(yōu)化模型和動(dòng)態(tài)自適應(yīng)多目標(biāo)遺傳算法的有效性，本節(jié)利用中國扇區(qū)網(wǎng)絡(luò)的實(shí)際數(shù)據(jù)進(jìn)行對(duì)比實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)數(shù)據(jù)及參數(shù)設(shè)置

為了評(píng)價(jià)3 種算法產(chǎn)生的解的收斂性、多樣性等特性，本文使用多目標(biāo)進(jìn)化算法性能評(píng)價(jià)的3 個(gè)經(jīng)典指標(biāo)，綜合性指標(biāo)、收斂性指標(biāo)和多樣性指標(biāo)來衡量算法性能[12]。

綜合性(Ih)[13]是對(duì)解集收斂性、均勻性以及廣泛性的綜合評(píng)價(jià)指標(biāo)，可以用來反映非支配解集與 Pareto最優(yōu)前沿的逼近程度，綜合性指標(biāo)越大，越是逼近 Pareto最優(yōu)前沿。

收斂性(Id)[14]是指算法搜索的非支配解集對(duì) Pareto最優(yōu)前沿的逼近程度，收斂性指標(biāo)越小，算法逼近問題 Pareto最優(yōu)解集的程度越好。

多樣性(Δ)[15]是評(píng)價(jià)算法求得非支配解集分布的離散程度和均勻性，多樣性指標(biāo)越小，非支配解集分布的越均勻分散，解的多樣性越好。

本文實(shí)驗(yàn)選取多目標(biāo)遺傳算法MOGA和非支配排序遺傳算法NSGA-Ⅱ 2種經(jīng)典多目標(biāo)遺傳算法進(jìn)行了對(duì)比。MOGA和NSGA-Ⅱ算法經(jīng)過遍歷分別取解的綜合性系數(shù)最優(yōu)時(shí)的交叉、變異概率取值分別為0.5、0.09和0.7、0.07。為確保算法和實(shí)驗(yàn)對(duì)比公平性，各算法設(shè)置相同的種群規(guī)模和適應(yīng)值評(píng)價(jià)次數(shù)，并分別進(jìn)行了25次獨(dú)立實(shí)驗(yàn)。算法主要參數(shù)取值見表1。

表1 算法主要參數(shù)取值

3.2 實(shí)驗(yàn)結(jié)果與對(duì)比分析

表2給出了3種算法25次獨(dú)立實(shí)驗(yàn)中得到最好的指標(biāo)值。其中就綜合性指標(biāo)而言，DA-MOGA和MOGA均優(yōu)于NSGA-Ⅱ，且DA-MOGA性能最優(yōu)。這表明采用 MOGA在解決異質(zhì)化全局飛行流量協(xié)同優(yōu)化問題上優(yōu)于NSGA-Ⅱ，可以找到更優(yōu)的航班飛行路徑和飛行時(shí)間，使得空中交通擁堵和航班飛行延誤更低。就收斂性而言，DA-MOGA明顯優(yōu)于其他2種算法，這表明動(dòng)態(tài)自適應(yīng)算子及交叉變異概率動(dòng)態(tài)調(diào)整機(jī)制可以有效改善算法局部搜索能力。

表3給出了3種算法在分別考慮效率優(yōu)先和安全優(yōu)先情況下，得到的Pareto最優(yōu)解的目標(biāo)函數(shù)值，并給出了DA-MOGA較MOGA和NSGA-Ⅱ算法在總體飛行延誤代價(jià)和空中交通擁堵2個(gè)目標(biāo)函數(shù)值的減少程度。

表2 主要性能評(píng)價(jià)指標(biāo)對(duì)比

在效率優(yōu)先情況下，DA-MOGA空中交通擁堵分別較MOGA和NSGA-Ⅱ算法減少了1.81%和14.82%，總體飛行延誤代價(jià)降低了12.79%和25.38%；在安全優(yōu)先情況下，DA-MOGA空中交通擁堵分別減少了1.22%和10.88%，總體飛行延誤代價(jià)降低了17.78%和30.41%。這表明DA-MOGA在解決空域扇區(qū)網(wǎng)絡(luò)飛行流量協(xié)同優(yōu)化問題上，可以有效降低軍民航總體飛行延誤代價(jià)、減少全局空中交通擁堵，這也從另一個(gè)方面表明，動(dòng)態(tài)自適應(yīng)算子及交叉變異概率動(dòng)態(tài)調(diào)整機(jī)制發(fā)揮了重要作用，有效印證了DA-MOGA的正確性和有效性。

DA-MOGA是基于傳統(tǒng)MOGA改進(jìn)而來的，兩者最大的區(qū)別在于動(dòng)態(tài)自適應(yīng)算子的使用，由于其時(shí)間復(fù)雜度遠(yuǎn)小于遺傳操作復(fù)雜度，因而其時(shí)間和空間復(fù)雜度與傳統(tǒng)MOGA基本保持不變。DA-MOGA總的時(shí)間復(fù)雜度是O(N(|F|+|T|+N))，空間復(fù)雜度是O(N|T||F|)。其中，N為種群規(guī)模，|T|為全局優(yōu)化時(shí)隙總數(shù)。具體各步驟時(shí)間復(fù)雜度見表4。

為了更好地對(duì)比和評(píng)價(jià)3種算法的性能，圖1給出了在目標(biāo)空間下3種算法經(jīng)過25次獨(dú)立實(shí)驗(yàn)所獲得Pareto前沿，從中同樣可看出，DA-MOGA得到的非支配解明顯優(yōu)于NSGA-Ⅱ算法和MOGA。

圖2展示了隨著進(jìn)化代數(shù)的增加，交叉和變異概率逐漸趨于收斂。

圖3展示了αcmi(2<αcmi<4)在不同取值條件下Pareto前沿面對(duì)比情況，可以看出過大或過小αcmi容易導(dǎo)致空中交通擁堵和總體延誤代價(jià)過度增大，從而無法得到較優(yōu)的Pareto面；當(dāng)αcmi在取值區(qū)間向中點(diǎn)收斂過程中，所得Pareto面逐漸優(yōu)化；αcmi=3所得Pareto面明顯優(yōu)于其他解。這也反映了過于側(cè)重軍航飛行活動(dòng)或過于側(cè)重民航飛行活動(dòng)均無法得到全局飛行流量調(diào)控的整體最優(yōu)，而適中的軍民航飛行活動(dòng)對(duì)比權(quán)重，即兼顧彼此的軍民融合更有益于全局的協(xié)同優(yōu)化，這也從一個(gè)側(cè)面印證了軍民融合、有機(jī)聯(lián)動(dòng)的重要性。

表3 3種算法目標(biāo)函數(shù)值對(duì)比

表4 DA-MOGA時(shí)間復(fù)雜度

圖1 3種算法Pareto前沿對(duì)比Fig.1 Comparison of pareto Front among three algorithms

圖2 DA-MOGA交叉、變異概率進(jìn)化趨勢Fig.2 Evolutionary trend of crossover and variation probability for DA-MOGA

圖3 不同αcmi下的Pareto前沿對(duì)比Fig.3 Comparison of Pareto front at different αcmi

4 結(jié) 論

隨著航空業(yè)的快速發(fā)展以及軍事航空需求的不斷拓展，如何在國家空域運(yùn)行全局，即軍民航飛行活動(dòng)的共同安全與效益的全局中取得更好平衡以推進(jìn)軍民融合深度發(fā)展，是本文研究的出發(fā)點(diǎn)和落腳點(diǎn)，主要?jiǎng)?chuàng)新有：

1) 設(shè)計(jì)了一種基于軍民航異質(zhì)化飛行活動(dòng)管制要求、考慮差異化調(diào)配方法與代價(jià)、兼顧軍民航管制員各自工作特點(diǎn)、有效解決扇區(qū)網(wǎng)絡(luò)運(yùn)行安全性和經(jīng)濟(jì)性問題的全局飛行流量多目標(biāo)協(xié)同優(yōu)化模型。

2) 提出了一種動(dòng)態(tài)自適應(yīng)多目標(biāo)遺傳算法(DA-MOGA)，考慮種群聚集距離及其多樣性，設(shè)計(jì)了算法交叉和變異概率自適應(yīng)變化機(jī)制，實(shí)驗(yàn)證明在Pareto前沿面和綜合性、收斂性等指標(biāo)方面均優(yōu)于2種經(jīng)典遺傳算法。

考慮到軍航飛行活動(dòng)穿越航路航線給民航飛行帶來的特定影響，基于軍民融合的全局飛行流量協(xié)同優(yōu)化后續(xù)研究中，將進(jìn)一步深化研究軍航飛行活動(dòng)對(duì)民航航路航線影響，以求更加科學(xué)、有效、精細(xì)化地調(diào)配空域資源。