改進(jìn)的協(xié)同航路分配優(yōu)化模型及算法研究

郭野晨風(fēng)，胡明華，張 穎，謝 華

(南京航空航天大學(xué)民航學(xué)院，南京211106)

0 引 言

協(xié)同航路分配程序(Collaborative Trajectory Options Program,CTOP)用于解決航路空域內(nèi)容量和流量不平衡問題.它融合了地面等待和改航兩種策略，提高了空域使用靈活性.此外，它在空域資源分配上以空管為主導(dǎo)，考慮航空公司的航路選擇偏好，具有協(xié)同決策的特征.

CTOP 優(yōu)化研究可分為參數(shù)設(shè)置優(yōu)化和空域資源分配優(yōu)化兩類，本文主要對(duì)后者進(jìn)行文獻(xiàn)梳理.模型層面：Rodionova[1]考慮了串聯(lián)式飛行流量限制區(qū)的空域資源分配模型；Zhu[2-3]在模型中考慮了兩次資源分配，第二次分配滿足了航空公司進(jìn)行時(shí)隙交換的需求；徐匯晴[4]構(gòu)建兩階段模型從空管和航空公司角度優(yōu)化航路資源分配.文獻(xiàn)[3-4]僅以效率為目標(biāo)，文獻(xiàn)[1-2]雖兼顧了效率和公平性目標(biāo)，但僅以加權(quán)求和的形式構(gòu)造，公平性內(nèi)涵不夠清晰.算法層面：相關(guān)研究不多，主要圍繞RBS(Ration-by-Schedule)算法展開，文獻(xiàn)[4]提及的兩階段啟發(fā)式算法就是在RBS算法的基礎(chǔ)上加入航空公司時(shí)隙交換過程.

綜上，現(xiàn)有CTOP研究存在公平性指標(biāo)定義模糊，優(yōu)化目標(biāo)構(gòu)造形式簡單，算法效果一般等問題.對(duì)此，本文進(jìn)一步研究CTOP 資源分配模型和算法.創(chuàng)新點(diǎn)為：引入基尼系數(shù)，定義衡量航路資源分配公平性的新指標(biāo)；構(gòu)建兼顧效率和公平的雙目標(biāo)非線性整數(shù)規(guī)劃模型；基于特殊的染色體編碼方式和滿意解的選擇過程，設(shè)計(jì)改進(jìn)的遺傳算法.

1 模 型

1.1 問題描述及條件假設(shè)

CTOP 一般運(yùn)行場景如圖1所示，空管下轄m個(gè)飛行扇區(qū)，其中，部分扇區(qū)(如S1和S2)受天氣影響容量下降，且每個(gè)扇區(qū)均有一條可供航班選擇的航路r.為確保安全，空管對(duì)各條航路設(shè)置最小飛行安全間隔λr；為充分利用空域，將允許飛經(jīng)受限扇區(qū)的航班通過改航進(jìn)入其他扇區(qū).由于改航航班的加入，各扇區(qū)的延誤分配情況將產(chǎn)生變化，因此，空管需要從整體考慮，為所有受限航班重新分配航路和延誤時(shí)間.

圖1 CTOP 一般場景圖Fig.1 General scenario of CTOP

在CTOP中，航空公司要向空管提交航路選擇集，其核心內(nèi)容是每個(gè)航班f對(duì)各條航路r評(píng)估的繞飛成本.在實(shí)際中，為方便管制員分配地面延誤時(shí)間，繞飛成本直接以等價(jià)的地面延誤時(shí)間來表示，如，其中，β為地面延誤成本系數(shù)，一般令0 的航路為該航班的原計(jì)劃航路.

為簡化實(shí)際問題，本文假設(shè)：

(1)航路最小安全間隔一經(jīng)設(shè)定不再更改；

(2)航班只受由CTOP 產(chǎn)生的延誤，且能嚴(yán)格執(zhí)行；

(3)CTOP分配的延誤在信息及時(shí)共享下可在航班起飛前通過地面等待消耗；

(4)所有航班的地面延誤成本系數(shù)一致；

(5)空管具備四維航跡預(yù)測技術(shù)，能準(zhǔn)確推算航班飛經(jīng)各點(diǎn)的計(jì)劃時(shí)間.

1.2 模型建立

