楊 越，王 犇，劉 楊

（1.中國民航大學(xué)空中交通管理學(xué)院，天津 300300；2.西安咸陽國際機(jī)場現(xiàn)場運(yùn)行中心指揮室，西安 712035；3.天津市博盈科技發(fā)展有限公司，天津 300200）

機(jī)場停機(jī)位分配問題是指綜合考慮航班和機(jī)位信息，為未來一段時(shí)間內(nèi)的進(jìn)港和離港航班指派合適的停機(jī)位資源，是機(jī)場現(xiàn)場指揮室的重要工作內(nèi)容之一[1]，國內(nèi)很多學(xué)者分別采用不同方法進(jìn)行了多角度的探討和研究。文軍[2-3]根據(jù)“先到先服務(wù)”的原則，通過引入機(jī)位標(biāo)號函數(shù)和航班標(biāo)號函數(shù)設(shè)計(jì)了一種停機(jī)位排序模型的標(biāo)號算法，并給出了機(jī)位分配的頂點(diǎn)序列著色算法；鞠姝妹[4-5]設(shè)計(jì)了一種貪婪模擬退火算法，以求解樞紐機(jī)場的停機(jī)位指派問題，該算法首先可得到使丟失“航班數(shù)”最少的初始解，隨后采用經(jīng)典模擬退火算法求解出最優(yōu)的指派結(jié)果；王力[6]提出結(jié)合考慮旅客登轉(zhuǎn)機(jī)時(shí)間、機(jī)型與停機(jī)位類型匹配、航班類型、航班數(shù)量與密度、停機(jī)時(shí)間為優(yōu)化目標(biāo)的數(shù)學(xué)模型，設(shè)計(jì)了求解模型的禁忌搜索算法。盡管算法研究層出不窮，但目前國內(nèi)的多數(shù)機(jī)場仍然采用人工指派機(jī)位的方式，即以每日的航班時(shí)刻表為依據(jù)，對進(jìn)場航班進(jìn)行手工的機(jī)位指派。其原因有二：一是算法理論過于復(fù)雜，不適合現(xiàn)場指揮人員的工作需求；二是多數(shù)算法未考慮到延誤航班對機(jī)位指派的重要影響。因此，制定一種實(shí)用且可靠的機(jī)位指派方法符合目前機(jī)場發(fā)展的要求。本文提出了一種機(jī)位預(yù)指派的搜索算法，并設(shè)計(jì)了針對延誤航班的機(jī)位再分配方案，以解決延誤航班對預(yù)指派結(jié)果的干擾問題。

1 研究方法與結(jié)果

1.1 機(jī)位預(yù)指派方法

停機(jī)位指派是經(jīng)典指派問題的一種變形，涉及到各航空公司的航線類型、機(jī)型、航班數(shù)量、航班密度、停機(jī)時(shí)間、旅客步行距離等多方面因素。合理編制停機(jī)位分配計(jì)劃是機(jī)場現(xiàn)場運(yùn)行中心完成作業(yè)任務(wù)的核心工作之一。建立停機(jī)位分配模型并設(shè)計(jì)相應(yīng)的算法是實(shí)現(xiàn)計(jì)算機(jī)輔助編制停機(jī)位分配計(jì)劃的重要內(nèi)容。為此，需要建立關(guān)于機(jī)場停機(jī)位分配問題的數(shù)學(xué)模型和算法。一般而言，構(gòu)建機(jī)位指派模型需要已知的條件包括：①機(jī)場終端區(qū)域的規(guī)劃和停機(jī)位的數(shù)量；②每日的航班時(shí)刻表，即當(dāng)日每架飛機(jī)的進(jìn)港、出港時(shí)間；③每架飛機(jī)的機(jī)型、所屬航空公司等屬性。

1.1.1 目標(biāo)函數(shù)和約束條件

