基于多目標規(guī)劃的低空飛行服務(wù)站選址

陳華群, 熊 靜, 黃炬凱

(1.中國民航飛行學(xué)院空中交通管理學(xué)院，廣漢 618307；2.西南交通大學(xué)交通運輸與物流學(xué)院，成都 610041)

低空飛行服務(wù)站是指為低空飛行活動提供飛行計劃的申報審批、航空情報、航空氣象、告警和協(xié)助救援等服務(wù)的機構(gòu)，是保障低空空域飛行安全必不可少的部門。低空改革政策引領(lǐng)帶動下，截至2019年底中國通航飛行達112.5萬h 同比增長13.8%，通航企業(yè)近五百家，通航飛機數(shù)量達到約 3 000架，建設(shè)國家級航空產(chǎn)業(yè)基地10個、地方航空產(chǎn)業(yè)園26個；民航局2018年發(fā)布了《低空飛行服務(wù)保障體系建設(shè)總體方案》，使得低空飛行服務(wù)站逐步推廣。因此迫切需要形成一套行之有效的科學(xué)選址理論和方法，合理規(guī)劃站點的選址位置、數(shù)量和運營規(guī)模，實現(xiàn)低空飛行的安全性和經(jīng)濟性。

美國、澳大利亞和加拿大在低空飛行服務(wù)領(lǐng)域處于世界領(lǐng)先，美國聯(lián)邦航空局針對低空飛行設(shè)置了一百多座低空飛行服務(wù)站，實現(xiàn)了從計劃申請到飛行中情報氣象等自動服務(wù)[1]。中國低空發(fā)展起步較晚，自2012年起，分別在沈陽、珠海、深圳和海南進行了試點，多地開展建設(shè)并摸索了飛行服務(wù)站管理模式。中國眾多專家學(xué)者對低空飛行服務(wù)進行了研究。朱丹彤[2]將運營發(fā)展模式理論優(yōu)化中國通用航空飛行服務(wù)站的系統(tǒng)運營并對服務(wù)流程進行仿真，周雪松等[3]提出了建立低空飛行服務(wù)站綜合信息平臺的思路，黃晶晶[4]提出了復(fù)雜低空飛行安全態(tài)勢的評估方法。上述研究聚焦于低空飛行服務(wù)站的運營和功能，均并未涉及低空飛行站點設(shè)置理論依據(jù)和方法。與低空飛行服務(wù)站的選址相似的場站選址問題如消防站、郵政所、物流配送站等，中外眾多學(xué)者進行了大量的研究，黃川等[5]提出了基于水域精細劃分的雷達站選址配置優(yōu)化；王兵等[6]運用免疫算法對后方倉庫選址進行建模與仿真；Uddin等[7]提出運用決策支持對復(fù)雜城市系統(tǒng)中消防站綜合選址和配置進行研究。

相較于傳統(tǒng)站點選址多偏重考慮經(jīng)濟成本，將服務(wù)響應(yīng)時間、服務(wù)覆蓋區(qū)域和重復(fù)覆蓋納入選址目標，通過系統(tǒng)分析低空飛行服務(wù)流程，明確低空飛行服務(wù)的需求特征，構(gòu)建選址評價體系，建立數(shù)學(xué)模型和遺傳搜索算法，實現(xiàn)低空飛行服務(wù)站選址的多目標全局優(yōu)化。

1 低空飛行服務(wù)流程

低空飛行是距地面100～1 000 m之間的飛行，適用于訓(xùn)練、傘降、空投、偵察、強擊和農(nóng)林等作業(yè)。低空飛行服務(wù)內(nèi)容包括：飛行計劃受理和飛行報備，低空飛行所需信息的服務(wù)如氣象信息、飛行情報、航行情報，以及協(xié)助搜尋救援服務(wù)。低空飛行服務(wù)站需向用戶確保各種服務(wù)信息及情報的可獲得性、全面性、準確性、實時性和安全性，提供服務(wù)時需考慮安全程度最高、成本代價最小的最優(yōu)效果，建立了基于飛行過程的服務(wù)流程，如圖1所示。

