航路資源協同分配的多目標優化方法研究

楊 帆，田 文，宋津津

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

1 引言

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

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

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

2 模型描述

2.1 問題描述與基本假設

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

圖1 航跡選項示例

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

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

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

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

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

2.2 模型參數設定

基于上述描述進行數學建模，并引入以下變量：

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；

α：地面延誤成本系數；

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

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

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

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

Fj：航跡選項j內FCA的容量限制；

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

ni：受影響航班i的乘客數量。

2.3 模型建立

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

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

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

2.3.1 系統效率性

第一個目標為使目標函數的效率最高，即令系統的總延誤成本最低

目標函數

(1)

約束條件

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

(2)

(3)

(4)

(5)

(6)

(7)

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

2.3.2 系統公平性

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

目標函數

(8)

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

(9)

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

(10)

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

3 時隙航跡協同分配的多目標遺傳算法

3.1 多目標遺傳算法

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

3.2 算法設計

1)編碼設計

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

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

表1 染色體基因選擇方案

2)適應度函數確定

由目標函數，定義每條染色體有2個適應度函數：

(11)

(12)

3)遺傳操作

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

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

4)算法步驟

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

圖3 算法流程圖

4 實例分析

本文基于南中國海地區三亞情報區歷史運行數據進行實例分析，擁有兩條航跡選項的航路在某日19時至20時預計飛越航班共23架，受惡劣天氣影響，兩條航跡選項各生成一個流量受限區。航路的相關信息如航跡性質、容量及延誤成本見表2所示。空中管制部門發布的航跡可用時隙信息見表3。空中交通管制部門在收到各航空公司受影響航班的具體信息和偏好需求后，將會為其分配航跡與時隙資源。所有受影響航班的詳細信息以及飛行偏好如表4所示。

表2 航路相關信息

表3 可用時隙信息

表4 航班信息表

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

圖4 帕累托最優前沿

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

表5 帕累托解集染色體

表6 帕累托解集函數值

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

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

圖5 解集方案與RBS結果比較圖

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

5 結束語

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