基于仿真優(yōu)化的臨時(shí)航線動(dòng)態(tài)規(guī)劃

朱承元，晏楠欣，劉裕旭

(1.中國(guó)民航大學(xué)空中交通管理學(xué)院，天津 300300；2.濟(jì)南國(guó)際機(jī)場(chǎng)股份有限公司運(yùn)行控制中心，山東 濟(jì)南 250000)

1 引言

隨著航班流量的增長(zhǎng)以及國(guó)內(nèi)臨時(shí)航線“主動(dòng)釋放”機(jī)制的逐漸普及，臨時(shí)航線的規(guī)劃研究引起眾多學(xué)者的關(guān)注。航路航線規(guī)劃模型方面，文獻(xiàn)[1]中提出的空中交通路線規(guī)劃模型，利用啟發(fā)式算法找到最優(yōu)解；文獻(xiàn)[2]中提出的基于動(dòng)態(tài)航路的交通流量模型，利用雙重組合法解決航路的優(yōu)化問(wèn)題；文獻(xiàn)[3]中提出了基于塊狀限制空域的臨時(shí)航線規(guī)劃模型，利用面積度量法實(shí)現(xiàn)航線的規(guī)劃。上述研究模型針對(duì)性強(qiáng)，能有效緩解延誤、減少運(yùn)營(yíng)成本以及縮短飛行距離，但缺乏對(duì)問(wèn)題的綜合性描述，同時(shí)未能將管制員工作負(fù)荷考慮在內(nèi)。航路航線規(guī)劃算法方面，常用算法有：遺傳算法[4]，蟻群算法[5]，粒子群算法[6]等。其中，粒子群算法具有計(jì)算簡(jiǎn)單，搜索速度快，易于工程實(shí)現(xiàn)等特點(diǎn)。而在應(yīng)用上述算法時(shí)，文獻(xiàn)[3]未有機(jī)結(jié)合仿真軟件和優(yōu)化算法，其研究不能有效的應(yīng)用于實(shí)際工程之中。

針對(duì)上述不足，首先，本文從實(shí)際工程應(yīng)用的角度，借鑒文獻(xiàn)[7]的思想，建立了臨時(shí)航線和固定航線同時(shí)處于可用條件下的臨時(shí)航線規(guī)劃模型；其次，采用TAAM模型和改進(jìn)DPSO算法，進(jìn)行模型的優(yōu)化與求解，并且利用TAAM模型的多線程仿真實(shí)現(xiàn)仿真優(yōu)化的并行運(yùn)行；最后，選取上海區(qū)域管制區(qū)內(nèi)的部分扇區(qū)作為優(yōu)化區(qū)域，進(jìn)行相關(guān)模型和算法的驗(yàn)證，同時(shí)從安全性和經(jīng)濟(jì)效益性的角度，調(diào)節(jié)管制員工作負(fù)荷和節(jié)省飛行成本。

2 構(gòu)建仿真優(yōu)化系統(tǒng)

2.1 仿真優(yōu)化路線

步驟1：明確優(yōu)化區(qū)域，確定初始方案和初始解，構(gòu)建TAAM仿真模型。

步驟2：考慮飛行流量和軍民航協(xié)調(diào)的影響確定是否對(duì)選定區(qū)域的初始方案進(jìn)行優(yōu)化；然后，運(yùn)行TAAM模型的多線程仿真，實(shí)現(xiàn)并行的多次隨機(jī)仿真；再后，通過(guò)MATLAB程序連接TAAM模型并提取MySQL數(shù)據(jù)庫(kù)中相關(guān)數(shù)據(jù)，并對(duì)其進(jìn)行平均處理。

步驟3：計(jì)算管制員工作負(fù)荷，飛行成本以及離散粒子群算法的適應(yīng)度。

步驟4：判斷是否滿足迭代次數(shù)，若滿足，則輸出最優(yōu)解即臨時(shí)航線動(dòng)態(tài)規(guī)劃的最優(yōu)方案；否則使用改進(jìn)離散粒子群優(yōu)化算法進(jìn)行優(yōu)化，隨后對(duì)TAAM模型后臺(tái)的腳本數(shù)據(jù)進(jìn)行處理，然后循環(huán)執(zhí)行步驟2—步驟4，直至得到最優(yōu)解。

仿真優(yōu)化路線的流程如圖1所示。

