袁 媛， 翟好鑫

(沈陽航空航天大學(xué)經(jīng)濟與管理學(xué)院, 沈陽 110136)

機場停機位作為進港飛機運行的終點和離港飛機運行的起點，其為飛機停放、旅客上下機、行李及貨物裝載提供了場所，也是航空與地面運輸?shù)霓D(zhuǎn)接點。隨著航空運輸業(yè)的快速發(fā)展，中國各大機場的航班數(shù)量都有明顯增長，有限的機場設(shè)施資源逐漸成為限制民航事業(yè)發(fā)展的重要因素，因此，合理地分配使用各項設(shè)施資源是機場需解決的主要問題。而停機位作為機場運輸資源的核心，其分配結(jié)果對大量物資、旅客及相關(guān)工作人員都產(chǎn)生影響，分配計劃對機場航班和航線也有著直接的經(jīng)濟影響。作為機場運營管理人員日常面臨的重要問題之一，停機位分配的目的是把每個航班分配至可用的登機口，同時也最大限度地為乘客和機場的運營效率提供便利，這就需要一個高效的解決方法來提供合理的停機位分配數(shù)據(jù)。

停機位分配問題(gate assignment problem, GAP)的研究方法大致分為數(shù)學(xué)規(guī)劃[1]、智能優(yōu)化[2]和系統(tǒng)仿真[3]等3類。由于數(shù)學(xué)規(guī)劃法中基于圖論的網(wǎng)絡(luò)流模型自身較好的適應(yīng)性和可擴展性，近幾年中外文獻選用此方法進行研究。國外文獻較早將網(wǎng)絡(luò)流理論運用到停機位分配中，二值整數(shù)多商品網(wǎng)絡(luò)流模型在實際問題的分解方法中被證明計算效率很高[4]，而建立兩個多商品網(wǎng)絡(luò)流模型[5]可以有效地解決停機位再分配問題，對于多目標優(yōu)化模型[6]，利用多商品網(wǎng)絡(luò)流同樣可以得到合理的停機位分配模型。在大規(guī)模停機位分配問題中，中國文獻在計算時采用分子區(qū)的策略[7]來加速對網(wǎng)絡(luò)流模型的求解，而采用多商品網(wǎng)絡(luò)流模型建立的雙目標停機位實時再分配優(yōu)化模型[8]，在仿真實驗中達到了良好的時效性和乘客滿意度。中外文獻將多商品網(wǎng)絡(luò)流的停機位魯棒性結(jié)合研究，部分文獻利用算法加速模型求解?，F(xiàn)將網(wǎng)絡(luò)流理論應(yīng)用到多目標優(yōu)化模型中，首先對網(wǎng)絡(luò)流模型進行詳細描述，并用實例驗證其在大規(guī)模停機位分配應(yīng)用中的適用性和高效性，同時還證明其對多目標優(yōu)化問題的有效性。

中外學(xué)者對于停機位分配模型的研究主要考慮旅客步行距離[9]、預(yù)分配方案的魯棒性[10]或停機位再分配[11-12]建立單目標優(yōu)化模型，或是兼顧停機位使用效率、航空公司公平性、航空綠色發(fā)展等建立雙目標停機位分配優(yōu)化模型[13-14]。但是這些研究只能反映停機位分配需要解決的部分問題。為此，在實際的停機位分配過程中平衡機場、旅客和航空公司的多方利益，考慮停機位分配過程中新的特征，改進停機位分配中實際存在的條件約束和優(yōu)化目標，建立更高效的分配模型，盡可能使調(diào)度結(jié)果的綜合效能最大化。在進行優(yōu)化目標選擇時，綜合考慮旅客步行距離、航空公司成本與停機位浪費率進行協(xié)同決策，以期提升旅客滿意度，增大機場運行效率，降低航空公司運行成本，達到綜合效益最優(yōu)。

1 停機位分配問題模型描述

1.1 假設(shè)條件

在模型建立之前，先提出如下假設(shè)條件。

(1)信息完備假設(shè)：在機場某個工作日開始之前，制訂決策所必需的航班計劃、機場資源等信息是已知且完備的，同時不考慮過夜航班。

(2)容量滿足假設(shè)：航班總量及其進離港時間分布保持在機場容量許可范圍之內(nèi)，遠機位可以容納無限架次飛機，即任何時刻，機場總可以為任一進港航班分配一個停機位，盡管不是最優(yōu)但一定可行。

