基于松弛算法的停機位分配優化方法

邢志偉，喬 迪*，劉洪恩，高志偉，羅 曉，羅 謙

（1.中國民航大學電子信息與自動化學院，天津 300300；2.中國民航局第二研究所工程技術研究中心，成都 610041）

（?通信作者電子郵箱331746800@qq.com）

0 引言

隨著近年來旅客吞吐量和飛機起降架次逐年增加，航班延誤對機場運行的擾動日益嚴重。停機位資源的分配是機場運營管理的重要環節之一，合理的機位資源分配方案是減少沖突、提高機位利用率的重要途徑。在航空需求無限增長與機位資源有限的不均衡現象日益突出的情況下，如何在減少航班延誤或提前到達對機位分配方案產生的沖突的同時又提高機位利用率是機場運行亟待解決的問題。

目前，已有很多國內外學者分別從不同的角度對機位分配問題進行了深入研究。李亞玲等［1］以最大化停機位利用率和最小化旅客行走路程為優化目標，提出了能夠動態、靈活進行機位分配的禁忌搜索算法；Yu等［2］從緩沖時間成本、設備及工作人員調度成本、旅客滿意度等方面進行建模，并通過將二次模型轉化為等效的混合整數規劃（Mixed Integer Programming，MIP）模型用啟發式算法進行求解；Liu 等［3］以最小化空閑時間段和遠機位數為優化目標，設計相應的遺傳算法；Behrends 等［4］考慮了因旅客登機及貨物運輸對航班造成延誤影響并設計遺傳算法求解；Deng 等［5］通過分析停機位和航班特點，以空閑時間均衡、旅客行走距離最短、遠機位數最小為目標，設計了一種改進的蟻群優化算法；Stollenwerk 等［6］以旅客總的換乘時間最短為優化目標，設計量子退火方法進行求解，但是只能解決小范圍的問題，當范圍過大時花費的成本較高；馮霞等［7］考慮了航班在推出-滑入機位時在滑行道存在的沖突情況，在模型中添加防沖突約束，并設計了禁忌搜索算法求解。以上研究均未考慮航班延誤對機位分配結果的影響，且旅客的行走距離、旅客換乘時間等數據不易在機場實際運行中準確地獲取。從提高魯棒性的角度出發：李軍會等［8］通過分析航班延誤分布，以機位沖突概率最小為目標，設計貪婪禁忌搜索算法；Kumar 等［9］從新的角度出發，提出了以區域使用成本最小、運營收入最大、機位分配的魯棒性這幾個角度出發進行設計；劉君強等［10］以最小延誤費用原則為約束，采用混合集合規劃進行指派模型的建立與求解；Dorndorf 等［11］以最小化機位沖突為目標，將此問題看作是區域劃分問題來求解，在設計過程中沒有像其他研究一樣建立虛擬停機位；楊新湦等［12］以機場運行系統擾動最小為優化目標，建立停機位與滑行路徑臨時改派雙層模型；Kim 等［13］通過分析航班到離港情況建立了避免沖突的魯棒性模型；Van Schaijk 等［14］提出了一種將確定的機位約束由隨機機位約束替換的方法，并建立了線性規劃模型，驗證了該方法具有較好的魯棒性。

以上大部分研究都是從魯棒性、旅客行走距離、換乘時間等方面進行研究，未考慮到機位利用率與魯棒性的關系。本文綜合考慮了停機位的利用率及魯棒性，提出了一種新的停機位分配方法，通過分析航班到達的分布特點，設計同機位相鄰航班間的緩沖時間，并考慮運行中的相關約束，建立停機位分配模型。針對該分配模型的特點采用拉格朗日松弛算法對其進行仿真模擬優化，并與實際機場運行數據進行驗證和對比，說明本文所提出的方法能夠較好地提高機位利用率，并減少航班沖突數量。

1 停機位分配模型

1.1 問題描述與模型假設

機場停機位分為近機位和遠機位，近機位配有廊橋，乘客上下飛機方便，乘客在遠機位登機則需要借助擺渡車，不但給旅客帶來不便，而且增加機場運營成本。停機位分配是指將有限的停機位資源合理地分配給某個時間段內的到港航班，兼顧旅客登轉機時間、航班地面服務時間、航班類型、航班時刻、停機位類型等因素，最終實現對未來某個時間段內的到港航班分配合適的停機位，并且在分配過程中力求提高機場運行效率、減少運營成本，同時又能提高旅客滿意度。