圖1 低空飛行服務(wù)流程Fig.1 The process of low altitude flight service

通過低空飛行服務(wù)流程圖可知：飛行服務(wù)站為低空飛行提供的服務(wù)貫穿整個飛行過程，且兼具著緊急情況下的告警和協(xié)助搜尋救援工作。因此，低空飛行服務(wù)站所能提供的服務(wù)必須覆蓋飛行需求范圍，通過系統(tǒng)分析和合理界定低空飛行需求，使站點設(shè)置的數(shù)量和規(guī)模更優(yōu)化。

2 低空飛行服務(wù)需求

低空空域服務(wù)和管理的對象是通用航空的各項飛行活動，飛行需求因社會經(jīng)濟活動需要而使用航空器在規(guī)定空域范圍內(nèi)、給定時段內(nèi)實現(xiàn)位移轉(zhuǎn)移的要求。因此分析低空飛行服務(wù)需求時，應(yīng)充分考慮其飛行時間、位移轉(zhuǎn)換空間及與之相關(guān)的諸多不確定的需求，將其界定為派生性需求；科學(xué)、全面地分析低空飛行服務(wù)需求為飛行服務(wù)站選址提供定性和定量的決策支持作用。

2.1 不定期的時間需求

由于飛行設(shè)備和飛行業(yè)務(wù)性質(zhì)的原因，開展低空飛行活動的時間需求不同于民航運輸，飛行時間需求的特點具有：白天、天氣晴朗、飛行時段持續(xù)較短?，F(xiàn)考慮低空飛行的用戶對飛行服務(wù)時效性要求，即考慮飛行需求量隨著晝夜交替、天氣變化的反應(yīng)時間的增大而產(chǎn)生的相應(yīng)衰退。通過跟蹤調(diào)查和統(tǒng)計，采用Python對中國南方某地區(qū)通航活動時間分布規(guī)律進行大數(shù)據(jù)分析[8]，得到各季節(jié)在不同時間段的需求占比結(jié)果如圖2所示。

圖2 不同季節(jié)的低空飛行時間需求占比Fig.2 The percent of low altitude flight time request in different season

2.2 經(jīng)濟活動聚集的安全超障空間需求

低空飛行需求是人類經(jīng)濟活動過程中產(chǎn)生的一種派生性需求，與其所涉及地區(qū)人類經(jīng)濟活動的空間分布具有一致性，而經(jīng)濟活動在本質(zhì)上具有空間集聚特征，因此低空空域飛行空間需求的分布是以通航機場或起降點之間為需求集聚區(qū)，從通航機場或起降點之間實現(xiàn)空域之間的區(qū)域飛行方式。根據(jù)相似飛行空間需求將該區(qū)域總飛行空間需求區(qū)域分為多個飛行空間需求次區(qū)域，選取需求次區(qū)域的幾何中心來代表離散飛行空間需求點；轉(zhuǎn)換后飛行空間的需求區(qū)域被轉(zhuǎn)化為單個空間需求點的集合，用網(wǎng)絡(luò)節(jié)點代替需求區(qū)域，采用聚類方法，將實際飛行區(qū)域根據(jù)不同飛行密度聚類分成多個次區(qū)域，再利用ArcGis 10.1軟件處理成輸入模型中進行求解的基本數(shù)據(jù)，描述方式如圖3所示。

圖3 節(jié)點集聚式的低空飛行空間服務(wù)需求描述Fig.3 Description of low altitude flight airspace demand sevice with point congestion

圖3利用ArcGis軟件實現(xiàn)了低空飛行空間需求更為現(xiàn)實的集聚，不同于傳統(tǒng)的簡單以通航機場中心或飛行空域中心作為飛行空間需求集聚點，這種飛行空間需求量描述方式是基于飛行區(qū)域需求密度來選擇的最優(yōu)集聚模式。

2.3 低空飛行所需服務(wù)的不確定性

