繁忙機(jī)場(chǎng)機(jī)位分配的混合集合規(guī)劃方法

王巖華，朱金福，朱 博，唐小衛(wèi)

(南京航空航天大學(xué) 民航學(xué)院，江蘇 南京211106)

隨著航班數(shù)量快速增長(zhǎng)，停機(jī)位資源不足將嚴(yán)重制約我國(guó)民航運(yùn)輸?shù)陌l(fā)展。對(duì)機(jī)位資源進(jìn)行優(yōu)化分配，可以提高機(jī)位利用率，在一定程度上緩解繁忙機(jī)場(chǎng)機(jī)位資源的緊張狀況。因此，對(duì)停機(jī)位優(yōu)化分配的研究具有重要理論意義和實(shí)用價(jià)值。

停機(jī)位分配問(wèn)題(gate assignment problem，GAP)是近年來(lái)學(xué)術(shù)界研究的熱點(diǎn)。GAP 問(wèn)題具有NP -Hard 特性，對(duì)于大規(guī)模問(wèn)題在有限時(shí)間內(nèi)較難得到最優(yōu)解［1］。目前對(duì)停機(jī)位分配的研究主要有3 類(lèi)方法：①數(shù)學(xué)規(guī)劃方法。2001 年，XU 等將該問(wèn)題描述為一個(gè)混合二次0 -1 整數(shù)規(guī)劃問(wèn)題［2］。2013 年，楊雙雙等以停機(jī)位保障能力和客戶(hù)滿(mǎn)意度為目標(biāo)建立優(yōu)化模型［3］。2014年，曾琳燕等以旅客步行距離最小為優(yōu)化目標(biāo)建立停機(jī)位指派優(yōu)化模型［4-5］。②系統(tǒng)仿真方法。2010 年，尹嘉男等建立多跑道機(jī)位分配仿真模型，尋求滑行時(shí)間最短的分配方案［6］。2012 年，馮程等利用計(jì)算機(jī)仿真進(jìn)行算法設(shè)計(jì)［7］。③人工智能方法。2002 年，LAM 等建立了與人工智能相結(jié)合的機(jī)位分配專(zhuān)家系統(tǒng)［8］。

盡管對(duì)機(jī)位分配的研究已取得一定成果，但在實(shí)際分配中業(yè)務(wù)規(guī)則較復(fù)雜，已有的整數(shù)規(guī)劃方法需對(duì)業(yè)務(wù)規(guī)則進(jìn)行較多抽象和簡(jiǎn)化才能建立模型。雖然機(jī)位分配的最本質(zhì)約束能夠得到正確描述，但是重要業(yè)務(wù)規(guī)則仍然無(wú)法表達(dá)，限制了這些研究成果在實(shí)際問(wèn)題中的應(yīng)用?；旌霞弦?guī)劃(mixed set programming，MSP)特別適用于求解集合覆蓋/劃分、任務(wù)分配等問(wèn)題。為解決上述問(wèn)題，筆者采用MSP 方法對(duì)繁忙機(jī)場(chǎng)機(jī)位分配問(wèn)題建模并求解。

1 繁忙機(jī)場(chǎng)機(jī)位分配問(wèn)題描述

停機(jī)位分配問(wèn)題是在給定的作業(yè)時(shí)間窗內(nèi)，將進(jìn)出港航班分配到有限的機(jī)位?？?，進(jìn)行地面保障作業(yè)的運(yùn)行決策問(wèn)題。解決繁忙機(jī)場(chǎng)機(jī)位分配問(wèn)題，存在以下困難：

(1)繁忙機(jī)場(chǎng)航班流量大。以首都機(jī)場(chǎng)為例，據(jù)統(tǒng)計(jì)，其停機(jī)位多達(dá)350 個(gè)，日平均航班起降架次已超過(guò)1 500 架次。因此，繁忙機(jī)場(chǎng)機(jī)位分配問(wèn)題屬于大規(guī)模的整數(shù)規(guī)劃問(wèn)題。

