基于列生成算法的停機(jī)位指派的魯棒性研究*

王笑天　田　勇　萬莉莉　楊　曄

(南京航空航天大學(xué)民航學(xué)院　南京　210016)

基于列生成算法的停機(jī)位指派的魯棒性研究*

王笑天田勇萬莉莉楊曄

(南京航空航天大學(xué)民航學(xué)院南京210016)

摘要：引入停機(jī)位計劃的概念來描述指派到同一機(jī)位上的一系列的航班，將停機(jī)位指派問題轉(zhuǎn)化為選擇符合相應(yīng)的停機(jī)位類型的最佳停機(jī)位計劃，建立增大停機(jī)位指派魯棒性的數(shù)學(xué)模型.應(yīng)用列生成算法求解該模型.算例分析表明，該停機(jī)位指派模型和算法在計算時間和指派結(jié)果上具有一定的優(yōu)勢，在實際操作中是有效可行的.

關(guān)鍵詞：停機(jī)位指派；魯棒性；停機(jī)位計劃；列生成算法

王笑天(1988- ):碩士生，主要研究領(lǐng)域為空中交通管理

0引言

停機(jī)位指派的魯棒性是指機(jī)位預(yù)指派自身具有一定的“抗干擾能力”.目前機(jī)場停機(jī)位資源緊缺，當(dāng)進(jìn)出機(jī)位的航班發(fā)生隨機(jī)延誤時，會影響到其他航班，重新指派耗時耗力.因此，建立增大停機(jī)位指派魯棒性的模型并采用高效的算法快速生成指派方案勢在必行.國內(nèi)外學(xué)者對停機(jī)位指派的魯棒性進(jìn)行了一定的研究.Hassounah等[1]首次對停機(jī)位指派的魯棒性進(jìn)行了研究.ABolat等[2]研究了以最小化機(jī)位空閑時間段的方差為目標(biāo)的機(jī)位指派問題，用分支定界法進(jìn)行求解.爾后又對該問題進(jìn)行了進(jìn)一步的研究，并設(shè)計啟發(fā)式算法求解[3].田晨等[4]采用遺傳算法對停機(jī)位指派的魯棒性問題進(jìn)行了研究.衛(wèi)東選等[5]以最小化停機(jī)位各空閑時間段的離差為優(yōu)化目標(biāo)，采用貪婪算法結(jié)合動態(tài)時間窗法對模型進(jìn)行優(yōu)化求解.楊雙雙等[6]基于客戶評價體系，對停機(jī)位分配優(yōu)化技術(shù)進(jìn)行了研究.本文將具有相同特性的停機(jī)位劃分為一種停機(jī)位類型，從而將停機(jī)位指派問題轉(zhuǎn)化為選擇符合相應(yīng)的停機(jī)位類型的最佳停機(jī)位計劃，在此基礎(chǔ)上建立了增大停機(jī)位指派魯棒性的數(shù)學(xué)模型，并應(yīng)用列生成算法求解該模型.

1停機(jī)位指派的數(shù)學(xué)模型

1.1魯棒性評價函數(shù)的設(shè)計

魯棒性評價函數(shù)應(yīng)具有2個特點：(1)它應(yīng)該指派給較小的空閑時間間隔以較高的成本來作為懲罰，而對于較大的空閑時間間隔則設(shè)置適當(dāng)?shù)某杀具M(jìn)行略微的懲罰；(2)函數(shù)在較小的空閑時間間隔時應(yīng)非常陡峭，后趨于平緩，以反映在小的時間間隔范圍內(nèi)時間間隔的增加是有利且明顯的.相關(guān)參數(shù)是由我國機(jī)場航班歷史統(tǒng)計數(shù)據(jù)擬合得到的.基于以上特點，設(shè)計評價函數(shù)如下.

(1)

式中：t為指派到同一機(jī)位上相鄰2架航班之間的時間間隔，即機(jī)位緩沖時間，根據(jù)機(jī)位指派人員經(jīng)驗，最小取值為20min.

1.2停機(jī)位類型劃分

本文提出一種比較細(xì)致地劃分停機(jī)位類型的方法，具體分類標(biāo)準(zhǔn)參見表1，那么根據(jù)停機(jī)位所能停放機(jī)型的大小，最多可將停機(jī)位劃分成A,B,C,D,E,F6種類型.

表1　飛機(jī)分類標(biāo)準(zhǔn)

1.3停機(jī)位計劃的概念

將研究時間段內(nèi)可以指派到同一機(jī)位上的一系列的航班定義為一個停機(jī)位計劃，因而可能的停機(jī)位計劃有無數(shù)種.在列生成算法中，停機(jī)位計劃起著聯(lián)系主問題和子問題的重要作用，它在主問題中是決策變量，同時子問題產(chǎn)生的結(jié)果是一個新的停機(jī)位計劃.

