劉長有，曹 強

（中國民航大學(xué)空中交通管理學(xué)院，天津 300300）

基于運行安全的停機位再分配問題研究

劉長有，曹 強

（中國民航大學(xué)空中交通管理學(xué)院，天津 300300）

分析了基于運行安全的停機位再分配問題。首先，在該多目標(biāo)優(yōu)化問題中考慮了3個目標(biāo)函數(shù)，即分配到停機坪的航班數(shù)量最少、停機位分配的擾動最小和停機位被占用時間均衡。然后在停機位再分配模型中引入了安全性約束以避免潛在的航班雙推沖突，并采用粒子群遺傳算法對問題進行優(yōu)化求解。最后，結(jié)合算例分析，檢驗了模型和算法的有效性。

機場停機位；最優(yōu)化；再分配；粒子群遺傳算法

按照航班計劃合理地分配停機位，是提高機場運行效率的重要途徑。當(dāng)發(fā)生航班延誤時，則需要在停機位預(yù)分配優(yōu)化方案的基礎(chǔ)上進行動態(tài)調(diào)度，即需考慮停機位的再分配問題。

在停機位分配優(yōu)化問題的研究中，主要是以旅客行走距離最小、停機位的空閑時間最小、近機位的使用率最大等為目標(biāo)函數(shù)進行建模，并采用排序算法、遺傳算法和禁忌搜索等算法進行優(yōu)化[1-5]。這些研究對停機位的預(yù)分配計劃考慮的比較完整，但沒有考慮對航班延誤應(yīng)急處理的停機位再分配問題，并且僅考慮了運行效率問題，而沒考慮運行安全問題。

文獻[6]采用禁忌搜索算法研究了停機位的再分配問題，文獻[7]在停機位分配中引入避免航班雙推沖突的安全性約束，初步研究了兼顧運行安全和運行效率的停機位分配優(yōu)化問題。本文則在上述研究的基礎(chǔ)上，研究了避免雙推沖突的停機位再分配問題，即在對航班延誤應(yīng)急處理的停機位再分配問題中，仍然考慮安全性約束以避免潛在的航班雙推沖突。

1 數(shù)學(xué)模型

假設(shè)有M個停機位，在一段時間T內(nèi)，有N架航班要進行停機位分配，已知航班的預(yù)計進離場時間、地面活動時間及機型大小信息。

1.1 目標(biāo)函數(shù)分析

1）停機位被占用時間的均衡性

航班在停機位停留時間為

式（1）表示航班i在停機位k的停留時間。

如果近機位資源總體使用不均衡，那么是對停機位資源的浪費，從而函數(shù)為

其中：F1為飛機占用停機位總時間的平方和。minF1使得機位占用時間盡量均衡。

2）航班機位分配的擾動性

如果有航班延誤或者取消，原有的機位分配將會被打亂，需要再分配停機位。若再分配時，又被分配到原來機位，則變量xi=0，否則xi=1。從而函數(shù)為

其中：F2為受擾動的航班數(shù)。minF2使停機位再分配時所受到擾動性最小。

3）分配到停機坪的航班數(shù)最少

當(dāng)航班密度較大時，可能會出現(xiàn)部分航班被分配到停機坪的情況，從而導(dǎo)致旅客的滿意度被降低，所以有必要將分配到停機坪的航班數(shù)量盡量減少作為優(yōu)化計算的目標(biāo)。如分配到停機坪，則變量pi=1；如果可分配到一個停機位，則pi=0。從而函數(shù)為

其中：F3為分配到停機坪上的航班數(shù)。min F3使分配到停機坪上的航班數(shù)最少。

1.2 基本約束條件

1）獨占性約束

式（5）表示每個航班僅需分配一個停機位，yik是航班i被分配到停機位k，是一個二進制變量，當(dāng)且僅當(dāng)航班i被分配到停機位k時，yik=1，否則yik=0。

2）緊鄰航班約束

安排同一停機位的航班像一個隊列，有進有出。式（6）表示緊鄰某個航班之前至多只能有一個航班，緊鄰其后也至多只能有一個航班。當(dāng)航班i和航班j被分配到停機位k而且航班i是航班j的直接前鄰航班時zijk為1，否則為0。

3）航班-機位類型匹配約束

其中：gk為停機位k的屬性值；fi為航班i機型屬性值。式（7）表示航班機型與機位類型的匹配約束，停機位只能停放允許的航班機型。

4）安全間隔約束

其中：aj為航班j的計劃進場時間；di為航班i的計劃離場時間。式（8）表示分配到同一停機位k的相鄰航班i和航班j必須要滿足一定的時間間隔δ的約束，以保證地面安全有效的運行。

5）避免潛在的雙推沖突安全約束

當(dāng)被分配到相鄰?fù)C位的2個航班的離港時間過于接近時，則可能存在潛在的雙推沖突。式（9）中β為相鄰?fù)C位的航班離港時間的最小間隔。

1.3 多目標(biāo)規(guī)劃模型

1）停機位初次分配模型的目標(biāo)函數(shù)為

在基本約束條件（5）~（8）中，增加安全性約束條件（9）。

2）停機位再分配模型的多目標(biāo)函數(shù)為

其中，Pi（i=1，2，3）為優(yōu)先權(quán)。同樣在基本約束條件（5）~（8）中增加安全性約束條件（9）。

對于多目標(biāo)函數(shù)F＇，采用分優(yōu)先級處理的方法，即先求解優(yōu)先級數(shù)高的目標(biāo)函數(shù)，然后再求解次優(yōu)先級數(shù)的目標(biāo)函數(shù)，以此類推。

2 算法設(shè)計

