劉君強 雷 凡 王英杰 左洪福

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

0 引 言

機場停機位的分配一般采用先到先服務的方式，這種落后的分配方式會帶來許多問題.學者們開始研究采用遺傳算法、禁忌搜索算法等來提高機場運行效率以降低航空公司運行成本.

當前我國樞紐機場面臨停機位的資源短缺和實際利用率很低的狀況.張晨等[1]通過減少前序延誤航班對后來的航班延誤的最小化為目標，研究了基于航班晚點傳播的機位分配模型.Wang等[2]利用著色的Petri網(wǎng)理論建立機場場面模型以及滑行路徑優(yōu)化算法.劉君強等[3]以最小延誤成本為約束，以航空公司時隙交替均衡為目標，提出了一種聯(lián)合決策的機位實時分配方法.

文獻[4]在基于滑行時間最優(yōu)的最優(yōu)滑行路徑的前提下，建立了規(guī)避沖撞的飛機動態(tài)路由分配的算法.文獻[5]提出了多目標數(shù)學模型，這是基于航空器的地面輪候時間最優(yōu)化設計的，并在此后建立了基于Agent的路徑優(yōu)化算法.文獻[6]通過借鑒遺傳禁忌算法研究了飛機地面滑行的優(yōu)化，這種算法能夠有效提升數(shù)據(jù)計算的精確度，減小了運算時間.當前的停機位分配研究主要以單目標函數(shù)為主，主要工作包括使用智能算法進行停機位求解，多跑道停機位分配，停機位優(yōu)化技術(shù),停機位分配仿真技術(shù)[7-11]等.

在多目標函數(shù)研究方面，丁建立等[12]利用組合優(yōu)化后的蟻群協(xié)同算法和滑動窗口算法，來協(xié)調(diào)路徑?jīng)_突約束并且合理的分配跑道資源.牟德一等[13]利用Floyd算法建立了混合整數(shù)線性規(guī)劃模型，這種模型可以將停機位或者滑行道入口的等待點不限時間等待的情況有效解決，將其分散到滑行跑道的各個節(jié)點上，這樣為每架飛機分配了最優(yōu)的滑行路徑.李倩雯[14]對航班到達延誤以及起飛延誤的差異化的分布特征進行量化研究，給出機位沖突概率的計算方法.楊順秀[15]以減少分配至遠機位的航班數(shù)、降低對原計劃方案的擾動性及減少旅客進港用時為目標，建立了面向延誤情景的停機位調(diào)度多目標模型.

以上研究很少涉及停機位和滑行道一體化分配問題.楊新涅等[16]充分考慮了航班停靠安排變更對機場運行秩序產(chǎn)生的干擾, 以對原計劃方案擾動最小為目標, 建立停機位及滑行路徑實時變更模型，而本文研究的停機位-滑行道一體化分配能夠保證機場在延誤下依然能夠高效運行.

1 延誤下滑行道-停機位實時分配建模

1.1 模型符號

1.2 一體化分配模型

延誤下的一體化分配模型為

(1)

大型水庫多被群山環(huán)繞，大多地段山體陡峭，植被良好，少有人生產(chǎn)活動跡象，水庫管理單位對庫區(qū)大部分土地并未進行確權(quán)劃界，也未采取隔離措施。但近年，人類活動范圍不斷外延，加之水庫管理單位對庫區(qū)土地管理不到位，目前土地權(quán)屬爭議較大。水庫確權(quán)劃界難度較大，主要存在以下問題：

(2)

(3)

(4)

Xij={0，1}i∈N，j∈M

(5)

(6)

Lij+ΔT-Rkj≤0