由于機(jī)場機(jī)位指派涉及到旅客行走距離、航空公司的經(jīng)濟(jì)效益、機(jī)場資源的有效利用和地面服務(wù)部門的工作場所等多個(gè)方面，因此從不同角度出發(fā)可以得到不同的優(yōu)化模型。本文主要以提高機(jī)場的運(yùn)營效益和服務(wù)質(zhì)量為目標(biāo)，設(shè)計(jì)預(yù)分配算法時(shí)主要考慮以下兩個(gè)方面：

1）運(yùn)營效益目標(biāo)函數(shù)：為提高機(jī)場的橋位利用率（靠橋率），以達(dá)到近機(jī)位利用率最大為優(yōu)化化目標(biāo)

其中

z為當(dāng)日航班總量。

2）服務(wù)質(zhì)量目標(biāo)函數(shù)：為縮短進(jìn)出港旅客的步行距離，以旅客步行距離最短為優(yōu)化目標(biāo)

其中：ri表示航班i的旅客數(shù)。由于在機(jī)位指派前各航班的旅客數(shù)未知，本文采用不同機(jī)型的最大座位數(shù)e與各航班的客座率u的乘積來表示所研究機(jī)型的旅客數(shù)，即

其中：dk表示停機(jī)位k至安檢口的距離。在此假設(shè)所有旅客從安檢口到停機(jī)位所走的路線是一致的，即同一個(gè)航班的所有旅客在進(jìn)登機(jī)口時(shí)所走的距離是相等的。若機(jī)位為遠(yuǎn)機(jī)位，距離則統(tǒng)一取一個(gè)稍大的值1 000 m。

機(jī)場停機(jī)位指派的約束條件是由停機(jī)位指派的規(guī)則轉(zhuǎn)化而來。具體指派停機(jī)位時(shí)，在一日的不同時(shí)間段內(nèi)，由于進(jìn)港和離港的航班種類、數(shù)目和時(shí)間不同，確定航班使用停機(jī)位的種類和時(shí)間也就不同。本文所考慮的限制約束條件主要包括5個(gè)方面：

1）航班唯一屬性約束：每個(gè)進(jìn)港航班只能分配一個(gè)機(jī)位

其中：M為待分配機(jī)位集合；N為當(dāng)日航班集合。

2）機(jī)位唯一屬性約束：每個(gè)機(jī)位一次只能指派給1架飛機(jī)

3）機(jī)型屬性約束：停機(jī)位只能停放與其匹配機(jī)型的飛機(jī)。例如：機(jī)場的部分機(jī)位可以停放機(jī)型為E類的大型飛機(jī)，一些機(jī)位只能停放C類及以下的小型飛機(jī)

4）航線屬性約束：停機(jī)位與所停航班的航線屬性匹配。例如：多數(shù)中小機(jī)場的大部分停機(jī)位只停放飛國內(nèi)航線的飛機(jī)，少量機(jī)位可停放飛國際航線的飛機(jī)

5）航空公司屬性約束：停機(jī)位與航空公司屬性匹配。為方便地勤服務(wù)需求，機(jī)場會要求不同航空公司的航班停放在其專屬的機(jī)位

1.1.2 機(jī)位預(yù)分配算法設(shè)計(jì)

在本文涉及的算法中，要求預(yù)指派的機(jī)位在滿足上述各約束條件的基礎(chǔ)上達(dá)到提高近機(jī)位利用率和縮短旅客步行距離兩個(gè)目標(biāo)，并且根據(jù)航班到達(dá)機(jī)場的時(shí)間進(jìn)行先到先服務(wù)的排序，以盡量減小本場的延誤時(shí)間。算法的計(jì)算步驟如下：

1）根據(jù)當(dāng)日航班時(shí)刻表，將所有進(jìn)港航班和出港航班按到達(dá)本場和從本場出發(fā)的發(fā)生時(shí)間的先后重新排序。為提高機(jī)位的利用率，當(dāng)?shù)竭_(dá)與出發(fā)航班同時(shí)發(fā)生時(shí)，總是安排出發(fā)航班在前。

2）整理當(dāng)日機(jī)位的初始占用情況，將已占用機(jī)位標(biāo)記為koccupied，將空閑機(jī)位標(biāo)記為kfree，并將每個(gè)機(jī)位的機(jī)型屬性Pk、航線屬性Qk和公司屬性Tk按照本場要求賦值。