(3)停機位使用假設(shè)：對到達航班分配停機位時采取“先到先服務(wù)”服務(wù)策略，不組合使用停機位，不考慮使用備用停機位以及維修機位。

(4)機場為單跑道，每一個時間段僅允許一架次飛機降落。

1.2 數(shù)學(xué)符號

停機位分配問題相關(guān)的數(shù)學(xué)符號定義如下:F為停機位分配計劃期內(nèi)所有到港航班集合；B為停機位分配計劃期內(nèi)所有離港航班集合；G為停機位分配計劃期可提供的所有停機位集合；M為計劃期內(nèi)的航班總數(shù)；N為機場的停機位總數(shù)，其中N+1為遠機位；i為進港航班對應(yīng)序號，且?i∈F;j為離港航班對應(yīng)序號，且?j∈B;k為停機位對應(yīng)序號，且?k∈G;ATi為航班i計劃到港時刻;DTi為航班i計劃離港時刻;Ei為航班i的停機位占用時間，即航班過站時間，Ei=DTi-ATi;ci為執(zhí)行航班i的航空器大小;ρk為停機位k允許停放的最大機型;Ω為一個很大的正數(shù)。

1.3 網(wǎng)絡(luò)流模型

多商品網(wǎng)絡(luò)流的圖形是通過網(wǎng)絡(luò)中的停機位弧在箭頭的方向流動來表示的。停機位(G1，G2，…，GN)代表商品，這些商品是從源節(jié)點(S)到終節(jié)點(T)通過中間的航班到達節(jié)點(A1，A2，…，AM)和離開節(jié)點(D1，D2，…，DM)連接，每一組節(jié)點弧沿箭頭方向在網(wǎng)絡(luò)中從源節(jié)點(S)流經(jīng)到達節(jié)點和離開節(jié)點流向終節(jié)點(T)的過程構(gòu)成一個完整的商品流，多個商品流相互交錯形成多商品網(wǎng)絡(luò)流模型。以3個停機位5個航班為例，圖1所示為其多商品網(wǎng)絡(luò)流模型的一個可行分配方案。

圖1 多商品網(wǎng)絡(luò)流模型的一個可行分配方案Fig.1 A feasible allocation plan of the multi-commodity network flow model

1.3.1 節(jié)點

S為源節(jié)點，T為終節(jié)點，(A1，A2，…，AM)為到港航班節(jié)點，(D1，D2，…，DM)為離港航班節(jié)點。其中源節(jié)點和終節(jié)點是虛擬的節(jié)點，只表示網(wǎng)絡(luò)發(fā)散之源和匯聚之處。

1.3.2 弧

(1)流入弧。流入弧是指連接源節(jié)點(S)到港航班節(jié)點(Ai)之間的弧，使用弧(S，i)表示，其存在表示停機位被使用，且航班i第一個分配給停機位。

(2)服務(wù)弧。服務(wù)弧是指連接到港航班節(jié)點(Ai)到離港航班節(jié)點(Dj)之間的弧。服務(wù)弧從航班到達時開始使用停機位，一直到航班離開為止，使用弧(i，j)(s.t.i=j)表示，其存在表示航班i在停機位接受服務(wù)。航班的服務(wù)由乘客離機、加油、清洗和乘客登機等服務(wù)組成。

(3)流出弧。流出弧是指連接離港航班節(jié)點(Dj)到終節(jié)點(T)之間的弧，使用弧(j，T)表示，該弧的存在表示航班j最后一個分配給停機位，并從此停機位離開。

(4)反饋弧。反饋弧是指連接離港航班節(jié)點(Dj)和到港航班節(jié)點(Ai)之間的弧，其流的方向與其他流向相反，使用弧(j，i)(s. t.j≠i)表示，其存在表示航班i在航班j之后使用停機位(Gk)，如圖1中到港航班節(jié)點(A2)與離港航班節(jié)點(D1)連接的反饋弧，即表示航班2就在航班1之后被安排在第1個停機位。反饋弧只有在航班i的到達時刻比航班j的離開時刻大時才存在，且同用一個停機位的相鄰航班之間有安全間隔時間p，取p=30 min。定義一個參數(shù)Iji如下：

(1)

(5)穿過弧。穿過弧是指連接源節(jié)點(S)到終節(jié)點(T)之間的弧，使用弧(S，T)表示，其存在表示沒有使用任何中間節(jié)點(到達節(jié)點、離開節(jié)點)，即沒有航班分配到該停機位。如圖1中沒有航班?？吭诘?個停機位。

