基于安全約束的停機(jī)位分配問題的研究

陳 前， 樂美龍

(上海海事大學(xué) 科學(xué)研究院， 上海 201306)

?

基于安全約束的停機(jī)位分配問題的研究

陳 前*， 樂美龍

(上海海事大學(xué) 科學(xué)研究院， 上海 201306)

停機(jī)位在機(jī)場運(yùn)作系統(tǒng)中扮演著重要的角色，如果沒有制定高效合理的停機(jī)位分配方案，航班便不能按原計劃準(zhǔn)時到達(dá)預(yù)定的停機(jī)位.隨著航班數(shù)量的不斷增加，機(jī)場運(yùn)作效率的提高面臨重大挑戰(zhàn)，因此需要對航班進(jìn)行停機(jī)位的合理分配.同時，合理地控制各個停機(jī)位的空閑時間可以避免相鄰機(jī)位航班的運(yùn)行沖突.考慮到機(jī)場系統(tǒng)的安全運(yùn)行約束，建立避免沖突的停機(jī)位分配模型，引入實例，采用遺傳算法進(jìn)行求解，得出停機(jī)位分配的甘特圖，驗證了模型的合理性與有效性，更加貼近實際，提高了機(jī)場運(yùn)行效率.

航空運(yùn)輸管理； 機(jī)位分配； 效率； 安全運(yùn)行； 遺傳算法

合理的機(jī)位分配方案可以幫助航空公司減少由于機(jī)位分配而造成的時間延誤，保持其所制定的固定航班時刻，也可以減少旅客從機(jī)位到機(jī)位以及機(jī)位到出、入口的步行時間和距離，提高旅客滿意度.雖然民航得到了迅速的發(fā)展，但基礎(chǔ)設(shè)施明顯不足，限制了機(jī)場運(yùn)營規(guī)模的擴(kuò)大，因此停機(jī)位的優(yōu)化分配問題就成為了一個很重要的問題.

關(guān)于機(jī)位分配問題，國內(nèi)外研究方法注意可以歸納為3類：數(shù)學(xué)規(guī)劃方法、人工智能方法、計算機(jī)仿真方法，樂美龍[1]等針對機(jī)場和航班非正常運(yùn)行時機(jī)場停機(jī)位分配問題，建立了非正常運(yùn)行條件下的機(jī)場停機(jī)位實時分配混合整數(shù)規(guī)劃模型，模型考慮了實際操作中的飛機(jī)空中等待時間以及航班延誤和停機(jī)位故障等突發(fā)狀況，最后運(yùn)用CPLEX軟件求解；王志清[2]等考慮到在登機(jī)口實際運(yùn)作調(diào)度中存在機(jī)場的時間限制，航班對的限制和機(jī)型與登機(jī)口的匹配等限制，提出了以圖論為基礎(chǔ)的旅客登機(jī)口優(yōu)化模型，來實現(xiàn)縮短旅客步行距離和提高設(shè)施利用率.朱金福[3]等以盡量減少旅客行走距離，實現(xiàn)航班的快速銜接從而縮短旅客中轉(zhuǎn)時間，減少航班延誤為目標(biāo)，設(shè)計了一種排序模擬退火算法以求解樞紐機(jī)場的停機(jī)位指派問題.楊文東[4]等分析了機(jī)場停機(jī)位指派的基本約束和附加約束，以航班延誤和停機(jī)位空閑時間總和最小為目標(biāo)函數(shù)，構(gòu)建機(jī)場停機(jī)位指派模型，提出停機(jī)位航班連接樹的概念和構(gòu)造方法，設(shè)計指派模型的貪婪算法.Ching-Hui Tang[6]等考慮航班延遲而重新分配問題，將其分為預(yù)處理和實處理兩個階段，以最小化時間和空間一致性為目標(biāo)建立模型.

停機(jī)位作為重要的機(jī)場資源，要保證旅客能夠方便的上下飛機(jī)，轉(zhuǎn)機(jī)以及進(jìn)出港，合理的停機(jī)位分配可以大大提高機(jī)場服務(wù)水平.從文獻(xiàn)中可以看出，為了提高操作性能，研究者們已經(jīng)提出了精確的和啟發(fā)式的方法來探索很多完美的和接近完美的解決方案.確切說來，精確的算法特別適合用來解決小規(guī)模問題.然而，實際上，很多大城市機(jī)場每天通常有至少幾十個登機(jī)口用來調(diào)度.這種情況下，由于問題規(guī)模太大，傳統(tǒng)的精確算法無法解決實際的問題.因此，很多研究普遍采用啟發(fā)式方法來解決停機(jī)位分配的問題(遺傳算法，禁忌搜索算法，模擬退火法，蟻群算法和他們的混合算法).在此運(yùn)用遺傳算法來解決問題，同時分析在原始停機(jī)位分配問題中添加一些安全性約束之后產(chǎn)生的一些影響.一般來說，遺傳算法更適用于全局搜索.現(xiàn)階段優(yōu)化的目標(biāo)基本多是以基于旅客行走距離最少、要最小化延誤等待時間、使機(jī)場資源利用最大化等為目標(biāo)，但是這些都很難反映機(jī)位分配過程的實質(zhì)，也無法解決有限資源有效利用和航班延誤等問題.