(2)繁忙機(jī)場(chǎng)機(jī)位分配的業(yè)務(wù)規(guī)則復(fù)雜。除了機(jī)型與機(jī)位匹配約束之外，繁忙機(jī)場(chǎng)機(jī)位分配還有許多復(fù)雜的業(yè)務(wù)規(guī)則，包括航班分為純出港、純進(jìn)港和過(guò)站航班3 類(lèi)，現(xiàn)有研究一般不進(jìn)行區(qū)分，實(shí)際問(wèn)題必須區(qū)分;為緩解機(jī)位資源不足，某些組合機(jī)位可根據(jù)需要進(jìn)行合并或拆分;為提高近機(jī)位利用率，對(duì)過(guò)站時(shí)間較長(zhǎng)的飛機(jī)進(jìn)行拖曳，離港前再拖至近機(jī)位上客。

(3)實(shí)時(shí)性要求較高。機(jī)場(chǎng)運(yùn)行指揮中心在匯集各航空公司第二天航班計(jì)劃后，要求在短時(shí)間內(nèi)快速準(zhǔn)確地進(jìn)行機(jī)位分配，以便空管和地面保障部門(mén)進(jìn)行保障工作，這就要求模型和算法能夠快速解決該問(wèn)題。

由此可見(jiàn)，繁忙機(jī)場(chǎng)機(jī)位分配是一個(gè)復(fù)雜的離散系統(tǒng)決策優(yōu)化問(wèn)題，采用傳統(tǒng)數(shù)學(xué)規(guī)劃模型難以解決?；旌霞弦?guī)劃擅長(zhǎng)對(duì)業(yè)務(wù)問(wèn)題進(jìn)行描述性建模，筆者以此為出發(fā)點(diǎn)進(jìn)行研究。

2 繁忙機(jī)場(chǎng)機(jī)位分配的MSP 模型

2.1 混合集合規(guī)劃方法

混合集合規(guī)劃是以一階邏輯與集合推理為算法框架的邏輯求解系統(tǒng)［9-10］。與數(shù)學(xué)規(guī)劃不同，混合集合規(guī)劃方法建模的步驟為：數(shù)據(jù)建模→邏輯建?！蠼庖?guī)則設(shè)計(jì)。混合集合規(guī)劃首先通過(guò)約束推理切割解空間，之后查詢(xún)關(guān)鍵變量對(duì)解空間進(jìn)行完備搜索，使得關(guān)鍵變量從模糊變?yōu)榇_定。筆者基于MSP 方法對(duì)繁忙機(jī)場(chǎng)機(jī)位分配提出新的建模方向，并采用自然約束語(yǔ)言(natural constraint language，NCL)進(jìn)行編程。

2.2 數(shù)據(jù)建模

在混合集合規(guī)劃模型中存在3 類(lèi)變量：原始數(shù)據(jù)變量、中間變量和決策變量。原始數(shù)據(jù)變量直接從數(shù)據(jù)庫(kù)中讀取;中間變量由原始數(shù)據(jù)變量通過(guò)建模計(jì)算得到;決策變量則通過(guò)邏輯建模求解得到。數(shù)據(jù)類(lèi)采用全英文大寫(xiě)命名，如FLIGHT;類(lèi)中的各屬性命名則為屬性加類(lèi)，如id-Flighti;集合為首字母大寫(xiě)，如ArrivalFlight。

MSP 數(shù)據(jù)建模涉及的原始數(shù)據(jù)類(lèi)有航班、機(jī)位和機(jī)型。NCL 采用面向?qū)ο蟮姆椒ǖ贸鲆韵?個(gè)原始數(shù)據(jù)類(lèi)：

(1)FLIGHT(id，name，outIn，aircraft，id-TypeAircraf，first，t，gateYday，mct，Property)。id-Flighti為航班i唯一標(biāo)識(shí);nameFlighti為航班i的航班號(hào);outInFlighti為航班i進(jìn)離港標(biāo)識(shí);id-TypeAircraftFlighti為執(zhí)飛航班i的機(jī)型標(biāo)識(shí);first-Flighti為航班i的始發(fā)標(biāo)識(shí);tFlighti為航班起降時(shí)刻;gateYdayFlighti為始發(fā)航班i前一天停場(chǎng)機(jī)位;mctFlighti為航班i最小過(guò)站時(shí)間;Property-Flighti為航班i性質(zhì)。

