基于松弛算法的停機(jī)位分配優(yōu)化方法

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

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

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

0 引言

隨著近年來旅客吞吐量和飛機(jī)起降架次逐年增加，航班延誤對(duì)機(jī)場運(yùn)行的擾動(dòng)日益嚴(yán)重。停機(jī)位資源的分配是機(jī)場運(yùn)營管理的重要環(huán)節(jié)之一，合理的機(jī)位資源分配方案是減少?zèng)_突、提高機(jī)位利用率的重要途徑。在航空需求無限增長與機(jī)位資源有限的不均衡現(xiàn)象日益突出的情況下，如何在減少航班延誤或提前到達(dá)對(duì)機(jī)位分配方案產(chǎn)生的沖突的同時(shí)又提高機(jī)位利用率是機(jī)場運(yùn)行亟待解決的問題。

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

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

1 停機(jī)位分配模型

1.1 問題描述與模型假設(shè)

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

不失一般性，需要解決的問題可以描述為：存在m個(gè)停機(jī)位為航班?？考奥每偷菣C(jī)服務(wù)，選取的時(shí)間段內(nèi)有n個(gè)航班需要停靠在機(jī)位上。穩(wěn)定性是反映停機(jī)位分配方案魯棒性的指標(biāo)，即停機(jī)位分配方案在受到擾動(dòng)后的偏離程度，假設(shè)QA為實(shí)際運(yùn)行時(shí)偏離停機(jī)位分配方案的航班數(shù)量，n為總的航班數(shù)量，則可用QA/n的值來評(píng)價(jià)分配方案的魯棒性。如果在同一機(jī)位相鄰兩航班間的時(shí)間間隔較大時(shí)，前序航班產(chǎn)生的延誤對(duì)后續(xù)航班的影響較小，則QA/n的值越小魯棒性越好；反之，若兩航班間的間隔過小時(shí)，前序航班產(chǎn)生的延誤對(duì)同一機(jī)位后續(xù)航班的影響較大，則QA/n的值越大魯棒性越差。另一方面，如果兩航班間的間隔時(shí)間較大，雖然魯棒性很好，但是會(huì)造成資源浪費(fèi)，因此如何合理地進(jìn)行設(shè)計(jì)是一個(gè)關(guān)鍵問題。航班j和航班i是分配在同一機(jī)位的兩個(gè)航班，且航班j是航班i的緊后航班，[di，aj]表示航班i和j間的空閑時(shí)間窗。結(jié)合機(jī)場運(yùn)行實(shí)際需求，設(shè)定停機(jī)位分配的優(yōu)化目標(biāo)如下：

1）最小化每個(gè)停機(jī)位的空閑時(shí)間，即所有停機(jī)位的未被占用時(shí)間總和最小。

2）最小化遠(yuǎn)機(jī)位的占用時(shí)間，即盡可能把航班分配到近機(jī)位，最小化遠(yuǎn)機(jī)位個(gè)數(shù)，從而既方便旅客登機(jī)又減少擺渡車等的費(fèi)用。

本文研究停機(jī)位分配問題，基于如下假設(shè)：

1）機(jī)場停機(jī)位數(shù)量充足，在某時(shí)間段內(nèi)不會(huì)出現(xiàn)航班無機(jī)位可分配的情況；

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

3）進(jìn)港航班均服從“先到先服務(wù)”的原則；

4）航班計(jì)劃信息完備已知，包括航班機(jī)型、到離港航班時(shí)刻計(jì)劃等；

5）不考慮某些停機(jī)位因設(shè)備故障等特殊原因而導(dǎo)致的不可用的情況。

1.2 模型構(gòu)建

1.2.1 符號(hào)變量說明

停機(jī)位分配模型所使用的符號(hào)參數(shù)說明如下：

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

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

1.2.2 優(yōu)化目標(biāo)

根據(jù)上述分析，停機(jī)位分配模型的優(yōu)化目標(biāo)如下。

1）最小化各機(jī)位空閑時(shí)間為：

2）最小化遠(yuǎn)機(jī)位占用時(shí)間為：

1.2.3 約束條件

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

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

2 基于雙目標(biāo)松弛算法的停機(jī)位分配模型

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

2.1 拉格朗日對(duì)偶解的分析

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

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

得到：

若zLD的目標(biāo)值有界，則

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

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

然后在已知的可行解域中對(duì)凸函數(shù)使用次梯度算法通過不斷的迭代求得全局最優(yōu)解。

2.2 機(jī)位分配問題的拉格朗日對(duì)偶松弛問題

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

上述目標(biāo)函數(shù)需滿足式（4）～式（9）和式（11）：

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

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

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

其中，λi反映了航班占用機(jī)位k所需要付出的代價(jià)，占用不同的機(jī)位需要付出相應(yīng)的代價(jià)。式（16）的目標(biāo)是確定航班占用的機(jī)位及其空閑的時(shí)間，使其占用機(jī)位所付出的代價(jià)和空閑時(shí)間總和達(dá)到最小。