1.4整數(shù)線性規(guī)劃模型

定義航班集合V，停機(jī)位類型集合A，停機(jī)位計劃集合N，并引入以下符號.

1) 下標(biāo)號記號i,停機(jī)位計劃下標(biāo)；v,航班下標(biāo)；a,停機(jī)位類型下標(biāo).

2) 參數(shù)ci,停機(jī)位計劃i的成本，可通過停機(jī)位計劃i中相鄰2架航班之間的空閑時間間隔成本求和得到；Qv,一個非常大的成本系數(shù)，本文取1 000 000；gvi,當(dāng)航班v包含在停機(jī)位計劃i中時等于1，否則等于0；eia,當(dāng)停機(jī)位計劃i可指派到a類型的停機(jī)位上時等于1，否則等于0；Sa,a類型的停機(jī)位數(shù)量.

3) 決策變量xi,執(zhí)行停機(jī)位計劃i時等于1，否則等于0；UAFv,存在未指派的航班v時等于1，否則等于0.若存在未指派航班，則將其指派至遠(yuǎn)機(jī)位.

應(yīng)用以上符號，建立如下增大停機(jī)位指派魯棒性的數(shù)學(xué)模型.

(2)

(3)

(4)

(5)

(6)

式(2)為目標(biāo)函數(shù)，要求停機(jī)位指派成本最低；式(3)為航班指派約束，表示每個航班僅且僅能被指派到一個停機(jī)位計劃中；式(4)為停機(jī)位類型個數(shù)約束，表示指派到a類型停機(jī)位上的停機(jī)位計劃數(shù)必須等于a類型停機(jī)位數(shù)；式(5)和(6)為變量取值約束.

2列生成算法求解過程

具體求解步驟如下.

步驟1初始化.由指派人員根據(jù)經(jīng)驗給定初始解，生成限制主問題.

步驟2求解限制主問題.

步驟3計算航班約束和停機(jī)位類型約束的對偶變量的值，分別用πv(v=1,2,…，V)和λa(a=1,2,…,A)表示.

步驟4利用上述對偶變量值對子問題網(wǎng)絡(luò)圖中邊的權(quán)值進(jìn)行調(diào)整.

步驟5對子問題進(jìn)行求解(求得主問題非基變量的最小簡約成本).

步驟6若最小簡約成本小于0，則將其所對應(yīng)的停機(jī)位計劃作為新的列加入到初始解中，轉(zhuǎn)至步驟2；否則，轉(zhuǎn)至步驟7.

步驟7若限制主問題的解為非整數(shù)，則利用分支定界法求得整數(shù)解；否則，當(dāng)前解即為最優(yōu)解.

2.1限制主問題

將式(5)和(6)表示成約束松弛便得到松弛線性規(guī)劃問題，可作為列生成算法的主問題。從所有停機(jī)位計劃中選擇符合各類停機(jī)位類型且與其數(shù)目相等的停機(jī)位計劃構(gòu)建停機(jī)位指派模型的限制主問題。

2.2子問題的構(gòu)造

列生成算法的關(guān)鍵是構(gòu)造子問題.為求得所有實際可行的停機(jī)位計劃的最小簡約成本，本文構(gòu)建這樣一個網(wǎng)絡(luò)，在該網(wǎng)絡(luò)中，每個可行的停機(jī)位計劃等價于網(wǎng)絡(luò)中的一條路徑，反之亦然.并且，路徑的長度等于相應(yīng)的停機(jī)位計劃的簡約成本，從而將求解最小簡約成本的問題轉(zhuǎn)化為求解網(wǎng)絡(luò)中的最短路徑問題.

圖1　有向網(wǎng)絡(luò)圖

最后，對每種停機(jī)位類型下的最小簡約成本再求最小，即得最終的停機(jī)位計劃i的最小簡約成本.

3算例分析

本文對國內(nèi)某機(jī)場一個航站樓20個停機(jī)位1d內(nèi)的110架航班進(jìn)行指派.根據(jù)航班和機(jī)位信息，將停機(jī)位劃分為E類國內(nèi)航班停機(jī)位、D類國內(nèi)航班停機(jī)位、C類國內(nèi)航班停機(jī)位、E類國際航班停機(jī)位、D類國際航班停機(jī)位和C類國際航班停機(jī)位6種類型，對應(yīng)的個數(shù)分別為4,2,6,2,2,4.航班信息見表2.表中No為航班序號；Arr為進(jìn)場時刻；Dep為離場時刻；S為機(jī)型；Cat為航班類型.航班從早上08：00(表中以08：00為0時刻)開始到晚上22:35結(jié)束.

表2　航班信息