(2)GATE(id，name，IdGateForbidden，charac-ter，IdTypeAircraft，Property)。idGatei為機(jī)位i唯一標(biāo)識(shí);nameGatei為機(jī)位i的名稱(chēng);IdGateForbiddenGatei為機(jī)位i被占用時(shí)，其不可用組合機(jī)位集合;characterGatei為機(jī)位i遠(yuǎn)/近機(jī)位性質(zhì);Id-TypeAircraftGatei為機(jī)位i可停靠機(jī)型集合;PropertyGatei為機(jī)位i國(guó)際/國(guó)內(nèi)性質(zhì)。

(3)TYPEAIRCRAFT(id，name)。idTypeAircrafti為機(jī)型i唯一標(biāo)識(shí);nameTypeAircrafti為機(jī)型i型號(hào)。

MSP 模型的已知參數(shù)有航班保障時(shí)間time-Support，同機(jī)位前后航班安全時(shí)間間隔gapSecurity和最大過(guò)站時(shí)間maxmct。

根據(jù)以上原始數(shù)據(jù)變量，通過(guò)建模計(jì)算得到MSP 模型的中間變量，如表1 所示。

表1 中間變量表

筆者將待分配的航班分為3 類(lèi)：純進(jìn)港、純出港和過(guò)站航班。不同類(lèi)型的航班，其占用機(jī)位的時(shí)間區(qū)間不同，如表2 所示。需特別指出，參考繁忙機(jī)場(chǎng)實(shí)際運(yùn)營(yíng)情況，對(duì)于過(guò)站航班，若過(guò)站時(shí)間不超過(guò)一定值，則到達(dá)航班和出發(fā)航班?？客粋€(gè)機(jī)位，占用機(jī)位時(shí)間為總時(shí)間的1/2;若過(guò)站時(shí)間過(guò)長(zhǎng)，則進(jìn)行拖曳，分別將到達(dá)航班和出發(fā)航班看成一個(gè)純進(jìn)港航班和一個(gè)純出港航班，下客完畢后拖至遠(yuǎn)機(jī)位?？?。

MSP 模型中的決策變量為gateFlighti和FlightGatej。其中，gateFlighti為航班i分配的機(jī)位;FlightGatej為機(jī)位j上?？康乃泻桨嗉稀ateFlighti為關(guān)鍵決策變量，確定gateFlighti后可以確定其他決策變量。

表2 航班類(lèi)型及其占用機(jī)位時(shí)間區(qū)間

2.3 邏輯建模

2.3.1 基本約束

停機(jī)位分配的基本約束包括機(jī)型與機(jī)位匹配約束、獨(dú)占性約束、最小過(guò)站時(shí)間約束、安全時(shí)間間隔約束和航班集合覆蓋約束，如式(1)～式(5)所示。

其中，式(1)表示機(jī)型與機(jī)位相互匹配約束，執(zhí)飛航班j的機(jī)型在機(jī)位i可?？康臋C(jī)型集合中。式(2)表示同一時(shí)刻同一機(jī)位最多能停靠一個(gè)航班。式(3)表示最小過(guò)站時(shí)間約束。式(4)表示同機(jī)位安全間隔時(shí)間約束，即同一機(jī)位上一航班離港時(shí)間與緊鄰的下一航班進(jìn)港時(shí)間間隔必須大于機(jī)場(chǎng)規(guī)定的安全間隔時(shí)間。式(5)表示航班集合覆蓋約束。

2.3.2 業(yè)務(wù)規(guī)則約束

業(yè)務(wù)規(guī)則是機(jī)場(chǎng)進(jìn)行機(jī)位分配必須遵守的運(yùn)行規(guī)定，有些是行業(yè)內(nèi)共同遵守，有些是各機(jī)場(chǎng)專(zhuān)門(mén)制定。在現(xiàn)有機(jī)位分配研究中，一般只考慮基本約束，對(duì)業(yè)務(wù)規(guī)則約束研究較少。筆者的MSP模型中考慮的業(yè)務(wù)規(guī)則約束包括組合機(jī)位約束、始發(fā)航班約束、飛機(jī)拖曳約束和國(guó)際國(guó)內(nèi)航班約束。其中，組合機(jī)位約束、飛機(jī)拖曳約束是提高繁忙機(jī)場(chǎng)近機(jī)位利用率需滿(mǎn)足的必然要求。這些業(yè)務(wù)規(guī)則可用式(6)～式(13)表示。