不失一般性，需要解決的問題可以描述為：存在m個停機位為航班停靠及旅客登機服務，選取的時間段內有n個航班需要停靠在機位上。穩定性是反映停機位分配方案魯棒性的指標，即停機位分配方案在受到擾動后的偏離程度，假設QA為實際運行時偏離停機位分配方案的航班數量，n為總的航班數量，則可用QA/n的值來評價分配方案的魯棒性。如果在同一機位相鄰兩航班間的時間間隔較大時，前序航班產生的延誤對后續航班的影響較小，則QA/n的值越小魯棒性越好；反之，若兩航班間的間隔過小時，前序航班產生的延誤對同一機位后續航班的影響較大，則QA/n的值越大魯棒性越差。另一方面，如果兩航班間的間隔時間較大，雖然魯棒性很好，但是會造成資源浪費，因此如何合理地進行設計是一個關鍵問題。航班j和航班i是分配在同一機位的兩個航班，且航班j是航班i的緊后航班，[di，aj]表示航班i和j間的空閑時間窗。結合機場運行實際需求，設定停機位分配的優化目標如下：

1）最小化每個停機位的空閑時間，即所有停機位的未被占用時間總和最小。

2）最小化遠機位的占用時間，即盡可能把航班分配到近機位，最小化遠機位個數，從而既方便旅客登機又減少擺渡車等的費用。

本文研究停機位分配問題，基于如下假設：

1）機場停機位數量充足，在某時間段內不會出現航班無機位可分配的情況；

2）不考慮某些特定區域機位指定給某固定的航空公司使用；

3）進港航班均服從“先到先服務”的原則；

4）航班計劃信息完備已知，包括航班機型、到離港航班時刻計劃等；

5）不考慮某些停機位因設備故障等特殊原因而導致的不可用的情況。

1.2 模型構建

1.2.1 符號變量說明

停機位分配模型所使用的符號參數說明如下：

1）輸入變量：N為航班集合；M為停機位集合；εi為航班i的飛機型號；ρk為機位k允許停放的最大機型；TP為同一機位相鄰兩個航班間的最小安全緩沖時間；ai為航班i的到港時間；di為航班i的離港時間；ti為航班i在遠機位的停放時間；Tik為機位k相鄰兩航班間的空閑時間；U為航班過站時間；i，j=1，2，…，n，i≠j；k=1，2，…，m；飛機型號為｛1，2，3｝；停機位大小為｛A，B，C｝，分別代表大型、中型、小型停機位。

2）決策變量：yik為機位k是否指派給航班i，yik=，i=1，2，…，n，k=1，2，…，m；Zi為航班i是否被分配到遠機位，；yijk為相鄰兩航班i、j是否被分配到同一停機位k，同時i＜j，yijk=。

1.2.2 優化目標

根據上述分析，停機位分配模型的優化目標如下。

1）最小化各機位空閑時間為：

2）最小化遠機位占用時間為：

1.2.3 約束條件

如果航班i和航班j為同機位的相鄰航班，則兩航班間要有安全緩沖時間，需要滿足：航班i離港時間-航班j進港時間≥最小安全緩沖時間；如果航班i和航班j為同機位的緊前緊后航班，可以推算兩航班間的空閑時間應小于航班過站時間：航班i離港時間-航班j進港時間≤航班過站時間。綜上停機位分配模型的約束條件如下：

式（3）表示每架航班只能且必須分配一個停機位。式（4）表示同一停機位在同一時刻只能停放一架飛機，分兩種情況：1）航班i先被分配到停機位k上，航班j后被分配到停機位k上，即ai＜di＜aj＜dj；2）航班j先被分配到停機位k上，航班i后被分配到停機位k上，即aj＜dj＜ai＜di。式（5）表示機位大小與機型的約束，ψ為一個足夠大的正整數。式（6）表示分配在同一機位的相鄰兩架航班的最小緩沖時間約束。式（7）表示分配到同一機位的兩航班間隔時間與過站時間的約束。式（8）表示機位空閑時間。式（9）表示航班占用機位時間。

2 基于雙目標松弛算法的停機位分配模型

根據1.2 節的介紹，停機位分配調度模型是一個典型的NP（Non-deterministic Polynomial）-hard 混合整數規劃問題，拉格朗日松弛算法可以通過將機位分配問題中的困難約束條件松弛到目標函數中，從而降低模型的求解難度。同時通過求解松弛問題，可獲得原問題的解的上下界，然后對拉格朗日乘子進行不斷的迭代更新，使得松弛問題的解逐漸逼近原問題的解。

