基于網絡流理論的停機位分配多目標優化模型

袁 媛， 翟好鑫

(沈陽航空航天大學經濟與管理學院, 沈陽 110136)

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

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

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

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

1.1 假設條件

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

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

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

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

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

1.2 數學符號

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

1.3 網絡流模型

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

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

1.3.1 節點

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

1.3.2 弧

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

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

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

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

(1)

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

1.3.3 變量

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

1.4 約束條件

(2)

i=j,k∈G

(3)

i=j,k∈G

(4)

(5)

(6)

?i∈F,k∈G

(7)

(8)

2 目標函數

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

2.1 旅客

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

(9)

2.2 航空公司

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

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

(10)

Ci,k計算方式為

(11)

2.3 機場

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

(12)

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

(13)

2.4 多目標優化

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

(14)

3 實例分析

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

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

3.1 求解速度分析

傳統數學模型對停機位與航班的唯一性、同一停機位相鄰航班的時間間隔和停機位-航班類型匹配進行約束并建模[16]，利用傳統數學模型和建立的多商品網絡流模型分別對3種停機位-航班規模進行求解并記錄求解時間，對比發現以下結果。

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

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

3.2 分配結果分析

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

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

表2 貪婪啟發式與單目標優化目標函數值對比Table 2 Comparison of objective function values between greedy heuristic and single objective optimization

通過對36種權重賦值方案對應的停機位分配結果進行分析發現以下結果。

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

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

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

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

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

3.3 較優方案選擇

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

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

表3 停機位分配結果Table 3 The results of gate assignment

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

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

4 結論

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

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

(3)停機位資源的高效率使用是多方主體共同合作的結果，要實現多目標優化模型的結果，不僅需要航空公司和機場之間形成長期合作的溝通機制，還需要根據航空運輸業的發展動態調整停機位分配規劃。

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