1 模型建立

地面運(yùn)行沖突主要指的是在相鄰機(jī)位的航班的進(jìn)離港時間相近，但是都使用的是同樣的滑行道時，就容易在滑行道上相遇造成堵塞，對后續(xù)航班都會造成影響，導(dǎo)致不能準(zhǔn)時的?？浚悦總€航班在地面運(yùn)行時都需要和其他航班活動保持一定的安全間隔時間；對于同一個機(jī)位同一時間段內(nèi)不允許同一個機(jī)位被兩架航班或以上來占用.飛機(jī)在機(jī)場地面運(yùn)行過程中為了避免沖突，必須設(shè)置一個安全的距離間隔和安全時間間隔.無論是相鄰機(jī)位之間需要安全緩沖時間還是同一機(jī)位上需要設(shè)定安全緩沖時間，這兩個時間不相互影響，都是為了避免地面活動作業(yè)發(fā)生沖突，在此對于這兩個時間做了一個簡單的設(shè)定，將這兩個安全緩沖時間都設(shè)定為相同的時間用表示來研究避免地面活動作業(yè)沖突的停機(jī)位分配問題.本文以合理使用停機(jī)位空閑時間作為優(yōu)化目標(biāo)，合理的安排空閑時間來避免地面活動帶來的沖突而導(dǎo)致航班延誤.

1.1 模型的假設(shè)條件

1) 對任意航班，都遵循先到先服務(wù)原則.

2) 依靠在相鄰?fù)C(jī)位的飛機(jī)相互獨(dú)立，只有一條跑道.

3) 時間假設(shè)，因為機(jī)場運(yùn)作是一個連續(xù)不斷的過程，在此為了尋找一個全局最優(yōu)解，截取其中一段時間來分析.

4) 假設(shè)停靠該機(jī)場的航班量和時間分布保持在機(jī)場容量許可的范圍內(nèi)，停機(jī)位分配來說，總是可以為任一個到達(dá)航班分配到一個停機(jī)位.

5) 假設(shè)在每個工作日開始以前，當(dāng)日停機(jī)位分配所必須的基本信息是已知的.

1.2 模型的參數(shù)設(shè)定

F表示航班集合；i，j表示航班下標(biāo)；M表示機(jī)型集合，主要分為小、中、大3種機(jī)型，對應(yīng)取值設(shè)為1、2、3，即Mk∈{1,2,3}；k，l表示停機(jī)位下標(biāo)；G表示停機(jī)位集合,停機(jī)位根據(jù)機(jī)型也分為小、中、大3種類型的停機(jī)位，對應(yīng)取值設(shè)為1、2、3，即Gi∈{1,2,3}；Ai表示航班i到達(dá)時間；Di表示航班i離港時間；Bk表示機(jī)位k的開放時間；Tq表示每個航班最小過站時間，設(shè)為40 min；Tp表示同一停機(jī)位最小安全緩沖時間，設(shè)為5 min；Si,j,k表示連續(xù)分配到同一停機(jī)位k的航班i和j之間的空閑時間；Pi,j表示航班i到航班j的旅客人數(shù)；wk,i表示停機(jī)位k到停機(jī)位l的距離；xi,k表示航班i分配到停機(jī)位k，xi,k=1 當(dāng)且僅當(dāng)分配飛機(jī)停到停機(jī)位k時，否則為0；yi,j,k,l表示分配至不同停機(jī)位的兩架飛機(jī)之間的位置關(guān)系，當(dāng)且僅當(dāng)航班i分配至機(jī)位k，航班j分配至機(jī)位l時，yi,j,k,l=1；此時有yi,j,k,l=xi,kxj,l，可以將非線性轉(zhuǎn)化為關(guān)于yi,j,k,l的線性表達(dá)式；表示相鄰航班i和航班j被分配至同一個停機(jī)位k時，同時i

1.3 模型的目標(biāo)函數(shù)

模型的目標(biāo)函數(shù)公式為：