設(shè)穿越受限扇區(qū)的航路構(gòu)成集合RC，穿越非受限扇區(qū)的航路構(gòu)成集合RN，所有航路集合為R=RC?RN；飛經(jīng)任意一個(gè)扇區(qū)Sr的航班構(gòu)成集合Fr，其中，受限航班集合為FC，非受限航班集合為FN，所有航班集合為F=FC?FN.模型決策變量為df,r和xf,r，df,r表示航班f分配至航路r時(shí)的地面延誤時(shí)間；xf,r是二元變量，當(dāng)航班f分配至航路r時(shí)，xf,r=1，否則xf,r=0，即

此外，決策變量還應(yīng)滿足

式(2)中Z 為整數(shù)集，實(shí)際航班調(diào)配間隔均以整分鐘為單位，故df,r是整數(shù)變量；式(3)中df,r不得為負(fù)數(shù)，即航班不能早于計(jì)劃起飛時(shí)間起飛；式(4)表示每個(gè)航班能分配到的航路有且只有一條；式(5)為容量約束，即對(duì)于選擇同一航路的任意兩架航班，在到達(dá)扇區(qū)進(jìn)入點(diǎn)時(shí)，航班間的距離不小于該航路設(shè)定的最小安全間隔，其中，為航班f原計(jì)劃到達(dá)扇區(qū)Sr進(jìn)入點(diǎn)的時(shí)間；式(6)和式(7)分別表示原計(jì)劃飛經(jīng)不受限扇區(qū)的航班不受延誤影響，且保持原計(jì)劃航路選擇.

在優(yōu)化目標(biāo)方面，本文主要考慮效率和公平性.空管將效率性能定義為總航班延誤成本，但在CTOP 中，航班不僅需承受地面等待延誤成本，還要承擔(dān)因改航產(chǎn)生的繞飛成本，故單個(gè)航班f分配至航路r的成本為

本文重點(diǎn)研究航班延誤時(shí)間的分配，故令β=1，則單個(gè)航班的校準(zhǔn)延誤為

由此，本文效率目標(biāo)定義為最小化總校準(zhǔn)延誤，即

空管中公平性概念較為模糊且最受爭議.早期，Metron公司提出航空公司公平性評(píng)估指標(biāo)[5]為

式中：da和qa分別為航空公司a的總航班延誤時(shí)間和所擁有的航班數(shù)量.當(dāng)ρa(bǔ)=1 時(shí)，航空公司a得到公平對(duì)待.根據(jù)式(11)，該公平性內(nèi)涵為盡可能使所有航空公司的平均航班延誤趨于一致.假設(shè)航空公司a的航班集合為，則為

ρa(bǔ)只能評(píng)價(jià)單個(gè)航空公司的公平性，對(duì)于系統(tǒng)而言，如果僅對(duì)ρa(bǔ)簡單求和，則缺少合理性.本文引入經(jīng)濟(jì)學(xué)中的基尼系數(shù)，能較好地表征系統(tǒng)的公平性，目標(biāo)函數(shù)為

式中：A為航空公司集合；nA為航空公司數(shù)量；為航空公司a′的平均航班延誤.

式(13)是使G趨于理論最小值0，也就是盡可能使各個(gè)航空公司的趨于一致，符合式(11)的公平性內(nèi)涵.基尼系數(shù)還可通過構(gòu)造洛倫茲曲線的幾何方法表示，如圖2所示，設(shè)陰影部分面積為S，則基尼系數(shù)G=1-2S.洛倫茲曲線構(gòu)造方法如下：基于由小到大順序，確定航空公司排序；基于該順序，依次計(jì)算累計(jì)航空公司數(shù)量之和的比例和累計(jì)之和的比例；進(jìn)而以前者為橫坐標(biāo)，后者為縱坐標(biāo)，繪出nA個(gè)點(diǎn)；最后從原點(diǎn)開始依次將所有點(diǎn)以直線相連，近似代表理想的平滑洛倫茲曲線.當(dāng)洛倫茲曲線越靠近圖中的絕對(duì)公平線時(shí)，G越接近0，則系統(tǒng)越公平.

圖2 基尼系數(shù)幾何含義Fig.2 Geometric significance of Gini coefficient

1.3 模型分析