1.3.3 變量

多商品網(wǎng)絡(luò)流中的0-1整數(shù)變量與5種類型的弧一一對應(yīng)：變量XkSi表示航班i第一個分在停機位k，即從源節(jié)點S到到達航班節(jié)點(Ai)的停機位(Gk)流入弧；變量Xkij表示航班i在停機位k接受服務(wù)，即從到港航班節(jié)點(Ai)到離港航班節(jié)點(Dj)的停機位(Gk)服務(wù)弧(i=j)；變量XkjT表示航班j最后一個流經(jīng)停機位k，即從離港航班節(jié)點(Dj)到終節(jié)點(T)的停機位(Gk)流出??；變量Xkji表示航班i在航班j之后使用停機位k，即從離港航班節(jié)點(Dj)到港航班節(jié)點(Ai)的停機位(Gk)反饋弧(i≠j)；變量XkST表示沒有航班流經(jīng)停機位k，即從源節(jié)點(S)到終節(jié)點(T)的停機位(Gk)穿過弧。

1.4 約束條件

(2)

i=j,k∈G

(3)

i=j,k∈G

(4)

(5)

(6)

?i∈F,k∈G

(7)

(8)

2 目標函數(shù)

由于停機位分配問題涉及到旅客步行距離、航空公司的經(jīng)濟效益、機場資源的有效利用以及地面服務(wù)部門的工作場所等多個方面，因此從不同角度出發(fā)可以得到不同的優(yōu)化模型，而不同機場的側(cè)重點也不相同。采用線性加權(quán)法權(quán)衡多方主體利益來優(yōu)化目標函數(shù)指標。

2.1 旅客

從旅客的角度，停機位分配的主要目的是提高旅客滿意度。以最小化進離港旅客步行距離為目標建立停機位分配目標函數(shù)為

(9)

2.2 航空公司

航空公司運行過程中，應(yīng)該盡可能地降低航空器運行成本和停機成本。航空器運行成本往往受到惡劣天氣、突發(fā)事故等不可控因素的影響[15]，且較難控制。而停機成本受到分配效率、分配公平性等因素影響較多，可以通過有效的管理降低航空器停機成本。

根據(jù)不同機型的運行性能數(shù)據(jù)設(shè)定滑行油耗為: 大型航空器 40 kg/min、中型航空器22 kg/min、小型航空器12 kg/min。航油價格取7 500元/t。按照民航局2007年頒布的《民用機場收費改革實施方案》中的停機位收費標準和分配原則，假設(shè)所有靠橋航班均采用單橋，并建立最小化航空器運行成本和停機成本的停機位分配目標函數(shù)為

(10)

Ci,k計算方式為

(11)

2.3 機場

為了充分利用機場的停機位資源，停機位大小要與所停放的飛機機型相匹配，即對于小型機，優(yōu)先為其分配小型停機位，如果當(dāng)前沒有小型停機位，則再考慮將其分配到空閑的中型停機位上，最后考慮將其分配到空閑的大型停機位上；對于中型機，不能分配到小型停機位，如果當(dāng)前沒有中型停機位，則再考慮將其分配到空閑的大型停機位上；對于大型機，只能被分配到大型停機位上，如果當(dāng)前暫無空閑停機位，則將到達的飛機停放至遠機位。由于機型與停機位不匹配時會造成停機位資源的浪費，因此最大化停機位利用率就是最小化停機位資源的浪費。對于分配到停機位k的航班i，給定一個參數(shù)yik來表示停機位資源的浪費率:

(12)

所以最小化停機位資源浪費率的停機位分配目標函數(shù)為

(13)

2.4 多目標優(yōu)化

為平衡機場、旅客和航空公司的多方主體利益，建立多目標優(yōu)化模型盡可能使調(diào)度結(jié)果的綜合效能最大化，并利用線性加權(quán)法進行系統(tǒng)分析，根據(jù)各目標的優(yōu)先級把多目標優(yōu)化模型轉(zhuǎn)化為綜合目標進行優(yōu)化。由于目標函數(shù)具有各自的量綱，其單位和數(shù)量級都有所差別，因此不能簡單地通過設(shè)置權(quán)重因子來得到最終的目標函數(shù)，而需要對效用函數(shù)進行歸一化處理。設(shè)βm為第m個目標函數(shù)的權(quán)重，Zmax=maxZm，則經(jīng)過歸一化處理的效果函數(shù)為

