劉君強(qiáng) 雷 凡 王英杰 左洪福

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

0 引 言

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

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

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

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

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

1 延誤下滑行道-停機(jī)位實(shí)時分配建模

1.1 模型符號

1.2 一體化分配模型

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

(1)

大型水庫多被群山環(huán)繞，大多地段山體陡峭，植被良好，少有人生產(chǎn)活動跡象，水庫管理單位對庫區(qū)大部分土地并未進(jìn)行確權(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)

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

2 基因-蟻群一體化算法

2.1 描述

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

(11)

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

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

2.2 本文提出的算法

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

圖1 基因蟻群算法流程圖

3 實(shí)例驗證

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

圖2 機(jī)位分布圖

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

表1 T1航站樓航班停機(jī)位預(yù)分配表

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

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

表2 T1航站樓航班停機(jī)位預(yù)分配表

表3 T2航站樓航班停機(jī)位預(yù)分配表

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

表4 T2航站樓B域航班停機(jī)位預(yù)分配表

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

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

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

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

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

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

圖3 滑行耗油圖

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

圖5 總花費(fèi)圖

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

4 結(jié) 束 語

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