3）順序讀取已排序的航班。若航班Fi為出港航班，則釋放當(dāng)前Fi所占用機(jī)位k，將該機(jī)位標(biāo)記為kfree，并令Mfree=Mfree+1。若航班Fi為進(jìn)港航班，則找出一個(gè)空閑機(jī)位k∈Mfree，使其滿足

若滿足上述條件的機(jī)位k存在，則賦值該航班的機(jī)位號為Flt（i）=k，將該機(jī)位標(biāo)記為koccupied，并令Mfree=Mfree-1；如果符合上述條件的機(jī)位不存在，則在當(dāng)前所有空閑機(jī)位Mfree中，尋找機(jī)位k，使其滿足

若滿足上述條件的機(jī)位仍不存在，則令Flt（i）=0，分配結(jié)果顯示“再分配”。

4）按順序讀取下一航班，重復(fù)步驟3）。

5）直至處理完最后一個(gè)航班，輸出Flt（i），i=1，2，…，N。

該算法的流程如圖1所示。

圖1 機(jī)位預(yù)分配算法流程圖Fig.1 Process of gate pre-assignment algorithm

1.1.3 預(yù)分配算例分析

算例采用中國主要干線機(jī)場之一的西安咸陽國際機(jī)場在2012年某日10：00—12：00時(shí)段內(nèi)40個(gè)按飛行計(jì)劃執(zhí)行任務(wù)的航班數(shù)據(jù)，所研究的機(jī)位范圍如表1所示。

表1 咸陽機(jī)場停機(jī)位的統(tǒng)計(jì)數(shù)據(jù)Tab.1 Statistic of gates in Xianyang Airport

涉及的算法按照圖1所示的流程在Matlab7.0的運(yùn)行環(huán)境下編程實(shí)現(xiàn)，結(jié)果如表2所示。其中，計(jì)劃進(jìn)港時(shí)間指按照當(dāng)日的航班時(shí)刻表進(jìn)入咸陽機(jī)場的時(shí)間；預(yù)計(jì)進(jìn)港時(shí)間指根據(jù)前方機(jī)場起飛時(shí)間和相關(guān)情報(bào)預(yù)計(jì)到達(dá)咸陽機(jī)場的時(shí)間；預(yù)計(jì)離港時(shí)間指根據(jù)預(yù)計(jì)進(jìn)港時(shí)間和計(jì)劃過站時(shí)間推斷的航班能夠從咸陽機(jī)場起飛的時(shí)間。預(yù)分配是指由預(yù)指派算法分配的機(jī)位；實(shí)際分配是指現(xiàn)場指揮室工作人員實(shí)際手工分配的機(jī)位。表中的0時(shí)刻作為起始時(shí)間，表示上午10：00。括號中的數(shù)值表示該停機(jī)位距離安檢口的直線步行距離的粗測值。

預(yù)指派算法按照先到先服務(wù)的原則，根據(jù)航班計(jì)劃進(jìn)離港的時(shí)間順序進(jìn)行排序，以實(shí)現(xiàn)航班的機(jī)位自動指派，同時(shí)滿足規(guī)定的機(jī)型、航線和航空公司的屬性約束。若分析某一航班，預(yù)指派算法的計(jì)算結(jié)果可能不比指揮室的實(shí)際指派結(jié)果更為優(yōu)化，如5號航班被指派到了遠(yuǎn)機(jī)位144，旅客需步行1 000 m；實(shí)際指派機(jī)位為107，旅客需步行280 m。這是因?yàn)樵撍惴ǜ鶕?jù)當(dāng)前所有機(jī)位的空閑狀態(tài)來對航班進(jìn)行分配，可能會產(chǎn)生某些步行距離短的近機(jī)位已被占用的情況，從而影響了航班的機(jī)位指派效果。但是，由于算法在對每個(gè)航班進(jìn)行分配時(shí)，都是以近機(jī)位占用為原則，在此基礎(chǔ)上以旅客步行距離最小為優(yōu)先考慮的，因此從全天運(yùn)行的近千架航班來整體對比分析，所要求達(dá)到的優(yōu)化指標(biāo)足以保證。為此，給出了2012年某一周內(nèi)所有按計(jì)劃執(zhí)行飛行任務(wù)的航班的機(jī)位預(yù)指派結(jié)果，比較了預(yù)分配算法與實(shí)際指派結(jié)果在靠橋率和旅客步行距離這兩個(gè)關(guān)鍵指標(biāo)的表現(xiàn)，如表3所示。