(14)

3 實例分析

采用某機場實際運行的58個航班數(shù)據(jù)和航站樓的10個典型的近機位、一個遠機位進行實驗，其中G01、G02、G03、G04、G05、G06機位為大型機位；G07、G08、G09號機位為中型機位；G10號機位為小型機位。同時選取某日08：00—22：00出發(fā)或到達的航班驗證和求解模型。算例數(shù)據(jù)統(tǒng)計如表1所示。

表1 某機場待分配航班數(shù)據(jù)Table 1 Flight data to be assigned in an airport

3.1 求解速度分析

傳統(tǒng)數(shù)學(xué)模型對停機位與航班的唯一性、同一停機位相鄰航班的時間間隔和停機位-航班類型匹配進行約束并建模[16]，利用傳統(tǒng)數(shù)學(xué)模型和建立的多商品網(wǎng)絡(luò)流模型分別對3種停機位-航班規(guī)模進行求解并記錄求解時間，對比發(fā)現(xiàn)以下結(jié)果。

所建立的多商品網(wǎng)絡(luò)流模型對于停機位分配問題的求解速度有明顯的提升(圖2)。隨著停機位-航班規(guī)模的增加，求解速度的提升越來越明顯，當(dāng)對21個停機位116個航班進行分配停機位時，多商品網(wǎng)絡(luò)流模型的平均求解速度比傳統(tǒng)數(shù)學(xué)模型增長了38.31%?？梢娝⒌亩嗌唐肪W(wǎng)絡(luò)流模型在大規(guī)模停機位分配問題中的高效性和合理性。另外，所建模型對多目標優(yōu)化函數(shù)的求解速度與大部分單一目標函數(shù)相比較快，當(dāng)對21個停機位116個航班進行分配停機位時，多商品網(wǎng)絡(luò)流模型對多目標函數(shù)求解速度較單目標函數(shù)求解速度平均快了13.49%，尤其是相對于乘客步行距離單目標函數(shù)速度增長了21.17%，驗證了多商品網(wǎng)絡(luò)流模型對于多目標優(yōu)化函數(shù)求解的可行性和高效性。

圖2 兩種模型求解時間對比Fig.2 Comparison chart of solution time of two models

3.2 分配結(jié)果分析

首先采用貪婪啟發(fā)式，根據(jù)“先到先服務(wù)”的原則，綜合考慮停機位和航班類型對航班分配停機位，盡量讓同等類型的航班和停機位匹配，相同條件下選擇距離較近的停機位；若沒有同等類型的停機位與其相匹配，再選擇次近類型的停機位，相同條件下選擇距離較近的停機位。

分別對單目標函數(shù)求得最優(yōu)后，與貪婪啟發(fā)式對比分析如表2所示。對比數(shù)據(jù)可見，旅客、航空公司和機場主體利益之間會互相制約、互相影響。當(dāng)盡量多地考慮停機位類型利用率時會優(yōu)先將航班分配到與其大小匹配的停機位，此時停機位類型利用率相對貪婪啟發(fā)式優(yōu)化了4.69%，從而忽視行李大廳至停機位的距離和安檢口至停機位的距離，導(dǎo)致進離港旅客行走距離增加；同樣地，如果只考慮乘客滿意度而最小化旅客步行距離使得旅客行走距離相對貪婪啟發(fā)式優(yōu)化5.18%，極大可能導(dǎo)致中小型航班分配在較近的大型停機位。但是，各目標函數(shù)都有其現(xiàn)實意義。

表2 貪婪啟發(fā)式與單目標優(yōu)化目標函數(shù)值對比Table 2 Comparison of objective function values between greedy heuristic and single objective optimization

通過對36種權(quán)重賦值方案對應(yīng)的停機位分配結(jié)果進行分析發(fā)現(xiàn)以下結(jié)果。

(1)存在3種不隨權(quán)重變化的停機位-航班組合，如中型航班F35、F50一直分配在中型停機位G07。同等類型的航班-停機位相互匹配，若同時進離港時間只允許其停放在此停機位，或此停機位距離值機柜臺距離較近，則航班會一直分配在此停機位。

(2)存在不同航班分配的停機位一直一致，如無論何種目標函數(shù)權(quán)重，航班F08和航班F15的停機位一直一致。分析上述航班進離港時間可以發(fā)現(xiàn)，兩個分配同一停機位的相鄰航班的間隔時間較為接近安全時間間隔，可以增加為后續(xù)航班分配在此停機位爭取更多的可利用時間。

