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

王笑天　田　勇　萬(wàn)莉莉　楊　曄

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

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

王笑天田勇萬(wàn)莉莉楊曄

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

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

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

王笑天(1988- ):碩士生，主要研究領(lǐng)域?yàn)榭罩薪煌ü芾?/p>

0引言

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

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

1.1魯棒性評(píng)價(jià)函數(shù)的設(shè)計(jì)

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

(1)

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

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

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

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

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

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

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

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

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

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

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

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

(2)

(3)

(4)

(5)

(6)

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

2列生成算法求解過(guò)程

具體求解步驟如下.

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

步驟2求解限制主問(wèn)題.

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

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

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

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

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

2.1限制主問(wèn)題

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

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

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

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

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

3算例分析

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

表2　航班信息

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

圖2　最終指派方案甘特圖

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

圖3　空閑時(shí)間段分布圖

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

4結(jié)束語(yǔ)

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

參 考 文 獻(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ī)場(chǎng)機(jī)位指派策略[J].計(jì)算機(jī)工程,2005,31(3):186-189.

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

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

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

中圖法分類(lèi)號(hào)：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ù)費(fèi)專(zhuān)項(xiàng)資金資助(項(xiàng)目編號(hào)：NJ20140017)