低空飛行活動是一項較復(fù)雜、煩瑣的空間位置轉(zhuǎn)移，飛行過程中需要眾多部門的配合，同時受天氣、飛行人員人為因素、與軍民航協(xié)調(diào)等的影響。此外，低空飛行活動通常是在導(dǎo)航設(shè)備相對簡陋的通航機場、起降點之間進行，飛行區(qū)域多是非管制地帶，飛行人員的操作靈活性大，因此可將以上因素均納入低空飛行所需服務(wù)的不確定性。

3 低空飛行服務(wù)站多目標優(yōu)化模型

3.1 飛行服務(wù)站選址決策評價

低空飛行服務(wù)選址一項綜合決策行為，需要全面分析飛行需求，制定即符合局方要求又高效規(guī)范的管理模式，明確飛行服務(wù)的響應(yīng)時間要求，充分考慮設(shè)施設(shè)備建設(shè)的固定成本和后期的運營維護費用等各項因素。因此，在構(gòu)架飛行服務(wù)站主要評價指標，需考慮飛行服務(wù)響應(yīng)時效性、經(jīng)濟性和魯棒性；將整個飛行過程所需服務(wù)的響應(yīng)總時間為其時效性，服務(wù)站建設(shè)固定成本表示經(jīng)濟性，后期運營和維護成本及需求的變動表示目標魯棒性(圖4)。

圖4 低空飛行服務(wù)站選址決策評價Fig.4 Decision evaluation of low altitude flight service site

傳統(tǒng)的服務(wù)站選址模型通常沒有充分考慮飛行服務(wù)響應(yīng)時間和后期站點可持續(xù)性發(fā)展的魯棒性[9],一定程度影響了選址決策的科學(xué)性。采用最大覆蓋問題模型的覆蓋半徑概念,建立滿足飛行安全服務(wù)響應(yīng)時間要求下的服務(wù)最大覆蓋區(qū)域和站點成本最低的多目標低空飛行服務(wù)站選址模型。

3.2 參數(shù)設(shè)定和決策變量

設(shè)置選址決策變量Xi、服務(wù)與需求匹配決策變量Yij和候選站點是否相交變量Wj，j+1，即

(1)

(2)

(3)

3.3 多目標優(yōu)化模型

飛行服務(wù)站選址問題的目標首先必須設(shè)置的站點確保所屬轄區(qū)內(nèi)開展的低空飛行活動的安全，然后兼具建設(shè)和使用的經(jīng)濟性，同時具備一定的抗需求變動的波動性。因此，根據(jù)3.2節(jié)所設(shè)定的基本參數(shù)和決策變量，建立如下的目標函數(shù)。

3.3.1 飛行服務(wù)響應(yīng)時間

飛行服務(wù)響應(yīng)時間表示各低空飛行服務(wù)站為各需求點提供響應(yīng)的總時間，目標函數(shù)Z1表示為

(4)

3.3.2 飛行服務(wù)站總成本

飛行服務(wù)站總成本包括選址建設(shè)成本、投入使用后的運營和維護成本的總和，目標函數(shù)Z2表示為

(5)

3.3.3 服務(wù)覆蓋

服務(wù)覆蓋目標是指飛行服務(wù)站所能服務(wù)的覆蓋區(qū)域的總和最大化，但站點之間的重復(fù)覆蓋需達到最小化，其目標函數(shù)分別用Z3和Z4表示，即

(6)

根據(jù)候選服務(wù)站點幾何中心位置和服務(wù)半徑判斷兩兩相鄰站點之間重復(fù)覆蓋的區(qū)域定重復(fù)區(qū)域。設(shè)幾何中心之間的距離為lj,j+1，即l<(rj+rj+1),重疊區(qū)域的半高度為h，相交區(qū)域?qū)?yīng)的圓心角分別為θj、θj+1,具體描述如圖5所示。

圖5 相鄰候選站點服務(wù)覆蓋Fig.5 Service coverage of adjacent candidate sites

建立多目標低空飛行服務(wù)站選址數(shù)學(xué)模型為

(7)

(8)

(9)

(10)

約束條件為

DiYij≤Mj， ?i∈M，j∈N

