基于啟發式隱枚舉算法的多機場GDP放行策略

呂雙回, 胡明華

(南京航空航天大學民航學院，江蘇 南京 210016)

0 引 言

多機場系統的離場放行策略是協同流量管理問題的子問題.同一終端區內的多個機場構成多機場系統，使用多個公共離場定位點，相應的標準離場航路因此形成耦合.盡管各國學者在離場排序問題方面進行了大量研究，但以往的研究多集中于單機場離場航班排序策略問題，協調同一終端區內多機場系統的離場放行策略研究才剛剛起步，多機場系統航班離場排序問題是NP難題.已有的單機場航班排序相關研究表明：先到先服務(First come first served)排隊方法整體效率較低[1]；滑動時間窗動態排序方法的局部最優解與全局最優解差異較大[2-3]；作為一種群智能多點并行隨機搜索方法，粒子群算法在進行大規模搜索時收斂速度有待提高[4]；考慮實際地理因素限制的離場排序模型在采用退火、禁忌搜索和陡峭下降搜索等算法時，某些情況下結果差異很大[5]；遺傳算法的適應度和交叉算子參數較難確定[6]；基于動態理論的排序算法的特征系數得出的排序位置對實際改動太大[7].

考慮地面等待策略，并基于多機場系統具有公共離場定位點的空域結構特點，建立多機場系統的航班放行策略模型.在此基礎上提出啟發式隱枚舉算法(HLEA)，通過引入機場優先級，并協調經由公共離場定位點的各機場航班比例，優化各機場航班的放行時刻，使多機場系統的航班總體延誤最小.

1 多機場系統航班放行策略模型

模型的目標函數為

(1)

表示研究時段內所有機場離場航班的總延誤時間最小.

模型約束為：

(2)

(3)

(4)

(5)

?f∈Fk,?f′∈Fk,?k∈K

(6)

?f∈Fk,?f′∈Fk,?k∈K

(7)

?t∈T,?f∈Fk,?k∈K

(8)

2 啟發式隱枚舉算法

由于多機場系統的航班放行策略模型是NP難問題，因此考慮用啟發式方法進行求解，本文采用隱枚舉算法.起飛機場的離場容量和離場航路的各定位點容量是確定的.

圖1 啟發式隱枚舉法流程圖

隱枚舉算法首先通過對有共同離場定位點的各機場航班放行序列算法求出初始可行解，再通過機場優先級的設定，以及公共離場定位點各機場航班流的比例調節，進行放行時刻的最優化求解.算法中，航班的優先級根據延誤時段數動態提高，當預計到達離場定位點的時刻相同時，航班流量大的起飛機場擁有更高的優先級.

3 算例分析

交通運輸是一門實踐性非常強的學科[8].因此仿真采用VC++編寫仿真程序，原始數據選自2008年3月5日18∶00～19∶00廣州白云機場(CAN)和珠海三灶機場(ZUH)的航班數據，包括39個航班，離場跑道占用時間為2分鐘一個時隙.兩機場共同離場定位點LMN點有流量控制，流控限制時間從18∶00至19∶00，經過LMN點的航路時間間隔為8分鐘，即航跡間隔(Miles-In-Trail).19∶00后，流控消除，過LMN點航班只要滿足安全間隔即可.其他航路點沒有流量限制.廣州白云機場比珠海三灶機場的優先級高.

表1顯示了不同機場流量比例因子下對應機場的總延誤時間(CAN是廣州機場的三字代碼，ZUH是珠海機場的三字代碼).可以看出，經由LMN離場定位點的航班架數較多的起飛機場，其航班延誤的總時間較少，機場航班延誤總量與其經由公共離場定位點的航班流量呈現此消彼長的關系.因此，可以調整兩個機場通過LMN點的航班架次比例，優化空域資源配置，使多機場系統的延誤總量最小，提高空域使用的效率.

表1 優先級比例因子不同時機場延誤時間 min

由表2可知：對于航班預計起飛時間分布不緊湊的珠海機場來說，航班能按時起飛，不涉及地面等待，兩種算法對其航班的離場時刻影響不大；對航班預計起飛時間分布緊湊的廣州機場來說，HLEA較之FCFS算法使其平均延誤減少了34.84%、最大延誤時間減少17.95%，放行時刻配置獲得了較好的優化.

HLEA較之FCFS算法使兩機場的總延誤減少了26.35%、兩機場的平均延誤減少了26.37%，因此可以較大幅度提高多機場系統的整體運行效率.

表2 兩種時刻表的統計比較 min

4 結 語

以上對多機場系統的協調放行策略進行了探索性的研究，基于地面等待策略提出了多機場系統的航班放行策略模型，并采用啟發式隱枚舉算法對該模型進行了求解.與基于FCFS的算法相比較，隱枚舉算法不僅算法簡捷，還考慮了機場優先級和機場通過耦合定位點的流量比例，可以大幅度減少離場延誤和地面等待時間.其他協同決策的影響因素、多機場多跑道的使用、不同SID的相互影響因素等對離場放行的效應更加復雜，也是今后需要進一步探索和研究的課題.

參考文獻：

[1]孫霞林，曾華，熊德之，楊建華.基于排隊的服務系統的最小成本[J]．武漢工程大學學報，2008，30(1)：125-126.

[2]張兆寧，王莉莉．基于流量和滑動窗的空中交通管理動態排序法[J]．交通運輸工程與信息學報，2004，2(3)：22-25.

[3]胡雄鷹，熊茜，黎偉東.基于結點的網絡最大流算法[J].武漢工程大學學報，2009，31(12)：7-69.

[4]高海超，胡明華．基于最小延誤成本的進港航班公平排序[J]．交通運輸工程與信息學報，2008，6(4)：57-62.

[5]Atkin JAD，Burke EK， Greenwood JS, et al. Hybrid metaheuristics to aid runway scheduling at London Heathrow airport[J]，Transportation Science，2007，41(1)，90-106.

[6]陶冶，白存儒，由嘉．基于遺傳算法的起降航班動態排序模型的研究[J]．中國民航學院院報，2005，23(4) ：6-9.

[7]胡明華，李丹陽，韓松臣．被動空中交通流量管理中的動態排序算法[J]．南京航空航天大學學報，2000，32(1)：85-90.

[8]張培林，劉清，丁濤,等．交通運輸專業虛擬實習平臺的建設[J]．武漢工程大學學報，2009，31(9)：72-77.