考慮時間執(zhí)行偏差的多目標(biāo)機(jī)位分配問題

朱承元，王志巍，王毅鵬

（1.中國民航大學(xué)空中交通管理學(xué)院，天津 300300；2.中國國際航空股份有限公司運(yùn)行控制中心，北京 101312）

機(jī)場場面運(yùn)行復(fù)雜多變，場面滑行、場面車輛調(diào)度以及機(jī)場的天氣情況等因素都會影響機(jī)位的實(shí)際運(yùn)行時間，基于機(jī)位計劃運(yùn)行時間產(chǎn)生的機(jī)位分配方案與實(shí)際運(yùn)行存在較大的時間執(zhí)行偏差。由于機(jī)位分配方案的關(guān)聯(lián)性，當(dāng)執(zhí)行偏差過大時，會增大場面車輛的調(diào)度頻率，從而增加指揮的難度，同時增加場面沖突的次數(shù)，不僅會影響機(jī)場運(yùn)行效率，也增加機(jī)場運(yùn)行風(fēng)險。因此，對減少機(jī)位時間執(zhí)行偏差問題的探討與研究是當(dāng)前提高機(jī)位分配效率與安全性的關(guān)鍵。

張晨等[1]提出了基于概率論的晚點(diǎn)傳播方法，以連續(xù)同機(jī)位航班間隔最小為目標(biāo)并通過禁忌搜索算法進(jìn)行求解；Dorndorf等[2]將最大化的航班緩沖時間作為目標(biāo)，減少場面運(yùn)行的隨機(jī)擾動影響；衛(wèi)東選等[3]提出了主動避免潛在沖突的模型，在相鄰機(jī)位之間加入了安全時間間隔，以機(jī)位空閑時間均衡為目標(biāo)，將其轉(zhuǎn)化為線性問題求解；李軍會等[4]統(tǒng)計分析不同航空公司的延誤水平對航班時間間隔進(jìn)行了分析，以機(jī)位沖突概率最小為目標(biāo)，使用貪婪禁忌算法[5]求解；馮霞等[6]以北京首都國際機(jī)場實(shí)際運(yùn)行數(shù)據(jù)為依據(jù)，分析時間偏差規(guī)律，建立了緩沖時間成本函數(shù)，使用禁忌搜索算法進(jìn)行求解；孫淑光等[7]以最小空閑時間、最大機(jī)位使用效率為目標(biāo)，將遺傳算法與禁忌搜索算法組合求解并與單一禁忌搜索算法進(jìn)行對比。

以上國內(nèi)外學(xué)者針對機(jī)位分配方案執(zhí)行偏差較大的問題都在機(jī)位計劃運(yùn)行時間的基礎(chǔ)上加入一定的緩沖時間，減少滑行沖突、場面車輛調(diào)度、機(jī)場天氣等隨機(jī)事件對機(jī)位分配方案的影響。這種加入緩沖時間的方法一定程度上減少了隨機(jī)事件對機(jī)位分配方案產(chǎn)生的擾動以及場面滑行中產(chǎn)生沖突的概率，增加了分配方案的魯棒性，但加入緩沖時間也增加了航班占用機(jī)位的時間，從而一定程度上增加了機(jī)場運(yùn)行成本，降低了機(jī)場運(yùn)行效率，機(jī)位時間執(zhí)行偏差大的問題并沒有得到有效解決。

為減少機(jī)位計劃運(yùn)行時間的執(zhí)行偏差，使用全空域與機(jī)場建模工具（TAAM，total airspace and airport modeller）建立跑道、滑行、機(jī)坪一體化機(jī)場場面模型，模擬場面實(shí)際運(yùn)行情況，對計劃時間進(jìn)行模擬仿真，優(yōu)化生成機(jī)位時間執(zhí)行偏差較小的初始機(jī)位分配方案，再通過基于熵權(quán)法的禁忌搜索算法求解兼顧旅客、機(jī)場、航空公司三方面效益的多目標(biāo)模型。

1 多目標(biāo)機(jī)位分配模型

1.1 模型假設(shè)及符號定義