(11)

Yij≤Xj

(12)

(13)

Xj={0,1}

(14)

Yij={0,1}

(15)

(16)

約束條件(11)表示飛行服務(wù)站的服務(wù)需求不能大于自身的服務(wù)上限，約束條件(12)和(13)表示每一個需求點有且僅有一個服務(wù)站為其服務(wù)，約束條件(14)～(16)為決策變量的取值范圍。

4 基于遺傳算法的模型求解

由于上述模型是0-1整數(shù)非線性多目標規(guī)劃問題，直接求解十分困難，因此求解該問題最重要的是多個目標函數(shù)的處理辦法。本文借鑒當前學(xué)者們對多目標的研究成果[10]，預(yù)采用從理想點出發(fā)，將原模型轉(zhuǎn)化成目標擾動最小化模型，并采用遺傳算法進行站點與需要點之間服務(wù)匹配迭代搜索，找出低空服務(wù)需求覆蓋程度最高、建設(shè)和運營成本最低和抗波動性最高的站點選址優(yōu)化方案。

4.1 模型改進

(17)

式(17)中：Zk表示第k個目標函數(shù)的值，則原模型改進為基于理想點的新擾動模型為

(18)

原模型中包含若干個極小極大運算，采用遺傳算法求解時會極大地提高求解難度[11-12]，而在改進原模型之后，遺傳算法求解該模型的效率將提高。

4.2 遺傳算法設(shè)計

算法設(shè)計的主要思路是首先確定服務(wù)站選址原模型的理想點Z0，再根據(jù)選擇、交叉和變異運算進行迭代搜索，求解基于理想點的最小擾動模型，直至滿足停止條件，停止搜索；將解的編碼采用長度為|I|的二進制串Xj,在Xj確定后根據(jù)相應(yīng)的函數(shù)找到站點服務(wù)方案Yij。

基于理想點的目標擾動最小化模型，引入滿足飛行安全要求的響應(yīng)時間、經(jīng)濟成本、覆蓋區(qū)域和重復(fù)覆蓋的最低標準為常數(shù)Fk分別構(gòu)建四個目標函數(shù)的最大化適應(yīng)函數(shù)fit(Xj)=Fk|a，具體的遺傳算法步驟如下：

Step1初始化：確定原目標函數(shù)的初始理想點Z0，設(shè)置最大進化代數(shù)T和進化代數(shù)計數(shù)器t=0，生成初始場站選址方案種群Xt。

Step2個體評價：評價初始方案Xt對應(yīng)的站點服務(wù)方案Yt1，計算個體適應(yīng)度fit(X)t=Fk|a。

Step3選擇運算：根據(jù)Step2中評估確定的初始個體群的適應(yīng)度，選擇動態(tài)需求變化Di作為算子作用于群體選擇搜索，直到所有需求都被站點服務(wù)覆蓋則算法停止，輸出當前最好的個體Xbest=Xt;否則依據(jù)個體適應(yīng)度fit(X)t，保留當代中最好個體Xbest進入下一代循環(huán)。

Step5變異操作：將對選址群體中的服務(wù)方案Yt作為個體串的基因變動。從0～1隨機獲取可接受的變異概率，對選址方案個體中任意選擇兩個站點服務(wù)對象進行逆序調(diào)換，則變異運算之后得到下一代的方案群體X(t+1)和目標函數(shù)群體Z(t+1)。

Step6判斷終止條件：若迭代次數(shù)t=T，以最后搜索所得的選址方案Xt作為最優(yōu)解輸出，計算對應(yīng)的目標函數(shù)值，算法終止；否則返回Step2，t++。

5 算例分析

為測試模型和算法的可行性和優(yōu)化效果，運用MATLAB分別采用傳統(tǒng)枚舉算法和本文提出的多目標遺傳算法進行仿真[12-13]。在300 km×300 km的平面上，均勻地隨機產(chǎn)生飛行服務(wù)需求點和服務(wù)站備選點，如圖1所示未標注的圓點代表低空飛行服務(wù)需求點；標注數(shù)字代號的圓點代表可供建設(shè)低空飛行服務(wù)站的設(shè)施備選位置。候選站“1”代表地區(qū)飛行服務(wù)中心，服務(wù)覆蓋半徑設(shè)為r1取值200 km；其他候選站表示地方飛行服務(wù)站，取服務(wù)覆蓋半徑r2=100 km。

