郭野晨風，胡明華，張 穎，謝 華

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

0 引 言

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

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

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

1 模 型

1.1 問題描述及條件假設

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

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

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

為簡化實際問題，本文假設：

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

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

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

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

(5)空管具備四維航跡預測技術，能準確推算航班飛經(jīng)各點的計劃時間.

1.2 模型建立

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

此外，決策變量還應滿足

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

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

本文重點研究航班延誤時間的分配，故令β=1，則單個航班的校準延誤為

由此，本文效率目標定義為最小化總校準延誤，即

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

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

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

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

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

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

1.3 模型分析

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

2 算 法

2.1 RBS算法

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

2.2 改進的遺傳算法

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

2.2.1 編碼設計

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

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

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

2.2.2 遺傳操作設計

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

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

(2)變異操作(雙點變異法).

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

(3)交叉操作.

隨機將種群中的個體兩兩配對，對每一對個體實施交叉操作前，先產(chǎn)生一個隨機數(shù).當隨機數(shù)小于交叉概率pc時繼續(xù)以下操作：隨機產(chǎn)生待交叉片段的起止基因點，將兩個個體的待交叉片段整段交換，由此生成的兩個新個體可能存在重復基因，再對片段外發(fā)生重復的基因進行變異修正，保證交叉后的個體是不重復航班的有效排列.如染色體對χ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 號航班重復，后者5 號航班重復，此時將片段外重復基因變異為缺失基因，如(2,3,4,1,5)和(1,5,3,4,2).

2.2.3 滿意解選擇設計

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

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

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

2.2.4 整體算法分析

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

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

3 仿真算例

3.1 參 數(shù)

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

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

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

3.2 結(jié) 果

3.2.1 算法可行性驗證

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

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

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

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

3.2.2 滿意解與RBS解的比較

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

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

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

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

4 結(jié) 論

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