針對多目標(biāo)機(jī)位分配模型進(jìn)行如下假設(shè)：

（1）運(yùn)行開始時所有機(jī)位可以使用；

（2）機(jī)場擁有充足的機(jī)位資源，可以為執(zhí)行每一個航班的飛機(jī)分配一個可行的機(jī)位資源；

（3）機(jī)位分配優(yōu)化所需的基本信息是完備、確定、已知的；

（4）飛機(jī)從脫離跑道滑行至任一機(jī)位的滑行路徑固定且已知。

模型變量定義如表1 所示。

表1 模型變量定義Tab.1 Definition of variable of the proposed model

1.2 模型建立

機(jī)位分配問題涉及到旅客、機(jī)場、航空公司三方面利益，因此對旅客行走距離、機(jī)場運(yùn)行效率及安全、航空公司效益等方面的單一變量建模并不能較好地解決機(jī)位分配的實(shí)際問題。為兼顧三方需求，分別構(gòu)造基于旅客、機(jī)場、航空公司利益的目標(biāo)函數(shù)。參考相關(guān)文獻(xiàn)[8-9]，分別以旅客總行走時間、總機(jī)位占用不均衡度、各航空公司航空器平均滑行距離均衡為目標(biāo)函數(shù)，并加入相鄰機(jī)位的安全間隔等約束建立多目標(biāo)機(jī)位分配模型。

1.2.1 目標(biāo)函數(shù)

l 為航空公司數(shù)量；| | 表示集合中元素的個數(shù)；式（1）為旅客目標(biāo)，表示旅客登機(jī)總用時最少；式（2）為機(jī)場效率目標(biāo)，表示機(jī)場所有機(jī)位使用時間的不均衡度最小；式（3）為航空公司公平性目標(biāo)，表示各航空公司平均滑行距離的不均衡度最小。

1.2.2 約束條件

式中：約束（4）表示航空器只能占用一個停機(jī)位；約束（5）表示前后連續(xù)進(jìn)入相同機(jī)位的航班順序；約束（6）表示同一機(jī)位進(jìn)出避免沖突的安全時間間隔；約束（7）～（9）表示相鄰機(jī)位進(jìn)出航班之間3 種情況的安全時間間隔；約束（10）表示航班機(jī)型符合機(jī)位可停靠機(jī)型；約束（11）～（13）表示模型各參數(shù)的取值范圍。

2 算法實(shí)現(xiàn)

2.1 算法設(shè)計

通過TAAM 產(chǎn)生機(jī)位分配的初步方案，并基于熵權(quán)法[10]使用禁忌搜索算法實(shí)現(xiàn)多目標(biāo)機(jī)位分配模型求解，算法思想如下。

（1）為解決分配方案執(zhí)行偏差較大的問題，使用TAAM 仿真模型根據(jù)原始計劃航班信息數(shù)據(jù)進(jìn)行模擬仿真。在TAAM 中加入機(jī)場實(shí)際起降、滑行、?？恳?guī)則，并設(shè)置滑行路徑、速度、機(jī)位使用限制、跑道方向等約束，加入滑行油量、滑行速度的隨機(jī)性，滑行沖突的自動解脫，使仿真模型更精確地模擬機(jī)場實(shí)際運(yùn)行。根據(jù)上述運(yùn)行條件利用TAAM 對計劃機(jī)位運(yùn)行時間進(jìn)行初步優(yōu)化，產(chǎn)生與實(shí)際運(yùn)行場景機(jī)位時間執(zhí)行偏差較小的機(jī)位運(yùn)行時間，并產(chǎn)生沒有優(yōu)化要求但實(shí)際可行的初始機(jī)位分配方案，作為禁忌搜索算法求解的初始方案。

（2）為解決多目標(biāo)求解過程中人為因素影響較大的問題，在禁忌搜索過程中加入熵權(quán)法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題進(jìn)行求解。該方法可以避免專家打分法、分層序列法[11]等由于打分或優(yōu)先級的確定等人為因素帶來的影響，使權(quán)重計算更具有客觀公正性。

