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

呂雙回, 胡明華

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

0 引 言

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

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

1 多機場系統(tǒng)航班放行策略模型

模型的目標函數(shù)為

(1)

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

模型約束為：

(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 啟發(fā)式隱枚舉算法

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

圖1 啟發(fā)式隱枚舉法流程圖

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

3 算例分析

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

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

表1 優(yōu)先級比例因子不同時機場延誤時間 min

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

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

表2 兩種時刻表的統(tǒng)計比較 min

4 結(jié) 語

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

參考文獻：

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

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

[3]胡雄鷹，熊茜，黎偉東.基于結(jié)點的網(wǎng)絡最大流算法[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]陶冶，白存儒，由嘉．基于遺傳算法的起降航班動態(tài)排序模型的研究[J]．中國民航學院院報，2005，23(4) ：6-9.

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

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