(1)

1.4 模型的約束條件

模型的約束條件為：

(2)

Gk-Mi*xi,k≥0,?i∈F,?k∈G,

(3)

xi,k+xj,l≤,?i,j∈F,?k,∈G;i≠j,

(4)

(5)

xi,k+xj,l-2yi,j,k,l≥0,

?i,j∈F,?k,l∈G;i≠j,

(6)

如果(Dj-Ai)(Di-Aj)>0,則

(7)

xi,k+xj,k-2yi,j,k≥0,?i,j∈F,?k,l∈G,

(8)

Si,j,k≥Tp,?i,j∈F,?k∈G,

(9)

xj,k-yo,j,k≥0,?j∈F,?k∈G,

(10)

Aj-Di≥Tpyi,j,k?i,j∈F,?k∈G,

(11)

Si,j,k≤Ai-Diyi,j,k,?i,j∈F,?k∈G,

(12)

Si,j,k≥Ajyi,j,k-Diyi,j,k?i,j∈F,?k∈G,

(13)

(14)

xi,k,yi,j,k,yi,j,k,yo,j,k∈{0,1},

?i,j∈F,?k∈G,

(15)

|Gi-Dj|≥Tpxi,kxj,k+1,?i,j∈F,?k∈G,

|Gi-Dj|≥Tpxi,kxj,k+1,?i,j∈F,?k∈G,

|Gj-Di|≥Tpxi,kxj,k+1,?i,j∈F,?k∈G,

|Ai-Aj|≥Tpxi,kxj,k+1,?i,j∈F,?k∈G.

(16)

約束條件2表示唯一性約束，一個航班只能分配到一個停機(jī)位；約束條件3表示機(jī)型與停機(jī)位的配對關(guān)系；約束條件4表示一個停機(jī)位在同一時刻只能分配給一個航班；條件5，6表示對yi,j,k,l取值；約束條件7，8表示對yi,j,k的取值；約束條件9表示的是分配到同一停機(jī)位的兩個航班之間的空閑時間要大于等于安全緩沖時間；約束條件10表示的對第一個分配到k機(jī)位的變量yo,j,k的定義；約束條件15表示變量的取值范圍；約束條件11表示的是對于分配到同一機(jī)位的兩個連續(xù)航班之間最小間隔時間的定義；約束條件12和13表示的對同一機(jī)位兩連續(xù)航班之間的空閑時間；約束條件14表示的對每個機(jī)位最后一個航班的離開時間的定義；約束條件15表示的是各個變量的取值范圍.約束條件16是為了避免分配到相鄰?fù)C(jī)位的兩個航班進(jìn)出產(chǎn)生沖突的最小時間，以此來保證相鄰機(jī)位之間不會出現(xiàn)運(yùn)行沖突.

1.5 解決方法

遺傳算法包括全部的染色體或者每一代的個體染色體.每一個染色體都代表著問題的一種解決方案.對群體的個體按照它們對環(huán)境適應(yīng)度施加一定的操作，從而實現(xiàn)優(yōu)勝劣汰的進(jìn)化過程.從優(yōu)化搜索的角度而言，遺傳操作可以使問題一步一步接近最優(yōu)解.用整數(shù)字符串代表染色體是展現(xiàn)飛機(jī)與登機(jī)口關(guān)系的一個簡單方式.字符串的長度和每一個字符都與一架飛機(jī)相聯(lián)系，同時基因里的特殊數(shù)字代表著這架飛機(jī)分配的登機(jī)口.比如，字符串6314542表示成功安排7架飛機(jī)到6個停機(jī)位，飛機(jī)4和6都被分配到停機(jī)位4.

1)適應(yīng)度函數(shù)

在前文中提到過遺傳算法在開始階段會隨機(jī)產(chǎn)生一個初始種群，然后對初始種群的每條染色體進(jìn)行評價，留下適應(yīng)度高的個體，低的被淘汰，再按照交叉概率和規(guī)則進(jìn)行交叉操作，對于新產(chǎn)生的個體計算其適應(yīng)度值，同樣留下適應(yīng)度值高的個體最后進(jìn)行變異操作，就這樣一代代的遺傳優(yōu)良的基因個體，這樣逐步朝著更優(yōu)解的方向進(jìn)化.在這個過程中適應(yīng)度值的計算是根據(jù)適應(yīng)度函數(shù)來決定的，設(shè)定適應(yīng)度函數(shù)為：fitness f=1/Z.適應(yīng)度值越大，所求的目標(biāo)函數(shù)值越小.

2)選擇方式