表 3中數(shù)據(jù)是按照式（1）、式（2）的計(jì)算方法，以反映機(jī)場運(yùn)營效益的指標(biāo)靠橋率和反映機(jī)場服務(wù)質(zhì)量的指標(biāo)旅客步行距離來分別評價(jià)算法和實(shí)際分配結(jié)果的?？梢钥闯?，在所研究的時(shí)間范圍內(nèi)，算法分配的靠橋率均高于實(shí)際的指派結(jié)果，如圖2所示；算法分配的旅客步行距離均小于實(shí)際的指派結(jié)果，如圖3所示。按照航班計(jì)劃表中的計(jì)劃進(jìn)出港時(shí)間排序后的算法在靠橋率指標(biāo)上提高了5.1%，步行距離指標(biāo)上提高了8.3%，說明該算法比手工分配機(jī)位的方式更能提高機(jī)場的運(yùn)營效益和服務(wù)質(zhì)量。

表2 2012年某日10：00—12：00時(shí)段內(nèi)計(jì)劃航班的機(jī)位預(yù)指派結(jié)果Tab.2 Result of gate pre-assignment according to airline flight plan during 10：00-12：00 on someday in 2012

表3 預(yù)指派算法與實(shí)際指派機(jī)位的比較結(jié)果Tab.3 Comparison of gate pre-assignment between algorithm and practice

1.2 機(jī)位的再分配方案

圖2 算法與實(shí)際指派結(jié)果的靠橋率比較Fig.2 Comparison of utilization ratio of near gate between algorithm and practice

圖3 算法與實(shí)際指派結(jié)果的旅客步行距離比較Fig.3 Comparison of ambulation distance for passengers between algorithm and practice

停機(jī)位的再分配是指在對航班作好初始機(jī)位分配計(jì)劃的基礎(chǔ)上，根據(jù)實(shí)時(shí)航班時(shí)刻的變化，對機(jī)位分配方式進(jìn)行相應(yīng)調(diào)整，使得分配更加合理。一般是在確定了延誤航班新的進(jìn)/離港信息的情況下，對其及相關(guān)航班的停機(jī)位預(yù)分配結(jié)果進(jìn)行相應(yīng)微調(diào)[7]。目前，國內(nèi)多數(shù)機(jī)場采用人工指派機(jī)位的原因之一就是由于延誤航班較多，若完全按照預(yù)分配的方案提前將機(jī)位分配好，在實(shí)際運(yùn)行中需要調(diào)整的機(jī)位也較多。因此，在機(jī)位預(yù)分配的基礎(chǔ)上，設(shè)計(jì)一種能夠自動對延誤航班進(jìn)行再分配的方案，不僅能減輕指揮室人員的工作負(fù)荷，也能在一定程度上提高機(jī)場的運(yùn)營效率。

1.2.1 延誤航班的界定

延誤航班是指由于各種原因未能按計(jì)劃時(shí)間進(jìn)港或離港的航班，由于不同機(jī)場的運(yùn)行方式不同，對延誤航班的具體界定標(biāo)準(zhǔn)也不盡相同。目前，多數(shù)機(jī)場現(xiàn)場指揮室對延誤航班的界定如下：

1）進(jìn)港延誤：若航班在前方機(jī)場的實(shí)際起飛時(shí)間晚于計(jì)劃30 min，則將其視為延誤航班；

2）出港延誤：