（3）為加快尋優(yōu)速度，改進(jìn)隨機(jī)選擇的鄰域搜索方法，將機(jī)位代號按照機(jī)位占用時間由長至短進(jìn)行排序。插入操作，選擇排序靠前的機(jī)位作為操作對象，隨機(jī)選擇該機(jī)位的幾個航班插入排序靠后的機(jī)位；互換操作，選擇排序靠前和靠后的兩個機(jī)位作為操作對象，分別從兩機(jī)位隨機(jī)選擇一個航班進(jìn)行機(jī)位互換。

2.2 算法步驟

機(jī)位分配算法步驟如下。

步驟1將計劃航班信息和滑行、機(jī)位等參數(shù)輸入TAAM中，仿真得到一個可行的初始解x0=（α1，α2，…，αm），m 為參與分配的航班數(shù)，αi表示i 號航班?？康臋C(jī)位代號。

步驟2將初始解輸入禁忌算法，并加入禁忌表。

步驟3設(shè)置終止準(zhǔn)則final，即最大迭代次數(shù)。

步驟4判斷當(dāng)前迭代次數(shù)fi，若滿足fi≥final 則輸出結(jié)果，不滿足則繼續(xù)步驟5。

步驟5從當(dāng)前解出發(fā)搜索其鄰域，通過下列兩種操作分別得到兩個候選解。

計算出當(dāng)前解在各個機(jī)位的占用時間，并排序Tk≥…≥Tl：

1）插入操作

將解分配在k 機(jī)位的i 號航班，重新分配至d 機(jī)位，得到x1解，即

2）互換操作

將x0解分配在k 機(jī)位的e 號航班與分配在l 機(jī)位的i 號航班進(jìn)行機(jī)位互換，得到x1解，即

按照機(jī)位排序依次搜索鄰域，選取候選解x1，x2，x3，x4。

步驟6對多目標(biāo)模型利用熵權(quán)法[9]處理Zi，1≤i≤3，x∈{x1，x2，x3，x4}，生成決策矩陣（Z1，Z2，Z3）×（x1，x2，x3，x4）T。對決策矩陣進(jìn)行歸一化處理，并計算信息熵、權(quán)重向量（λ1，λ2，λ3），得到候選方案的當(dāng)前綜合屬性值，即

步驟7若滿足藐視準(zhǔn)則wi≥w，w 為3 個目標(biāo)函數(shù)值的綜合特征值，結(jié)果直接作為下次搜索的當(dāng)前解；如果不滿足，則將非禁忌對象的各候選解通過結(jié)果排序篩選出當(dāng)前最優(yōu)解xi。

步驟8將xi代入步驟4 繼續(xù)搜索。

算法流程如圖1 所示。

圖1 算法流程圖Fig.1 Flow chart of algorithm

3 實(shí)例計算

3.1 數(shù)據(jù)來源及參數(shù)設(shè)置

選取蘭州中川國際機(jī)場2019 年某日8 點(diǎn)—24 點(diǎn)中國國際航空股份有限公司、中國南方航空集團(tuán)有限公司、中國東方航空集團(tuán)有限公司、海南航空控股股份有限公司、四川航空股份有限公司5 個航空公司共50 個航班。航班計劃信息如表2 所示（只列出部分航班信息）。

表2 航班計劃信息表Tab.2 Information table of flight plan

機(jī)場使用18 號跑道運(yùn)行，設(shè)定所有航班通過A5快速脫離道脫離，起飛通過A1 滑行道進(jìn)入跑道等待起飛，滑行距離按照上述運(yùn)行計算。所有機(jī)位全天開放，按照該機(jī)場管制實(shí)際運(yùn)行規(guī)定，上述航空公司可使用機(jī)位（近機(jī)位101～107，遠(yuǎn)機(jī)位201～207）及機(jī)位信息如表3 所示。為了便于計算求解，將航班按表格順序編號為1～50（只列出部分機(jī)位數(shù)據(jù)），將停機(jī)位101～107、201～207 分別對應(yīng)機(jī)位1～7、8～14。

表3 機(jī)位信息表Tab.3 Information table of gate