圖1 仿真優(yōu)化路線的流程圖

2.2 臨時(shí)航線規(guī)劃模型

2.2.1 模型的假設(shè)

為建立臨時(shí)航線動(dòng)態(tài)規(guī)劃模型，作出如下假設(shè)：

1)優(yōu)化區(qū)域內(nèi)臨時(shí)航線存在，并且軍方對(duì)民航開(kāi)放使用。

2)優(yōu)化區(qū)域內(nèi)的航路段流量和扇區(qū)容量已知。

3)航班飛經(jīng)優(yōu)化區(qū)域時(shí)，飛行時(shí)間固定不變，即航班進(jìn)扇和出扇時(shí)間固定不變。

2.2.2 模型的構(gòu)建

模型中的多目標(biāo)函數(shù)的對(duì)象為：

1)管制員工作負(fù)荷最小 管制員對(duì)應(yīng)管制扇區(qū)的監(jiān)視負(fù)荷、潛在沖突負(fù)荷、移交負(fù)荷、高度改變負(fù)荷和改變高度層負(fù)荷達(dá)到總體最小。

2)航空器的飛行成本最小 燃油消耗最小。

考慮飛行流量和軍民航協(xié)調(diào)的影響，建立的數(shù)學(xué)模型如下

(1)

f1(x)=∑sWLs=α1WLs1+α2WLs2

(3)

其中，目標(biāo)函數(shù)對(duì)象權(quán)重系數(shù)的約束：

α1+α2+α3+α4+α5=1

(4)

式中，αi(i=1，2…，5)為管制員工作負(fù)荷的權(quán)重系數(shù)。

考慮TAAM模型的工作原理和實(shí)際管制員工作特點(diǎn)，構(gòu)造各類管制員工作負(fù)荷的計(jì)算公式，見(jiàn)式(5)-(9)。其中KOi(i=1，2…7)表示相關(guān)負(fù)荷對(duì)應(yīng)的調(diào)整因子，由TAAM模型的相關(guān)系數(shù)確定。具體公式如下

(5)

(6)

式中，sfonfl(t)為管制扇區(qū)s內(nèi)，有沖突的航空器數(shù)量；sconflsep為沖突等級(jí)是conflsep的調(diào)整因子，conflsep={1，…，4}；sconfltype為沖突類型為confltype的調(diào)整因子，confltype={1，…，9}。

(7)

式中，sf1，from(t)、sf2，to(t)為扇區(qū)s接收或者移交的航空器數(shù)量。

KO4+sf3，descent(t)×KO5]

(8)

式中，sf1，level(t)、sf2，climb(t)、sf3，descent(t)為扇區(qū)s內(nèi)，有高度改變時(shí)，對(duì)應(yīng)的平飛、爬升、下降的航空器數(shù)量。

(9)

式中，sf1，flasclimb(t)、sf2，flasdescent(t)為扇區(qū)s內(nèi)，按FLAS高度層爬升、下降的航空器數(shù)量。

針對(duì)上述數(shù)學(xué)模型，在TAAM模型中有如下約束：

1)流量守恒 在任意的時(shí)間間隔內(nèi)，航路段的交通流量動(dòng)態(tài)守恒。

2)流量分配限制 在任意時(shí)間間隔內(nèi)，優(yōu)化飛行路徑的流量小于航路段流量。

3)容量限制 在任意時(shí)間間隔內(nèi)，目標(biāo)空域的扇區(qū)飛行流量不大于其容量值。

4)偏航角度限制 航空器的最大偏航角度小于90°。

5)規(guī)避沖突集中點(diǎn) 有效規(guī)避從沖突點(diǎn)比較集中的航路點(diǎn)穿過(guò)。

2.3 改進(jìn)DPSO算法

臨時(shí)航線的動(dòng)態(tài)優(yōu)化是針對(duì)可用臨時(shí)航線和原航班計(jì)劃中固定航路航線的組合進(jìn)行優(yōu)化，該問(wèn)題屬于離散問(wèn)題。因此，借鑒文獻(xiàn)[9]的求解旅行商的DPSO算法的設(shè)計(jì)思想，對(duì)DPSO算法中狀態(tài)表示和運(yùn)算規(guī)則進(jìn)行重新定義。

1)符號(hào)說(shuō)明

