楊 越，王 犇，劉 楊

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

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

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

1.1 機位預指派方法

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

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

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

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

其中

z為當日航班總量。

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

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

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

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

1）航班唯一屬性約束：每個進港航班只能分配一個機位

其中：M為待分配機位集合；N為當日航班集合。

2）機位唯一屬性約束：每個機位一次只能指派給1架飛機

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

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

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

1.1.2 機位預分配算法設計

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

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

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

3）順序讀取已排序的航班。若航班Fi為出港航班，則釋放當前Fi所占用機位k，將該機位標記為kfree，并令Mfree=Mfree+1。若航班Fi為進港航班，則找出一個空閑機位k∈Mfree，使其滿足

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

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

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

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

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

圖1 機位預分配算法流程圖Fig.1 Process of gate pre-assignment algorithm

1.1.3 預分配算例分析

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

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

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

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

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

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

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

1.2 機位的再分配方案

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

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

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

1.2.1 延誤航班的界定

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

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

2）出港延誤：

a）與進港航班相關的延誤：若未進港的航班已有預達本場時間，則預達本場時間+過站時間晚于本場計劃出港時間的航班視為延誤；若未進港的航班直到計劃離港前30 min仍無預達本場時間，則將其視為延誤航班；

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

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

1.2.2 機位再分配算法設計

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

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

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

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

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

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

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

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

1.2.3 再分配算例分析

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

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

2 結(jié)語

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

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

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

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

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

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

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

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