(i，j，k)∈{(i，j，k)|Rij

(7)

Rij-K1j>0，Lij-K2j<0i∈N，j∈M

(8)

ΔT，Rij，Lij，K1i，K2i，EШ，Шa，Шp>0

i∈N，j∈M，Ш，Шa，Шp∈W

(9)

α+β=1

(10)

本文給出了雙目標函數(shù)建模，可以同時解決滑行道分配和停機位分配.在建模中考慮到了旅客中轉(zhuǎn)時間和飛機滑行時間需要帶入系數(shù)運算，能更好地反映機場實際運行情況.

2 基因-蟻群一體化算法

2.1 描述

當前的停機位分配問題可以用基因算法進行求解.基因算法在進行停機位分配問題的研究的時候，需要經(jīng)過一定的改進.結(jié)合建模時的式(1)可以將適應度函數(shù)確定為

(11)

另外基因算法需要設置初始種群大小、群體規(guī)模最大數(shù)量、終止條件、交叉概率，以及變異概率等.

機場滑行道優(yōu)化問題可以用蟻群算法進行求解.當前已有很多文獻用蟻群算法求解滑行道分配問題，利用圖論的方法進行機場停機位分配建模，然后利用蟻群算法收斂性好的特點進行全局求解.蟻群算法的主要步驟包括：①初始化A(t){初始化蟻群}；②評價A{根據(jù)目標函數(shù)對每只螞蟻做出評價}；③釋放信息素{適應度越高，螞蟻釋放信息素越多}；④信息素揮發(fā) {隨時間消散}；⑤求解.

2.2 本文提出的算法

為了求解停機位-滑行道一體化分配問題，結(jié)合基因算法和蟻群算法的優(yōu)點，設計了基因-蟻群算法，流程見圖1.

圖1 基因蟻群算法流程圖

3 實例驗證

本文仿真數(shù)據(jù)取自國內(nèi)某一小型機場，機場中擁有1條跑道，2個航站樓，22個停機位，多條常用滑行道，以及分布在兩個航站樓區(qū)域的37個航班進行仿真模擬見圖2.

圖2 機位分布圖

本文設定大型飛機耗油量為45 kg/min，中型飛機耗油量為30 kg/min，小型飛機耗油量為15 kg/min，燃油價格為每7元/kg.旅客中轉(zhuǎn)等待成本為0. 5元/min，設α=0.55，β=0.45，航班的編號以及航班信息見表1～4.

表1 T1航站樓航班停機位預分配表

根據(jù)圖2可知，T1航站樓A區(qū)域有5個停機位，B區(qū)域有6個停機位，結(jié)合表1中的航班預分配情況我們可以發(fā)現(xiàn)，航班在1、2、3、4號停機位的離港時的滑行路徑為KA-K-T-L，在6號停機位的離港時的滑行路徑為M-K-T-L，在8號停機位的離港時的滑行路徑為KB-K-T-L，當前時刻有8個航班被分配到了這里.

由表2可知，當前時刻有10個航班被預分配到了這里，航班在1、3號停機位的離港時的滑行路徑為KA-K-T-L，航班在6、7號停機位的離港滑行路徑為M-K-T-L，航班在8、9、10號停機位的離港滑行路徑為KB-K-T-L.

表2 T1航站樓航班停機位預分配表

表3 T2航站樓航班停機位預分配表

由表3可知，T2航站樓A區(qū)域中有5個停機位，B區(qū)域有6個停機位，當前時刻有9個航班被預分配到了這里，航班在12、13、14、15、16號停機位的離港滑行路徑為T2-T-L.

表4 T2航站樓B域航班停機位預分配表

由表4可知，T2航站樓當前時刻有10個航班被預分配到了這里，表中的各個航班的停機位的離港滑行路徑均為T1-T-L.

在已經(jīng)知道預先分配的情況下，根據(jù)空管部門發(fā)布的航班延誤情況，見表5～6，結(jié)合基因-蟻群算法進行求解.

表7 再分配后機位指派表格(左邊T1航站樓，右邊T2航站樓)

由于涉及油耗價格方面，發(fā)現(xiàn)油耗對比并不明顯，所以將油耗單獨提出來進行對比.旅客中轉(zhuǎn)時間損失比較大，所以在對比的時候，也需要提出來進行單獨對比，否則感覺對比效果不明顯，由于滑行時間不能準確體現(xiàn)出涉及航空公司及機場利益，所以將滑行時間通過計算變?yōu)楹娇展九c機場更為關注的滑行油耗問題，以便更好的體現(xiàn)航班延誤情況下機場滑行道停機位的再分配，從而給航空公司和機場避免很多不必要的消耗.

根據(jù)上面的運算過程可以得出，經(jīng)過一體化分配后的滑行時間為792 min，滑行油耗23 760 kg,旅客中轉(zhuǎn)等待時間448 000 min，總共耗費390 320元，這是在延誤情況下停機位再分配得到的數(shù)據(jù).采用先到先分配原則的方法進行數(shù)據(jù)計算，得到滑行時間為891 min，滑行油耗為26 730 kg,旅客中轉(zhuǎn)等待時間為462 000 min，總共耗費418 110元.

為了能夠更加明顯的觀察出優(yōu)化前和優(yōu)化后在各個變量上的變化，將優(yōu)化前和優(yōu)化后的各個變量進行橫向比較分析見圖3～5.

圖3 滑行耗油圖

圖4 旅客中轉(zhuǎn)等待時間圖

圖5 總花費圖

由圖3～5中可知，本文所提出的方法在旅客中轉(zhuǎn)時間、滑行消耗上均有減少，特別是總消耗上有明顯的減少，驗證本文提出的方法具有更好的性能.

4 結(jié) 束 語

本文研究基于延誤下的機場滑行道停機位分配，提出了滑行道和停機位一體化分配模型.由于單一算法無法對滑行道機位一體化分配進行求解，提出了基因-蟻群混合算法來求解延誤下機場滑行道機位分配的計算，通過本文所提出的模型和算法，分別計算出優(yōu)化前和優(yōu)化后的滑行時間、滑行耗油、旅客中轉(zhuǎn)等待時間以及總耗費來進行橫向比較，使用Matlab進行編碼進行求解，結(jié)合國內(nèi)機場設計了仿真應用實例，得到的仿真模擬結(jié)果基本與實際情況相符合，表明本文所提出的方法是有效可行的.