2.1 拉格朗日對偶解的分析

假設zIP為本文機位分配中的目標函數，zLR為將機位分配模型中的某個約束條件進行松弛后其對應的松弛問題，由于約束條件松弛，解空間范圍增大。這時，zLR為使得近機位空閑時間和遠機位占用最小解的下界，zLD為原問題的拉格朗日松弛對偶問題。若松弛問題存在可行解，則有ZLR≤ZLD≤ZIP表示其對應問題解的一個值。為了更好地接近原問題的最優解，因此用機位分配問題的拉格朗日對偶問題的對偶解來代替機位松弛問題的解。證明如下：

有限個離散點的集合Q={x|Bx≥d，x∈}是該問題的解集，且可證明Con(Q)為凸集。

得到：

若zLD的目標值有界，則

s.t.Ax≥b（松弛約束）

即zLD=min{cTx|Ax≥b，x∈Con(Q)}，所以有：

然后在已知的可行解域中對凸函數使用次梯度算法通過不斷的迭代求得全局最優解。

2.2 機位分配問題的拉格朗日對偶松弛問題

對機位分配模型中的約束式（3）松弛，則原問題變成了不考慮機位約束的問題。松弛后的模型相較于原模型約束條件減少一個，限制因素減弱，即解空間增大。拉格朗日松弛算法是一種求最值問題很有效的方法，設λi是非負的拉格朗日乘子，zLR為機位分配問題的拉格朗日松弛問題，則有：

上述目標函數需滿足式（4）～式（9）和式（11）：

記zLD為原問題的拉格朗日松弛對偶問題，則有：

將式（13）的拉格朗日松弛對偶問題分成兩部分：式（14）為非正則子問題；式（15）為正則子問題。當給定一組拉格朗日乘子λi時，式（14）為一個確定的值。正則子問題可基于不同航班進行分解。

正則子問題可以給予航班分解：

其中，λi反映了航班占用機位k所需要付出的代價，占用不同的機位需要付出相應的代價。式（16）的目標是確定航班占用的機位及其空閑的時間，使其占用機位所付出的代價和空閑時間總和達到最小。

2.3 次梯度算法優化拉格朗日乘子

次梯度算法是一種求解拉格朗日問題的有效方法，Tik、Zi、ti、yik可以通過子問題的求解過程得到。

式（17）中拉格朗日乘子的初始值為0，上標u表示迭代次數。Si表示拉格朗日乘子λi的次梯度方向，如式（18）所示：

θu表示第u次迭代的步長，如式（19）所示：

2.4 構造可行解

對偶問題得到的解對原問題來說可能是不可行的，因為可能不符合唯一性的約束條件（3），因此需要對松弛問題的解進行可行化，從而獲得原問題的上界。本文設計了一種啟發式算法，其步驟如下：將式（16）求得的解作為啟發信息，將的值從大到小排序，其值越大表明該機位沖突越嚴重，可調整的余地越小；其值越小表明機位沖突越少。按照從難到易的順序分別將子問題的解放到原問題中判斷其是否可行，若可行則為原問題的一個解；反之則無解。假設通過拉格朗日問題得到的解y=(y1k，y2k，…，ynk)T不是機位分配問題的可行解，即存在i使得=0時，一個直觀的可行化方法是：調整這些分配失敗的航班的優先級，優先分配前一次規劃失敗的航班，在規劃失敗的航班中選取讓λi為最小的k；令yik=1，并重復上述判別和計算直到所有的航班都被分配，這樣可以將拉格朗日算法產生的所有解擴展至可行解。若上述方案最終還是無法得到可行解，則以再增加停機位個數來完成。

2.5 機場停機位分配調度優化算法

基于松弛算法的停機位分配調度優化算法具體步驟如下：

步驟1 初始化：令當前迭代次數u=0，令所有拉格朗日乘子λi=0。

步驟2 計算下界：用動態規劃求解每個航班的子問題，得到原問題解的下界。

步驟3 解的可行化：對松弛問題的解進行可行化，得到原問題解的上界。

步驟4 更新解的上下界。

步驟5 判斷是否滿足終止條件：所得問題解的上界和下界差小于最優間隔或迭代次數大于200 時，則終止迭代，獲得最終解［15］。