(3)臨近的相同機型的航班在恰好與其匹配的停機位之間互換，如無論3個目標函數(shù)的權(quán)重如何分配，中型航班F01、F03在中型停機位G07、G08中互換。由此可見，相同機型的航班在與其相匹配的停機位之間互換不會對乘客步行距離、航空公司成本和停機位浪費率造成太多的負面影響。

(4)臨近的不同機型的航班在可與其匹配的停機位之間互換，如小型航班F33、F34在前3類目標函數(shù)值下停機位分配在G08和G10，而在第4類目標函數(shù)值(權(quán)重80/10/10)下分配在G04和G08，減少了乘客步行距離，卻使得停機位利用率明顯降低?？梢姴煌哪繕撕瘮?shù)取值下航班所分配的停機位會在匹配的前提下互換。

(5)遠機位使用情況：分析結(jié)果可以看出，只有大型航班F36或F37會分配至遠機位。由于航班?？吭谶h機位需要使用擺渡車等機場設(shè)施資源，耗費機場、航空公司的人力物力成本。由此可知，機場進行停機位分配時，如果可供分配的近機位不夠充裕時，應(yīng)盡可能地將大型航班安排在遠機位。

3.3 較優(yōu)方案選擇

根據(jù)表2結(jié)果設(shè)定各目標函數(shù)優(yōu)先級：旅客行走距離目標函數(shù)優(yōu)先于機位類型利用率目標函數(shù)，機位類型利用率目標函數(shù)優(yōu)先于航班成本目標函數(shù)。由于數(shù)據(jù)的理想化，導(dǎo)致不同的賦值權(quán)重得到不同的分配方式相同的目標函數(shù)值的情況，分析得出，該優(yōu)先級下當(dāng)賦值權(quán)重為50/10/40、50/20/30和60/10/30時目標函數(shù)值較優(yōu)，此時進離港旅客行走距離較貪婪啟發(fā)式優(yōu)化了2.08%，航班成本優(yōu)化了0.08%，機位類型利用率優(yōu)化了4.69%，比貪婪啟發(fā)式各個方面均有改善。

但由于3種分配方式下，不同的停機位的利用時間不同，故綜合考慮以上3種權(quán)重賦值時的停機位分配方案，3個目標函數(shù)賦值分別為60/10/30時不同停機位時間上的絕對利用率和相對利用率較為均衡，這樣就使得機場停機位資源的使用和機場各工作人員的工作強度較為均衡，同時也增強了停機位分配的魯棒性。相應(yīng)的停機位分配結(jié)果如表3所示，其對應(yīng)的甘特圖如圖3所示，每個停機位的絕對利用時間和相對利用時間如圖4所示。

表3 停機位分配結(jié)果Table 3 The results of gate assignment

圖3 較優(yōu)權(quán)重(60/10/30)下停機位分配甘特圖Fig.3 The Gantt chart of gate assignment under better weight (60/10/30)

圖4 較優(yōu)權(quán)重(60/10/30)下停機位利用時間Fig.4 The utilization time of gate under better weight(60/10/30)

4 結(jié)論

(1)建立了以旅客、航空公司、機場多方主體利益為目標的停機位分配策略，運用多商品網(wǎng)絡(luò)流進行建模并實現(xiàn)快速求解。

(2)通過線性加權(quán)法對多目標權(quán)重進行賦值，并在實例中分析不同主體利益的優(yōu)先級下停機位分配結(jié)果的特征，進而選擇一種較為經(jīng)濟、適用、滿意度高的停機位分配結(jié)果，在兼顧國際民航組織有關(guān)機場服務(wù)質(zhì)量的規(guī)定的同時，也能很好地均衡各主體之間的利益，使旅客獲得了不錯的滿意度，充分利用了停機位資源，降低了航空公司的成本，同時還保證了停機位分配的魯棒性。

(3)停機位資源的高效率使用是多方主體共同合作的結(jié)果，要實現(xiàn)多目標優(yōu)化模型的結(jié)果，不僅需要航空公司和機場之間形成長期合作的溝通機制，還需要根據(jù)航空運輸業(yè)的發(fā)展動態(tài)調(diào)整停機位分配規(guī)劃。

(4)將網(wǎng)絡(luò)流理論運用在多目標優(yōu)化的停機位分配問題中，考慮停機位分配的動態(tài)性可以作為停機位分配模型進一步研究方向。