楊 帆，田 文，宋津津

(南京航空航天大學(xué)國家空管飛行流量管理技術(shù)重點實驗室，江蘇 南京 210016)

1 引言

協(xié)同航跡選擇程序(Collaborative Trajectory Options Program，CTOP)是在協(xié)同決策(Collaborative Decision Making，CDM)程序的基礎(chǔ)上提出的一種新交通管理預(yù)案(Traffic Management Initiative，TMI)，用于解決航線和終端空域需求與容量不平衡問題[1]。CTOP的特點在于通過考慮空域使用者的飛行偏好需求，使航空公司參與到航路資源分配的決策中，減少非必要的空中延誤。這實現(xiàn)了空域在受限情況下盡可能地高效運行的同時更降低了航空公司的延誤成本。CTOP的關(guān)鍵在于航路網(wǎng)絡(luò)資源(航跡、時隙)高效、公平、合理的分配，因此研究高效科學(xué)的時隙航跡資源協(xié)同分配方法具有重大意義。

目前對航路網(wǎng)絡(luò)資源協(xié)同分配的研究已取得了較為顯著的成果：Andrew等在線性模型的基礎(chǔ)上考慮了容量的不確定性，使航路資源分配更合理[2]；楊賽等建立的扇區(qū)時隙資源分配模型，降低了航班延誤損失，提升了扇區(qū)使用效率[3]；Kim等對比分析了四種典型資源分配方案，提出了考慮航空公司偏好信息的航路資源分配有效性評估模型[4]；Cruiciol等提出了在發(fā)起CTOP的條件下改進單局決策過程的單人博弈論方法，使航空公司延誤相對減少[5]；Rodionova等建立了一種基于線性優(yōu)化的航班調(diào)度方法，顯著降低了確定性條件下的航班總延誤[6]。

上述成果分別從資源分配的有效性、公平性、可靠性等角度出發(fā)，提出了符合空中交通管制部門、航空公司等各方利益的分配理論模型與算法，但較少考慮多角度資源分配條件的均衡性滿足問題。因此本文基于有效性、效率性[7]和公平性多角度建立了基于多目標(biāo)遺傳算法的時隙航跡協(xié)同分配方法[8]，旨在將多方對航路網(wǎng)絡(luò)資源分配需求轉(zhuǎn)化為共同的優(yōu)化目標(biāo)函數(shù)。

2 模型描述

2.1 問題描述與基本假設(shè)

當(dāng)航路擁堵或天氣惡劣導(dǎo)致空域容量下降時，會導(dǎo)致航路上出現(xiàn)流量受限區(qū)(Flow Constrained Area，F(xiàn)CA)，隨后空中交通管制部門發(fā)起CTOP，航空公司收到CTOP后將受影響的航班的飛行偏好提交給空中交通管制部門?？罩薪煌ü苤撇块T根據(jù)接受的各航班飛行偏好為其分配時隙航跡資源，從而盡可能地降低飛行延誤，維持空域運行。如圖1所示，點A和點B為航路點，兩點之間有兩條航跡選項，箭頭方向為航班飛行方向。本文基于兩條航跡選項建模，包括原計劃航跡選項和改航航跡選項，兩條航跡上各有一個流量受限區(qū)，而每架受影響航班都有航跡選項1和航跡選項2兩種選擇。

圖1 航跡選項示例

在CTOP程序的啟用時間內(nèi)，根據(jù)流量受限區(qū)內(nèi)的容量限制和劃定時隙建模。模型滿足兩個目標(biāo)：效率性目標(biāo)：確保受影響航班的延誤成本最低；公平性目標(biāo)：使得各航空公司間的延誤成本分配趨于平等。在滿足效率性和公平性目標(biāo)的前提下，為各受影響航班分配航跡與時隙，該模型成立應(yīng)建立以下假設(shè)條件：

1)所有受影響航班均接受CTOP的調(diào)配，且各航班的航跡偏好選項與航班信息公開；

2)流量受限區(qū)的范圍及其容量已知；

3)各FCA內(nèi)可用的時隙資源已劃定；

4)所有受影響航班至少提交一條航跡選項。

2.2 模型參數(shù)設(shè)定

基于上述描述進行數(shù)學(xué)建模，并引入以下變量：

I：受影響的所有航班集合，i∈I；

J：航跡集合，j∈J={1，2}；

S：時隙集合，s∈S；

tij：受影響航班i被分配至航跡j的時隙集合；

δij：二元變量，1表示航班i有提交航跡選項j，0表示沒有；

A：航空公司a的集合，a∈A，card(A)=3；

Ia：航空公司a的航班i集合，i∈Ia；

α：地面延誤成本系數(shù)；

β：空中延誤成本系數(shù)(一般取2α=β)；

eij：受影響航班i提交的進入航跡選項j內(nèi)FCA的時間；

τi：受影響航班i提交的所有航跡中最早進入FCA的時間；

cij：受影響航班i選擇航跡選項j的附加航程時間成本；

Fj：航跡選項j內(nèi)FCA的容量限制；

μij：受影響航班i選擇航跡選項j時的不確定性成本；

ni：受影響航班i的乘客數(shù)量。