步驟6 更新拉格朗日乘子：設定迭代步長初始值為β=2，則令βu+1=0.8βu且u=u+1，根據2.3 節介紹的次梯度算法更新拉格朗日乘子λi，并跳轉到步驟2（參考文獻［15］對系數進行設定）。

3 實例分析

本文以某國際機場為研究對象，選用該機場5 月份某個繁忙日8：00—12：00 的航班數據，在此時間段內共有56 架航班、38 個停機位，其中包括近機位34 個、遠機位4 個。數據樣本如表1所示。

3.1 預分配方案前后對比

從圖1 所示的原計劃機位分配甘特圖可以看出，1 號和9號停機位中兩航班間的空閑時間較少，當有航班延誤時對后續航班占用機位的影響較大，分配方案的魯棒性較差。與原分配方案相比，如圖2 所示的優化后機位分配圖，其航班間的空閑時間分布均勻且間隔較大，能較好地吸收一定時間范圍內航班延誤產生的擾動，減少航班延誤對分配方案的影響。

表1 部分航班計劃Tab.1 Part of planning flight schedules

圖2 優化后的停機位預分配甘特圖Fig.2 Gantt Chart of gate pre-assignment after optimization

式（20）和（21）分別為機位空閑時間及機位占用比的計算方法：

其中：Fk為第k個機位的空閑時間；H為機位總時間；Bk為第k個機位的占用比。

3.2 機位空閑時間對比

優化前后的機位空閑時間如圖3所示。從圖3中可知，優化前機位最大空閑時間為270 min，最小空閑時間為140 min，求得其平均空閑時間約為220.9 min；優化后的平均空閑時間為204.2 min，空閑時間縮短了7.56%，滿足了目標函數中縮小機位間的空閑時間的需求，驗證了本文所提方法的有效性。

圖3 優化前后的機位空閑時間Fig.3 Gate idle time before and after optimization

3.3 機位占用比對比

從圖4 可以看出，優化后的機位預分配方案中幾乎大部分機位的占用比均有所提高，平均占用比為34.12%，而優化前的平均占用比只有28.74%，增幅為18.72%。大大提高了機位的利用率。

圖4 優化前后機位占用比（8：00—12：00）Fig.4 Gate occupancy ratio before and after optimization（8：00 to 12：00）

根據調查，該樞紐機場的航班高峰時段分別為8：00—12：00和15：00—18：00，同理采用上述方法對15：00—18：00 的39 個航班進行分配，得到機位占用比如圖5 所示。從圖5 中可以看出，優化后使用停機位的數量從30 個減少到26 個，停機位占用比從22.84%提高到26.36%。綜上可知，本文提出的基于松弛算法的停機位分配方法可以適應不同航班延誤時間、不同航班密度等情況。

圖5 優化前后機位占用比（15：00—18：00）Fig.5 Gate occupancy ratio before and after optimization（15：00 to 18：00）

表2 部分航班實際到離港時刻Tab.2 Arrival and departure time of some real flights

3.4 實際運行對比

將當日航班實際到、離港時刻運用到預分配方案中，表3為實際運行數據。這56 個航班中，航班最早到達時刻為8：22，航班最晚離港時刻為19：00。與原分配方案相比，優化后分配方案所用停機位數量從38個縮減到32個，機位使用量減少了15.79%，并且所有航班都被分配在近機位上，符合優化目標中最小化遠機位占用時間的要求，這樣既方便旅客上下飛機，又減少了調用擺渡車等的使用費用。

表3 實際運行數據Tab.3 Actual operation data

從表3 中可以看出，實際運行中，優化后的占用比相較優化前提高了22.47%，原沖突率為5.36%，優化后沖突率為3.57%，所以總的來說優化后的方案整體性能較好，達到了提高機位占用比、減少航班沖突的效果。

4 結語

本文研究了停機位分配問題，以提高停機位利用率為目標，并提出基于松弛算法的停機位分配模型求解方法，具體包括如下幾個方面：1）通過對機場的停機位分配業務流程進行深入分析，基于機場航班實際運行需求，構建了停機位分配模型。2）使用拉格朗日松弛算法對模型進行求解，得到一個停機位預分配方案。3）將實際運行數據運用到預分配方案中并與原方案進行對比，結果分析表明，所提方法得到的結果使得機位利用率提高，沖突率降低，在實際運行中是可行的。

停機位分配是一個動態調整的過程，其分配方案的影響因素也十分復雜，包括航班延誤、不同天氣條件等影響，接下來下將針對實時動態調整停機位分配的問題進行近一步研究。