以四個(gè)扇區(qū)為例，第i個(gè)粒子中第a個(gè)航班的航班走向定義如圖2所示。

圖2 航班a的走向定義圖

2)粒子的位置說(shuō)明

令第i(i=1，2，…，m)個(gè)粒子的位置向量為

Xi=(Xi1，Xi2，…，Xia，…，XiN)

(10)

其中，Xi1，Xi2，…，Xia，…，XiN表示N個(gè)航班的航班走向。第i個(gè)粒子的第a個(gè)航班的航班走向的可表示為

(11)

3)粒子速度和位置的更新公式

第i個(gè)粒子在DPSO算法中速度和位置的向量公式如下

Vi(k+1)=Vi(k)⊕r1?[pbΘXi(k)]

⊕r2?[gbΘXi(k)]

(12)

Xi(k+1)=Xi(k)⊕Vi(k+1)

(13)

式中，Vi表示粒子i的速度向量，i=1，2，…，m；k為當(dāng)前迭代步數(shù)；r1、r2為[0，1]之間的隨機(jī)數(shù)；pb表示粒子i的個(gè)體最優(yōu)位置；gb表示粒子i的群體最優(yōu)位置。

(15)

(17)

3 實(shí)例仿真

3.1 初始方案的確定

參考文獻(xiàn)[10]，分析可知ZSSS23扇的管制負(fù)荷較高且潛在沖突較多。因此，本文選取ZSSS23扇及其周邊扇區(qū)構(gòu)成優(yōu)化區(qū)域，采集數(shù)據(jù)，進(jìn)行TAAM模型的仿真建模與校驗(yàn)，并將原航班計(jì)劃中的航班走向作為初始方案。其中，優(yōu)化區(qū)域內(nèi)扇區(qū)和航路航線的分布情況如圖3所示。

圖3 優(yōu)化區(qū)域內(nèi)扇區(qū)和航路航線分布情況

3.2 實(shí)例參數(shù)的設(shè)置

3.2.1 算法設(shè)計(jì)和參數(shù)設(shè)置

1)確定粒子編碼

進(jìn)行改進(jìn)DPSO算法的粒子編碼時(shí)，優(yōu)化區(qū)域中可使用的臨時(shí)航線有：V14，V27，V70，V64，…，V78；固定航路航線有：G330，W554，W555，A539，…，W73。

以第i個(gè)粒子的第1個(gè)航班的編碼為例進(jìn)行說(shuō)明。假設(shè)第1個(gè)航班在優(yōu)化區(qū)域內(nèi)的航班走向?yàn)閆SSS-VILID，即以ZSSS為路徑起點(diǎn)，VILID為路徑終點(diǎn)。此航班走向中臨時(shí)航線有：V14，V64，V65；固定航路航線中的關(guān)鍵航路航線有：G330，G345，W73，W127。根據(jù)b、c符號(hào)的編碼原則，臨時(shí)航線對(duì)應(yīng)的臨時(shí)區(qū)域有三個(gè)，即b的取值為1，2和3，則第i個(gè)粒子的第1個(gè)航班的航路走向?yàn)?/p>

其中，第i個(gè)粒子的第1個(gè)航班的固定航路航線和臨時(shí)航線的具體編碼如表1所示。

表1 第i個(gè)粒子的第1個(gè)航班的編碼示意圖

2)確定初始粒子種群

將原航班計(jì)劃和可用臨時(shí)航線集合內(nèi)隨機(jī)生成的臨時(shí)航線構(gòu)成的其它航班走向一起作為改進(jìn)DPSO算法的初始粒子種群。

3)確定適應(yīng)度函數(shù)

令適應(yīng)度函數(shù)fit(x)=f(x)。其中f(x)為臨時(shí)航線規(guī)劃模型的多目標(biāo)函數(shù)。

4)確定改進(jìn)DPSO算法中的各類參數(shù)

根據(jù)臨時(shí)航線的實(shí)際運(yùn)行特點(diǎn)，固定值B取0.6；參考文獻(xiàn)[6]，迭代次數(shù)取100，粒子群種群數(shù)取40；參考相關(guān)文獻(xiàn)[11]，航空燃油的價(jià)格取10200元/噸；使用基于群組AHP與交叉熵的組合賦權(quán)法[8]，并且進(jìn)行規(guī)范化處理，最終確定的多目標(biāo)函數(shù)權(quán)重為：w1=0.5537，w2=0.0008。