其他條件：飛機(jī)滑行速度為15 km/h；由于近、遠(yuǎn)機(jī)位旅客登機(jī)方式不同，近機(jī)位旅客行走速度按照正常人5 km/h 計算，遠(yuǎn)機(jī)位旅客乘坐擺渡車按照平均行駛速度15 km/h 計算；避免沖突的安全間隔，分別取同機(jī)位安全間隔15 min，相鄰機(jī)位安全間隔5 min；禁忌搜索算法循環(huán)迭代次數(shù)500 次。

3.2 過程與結(jié)果

圖2 的TAAM 仿真運(yùn)行界面中，棕色數(shù)字為機(jī)位代號，白色為航空器呼號，紅色線條為滑行道中線，淡藍(lán)色矩形為跑道。

圖2 TAAM 仿真運(yùn)行界面Fig.2 Operation interface of TAAM simulation

通過TAAM 對機(jī)位預(yù)計時間處理后，機(jī)位初始分配方案甘特圖如圖3 所示。

圖3 TAAM 初始分配方案甘特圖Fig.3 Gantt chart of TAAM initial solution

禁忌搜索算法每次迭代產(chǎn)生的綜合屬性值以及最佳綜合屬性值出現(xiàn)的迭代序列如圖4 所示。

圖4 綜合屬性值變化曲線Fig.4 Change curves of synthetic attribution value

算法求解結(jié)果的機(jī)位分配方案如圖5 所示。初始解、最終解等迭代解的各目標(biāo)值結(jié)果如表4 所示。

圖5 優(yōu)化結(jié)果甘特圖Fig.5 Gantt chart of optimized results

表4 算法結(jié)果Tab.4 Resolution results of algorithm

3.3 機(jī)位時間執(zhí)行偏差驗(yàn)證

將最終機(jī)位分配方案輸入TAAM 仿真模型，模擬實(shí)際運(yùn)行情況下該分配方案的機(jī)位運(yùn)行時間。以TAAM 仿真驗(yàn)證模型機(jī)位運(yùn)行時間為基準(zhǔn)，對比計劃時間、算法最終解與其執(zhí)行偏差，如圖6 和圖7 所示。

圖6 進(jìn)入機(jī)位時刻執(zhí)行偏差圖Fig.6 Time execution deviation for entering the gate

圖7 離開機(jī)位時刻執(zhí)行偏差圖Fig.7 Time execution deviation for leaving the gate

3.4 結(jié)果分析

從圖4 中Matlab 產(chǎn)生的目標(biāo)曲線可以看出，算法迭代次數(shù)到達(dá)33 次時，綜合屬性值達(dá)到了最佳，得到各目標(biāo)值結(jié)果，如表4 所示，旅客總登機(jī)時間下降了8%，機(jī)位占用的不均衡度下降了7%，航空公司滑行的不均衡度下降了13%。旅客登機(jī)耗時、機(jī)場機(jī)位使用的均衡性、航空公司的公平性都得到了一定的改善。圖6—圖7 的TAAM 驗(yàn)證結(jié)果表明，優(yōu)化后執(zhí)行偏差明顯小于機(jī)位計劃時間產(chǎn)生的執(zhí)行偏差，且與TAAM模擬實(shí)際時間執(zhí)行偏差較小。

4 結(jié)語

使用TAAM 對機(jī)位計劃運(yùn)行時間進(jìn)行優(yōu)化處理可以有效減小計劃時間產(chǎn)生的執(zhí)行偏差，且可以避免使用增加緩沖時間方法而產(chǎn)生額外的機(jī)位占用時間，在降低執(zhí)行偏差的基礎(chǔ)上，使用較客觀的熵權(quán)法，綜合旅客、機(jī)場、航空公司三方面利益進(jìn)行機(jī)位分配策略的優(yōu)化。在保證旅客登機(jī)耗時較短、航空公司較公平的基礎(chǔ)上，提高了機(jī)位分配方案與實(shí)際運(yùn)行的匹配程度，增加了分配方案的抗干擾性，有效地減少場面指揮、車輛調(diào)度、人員配置的工作負(fù)荷，從而提高了機(jī)場的運(yùn)行效率。