遺傳算法中適應(yīng)性強(qiáng)的染色體就會有更大的機(jī)會被選擇.選擇兩個染色體，進(jìn)行交叉、變異得到下一代.重復(fù)這個過程多次，得到一個新的染色體.通過阻止好的染色體在交叉變異過程中被破壞，一些最好的染色體替代那些后代中最壞的染色體.當(dāng)然，最好染色體的數(shù)量是比較小的，這樣可以防止它們主導(dǎo)整個選擇的過程.選擇的目的是把優(yōu)化的個體(或解)直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代.種群中的個體的適應(yīng)度值是根據(jù)適應(yīng)度函數(shù)決定的，在算法進(jìn)行過程中會一直面臨選擇的問題，選擇適應(yīng)度值高的個體進(jìn)行交叉操作，進(jìn)行變異操作，所以都是通過選擇來使得好的解或者個體能夠被留下來進(jìn)行下一步操作，在這里用常見的輪盤賭選擇方法，來根據(jù)適應(yīng)度值的大小來進(jìn)行選擇.

交叉：交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新的個體，本文主要用的是單點(diǎn)交叉法.具體操作是：在個體串中隨機(jī)設(shè)定一個交叉點(diǎn)，實行交叉時，該點(diǎn)前或后的兩個個體的部分結(jié)構(gòu)進(jìn)行互換，并生成兩個新個體.這樣產(chǎn)生的子代可能是不可行的，所以需要不斷的檢查和修改，比如選擇了一個交叉點(diǎn)i(對應(yīng)航班號)，在其之前的基因都是可行的，就需要從i+1開始檢查，首先要確定當(dāng)前的停機(jī)位分配狀況，如果可行就轉(zhuǎn)到下一個基因，如果不可以就需要重新分配然后在轉(zhuǎn)到下一個基因.

變異：對群體中的個體串的某些基因的基因值作一個變動，一般來說，變異操作的基本步驟如下：對群中所有個體以事先設(shè)定的變異概率判斷是否進(jìn)行變異，然后對進(jìn)行變異的個體隨機(jī)選擇變異位進(jìn)行變異.

2 實例分析

現(xiàn)將上述模型應(yīng)用于某機(jī)場的停機(jī)位分配.因為機(jī)場運(yùn)作是一個連續(xù)不斷的過程，在此為了尋找一個全局最優(yōu)解，截取其中一段時間，該機(jī)場現(xiàn)有10個停機(jī)位可用，有34個航班在9∶00～18∶00時間內(nèi)需分配停機(jī)位，每個機(jī)位的開放時間都是9點(diǎn)，結(jié)束都是18點(diǎn)，具體計劃信息見表1.

表1 部分進(jìn)、離港航班時刻表

遺傳算法參數(shù)設(shè)定值如下：群體規(guī)模：20；交叉概率0.9；變異概率：0.05；最大進(jìn)化代數(shù)：200；運(yùn)用MATLAB進(jìn)行計算求解.

根據(jù)原計劃得到的停機(jī)位的分配甘特圖如圖1所示，通過運(yùn)用數(shù)學(xué)模型的嚴(yán)格約束之后得到的停機(jī)位分配甘特圖如圖2所示.

圖1展示了無安全條件下的機(jī)場停機(jī)位分配結(jié)果，圖2展示了考慮安全因素的停機(jī)位分配結(jié)果.根據(jù)測試結(jié)果，從圖1中可以看出，在135時刻和192時刻左右，對于停機(jī)位9和10來說，地面運(yùn)動時間的重疊性很高，航班6在135時刻要離港，而航班10在136時刻需要降落滑行進(jìn)港，同樣在192時刻航班10要離港而在193時刻航班17需要進(jìn)港，而且被分配在相鄰的停機(jī)位9和10，這樣就會在滑道上相遇，這種沖突必然就會導(dǎo)致一些航班無法正常進(jìn)港或者離港，帶來不必要的延誤，也具有一定的潛在危險性，所以在實際情況中這種事不合理的分配.同樣，在圖中也可以看到其他的一些航班，其抵達(dá)時間和離開時間的重疊性，可以看出沖突有時會發(fā)生在航班18和23，10和17，23和27，31和34等.