本文擬采用粒子群遺傳算法[8]求解機場停機位再分配問題，以達到優(yōu)化分配的效果。根據(jù)停機位分配的特點，本文設(shè)計了如下方案：初始化種群、設(shè)計適應(yīng)度函數(shù)、更新粒子的速度和位置、選擇、交叉、變異運算。

1）初始化停機位分配方案，確定粒子群中所有n=100個個體位置及其速度，搜索個體的最佳位置Pi，并將個體最佳位置的最優(yōu)值設(shè)定為群體最佳位置Pg初始位置，設(shè)置迭代次數(shù)0

2）按公式更新每個粒子的速度和位置，并計算其個體最佳位置Pi和群體最佳位置Pg；

3）如果滿足終止條件輸出最優(yōu)解Pg，終止程序，否則繼續(xù)第4）步；

4）選出m個個體，對它們執(zhí)行交叉操作，得到m＇個新個體，與選出m個個體比較，得到適度值大的m個個體；

5）對m-s個個體執(zhí)行變異操作，得到（m-s）＇個新個體，與m-s個個體比較，選擇適應(yīng)度高的m-s個個體，則新的m-s個個體進入下一代，轉(zhuǎn)第2）步。

3 仿真實驗結(jié)果與分析

3.1 停機位初次分配

算例采用某機場的20個停機位對116個航班的機位再分配問題，其中1~15號為大機位，允許停放大機型或者中機型，16~20為小機位，允許停放中機型。航班數(shù)據(jù)見文獻[6]中的航班計劃信息。同一個機位相鄰2架飛機的最小停機位時間間隔δ=30 min，β= 1 min。交叉概率為0.75，變異概率為0.25。航班機型屬性值，數(shù)字1表示中機型，數(shù)字2表示大機型。用粒子群遺傳算法得到停機位分配的結(jié)果，如圖1所示。

3.2 停機位再分配

在上述116個航班中隨機產(chǎn)生20%的延誤航班和3%的取消航班，其中28、57、66號航班被取消，延誤航班時刻信息如表1所示。

圖1 停機位初次分配模擬圖Fig.1 Simulation chart of initial gate assignment

表1 航班計劃變動信息Tab.1 Changed flight information

采用粒子群遺傳算法得到的停機位再分配結(jié)果，如圖2所示。

在圖2中，與圖1有16處不同（包括3個取消航班），占總航班量的13.79%（其中延誤或者取消航班有5個），其中有1個航班被分配到了停機坪上，與停機位初次分配結(jié)果不同，如表2所示。停機位再分配的結(jié)果兼顧了系統(tǒng)的運行安全和效率，優(yōu)化效果較為理想。

表2 相同航班所分配的不同停機位Tab.2 Different gates between two assignments for same flights

圖2 停機位再分配模擬圖Fig.2 Simulation chart of gate reassignment

4 結(jié)語

基于運行安全的停機位再分配問題，既要考慮在航班延誤或取消的情況下動態(tài)調(diào)度，又要考慮兼顧機場運行的安全和效率。本文通過在模型中引入安全性約束，將機場停機位再分配與避免潛在的航班雙推沖突有機結(jié)合，并采用粒子群遺傳算法進行問題求解。結(jié)合航班計劃的算例表明了模型和算法的有效性，即在保證機場運行安全的前提下，盡量減少由航班延誤帶來的停機位預(yù)分配計劃擾動，并提高系統(tǒng)的運行效率。

[1]文 軍，孫 宏，徐 杰，等.基于排序算法的機場停機位分配問題研究[J].系統(tǒng)工程，2004，22（7）：102-106.

[2]常 鋼.民航機場停機位分配與優(yōu)化技術(shù)研究[D].西安：西北工業(yè)大學(xué)，2006.

[3]YAN S Y，HUO C M.Optimization of multiple objective gate assignments[J].Transportation Research Part A：Policy and Practice，2001，35（5）：413-432.

[4]文 軍.機場停機位分配問題的遺傳算法[J].科學(xué)技術(shù)與工程，2010，10（1）：135-139.

[5]尹嘉男，胡明華，趙 征.多跑道機場停機位分配仿真模型及算法[J].交通運輸工程學(xué)報，2010，97（2）：187-203.

[6]衛(wèi)東選，劉長有.機場停機位再分配問題[J].南京航空航天大學(xué)學(xué)報，2009，41（2）：257-261.

[7]劉長有，翟乃鈞.避免航班雙推沖突的多目標(biāo)停機位優(yōu)化[C]//第29屆中國控制會議論文集，北京，2010：1082-1086.

[8]SHI X H，LU Y H，ZHOU C G，et al.Hybrid Evolutionary Algorithms Based on PSO and GA[C]//Proceedings of the 2003 Congress on Evolutionary Computation，Canberra，Australia，2003：2400-2405.

（責(zé)任編輯：楊媛媛）

On gate reassignment for aircraft based on operational safety

LIU Chang-you，CAO Qiang
（College of Air Traffic Management，CAUC，Tianjin 300300，China）

Gate reassignment for aircraft based on operational safety is researched.First，three objectives are proposed as following the minimization of flights assigned to the apron，the disturbance of airport gates and the nonbalance of gate utilization ratio.Then a safety restraint is introduced into the model of gate reassignment and the particle swarm genetic algorithm is applied to solve the model.Finally，an example with the realistic data is implemented to show the validity of the model and the algorithm.

airport gate；optimization；reassignment；particle swarm genetic algorithm

V351；TP18

：A

：1674-5590（2014）01-0015-04

2012-12-10；

：2013-02-25

：國家自然科學(xué)基金項目（60979007）

劉長有（1956—），男，河北盧龍人，教授，博士，研究方向為繁忙機場運行管理與調(diào)度優(yōu)化.