a）與進(jìn)港航班相關(guān)的延誤：若未進(jìn)港的航班已有預(yù)達(dá)本場時(shí)間，則預(yù)達(dá)本場時(shí)間+過站時(shí)間晚于本場計(jì)劃出港時(shí)間的航班視為延誤；若未進(jìn)港的航班直到計(jì)劃離港前30 min仍無預(yù)達(dá)本場時(shí)間，則將其視為延誤航班；

b）與進(jìn)港航班無關(guān)的延誤：若航班按計(jì)劃時(shí)間進(jìn)港，但由于目的地機(jī)場、天氣、航路限制、飛機(jī)故障等原因無法按計(jì)劃離港時(shí)間起飛的，則視為延誤。

延誤航班必然會對預(yù)指派的機(jī)位產(chǎn)生干擾。對于進(jìn)港延誤航班，若不及時(shí)更換原分配機(jī)位，則會使此機(jī)位長時(shí)間被無效占用，降低了機(jī)位的利用率；而出港延誤航班會使預(yù)分配方案中占用此機(jī)位的后繼航班受到影響，從而打亂機(jī)位預(yù)指派方案。本文針對有預(yù)計(jì)進(jìn)港時(shí)間和離港時(shí)間的延誤航班，設(shè)計(jì)了相應(yīng)的機(jī)位再分配算法，解決其對預(yù)指派機(jī)位的干擾問題。

1.2.2 機(jī)位再分配算法設(shè)計(jì)

當(dāng)確定了延誤航班后，就要采取措施對延誤航班及其后繼航班的機(jī)位預(yù)分配結(jié)果進(jìn)行相應(yīng)的調(diào)整。本文采取的策略為：針對延誤航班，仍然按照預(yù)分配的方案進(jìn)行機(jī)位指派，即保持原機(jī)位指派結(jié)果不變（除非是返航或備降的航班，則直接釋放預(yù)分配機(jī)位）；而對于與延誤航班占用相同機(jī)位的毗鄰后繼航班，則根據(jù)后繼航班的計(jì)劃進(jìn)港與離港時(shí)間，選擇是否對其重新分配機(jī)位。算法的計(jì)算步驟如下：

1）根據(jù)機(jī)場的延誤航班界定標(biāo)準(zhǔn)，確定延誤航班及其毗鄰后繼航班；

2）根據(jù)前方機(jī)場的實(shí)際起飛時(shí)間和計(jì)劃過站時(shí)間判定延誤航班的預(yù)計(jì)進(jìn)港時(shí)間和離港時(shí)間；

3）若延誤航班的預(yù)計(jì)離港時(shí)間早于毗鄰后繼航班的計(jì)劃進(jìn)港時(shí)間，證明雖然航班延誤了，但未影響所占機(jī)位的后續(xù)航班占用，則保持預(yù)分配方案不變；

4）若延誤航班的預(yù)計(jì)離港時(shí)間晚于毗鄰后繼航班的計(jì)劃進(jìn)港時(shí)間，證明延誤航班影響了機(jī)位預(yù)分配的結(jié)果，需對原占用該機(jī)位的后繼航班進(jìn)行機(jī)位的再分配。并且，為保持其它正常航班的預(yù)指派結(jié)果不受影響，搜索后繼航班在其計(jì)劃進(jìn)港至出港時(shí)間段內(nèi)的所有可用機(jī)位?？捎脵C(jī)位是指在該段時(shí)間內(nèi)沒有按預(yù)分配方案執(zhí)行的被占用的機(jī)位。

5）按照機(jī)位預(yù)分配的原則，對需要進(jìn)行機(jī)位再分配的后繼航班，以滿足近機(jī)位分配優(yōu)先和旅客步行距離最小為目標(biāo)，在所有可用機(jī)位中選擇最佳機(jī)位進(jìn)行指派；若沒有滿足上述條件的機(jī)位，則將其分配到符合約束條件的任一遠(yuǎn)機(jī)位。

算法的流程圖如圖4所示。

圖4 機(jī)位再分配算法流程圖Fig.4 Process of gate reassignment algorithm

1.2.3 再分配算例分析