2.3 模型建立

本文旨在解決擁堵空域內(nèi)的時隙航跡分配問題，為降低算法復(fù)雜性，假設(shè)每一個FCA區(qū)域只含有一條航路，進而將原有的時隙航跡分配問題轉(zhuǎn)化為時隙分配問題。時隙分配兼具有效性、效率性和公平性三個屬性。有效性是模型成立的基礎(chǔ)，表示問題的約束條件。效率性和公平性是模型建立的目標(biāo)，旨在通過同時滿足效率性和公平性使問題得到優(yōu)化。然而事實上，效率與公平通常是對立的，無法使兩者同時達(dá)到性能最優(yōu)。因此，本文考慮建立多目標(biāo)優(yōu)化模型，最大程度地兼顧效率性與公平性，使得航路資源分配更加均衡合理，優(yōu)化目標(biāo)包括：

1)系統(tǒng)效率性：航班延誤不僅會對航空公司帶來巨大的經(jīng)濟損失，更會造成旅客時間成本的損失。因此應(yīng)該盡量減少所有受影響航班的總延誤，滿足效率性的目標(biāo)。

2)系統(tǒng)公平性：由于在CTOP的發(fā)起時間內(nèi)，各航空公司受影響航班的數(shù)量不同，所載旅客也不同，各航路資源分配方案造成的各航空公司延誤也不同。為了使各航空公司都愿意加入CTOP，服從調(diào)配，必須要使系統(tǒng)分配方案具有公平性，即分配延誤趨于相等。

2.3.1 系統(tǒng)效率性

第一個目標(biāo)為使目標(biāo)函數(shù)的效率最高，即令系統(tǒng)的總延誤成本最低

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

(1)

約束條件

tij≥eij·δij;?i，i∈I;?j，j∈J

(2)

(3)

(4)

(5)

(6)

(7)

在上述模型中，式(1)為目標(biāo)函數(shù)，共分為三個部分：第一部分為航班被分配至航跡選項內(nèi)FCA所造成的地面等待延誤；第二部分為航班更改航路造成的空中延誤成本；第三部分是受影響航班的隨機延誤成本，服從(0，σ2)正太分布；式(2)規(guī)定航班被分配的時隙必須在該航班提交的進入該航跡選項FCA的時間之后；式(3)規(guī)定各受影響航班只能被分配至一個時隙；式(4)規(guī)定各時隙內(nèi)最多進入一架受影響航班；式(5)規(guī)定只有航班選擇該航跡選項，其才可以被分配至該航跡選項內(nèi)的FCA時隙中；式(6)規(guī)定了各FCA的容量限制；式(7)規(guī)定受影響航班的排序按照各航班最早進入FCA的時間進行排序。

2.3.2 系統(tǒng)公平性

第二個目標(biāo)即解決各個航空公司之間的公平性問題。公平性體現(xiàn)在受限空域內(nèi)，所有空域使用者所分配的空域資源平等，損失成本平等。公平損失偏差系數(shù)可以反映資源分配的公平性程度，因此，本文采用各航空公司之間資源分配的公平損失偏差系數(shù)來體現(xiàn)系統(tǒng)公平性。公平損失偏差系數(shù)可以理解為資源分配的基尼系數(shù)，即反映資源分配的公平性，其值位于[0，1]區(qū)間，系數(shù)越小，則表示分配越公平。

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

(8)

式中Pa為航空公司a的總延誤成本

(9)

qa表示航空公司a的當(dāng)量航班量與總當(dāng)量航班量之比，當(dāng)量航班量是指將所有航班按照某種性質(zhì)統(tǒng)一換算成的航班數(shù)總量。由于在受限空域內(nèi)，各航空公司的航班數(shù)不同，采用延誤時間等方法無法準(zhǔn)確比較各航空公司之間航班的性質(zhì)。因此，就需要引入當(dāng)量航班量來充分比較各航空公司在延誤分配過程中所占比例。當(dāng)量航班量越大，則該航空公司的受影響航班被分配的延誤成本也就越大。

(10)

式中：ωi表示當(dāng)量航班量。本文采用各航班的平均乘客數(shù)量作為同一性質(zhì)換算各航空公司的當(dāng)量航班量。因此，qa即可表示為航空公司a的乘客的延誤與所有受影響航班乘客的總延誤成本之比。

3 時隙航跡協(xié)同分配的多目標(biāo)遺傳算法

3.1 多目標(biāo)遺傳算法

遺傳算法通過模擬生物遺傳進化的過程，不斷進化搜索更優(yōu)子代，從而獲得最優(yōu)解，其在解決多目標(biāo)優(yōu)化問題時有較好的適用性。多目標(biāo)遺傳算法的結(jié)果是一群不具有相互支配關(guān)系的最優(yōu)解集，稱為近似Pareto最優(yōu)解集，決策者可以根據(jù)問題的實際情況以及參與者的需求確定最滿意的最優(yōu)解[9]。本研究針對某空域內(nèi)的時隙航跡分配問題，選取NSGA-II(Non-dominated Sorting Genetic Algorithm II)算法進行求解。該算法具有適值分配、保持種群多樣性和防止優(yōu)秀個體流失等優(yōu)點，綜合考慮了不同航空公司、不同載客人數(shù)、不同航跡選項的延誤成本，使受限空域以最高效的效率運行的同時滿足航空公司對所分配延誤相對均衡合理的要求，從而在解決時隙航跡協(xié)同分配的問題的同時保證了 Pareto 最優(yōu)解集的可靠性和準(zhǔn)確性。

