航路資源協(xié)同分配的多目標(biāo)優(yōu)化方法研究

楊 帆，田 文，宋津津

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

1 引言

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

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

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

2 模型描述

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

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

圖1 航跡選項(xiàng)示例

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

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

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

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

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

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

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

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

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

S：時(shí)隙集合，s∈S；

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

δij：二元變量，1表示航班i有提交航跡選項(xiàng)j，0表示沒(méi)有；

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

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

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

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

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

τi：受影響航班i提交的所有航跡中最早進(jìn)入FCA的時(shí)間；

cij：受影響航班i選擇航跡選項(xiàng)j的附加航程時(shí)間成本；

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

μij：受影響航班i選擇航跡選項(xiàng)j時(shí)的不確定性成本；

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

2.3 模型建立

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

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

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

2.3.1 系統(tǒng)效率性

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

2.3.2 系統(tǒng)公平性

第二個(gè)目標(biāo)即解決各個(gè)航空公司之間的公平性問(wèn)題。公平性體現(xiàn)在受限空域內(nèi)，所有空域使用者所分配的空域資源平等，損失成本平等。公平損失偏差系數(shù)可以反映資源分配的公平性程度，因此，本文采用各航空公司之間資源分配的公平損失偏差系數(shù)來(lái)體現(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ù)不同，采用延誤時(shí)間等方法無(wú)法準(zhǔn)確比較各航空公司之間航班的性質(zhì)。因此，就需要引入當(dāng)量航班量來(lái)充分比較各航空公司在延誤分配過(guò)程中所占比例。當(dāng)量航班量越大，則該航空公司的受影響航班被分配的延誤成本也就越大。

(10)

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

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

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

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

3.2 算法設(shè)計(jì)

1)編碼設(shè)計(jì)

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

圖2 染色體基因編碼實(shí)例圖

表1 染色體基因選擇方案

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

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

(11)

(12)

3)遺傳操作

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

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

4)算法步驟

具體算法實(shí)施流程如圖3所示。

圖3 算法流程圖

4 實(shí)例分析

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

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

表3 可用時(shí)隙信息

表4 航班信息表

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

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

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

表5 帕累托解集染色體

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

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

表7 解集方案與RBS方案對(duì)比

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

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

5 結(jié)束語(yǔ)

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