本文構(gòu)建以式(10)和式(13)為優(yōu)化目標(biāo)，式(1)～式(7)為約束條件的雙目標(biāo)非線性整數(shù)規(guī)劃模型.其中，兩目標(biāo)相對(duì)獨(dú)立，具有同等優(yōu)化地位，這不同于現(xiàn)有的方法，如設(shè)置權(quán)重系數(shù)關(guān)聯(lián)兩目標(biāo)進(jìn)而轉(zhuǎn)為單目標(biāo)問題.此外，效率與公平性目標(biāo)間存在典型的悖反關(guān)系，故模型不存在最優(yōu)解使兩目標(biāo)各自同時(shí)達(dá)到最優(yōu).

2 算 法

2.1 RBS算法

目前CTOP 主要采用RBS 算法進(jìn)行求解，該算法的本質(zhì)是貪心算法，具體步驟可參考文獻(xiàn)[1].RBS 算法在確定航班分配資源優(yōu)先級(jí)次序時(shí)以“先計(jì)劃先服務(wù)”為準(zhǔn)則，雖然該準(zhǔn)則下的公平性內(nèi)涵能被大多數(shù)航空公司接受，但由于這種公平性內(nèi)涵無法通過清晰的指標(biāo)來衡量，航空公司始終對(duì)結(jié)果的公平性感到模糊.

2.2 改進(jìn)的遺傳算法

根據(jù)雙目標(biāo)非線性整數(shù)規(guī)劃模型的特點(diǎn)，選擇第二代非支配遺傳算法(Non-dominated Sorting Genetic Algorithm II,NSGA-II)求解原問題[6].

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

由于CTOP模型含有約束條件，直接對(duì)決策變量進(jìn)行染色體編碼將導(dǎo)致染色體在變異、交叉后形成大量非可行解.可采用直接舍棄或引入罰函數(shù)的方法解決該問題，但會(huì)造成計(jì)算資源浪費(fèi).參考文獻(xiàn)[7]，本文設(shè)計(jì)染色體為受限航班分配資源的優(yōu)先級(jí)排列，即χ=(f1,f2),…,fi,…,fn，n為受限航班數(shù)量，如χ=(3,5,1,4,2)表示3 號(hào)航班第1 個(gè)分配資源，5號(hào)航班為第2個(gè)，以此類推，則算法搜索空間大小為n!.

為確保任意一個(gè)染色體能映射到一組原問題的可行解，需對(duì)染色體施加一個(gè)類似RBS 算法的貪心算法，以確保其解符合原模型中所有約束條件，如圖3所示，其中，m為可選航路總數(shù).特別地，當(dāng)輸入的χ是以“先計(jì)劃先服務(wù)”為準(zhǔn)則的優(yōu)先級(jí)次序時(shí)，輸出結(jié)果為RBS算法的結(jié)果.

圖3 貪心算法流程圖Fig.3 Flow chart for greedy algorithm

2.2.2 遺傳操作設(shè)計(jì)

(1)選擇操作(二元錦標(biāo)賽法).

隨機(jī)從種群中選擇兩個(gè)個(gè)體，比較其支配等級(jí)，等級(jí)排在前者直接獲勝；若支配等級(jí)相同，再比較其擁擠度，擁擠度低者獲勝；若擁擠度相同，則隨機(jī)選擇其一.設(shè)種群大小為nP，則選擇操作重復(fù)nP遍，確保種群規(guī)模保持不變.

(2)變異操作(雙點(diǎn)變異法).

對(duì)種群中每個(gè)個(gè)體實(shí)施變異操作前，先產(chǎn)生一個(gè)隨機(jī)數(shù).當(dāng)隨機(jī)數(shù)小于交叉概率pm時(shí)繼續(xù)以下操作：隨機(jī)挑選需變異的兩個(gè)不同基因點(diǎn)，再互換其位置.如χ=(3,5,1,4,2)隨機(jī)變異第2位和第5位基因點(diǎn)，變異后的染色體為χ=(3,2,1,4,5).

(3)交叉操作.