運用AIMMS軟件進(jìn)行求解,得到如圖2所示的最優(yōu)指派方案.其中，Gatetype1對應(yīng)E類國內(nèi)航班停機(jī)位，Gatetype2對應(yīng)D類國內(nèi)航班停機(jī)位，Gatetype3對應(yīng)C類國內(nèi)航班停機(jī)位，Gatetype4對應(yīng)E類國際航班停機(jī)位，Gatetype5對應(yīng)D類國際航班停機(jī)位，Gatetype6對應(yīng)C類國際航班停機(jī)位.

圖2　最終指派方案甘特圖

在所有相鄰2架航班之間的空閑時間中，最長空閑時間為275min，最短空閑時間為20min，平均空閑時間為81.833min.由于航班進(jìn)離場存在高峰時段和相對空閑時段，因而機(jī)位空閑時間段的跨度比較大.對各個機(jī)位上相鄰2架航班之間的空閑時間段及個數(shù)進(jìn)行統(tǒng)計，得到如圖3所示的空閑時間段分布圖.由圖3可見，空閑時間段集中在55～95min內(nèi)，這是由于空閑時間段較小時不利于增大停機(jī)位指派的魯棒性，而空閑時間段較大時則會導(dǎo)致一些航班無法指派到機(jī)位上.

圖3　空閑時間段分布圖

采用本文設(shè)計的算法對文獻(xiàn)[5]中的算例進(jìn)行求解，得到的優(yōu)化目標(biāo)值，即所有機(jī)位空閑時間段的平方和為773 024min2，而禁忌搜索算法得到的優(yōu)化目標(biāo)值為798 485 min2，遺傳算法得到的優(yōu)化目標(biāo)值為776 210 min2，可見本文設(shè)計的算法較啟發(fā)式算法能夠得到更為優(yōu)越的解.同時，本文算法的求解時間為204.4 s，而經(jīng)典算法一般無法在多項式時間內(nèi)求解出該NP難問題，所以該算法的求解速度明顯快于經(jīng)典算法.

4結(jié)束語

在機(jī)場實際運行過程中，航班的隨機(jī)延誤普遍發(fā)生，因此，提高停機(jī)位預(yù)指派方式的魯棒性對保障航班計劃執(zhí)行率尤為重要.未來還可進(jìn)一步考慮不同類型航班對應(yīng)不同的單位時間延誤成本，從而根據(jù)航班類型合理分配緩沖時間，使停機(jī)位指派的魯棒性研究更具現(xiàn)實意義.

參 考 文 獻(xiàn)

[1]HASSOUNAHM,STEUARTG.Demandforaircraftgates[J].TransportationResearchRecord,1993,1423:26-33.

[2]BOLATA,AS-SAIFANK.Proceduresforaircraft-gateassignment[J],Mathematical&ComputationalApplications,1996,1(1):9-14.

[3]BOLATA.Assigningproceduresforprovidingrobustgateassignmentsforarrivingaircrafts[J],EuropeanJournalofOperationalResearch,2000,120(1):63-80.

[4]田晨,熊桂喜.基于遺傳算法的機(jī)場機(jī)位指派策略[J].計算機(jī)工程,2005,31(3):186-189.

[5]衛(wèi)東選,劉長有.機(jī)場停機(jī)位指派問題研究[J].交通運輸工程與信息學(xué)報,2009,7(1):57-63.

[6]楊雙雙,田勇,萬莉莉,等.基于客戶評價體系的停機(jī)位分配優(yōu)化研究[J].武漢理工大學(xué)學(xué)報：交通科學(xué)與工程版,2013,37(1):167-171.

[7]白鳳,朱金福,高強(qiáng).基于列生成算法的不正常航班調(diào)度[J].系統(tǒng)工程理論與實踐,2010,30(11):2036-2045.

中圖法分類號：U8

doi:10.3963/j.issn.2095-3844.2015.01.039

收稿日期：2014-00-00

ResearchonRobustnessofGateAssignmentBasedon
ColumnGenerationMethods

WANGXiaotianTIANYongWANLiliYANGYe

(School of Civil Aviation,Nanjing University of

Aeronautics and Astronautics,Nanjing 210016,China)

Abstract：It is very significant to study the robustness of gate assignment scheme in the process of airport operation. The concept of gate plan is introduced to describe a series of flights which are assigned to the same gate, then the gate assignment problem boils down to selecting the best subset of gate plans which conform to the corresponding gate type, so a mathematical model of increasing gate assignment robustness is established. Column generation methods are introduced to solve this model. Finally, a given instance shows that the model and algorithm of gate assignment have certain advantages in computation time and assignment result, which are effective and feasible in practice.

Key words：gate assignment;robustness;gate plan;column generation methods

*中央高?；究蒲袠I(yè)務(wù)費專項資金資助(項目編號：NJ20140017)