3.2.2TAAM模型中相關(guān)參數(shù)設(shè)置

1)選取高峰時(shí)段(10：00-14：00)內(nèi)的154架航班進(jìn)行臨時(shí)航線優(yōu)化。

2)TAAM模型中管制員工作負(fù)荷的各類負(fù)荷的權(quán)重系數(shù)αi(i=1，2…，5)均取0.2。

3.3 優(yōu)化結(jié)果的分析

經(jīng)過(guò)百次的迭代和仿真優(yōu)化，得到改進(jìn)DPSO算法適應(yīng)度值的優(yōu)化過(guò)程，如圖4所示。

圖4 適應(yīng)度值的收斂趨勢(shì)圖

由圖4可知，適應(yīng)度值在迭代65次之后基本趨于穩(wěn)定，適應(yīng)度值為2143。優(yōu)化結(jié)果的具體分析如下：

1)優(yōu)化解的分析

154架航班中部分航班的優(yōu)化飛行路徑見(jiàn)表2。其中，進(jìn)行優(yōu)化調(diào)整使用了臨時(shí)航線的航班有62架，其優(yōu)化飛行路徑見(jiàn)表3；未調(diào)整使用臨時(shí)航線，保持原有航班走向的航班有92架。

表2 航班的優(yōu)化飛行路徑

表3 優(yōu)化飛行路徑

2)飛行成本優(yōu)化結(jié)果分析

仿真優(yōu)化后得到的154架航空器的燃油消耗，部分航班的燃油消耗見(jiàn)表4。表中，初始燃油消耗表示為Conori，優(yōu)化后的燃油消耗表示為Conopt。優(yōu)化前后的總?cè)加拖暮涂傦w行成本，見(jiàn)表5。

表4 航空器的燃油消耗(單位：kg)

表5 航空器的總?cè)加拖暮涂傦w行成本

從表4可以看出，仿真優(yōu)化后，不同航空器的燃油消耗變化不同，呈現(xiàn)上升和下降兩種表象。而從表5可以看出，優(yōu)化后的總?cè)加拖暮涂傦w行成本有明顯的下降，較初始方案的數(shù)據(jù)下降了9.08%。

3)管制員工作負(fù)荷優(yōu)化結(jié)果分析

仿真優(yōu)化后得到上海區(qū)域管制區(qū)內(nèi)ZSSS04，ZSSS14，ZSSS23，ZSSS26的扇區(qū)管制員工作負(fù)荷，如圖5所示。

圖5 扇區(qū)的管制員工作負(fù)荷數(shù)據(jù)匯總

由圖5可知，仿真優(yōu)化后ZSSS23扇和ZSSS26扇的管制員工作負(fù)荷有明顯的下降，四個(gè)扇區(qū)總管制員工作負(fù)荷下降了13.64%。

4)優(yōu)化前后沖突點(diǎn)分布及分析

仿真優(yōu)化前后，沖突點(diǎn)在航路航線中的位置分布情況如圖6所示。

圖6 優(yōu)化前后航路航線上沖突點(diǎn)位置分布

從圖6可得，臨時(shí)航線動(dòng)態(tài)優(yōu)化后，固定航路航線G330和R343上的沖突點(diǎn)數(shù)量減少，臨時(shí)航線V14和V64上的沖突點(diǎn)數(shù)量增多，但總體沖突點(diǎn)數(shù)量減少，降低了管制員工作負(fù)荷。

4 總結(jié)

本文從實(shí)際應(yīng)用的角度出發(fā)，改進(jìn)DPSO算法使其適用于臨時(shí)航線動(dòng)態(tài)優(yōu)化問(wèn)題的求解；結(jié)合改進(jìn)DPSO算法，研究了基于仿真優(yōu)化的臨時(shí)航線動(dòng)態(tài)規(guī)劃問(wèn)題。研究表明，本文研究的方法，能夠有效降低飛行成本、降低管制員工作負(fù)荷、減少飛行沖突以及緩解航路擁堵，方法可行、有效。

下一步的研究，需要綜合考慮軍方允許使用的臨時(shí)航線的具體開(kāi)放時(shí)間，使臨時(shí)航線的動(dòng)態(tài)優(yōu)化更加貼近實(shí)際的使用狀況。