式(6)和式(7)表示組合機(jī)位約束，當(dāng)小機(jī)位被占用時(shí)，組合大機(jī)位不能?？匡w機(jī)。式(8)表示航班?？拷鼨C(jī)位等同于航班分配的機(jī)位為近機(jī)位。式(9)和式(10)分別表示對(duì)于始發(fā)航班，若其前一天停靠近機(jī)位，第二天的始發(fā)航班安排在同一近機(jī)位;若其前一天?？窟h(yuǎn)機(jī)位，第二天的始發(fā)航班盡量安排在近機(jī)位。式(11)表示對(duì)于過(guò)站時(shí)間過(guò)長(zhǎng)的過(guò)站航班，考慮飛機(jī)拖曳，分別將到達(dá)航班和出發(fā)航班看成一個(gè)純進(jìn)港航班和一個(gè)純出港航班。式(12)和式(13)分別表示國(guó)際航班?？繃?guó)際機(jī)位，國(guó)內(nèi)航班停靠國(guó)內(nèi)機(jī)位。

2.3.3 優(yōu)化目標(biāo)

繁忙機(jī)場(chǎng)機(jī)位分配實(shí)際運(yùn)行中考慮的優(yōu)化目標(biāo)有靠橋率最大和飛機(jī)滑行距離最短等，其中最大化航班靠橋率為繁忙機(jī)場(chǎng)評(píng)價(jià)機(jī)位分配方案的核心，因此筆者以此為優(yōu)化目標(biāo)。航班靠橋率即停靠近機(jī)位的航班數(shù)量與航班總數(shù)的比值。

式(14)表示以最大化靠橋率為優(yōu)化目標(biāo)。式中：bridgegateFlighti為停靠近機(jī)位的航班數(shù)量，其計(jì)算如式(8)所示;#FLIGHT為航班總數(shù)。

2.4 求解策略

設(shè)計(jì)求解策略是MSP 模型的關(guān)鍵，設(shè)計(jì)合適的求解策略能對(duì)建立的停機(jī)位分配MSP 模型進(jìn)行高效求解。混合集合規(guī)劃的求解策略有最小松弛度、最大松弛度、最小遺憾度、順序性和貪婪性等原則。根據(jù)機(jī)位分配問(wèn)題的特點(diǎn)，采用最小松弛度和貪婪性原則進(jìn)行求解。

式(15)為關(guān)鍵變量gateFlighti的選擇規(guī)則，即基于最小松弛度原則，在FLIGHT中選擇使gateFlighti變量值域元素個(gè)數(shù)盡可能少的航班。松弛度越小，則非確定性越小，產(chǎn)生回溯的可能性也越小。式(16)表示分配停機(jī)位時(shí)在gateFlighti域中按照貪婪性原則，首先選擇近機(jī)位，即最有利于目標(biāo)函數(shù)的方向。執(zhí)行式(17)的查詢(xún)，檢查式(15)和式(16)航班?？康臋C(jī)位是否為近機(jī)位j。

3 國(guó)內(nèi)繁忙機(jī)場(chǎng)實(shí)例分析

以國(guó)內(nèi)某繁忙機(jī)場(chǎng)2014 年4 月22 日?？縏1 航站樓的航班為例，時(shí)間窗為24 h，包含164個(gè)國(guó)內(nèi)航班，共9 種機(jī)型，分配至4 個(gè)機(jī)坪的45個(gè)機(jī)位(近機(jī)位13 個(gè)，遠(yuǎn)機(jī)位32 個(gè))。其中，N1、W1、W2 為遠(yuǎn)機(jī)位機(jī)坪。該繁忙機(jī)場(chǎng)各機(jī)位均給出可?？繖C(jī)型集合，如表3 所示。具體航班時(shí)刻如表4 所示。該例中，根據(jù)機(jī)場(chǎng)實(shí)際情況設(shè)定國(guó)內(nèi)航班保障時(shí)間為40 min，安全間隔為5 min，對(duì)過(guò)站時(shí)間超過(guò)180 min 的航班進(jìn)行拖曳。