仍以咸陽機(jī)場為例，由于咸陽機(jī)場地處中國中心位置，多條航線在此交叉匯集，執(zhí)行中轉(zhuǎn)飛行的航班班次較多，航班延誤較為嚴(yán)重，使得預(yù)指派的方案不能順利實(shí)施。如表2中的11號航班，預(yù)計(jì)進(jìn)港時(shí)間相比于計(jì)劃進(jìn)港時(shí)間延誤了50 min，因而有可能造成對其后繼航班的影響。按照表2中的航班運(yùn)行數(shù)據(jù)，根據(jù)機(jī)場對延誤航班的界定規(guī)則，可以判定在該時(shí)段內(nèi)的延誤航班為第 5、7、11、13、15、18、22、34 和 36 號航班（第25號航班為取消飛行任務(wù)的航班）。算法通過查找這些航班的預(yù)分配機(jī)位，搜索該機(jī)位的毗鄰后繼航班的計(jì)劃時(shí)刻表，并通過比較延誤航班的預(yù)計(jì)離港時(shí)間和后繼航班的計(jì)劃進(jìn)港時(shí)間來判定是否要對后繼航班進(jìn)行機(jī)位的再分配，結(jié)果如表4所示。由于算法限制了再分配的機(jī)位必須是在后繼航班過站時(shí)間內(nèi)的占用狀態(tài)未發(fā)生變化的機(jī)位范圍內(nèi)進(jìn)行選擇，從而保證了再分配的機(jī)位對預(yù)分配機(jī)位的擾動性為0。在此基礎(chǔ)上，再分配的機(jī)位也以保證靠橋率和旅客步行距離最小這兩個(gè)指標(biāo)為依據(jù)進(jìn)行搜索選擇。因此，該方案在一定程度上降低了延誤航班對預(yù)分配方案的影響，同時(shí)達(dá)到了更加安全、高效和優(yōu)質(zhì)服務(wù)的目的。

表4 針對延誤航班的機(jī)位再分配算法計(jì)算結(jié)果Tab.4 Result of gate re-assignment due to delayed flight

2 結(jié)語

合理的機(jī)位指派可以幫助航空公司減少時(shí)間延誤，有利于航空公司的良好形象；同時(shí)可以減少旅客從機(jī)位到機(jī)位以及出、入口的步行時(shí)間和距離，提高機(jī)場的運(yùn)營效益和服務(wù)質(zhì)量。本文根據(jù)機(jī)場停機(jī)位的規(guī)劃和屬性特點(diǎn)，提出了一種簡要算法，可根據(jù)航班時(shí)刻表自動對次日進(jìn)離港航班進(jìn)行機(jī)位的預(yù)指派，并針對實(shí)際運(yùn)行中延誤航班對預(yù)指派結(jié)果的干擾，設(shè)計(jì)了相應(yīng)的機(jī)位再分配方案。結(jié)果表明，該算法可以提高飛機(jī)的靠橋率，在一定程度上減少了出入旅客的步行距離，同時(shí)降低了延誤航班對預(yù)分配結(jié)果的干擾。但本文僅考慮了在延誤航班預(yù)達(dá)本場時(shí)間確定和只針對機(jī)位毗鄰后繼航班再分配的情況，對于未知預(yù)達(dá)時(shí)間和大面積延誤的情況，涉及的約束條件和算法更加復(fù)雜，還需進(jìn)一步研究。

[1]常 鋼，魏生民.停機(jī)位分配問題優(yōu)化技術(shù)[J].中國民航學(xué)院學(xué)報(bào)，2006，24（2），25-29.

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

[3]文 軍，李 冰，王清蓉，等.機(jī)場停機(jī)位分配問題的圖著色模型及其算法[J].系統(tǒng)工程理論方法應(yīng)用，2005，14（2），136-140.

[4]鞠姝妹，許 俐.基于GSAA的停機(jī)位指派優(yōu)化問題的研究[J].交通運(yùn)輸系統(tǒng)工程與信息，2008，8（1），138-143.

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

[6]王 力，劉長友，涂奉生.民用機(jī)場停機(jī)位優(yōu)化配置[J].南京航空航天大學(xué)學(xué)報(bào)，2006，38（4），433-437.

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