圖2的結(jié)果可以看出通過加入嚴(yán)格的約束，控制每個機(jī)位航班的進(jìn)出時間間隔，可以盡量避免停靠在相鄰?fù)C(jī)位的航班沖突，將兩個進(jìn)離港時刻非常接近的航班安排在不相鄰的停機(jī)位上.對于地面活動重疊性高的航班，任意兩架飛機(jī)都不能安排到相鄰的停機(jī)位，這樣可以盡量減少因為地面活動時間沖突帶來的延誤.圖3的結(jié)果可以地面活動重疊性高的航班，任意兩架飛機(jī)都不能安排到相鄰的停機(jī)位.可以看出由于這個限制，很多其他航班的停機(jī)位分配也變得不同.隨著迭代次數(shù)的增加，群體值對應(yīng)的曲線在迅速下降.而且，解決方案顯示，經(jīng)過大概10次迭代，收斂性更強(qiáng).

圖1 原計劃停機(jī)位分配甘特圖Fig.1 Gate assignment information ganntt chart under original plan

圖2 優(yōu)化后停機(jī)位分配甘特圖Fig.2 Stands assignment information ganntt chart after optimizing

圖3 優(yōu)化結(jié)果輸出Fig.3 Output the results of optimization

3 小結(jié)

在總結(jié)國內(nèi)外對于停機(jī)位分配的研究的基礎(chǔ)上，確定停機(jī)位分配問題的要求和目標(biāo)，考慮航班地面活動，合理分配各停機(jī)位空閑時間，建立了避免沖突的停機(jī)位分配模型.結(jié)合實例.運(yùn)用MATLAB編程軟件對模型進(jìn)行求解，驗證了模型的有效性，結(jié)果顯示模型可以很好的避免在單跑道的機(jī)場出現(xiàn)航班滑行沖突的問題.但是停機(jī)位分配問題是一個復(fù)雜的多目標(biāo)多約束問題，考慮其他目標(biāo)或約束條件，進(jìn)一步的優(yōu)化是未來的研究方向.

[1] 樂美龍， 檀財茂. 非正常運(yùn)行下機(jī)場停機(jī)位實時分配模型[J].工業(yè)工程， 2014， 17(1):12-16．

[2] 王志清， 商紅巖， 寧宣熙. 機(jī)場登機(jī)口優(yōu)化調(diào)度算法及實證[J].南京航空航天大學(xué)學(xué)報(自然科學(xué)版)， 2007， 39(6):819-823．

[3] 陳 欣， 陸 迅， 朱金福. 停機(jī)位指派模型的排序模擬退火算法[J].應(yīng)用科學(xué)報， 2010， 25(5):520-525.

[4] 楊文東， 朱金福， 許 俐. 基于航班連接樹的機(jī)場停機(jī)位指派問題的研究[J]. 山東大學(xué)學(xué)報(工學(xué)版)， 2010， 40(2):153-158．

[5] TANG C H， YAN S H， HOU Y Z. A gate reassignment framework for real time flight delays[J].Springer-Verlag. 2010， 8(3):299-318．

[6] 馮 程， 胡明華, 趙 征. 一種新的停機(jī)位分配優(yōu)化模型[J].交通運(yùn)輸系統(tǒng)工程與信息. 2012， 12(1):131-138．

[7] 李軍會， 朱金福， 高 強(qiáng). 基于貪婪禁忌算法的停機(jī)位指派問題研究[J].交通運(yùn)輸系統(tǒng)工程與信息， 2011， 11(4):173-179．

[8] WANG H W， LUO Y X， SHI Z J. Real-time gate reassignment based on flight delay feature in hub airport[J].Mathematical Problems in Engineering,2013(3):1-10．

[9] DORNDORFA U， DREXLB A. Flight gate schedulingState-of-the-art and recentdevelopments[J]. Omega,2007(35):326-334．

[10] CHENG C H， HO S C， KWAN C L. The use of meta-heuristics for airport gate assignment[J]. Expert Systems with Applications, 2012, 39:12430-12437．

Based on the research of security constraints of airport gate assignment

CHEN Qian, LE Meilong

(Scientific Research Academy， Shanghai Maritime University， Shanghai 201306)

Gate plays a key role in the airport operation system. Without a reasonable and efficient gate assignment， the flights will not arrive at the scheduled gates on time according to the original plan. As the rising number of the flights， it’s a great challenge to enhance the efficiency of the airport operations， which requires rational allocation of gates. Meanwhile， reasonable control on idle time of the various gates is conducive to avoid the potential conflicts between adjacent gates. Considering the safety， the gate assignment model is established to avoid the conflicts and applied into the practice. The Gantt chart about the gate assignment demonstrates that the model is reasonable， efficient and more realistic indicating the improve on the operation efficiency of the airport．

air transportation management； gate assignment； efficiency； safety operation； genetic algorithm

2015-05-17.

國家自然科學(xué)基金項目(71471110).

1000-1190(2016)01-0055-06

U8

A

*E-mail: chenqian181@126.com.