基于運(yùn)行安全的停機(jī)位再分配問題研究

劉長有，曹 強(qiáng)

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

基于運(yùn)行安全的停機(jī)位再分配問題研究

劉長有，曹 強(qiáng)

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

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

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

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

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

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

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

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

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

1）停機(jī)位被占用時間的均衡性

航班在停機(jī)位停留時間為

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

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

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

2）航班機(jī)位分配的擾動性

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

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

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

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

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

1.2 基本約束條件

1）獨(dú)占性約束

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

2）緊鄰航班約束

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

3）航班-機(jī)位類型匹配約束

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

4）安全間隔約束

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

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

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

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

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

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

2）停機(jī)位再分配模型的多目標(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è)計(jì)

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

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

2）按公式更新每個粒子的速度和位置，并計(jì)算其個體最佳位置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個個體進(jìn)入下一代，轉(zhuǎn)第2）步。

3 仿真實(shí)驗(yàn)結(jié)果與分析

3.1 停機(jī)位初次分配

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

3.2 停機(jī)位再分配

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

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

表1 航班計(jì)劃變動信息Tab.1 Changed flight information

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

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

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

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

4 結(jié)語

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

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

[2]常 鋼.民航機(jī)場停機(jī)位分配與優(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ī)場停機(jī)位分配問題的遺傳算法[J].科學(xué)技術(shù)與工程，2010，10（1）：135-139.

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

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

[7]劉長有，翟乃鈞.避免航班雙推沖突的多目標(biāo)停機(jī)位優(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é)基金項(xiàng)目（60979007）

劉長有（1956—），男，河北盧龍人，教授，博士，研究方向?yàn)榉泵C(jī)場運(yùn)行管理與調(diào)度優(yōu)化.