圖6 低空服務(wù)需求分布和可建站點的位置Fig.6 Request distribution and location avaiable of low altitude

假設(shè)最低服務(wù)響應(yīng)時間Tact=15 s，根據(jù)本例候選站點與之覆蓋需求點的相對位置，需求點的響應(yīng)時間取值為15～10 s的隨機數(shù)且服從λ為大于0.5的泊松分布、需求點的需求量為0～100的隨機數(shù)，服務(wù)站的服務(wù)需求閾值為500，服務(wù)站的土地、設(shè)施、維護、預(yù)留成本分別為500萬～100萬、100萬～50萬、50萬～20萬、20萬～10萬的隨機數(shù)。

表1 枚舉法選址方案參數(shù)表Table 1 Parameters of site selection scheme

表1表明：方案S1選擇了全部的備選站,滿足響應(yīng)時間最短的目標，但服務(wù)成本最高，且重復(fù)覆蓋率最高。

算例的種群數(shù)量為23，設(shè)定研究區(qū)域的響應(yīng)時間、經(jīng)濟成本、覆蓋區(qū)域和重復(fù)覆蓋的最低標準分別為F4=(345,90 000,600,15%)：停止迭代次數(shù)為5 000，交配概率為0.8，變異概率為0.1。根據(jù)目標擾動最小化模型，利用遺傳算法選擇各項目標函數(shù)都最低的“4”作為父代，在剩下的種群中利用適應(yīng)度函數(shù)fit(X4)=F4|a對種群個體進行排序，選擇出適應(yīng)度好的個體進行下一個迭代，最終搜索迭代結(jié)果如表2所示。最優(yōu)方案是更接近S3的S4即選址站點“1”和“5”。對比傳統(tǒng)枚舉法，無需搜索所有方案且各目標函數(shù)更加優(yōu)化。

表2 多目標遺傳算法選址方案參數(shù)表Table 2 parameters of multi-objective genetic algorithm location scheme

方案S4＊實現(xiàn)了除服務(wù)響應(yīng)時間之外的其他目標函數(shù)最優(yōu)，也能滿足正常情況下的服務(wù)覆蓋的要求，但若候選站點“1”故障則緊急情況時搜尋救援的效率低；因此可采用增設(shè)一座三級低空飛行服務(wù)站“3”或“4”的方案。

6 結(jié)論

低空飛行服務(wù)站選址是非線性組合優(yōu)化問題，是在確保飛行安全的前提下，考慮運營的經(jīng)濟和高效。引入多目標規(guī)劃理論求解低空飛行服務(wù)站選址問題，得出主要的結(jié)論如下：

(1)系統(tǒng)分析低空飛行服務(wù)流程，有利于確定服務(wù)需求對象和各階段的服務(wù)內(nèi)容，便于低空飛行服務(wù)需求的合理界定和定量表達。

(2)基于層次分析法的選址評價體系，有助于確定選址的基本原則和約束限制。

(3)建立多目標的低空飛行服務(wù)站選址模型兼顧了選址成本和服務(wù)品質(zhì)，考慮了后期飛行服務(wù)的動態(tài)需求變化，增強服務(wù)站的抗擾動性。

(4)提出的改進遺傳算法，有利于均衡各目標函數(shù)值，且在大規(guī)模的選址求解時較傳統(tǒng)枚舉算法求解時間復(fù)雜度更低。

增加服務(wù)覆蓋面積和降低服務(wù)響應(yīng)時間這兩項目標往往需要增加服務(wù)成本為代價，屬于帕雷托解。因此在實際選址決策時，可結(jié)合研究區(qū)域的具體需求，采用如權(quán)重系統(tǒng)法、排序和共享等求解方法。