3.2 算法設(shè)計

1)編碼設(shè)計

本文采用了一條染色體中各基因數(shù)不會出現(xiàn)重復(fù)數(shù)的排列編碼法。一條染色體代表一種時隙航跡分配的結(jié)果；染色體長度表示受影響航班的總架數(shù)，染色體內(nèi)每個基因位置表示各航班選擇的航跡與時隙編號。染色體基因編碼實例如圖2所示。各基因數(shù)所對應(yīng)的選擇方案見表1。

圖2 染色體基因編碼實例圖

表1 染色體基因選擇方案

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

由目標(biāo)函數(shù)，定義每條染色體有2個適應(yīng)度函數(shù)：

(11)

(12)

3)遺傳操作

選擇算子：采用二元錦標(biāo)賽算子，該算子會對每代種群有放回地抽取并選擇最優(yōu)個體，從而確保問題在搜索過程中，每一代的最優(yōu)個體向子代遺傳，使解集不斷收斂。

交叉算子和變異算子：采用部分匹配交叉算子(Partial-Mapped Crossover)和多項式變異算子進行交叉、變異操作。以確保染色體在各組基因交叉變異時始終不會產(chǎn)生沖突基因，形成新的一對可行的子代基因。

4)算法步驟

具體算法實施流程如圖3所示。

圖3 算法流程圖

4 實例分析

本文基于南中國海地區(qū)三亞情報區(qū)歷史運行數(shù)據(jù)進行實例分析，擁有兩條航跡選項的航路在某日19時至20時預(yù)計飛越航班共23架，受惡劣天氣影響，兩條航跡選項各生成一個流量受限區(qū)。航路的相關(guān)信息如航跡性質(zhì)、容量及延誤成本見表2所示?？罩泄苤撇块T發(fā)布的航跡可用時隙信息見表3?？罩薪煌ü苤撇块T在收到各航空公司受影響航班的具體信息和偏好需求后，將會為其分配航跡與時隙資源。所有受影響航班的詳細(xì)信息以及飛行偏好如表4所示。

表2 航路相關(guān)信息

表3 可用時隙信息

表4 航班信息表

通過上述數(shù)據(jù)基于Python的Geatpy2平臺運行多目標(biāo)遺傳算法，取種群規(guī)模為50，最大進化代數(shù)為200，交叉概率設(shè)為0.9，變異概率為0.2。求得的帕累托最優(yōu)解集如圖4所示。

圖4 帕累托最優(yōu)前沿

從圖中可以看出，該算法的求解結(jié)果較好地描繪了帕累托解集的最優(yōu)前沿，符合效率性與公平性的對立關(guān)系。最優(yōu)Pareto解集中共有6組解，6組染色體如表5所示，對應(yīng)的延誤值與公平系數(shù)見表6。

表5 帕累托解集染色體

表6 帕累托解集函數(shù)值

將經(jīng)多目標(biāo)優(yōu)化后得出的最優(yōu)帕累托解集各方案的結(jié)果與傳統(tǒng)的按時刻表分配(Ration-by-schedule，RBS)算法結(jié)果比較分析。經(jīng)計算，RBS方案的總延誤成本為303.55分鐘，公平損失偏差系數(shù)為0.0678。兩種算法結(jié)果對比如表7所示，帕累托解集各方案與RBS算法結(jié)果的對比如圖5所示。

表7 解集方案與RBS方案對比

圖5 解集方案與RBS結(jié)果比較圖

根據(jù)表7的對比分析可知，基于多目標(biāo)遺傳算法求解的帕累托解集的結(jié)果比RBS算法有較大的提升，其平均延誤成本降低了8.5%，平均公平損失偏差系數(shù)降低了70.6%，效果較好，驗證了NSGA-II算法的可行性。該算法為空中交通管制部門提供了諸多選擇，空中交通管制部門的決策可以根據(jù)空域的實際情況選擇最終時隙航跡分配方案。

5 結(jié)束語

本文建立了基于效率性與公平性的時隙航跡協(xié)同分配的多目標(biāo)優(yōu)化方案。在CTOP的條件下，結(jié)合航空公司的航跡選項偏好，通過多目標(biāo)遺傳(NSGA-II)算法，實現(xiàn)了減少航班總延誤以及航空公司平均延誤趨于公平的兩個最優(yōu)目標(biāo)。實驗結(jié)果表明，采用的多目標(biāo)遺傳算法可以高效的求解航路資源協(xié)同分配的問題，且與傳統(tǒng)的RBS算法相比效率與公平性都有很大的改善。決策者可以根據(jù)實際需求選擇最終的分配方案。在此基礎(chǔ)上，可以通過增加更多航路運行條件，使模型考慮更為全面，進一步提高空域運行效率。