隨機(jī)將種群中的個(gè)體兩兩配對(duì)，對(duì)每一對(duì)個(gè)體實(shí)施交叉操作前，先產(chǎn)生一個(gè)隨機(jī)數(shù).當(dāng)隨機(jī)數(shù)小于交叉概率pc時(shí)繼續(xù)以下操作：隨機(jī)產(chǎn)生待交叉片段的起止基因點(diǎn)，將兩個(gè)個(gè)體的待交叉片段整段交換，由此生成的兩個(gè)新個(gè)體可能存在重復(fù)基因，再對(duì)片段外發(fā)生重復(fù)的基因進(jìn)行變異修正，保證交叉后的個(gè)體是不重復(fù)航班的有效排列.如染色體對(duì)χ1=(2,5,3,4,1)和χ2=(5,3,4,1,2)，待交叉片段為第2～4 位基因，初步交換后生成(2,3,4,1,1)和(5,5,3,4,2)，前者1 號(hào)航班重復(fù)，后者5 號(hào)航班重復(fù)，此時(shí)將片段外重復(fù)基因變異為缺失基因，如(2,3,4,1,5)和(1,5,3,4,2).

2.2.3 滿意解選擇設(shè)計(jì)

NSGA-II 將位于帕累托前沿的多個(gè)非劣解作為最終優(yōu)化解集，而實(shí)際中決策者會(huì)基于對(duì)不同目標(biāo)的偏好選擇一個(gè)非劣解作為滿意解，這一過程會(huì)因不同決策者而產(chǎn)生不確定性.對(duì)此，本文設(shè)計(jì)一項(xiàng)指標(biāo)，幫助管制員從諸多非劣解中選擇滿意解.

鑒于RBS 算法目前在業(yè)內(nèi)接受度較高，故滿意解的選擇應(yīng)充分考慮RBS 算法的結(jié)果.Ball[8]等在提出RBD(Ration-by-Distance)算法時(shí)，通過設(shè)置偏差閾值控制RBD 算法結(jié)果與RBS 算法結(jié)果的差異程度.本文沿用該思路，設(shè)計(jì)基于校準(zhǔn)延誤的偏差指標(biāo)為

式中：是由RBS 算法得到的單個(gè)航班的校準(zhǔn)延誤.ef表示單個(gè)航班的差異，則一個(gè)非劣解與RBS算法結(jié)果的整體差異就是對(duì)所有航班的差異進(jìn)行求和，如式(15)所示.最終，原問題的滿意解可選擇差異程度最小的非劣解.

2.2.4 整體算法分析

本文提出的改進(jìn)遺傳算法(如圖4所示，其中，jmax為最大迭代次數(shù))設(shè)計(jì)了基于航班優(yōu)先級(jí)排列的染色體編碼方式，再配合一種類似RBS 算法的貪心算法，實(shí)現(xiàn)將一個(gè)航班優(yōu)先級(jí)排列映射至原問題中的一組可行解，確保改進(jìn)算法的有效性.此外，算法末尾融合的滿意解選擇方法充分考慮了RBS 算法的結(jié)果，通過計(jì)算偏差指標(biāo)輔助管制員決策，在一定程度上減小非劣解選擇過程中的主觀影響.

圖4 改進(jìn)遺傳算法整體流程圖Fig.4 General flow chart for improved genetic algorithm

3 仿真算例

3.1 參 數(shù)

以三亞飛行情報(bào)區(qū)作為仿真環(huán)境，如圖5所示，采用該區(qū)域內(nèi)部分航班計(jì)劃作為仿真數(shù)據(jù).圖5中，三亞飛行情報(bào)區(qū)包含3個(gè)扇區(qū)，各自具有一條西南至東北走向的航路A202、A1 和M771，則點(diǎn)ASSAD、BUNTA 和DONDA 為扇區(qū)進(jìn)點(diǎn)，點(diǎn)SAMAS、IKELA和DOSUT為扇區(qū)出點(diǎn).實(shí)驗(yàn)中計(jì)算機(jī)配置為2.3 GHz i5 處理器，8 GB 內(nèi)存，算法在Matlab R2017b中編寫運(yùn)行.

圖5 三亞飛行情報(bào)區(qū)扇區(qū)及航路簡圖Fig.5 Air route map for Sanya flight information region

設(shè)三亞飛行情報(bào)區(qū)北邊兩個(gè)扇區(qū)在某一時(shí)間段容量下降，航路A202 和A1 的最小安全間隔為12 min，最南邊扇區(qū)容量完好，航路M771 的最小安全間隔為4 min.該時(shí)段內(nèi)受影響航班共9架，涉及5 家航空公司，限于篇幅，本文不給出具體航班參數(shù)，參數(shù)包含：每個(gè)航班所屬航空公司，每個(gè)航班計(jì)劃到達(dá)各進(jìn)入點(diǎn)的時(shí)間，每個(gè)航班對(duì)每條可選航路設(shè)置的繞飛延誤.改進(jìn)遺傳算法中參數(shù)設(shè)置如下：種群規(guī)模nP=100，最大迭代次數(shù)jmax=300，變異概率pm=0.3，交叉概率pc=0.9.