2.3 次梯度算法優(yōu)化拉格朗日乘子

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

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

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

2.4 構(gòu)造可行解

對(duì)偶問題得到的解對(duì)原問題來說可能是不可行的，因?yàn)榭赡懿环衔ㄒ恍缘募s束條件（3），因此需要對(duì)松弛問題的解進(jìn)行可行化，從而獲得原問題的上界。本文設(shè)計(jì)了一種啟發(fā)式算法，其步驟如下：將式（16）求得的解作為啟發(fā)信息，將的值從大到小排序，其值越大表明該機(jī)位沖突越嚴(yán)重，可調(diào)整的余地越?。黄渲翟叫”砻鳈C(jī)位沖突越少。按照從難到易的順序分別將子問題的解放到原問題中判斷其是否可行，若可行則為原問題的一個(gè)解；反之則無解。假設(shè)通過拉格朗日問題得到的解y=(y1k，y2k，…，ynk)T不是機(jī)位分配問題的可行解，即存在i使得=0時(shí)，一個(gè)直觀的可行化方法是：調(diào)整這些分配失敗的航班的優(yōu)先級(jí)，優(yōu)先分配前一次規(guī)劃失敗的航班，在規(guī)劃失敗的航班中選取讓?duì)薸為最小的k；令yik=1，并重復(fù)上述判別和計(jì)算直到所有的航班都被分配，這樣可以將拉格朗日算法產(chǎn)生的所有解擴(kuò)展至可行解。若上述方案最終還是無法得到可行解，則以再增加停機(jī)位個(gè)數(shù)來完成。

2.5 機(jī)場停機(jī)位分配調(diào)度優(yōu)化算法

基于松弛算法的停機(jī)位分配調(diào)度優(yōu)化算法具體步驟如下：

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

步驟2 計(jì)算下界：用動(dòng)態(tài)規(guī)劃求解每個(gè)航班的子問題，得到原問題解的下界。

步驟3 解的可行化：對(duì)松弛問題的解進(jìn)行可行化，得到原問題解的上界。

步驟4 更新解的上下界。

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

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

3 實(shí)例分析

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

3.1 預(yù)分配方案前后對(duì)比

從圖1 所示的原計(jì)劃機(jī)位分配甘特圖可以看出，1 號(hào)和9號(hào)停機(jī)位中兩航班間的空閑時(shí)間較少，當(dāng)有航班延誤時(shí)對(duì)后續(xù)航班占用機(jī)位的影響較大，分配方案的魯棒性較差。與原分配方案相比，如圖2 所示的優(yōu)化后機(jī)位分配圖，其航班間的空閑時(shí)間分布均勻且間隔較大，能較好地吸收一定時(shí)間范圍內(nèi)航班延誤產(chǎn)生的擾動(dòng)，減少航班延誤對(duì)分配方案的影響。

表1 部分航班計(jì)劃Tab.1 Part of planning flight schedules

圖2 優(yōu)化后的停機(jī)位預(yù)分配甘特圖Fig.2 Gantt Chart of gate pre-assignment after optimization

式（20）和（21）分別為機(jī)位空閑時(shí)間及機(jī)位占用比的計(jì)算方法：

其中：Fk為第k個(gè)機(jī)位的空閑時(shí)間；H為機(jī)位總時(shí)間；Bk為第k個(gè)機(jī)位的占用比。

3.2 機(jī)位空閑時(shí)間對(duì)比

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

圖3 優(yōu)化前后的機(jī)位空閑時(shí)間Fig.3 Gate idle time before and after optimization

3.3 機(jī)位占用比對(duì)比

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

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

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

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

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

3.4 實(shí)際運(yùn)行對(duì)比

將當(dāng)日航班實(shí)際到、離港時(shí)刻運(yùn)用到預(yù)分配方案中，表3為實(shí)際運(yùn)行數(shù)據(jù)。這56 個(gè)航班中，航班最早到達(dá)時(shí)刻為8：22，航班最晚離港時(shí)刻為19：00。與原分配方案相比，優(yōu)化后分配方案所用停機(jī)位數(shù)量從38個(gè)縮減到32個(gè)，機(jī)位使用量減少了15.79%，并且所有航班都被分配在近機(jī)位上，符合優(yōu)化目標(biāo)中最小化遠(yuǎn)機(jī)位占用時(shí)間的要求，這樣既方便旅客上下飛機(jī)，又減少了調(diào)用擺渡車等的使用費(fèi)用。

表3 實(shí)際運(yùn)行數(shù)據(jù)Tab.3 Actual operation data

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

4 結(jié)語

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

停機(jī)位分配是一個(gè)動(dòng)態(tài)調(diào)整的過程，其分配方案的影響因素也十分復(fù)雜，包括航班延誤、不同天氣條件等影響，接下來下將針對(duì)實(shí)時(shí)動(dòng)態(tài)調(diào)整停機(jī)位分配的問題進(jìn)行近一步研究。