表3 各機(jī)位相關(guān)屬性

表4 國(guó)內(nèi)某繁忙機(jī)場(chǎng)部分航班時(shí)刻表及分配結(jié)果對(duì)比

MSP 模型能夠滿(mǎn)足遵守該繁忙機(jī)場(chǎng)實(shí)際機(jī)位分配中業(yè)務(wù)規(guī)則的要求。機(jī)場(chǎng)在實(shí)際運(yùn)營(yíng)中不需要求得最優(yōu)解，只需在較短時(shí)間內(nèi)得到較優(yōu)的滿(mǎn)意解，因此設(shè)定求解時(shí)間為1 min，時(shí)間結(jié)束時(shí)程序停止運(yùn)行，計(jì)算結(jié)果如表4 所示。由分配結(jié)果可以看出，采用MSP 方法前，該機(jī)場(chǎng)人工分配時(shí)，111 個(gè)航班?？拷鼨C(jī)位，靠橋率為67.7%。采用混合集合規(guī)劃對(duì)該問(wèn)題進(jìn)行分配時(shí)，145 個(gè)航班停靠近機(jī)位，靠橋率為88.4%，比人工分配提升了20.7%。表4 中，對(duì)于過(guò)站航班HU7110 和HU7111，MSP 模型識(shí)別出其過(guò)站時(shí)間未超過(guò)180 min，則將其分配在同一機(jī)位上下客。采用MSP方法求解時(shí)，分配至遠(yuǎn)機(jī)位的19 個(gè)航班均?？吭陔xT1 航站樓較近的W1 坪和W2 坪，MSP 方法對(duì)遠(yuǎn)機(jī)位的分配也比人工分配更合理。

4 結(jié)論

筆者采用混合集合規(guī)劃方法，針對(duì)繁忙機(jī)場(chǎng)停機(jī)位分配問(wèn)題的特點(diǎn)，建立了包含飛機(jī)拖曳、組合機(jī)位等規(guī)則的約束規(guī)劃模型，并設(shè)計(jì)了簡(jiǎn)潔高效的求解策略。對(duì)國(guó)內(nèi)繁忙機(jī)場(chǎng)實(shí)例進(jìn)行求解分析，取得了較好的效果。

［1］ 鞠姝妹.樞紐機(jī)場(chǎng)停機(jī)位指派的算法優(yōu)化與仿真［D］.南京：南京航空航天大學(xué)，2008.

［2］ XU J F，BAILEY G.The airport gate assignment problem：mathematical model and a tabu search algorithm［C］//System Sciences，Proceedings of the 34th Annual Hawaii International Conference. ［S. l.］：IEEE，2001：102 -111.

［3］ 楊雙雙，田勇，萬(wàn)莉莉，等.基于客戶(hù)評(píng)價(jià)體系的停機(jī)位分配優(yōu)化研究［J］.武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版)，2013，37(1)：167 -174.

［4］ 曾琳燕，姜雨，羅宇驍.基于旅客步行距離的停機(jī)位均衡優(yōu)化指派建模［J］.武漢理工大學(xué)學(xué)報(bào)(交通科學(xué)與工程版)，2014，38(4)：895 -899.

［5］ 楊越，王犇，劉楊. 機(jī)場(chǎng)機(jī)位分配的一種實(shí)用方法［J］.中國(guó)民航大學(xué)學(xué)報(bào)，2014，32(2)：27 -32.

［6］ 尹嘉男，胡明華，趙征.多跑道機(jī)場(chǎng)停機(jī)位分配仿真模型及算法［J］. 交通運(yùn)輸工程學(xué)報(bào)，2010，10(5)：71 -76.

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

［8］ LAM S H，CAO J，F(xiàn)AN H. Development of an intelligent agent for airport gate assignment［J］. Journal of Air Transportation，2002，7(2)：103 -114.

［9］ ZHOU J Y.The NCL natural constraint language［M］.［S.l.］：Science Press，2012：131 -140.

［10］ ZHOU J.Introduction to the constraint language NCL［J］. The Journal of Logic Programming，2000，45(1)：71 -103.