3.2 結(jié) 果

3.2.1 算法可行性驗(yàn)證

根據(jù)改進(jìn)算法，仿真實(shí)驗(yàn)共得到13個(gè)非劣解，如圖6中圓圈所示.為驗(yàn)證該結(jié)果為真實(shí)帕累托前沿，本文設(shè)計(jì)遍歷算法：先找出所有可能的航班優(yōu)先級(jí)排列個(gè)體，如本實(shí)驗(yàn)涉及9 架受限航班，整個(gè)搜索空間包含362 280個(gè)可能個(gè)體，再將這些個(gè)體輸入至貪心算法，最終計(jì)算其效率和公平性目標(biāo)值，如圖7所示.結(jié)果發(fā)現(xiàn)，改進(jìn)算法與遍歷算法的帕累托前沿一致，證明了改進(jìn)算法的可行性.遍歷算法耗時(shí)1 679 s，改進(jìn)算法耗時(shí)77 s，縮短計(jì)算時(shí)間95.4%，滿足戰(zhàn)術(shù)流量管理要求.實(shí)驗(yàn)中還記錄每一代帕累托前沿解集的兩個(gè)目標(biāo)均值，如圖8所示，結(jié)果表明，改進(jìn)算法在約100 代時(shí)帕累托前沿解集趨于穩(wěn)定，收斂完成.

圖6 基于改進(jìn)遺傳算法的帕累托前沿Fig.6 Pareto frontiers based on improved genetic algorithm

圖7 遍歷尋優(yōu)結(jié)果Fig.7 All feasible solutions by enumeration

圖8 優(yōu)化目標(biāo)曲線Fig.8 Curves of optimization objectives

3.2.2 滿意解與RBS解的比較

根據(jù)文獻(xiàn)[1]中RBS 算法流程，計(jì)算本文數(shù)據(jù)條件下的RBS 解，結(jié)果如圖6中實(shí)心三角形所示.根據(jù)式(15)，計(jì)算非劣解與RBS 解的差異程度，如圖6中圓圈旁的數(shù)值所示，選擇數(shù)值最小的非劣解為滿意解(實(shí)心圓圈).根據(jù)式(10)和式(13)，本文滿意解與RBS 解的效率和公平性結(jié)果，如表1所示.相較于RBS解，滿意解能提高效率9.3%，提高公平性33.7%.本文按照式(11)計(jì)算ρa(bǔ)，如圖9所示，發(fā)現(xiàn)基于滿意解的各家航空公司的ρa(bǔ)值更趨向于1.為直觀展示公平性結(jié)果，繪制滿意解與RBS 解的基尼系數(shù)幾何含義圖，如圖10所示，菱形點(diǎn)連線為滿意解的洛倫茲曲線，叉點(diǎn)連線為RBS 解的洛倫茲曲線，可知滿意解的洛倫茲曲線更靠近絕對(duì)公平線(對(duì)角實(shí)線).

表1 RBS 算法與改進(jìn)算法的結(jié)果Table 1 Results of RBS algorithm and improved algorithm

圖9 航空公司公平性指標(biāo)結(jié)果Fig.9 Results for airline equity metric

圖10 洛倫茲曲線Fig.10 Lorenz curves

4 結(jié) 論

本文研究了CTOP 優(yōu)化問題：引入基尼系數(shù)，定義可量化的公平性指標(biāo)，構(gòu)建以效率和公平為目標(biāo)的非線性整數(shù)規(guī)劃模型，采用改進(jìn)的遺傳算法對(duì)問題求解.仿真結(jié)果表明：改進(jìn)算法能確保收斂得到真實(shí)帕累托前沿且計(jì)算時(shí)間滿足戰(zhàn)術(shù)流量管理的要求，具有可行性；改進(jìn)算法中融合的滿意解選擇過程，能有效減小管制員選擇非劣解時(shí)的不確定性影響；相比于RBS解，滿意解能在效率和公平性上均得到顯著優(yōu)化.未來隨著多效能研究的深入，CTOP 還可從穩(wěn)定性、靈活性等目標(biāo)進(jìn)行優(yōu)化，為空管提供更加全面的決策支持.