考慮組合機(jī)位的停機(jī)位預(yù)指派問題研究

盛 政,蔡碧金,王巖華

(南京航空航天大學(xué) 民航學(xué)院，江蘇 南京 211106)

?

考慮組合機(jī)位的停機(jī)位預(yù)指派問題研究

盛 政,蔡碧金,王巖華

(南京航空航天大學(xué) 民航學(xué)院，江蘇 南京 211106)

針對(duì)現(xiàn)有停機(jī)位指派研究?jī)?yōu)化程度不高的問題，對(duì)停機(jī)位指派中組合機(jī)位的使用進(jìn)行分析。以列生成算法為基礎(chǔ)，通過為組合機(jī)位設(shè)計(jì)獨(dú)立的飛機(jī)連接網(wǎng)絡(luò)，建立了可考慮組合機(jī)位的停機(jī)位指派模型，算例分析表明，該模型的指派結(jié)果比傳統(tǒng)停機(jī)位指派模型優(yōu)化程度更高，在實(shí)際操作中是有效可行的。

停機(jī)位指派；組合機(jī)位；列生成算法

停機(jī)位指派問題是指在給定的作業(yè)時(shí)間窗內(nèi)，考慮機(jī)型、停機(jī)位類型和航班時(shí)刻等因素，指派進(jìn)港飛機(jī)到有限的停機(jī)位上實(shí)現(xiàn)?？浚员ＷC陸空運(yùn)輸?shù)挠行с暯覽1]。

BRAAKSMA等在1971年最早采用定量的方法研究了停機(jī)位分配時(shí)旅客在航站樓內(nèi)行走距離最小化的問題，建立了基于關(guān)鍵路徑方法的仿真模型[2]；DREXL等研究了以最小化旅客行走距離、最小化未分配的航班數(shù)量和最大化航班的機(jī)位偏好為目標(biāo)的多目標(biāo)停機(jī)位分配優(yōu)化模型，采用基于Pareto的模擬退火算法求得Pareto前沿優(yōu)化解[3]；DORNDORF等將停機(jī)位指派看作一個(gè)集合劃分問題來研究，對(duì)停機(jī)位分配策略的魯棒性進(jìn)行了優(yōu)化，模型中考慮了相鄰?fù)C(jī)位間的飛機(jī)停靠限制[4]；NEUMAN等從機(jī)場(chǎng)和航空公司兩方面利益角度出發(fā)，建立了以最大化停機(jī)位分配的魯棒性、最大化停機(jī)位的空間利用率、最大化航空公司的機(jī)位偏好和最小化分配到遠(yuǎn)機(jī)位的航班數(shù)量為優(yōu)化目標(biāo)的多目標(biāo)停機(jī)位分配模型，研究中采用陰影約束來描述停機(jī)位間的互相限制、組合及拆分[5]。國內(nèi)對(duì)停機(jī)位分配問題的研究雖然起步較晚，但也取得了一定的成果。文軍等按照先到先服務(wù)原則，建立了航班停機(jī)位分配問題的排序模型，并給出了求解該模型的標(biāo)號(hào)算法[6]；衛(wèi)東選等建立了以分配到遠(yuǎn)機(jī)位的航班數(shù)量最少、分配方式擾動(dòng)性最小及相關(guān)旅客轉(zhuǎn)移距離最小為優(yōu)化目標(biāo)的多目標(biāo)停機(jī)位實(shí)時(shí)再分配優(yōu)化模型[7]；衛(wèi)東選等以最小化停機(jī)位各空閑時(shí)間段的離差平方和為優(yōu)化目標(biāo)，采用貪婪算法結(jié)合動(dòng)態(tài)時(shí)間窗法對(duì)模型進(jìn)行優(yōu)化求解[8]；楊雙雙等引入客戶評(píng)價(jià)體系，以客戶滿意度和停機(jī)位的保障能力為優(yōu)化目標(biāo)，研究停機(jī)位分配的優(yōu)化策略[9]。

受限于約束規(guī)則的復(fù)雜性，現(xiàn)有停機(jī)位指派方面的研究多采用啟發(fā)式算法或人工智能算法進(jìn)行求解，并且很少考慮組合機(jī)位之類的復(fù)雜約束。這種優(yōu)化方式雖然求解速度較快，但得到的指派方案通常質(zhì)量不高，一般無法獲得全局最優(yōu)解，并且在應(yīng)用時(shí)經(jīng)常與實(shí)際情況脫節(jié)，降低了停機(jī)位的使用效率。

1 問題描述

停機(jī)位預(yù)指派的主要工作是根據(jù)現(xiàn)有的航班信息及各類資源，按照一定規(guī)則合理編制停機(jī)位預(yù)分配計(jì)劃， 以達(dá)到提高機(jī)場(chǎng)資源利用率及旅客滿意度的目的。

在機(jī)場(chǎng)實(shí)際運(yùn)營過程中，停機(jī)位的組合與拆分使用是一種很常見的現(xiàn)象。每天的不同時(shí)刻，機(jī)場(chǎng)的到達(dá)航班流中不同機(jī)型所占的比例都在不斷變化，但機(jī)場(chǎng)中停機(jī)位的比例卻是固定的。因?yàn)橥C(jī)位類型與飛機(jī)型號(hào)之間的匹配約束問題，若不進(jìn)行停機(jī)位的組合與拆分，機(jī)場(chǎng)的停機(jī)位資源利用率會(huì)大大降低。

如圖1所示為飛機(jī)占用機(jī)位時(shí)間示例圖，停機(jī)位G1與G3分別為普通機(jī)位與組合機(jī)位，G1無法進(jìn)行組合與拆分操作，只能停靠與機(jī)位類型相匹配的飛機(jī)；G3為組合機(jī)位，在不進(jìn)行拆分操作的情況下，G3可?？看笮蜋C(jī)(如F1)，而當(dāng)機(jī)場(chǎng)中小型機(jī)位不夠用時(shí)，G3也可被拆分成兩個(gè)小型機(jī)位，分別停靠?jī)杉苄⌒蜋C(jī)(如F2與F3)。

圖1 飛機(jī)占用機(jī)位時(shí)間示例圖

2 停機(jī)位預(yù)指派列生成算法的數(shù)學(xué)模型

以列生成算法為基礎(chǔ)建立停機(jī)位預(yù)指派模型，在子問題的設(shè)計(jì)中針對(duì)組合機(jī)位與非組合機(jī)位的特性分別構(gòu)建不同的航班連接網(wǎng)絡(luò)，使得模型能準(zhǔn)確描述停機(jī)位的組合及拆分適用情況。列生成算法的數(shù)學(xué)模型分為主問題和子問題兩部分，主問題用以求得目標(biāo)解，子問題則作為輔助，負(fù)責(zé)生成主問題的決策變量(列)并判斷主問題的解是否已達(dá)到最優(yōu)。當(dāng)主問題和子問題迭代求解時(shí)，主問題需要放松整數(shù)約束以向子問題傳遞對(duì)偶變量信息(整數(shù)約束不屬于線性約束，無法計(jì)算其對(duì)偶變量)。限制主問題的最優(yōu)解可能是非整數(shù)形式，最后需采用分支定界法求得整數(shù)解。

2.1 限制主問題 (RMP)

(1)決策變量xi。若停機(jī)指派方案i被采用，則xi等于1，否則為0。停機(jī)位指派方案的定義是指派給某一機(jī)位飛機(jī)隊(duì)列。

(2)集合。I為停機(jī)位指派方案集合，i∈I；P為飛機(jī)集合，p∈P；G為停機(jī)位集合，g∈G。

(3)參數(shù)。agi表示若停機(jī)位方案i可被指派給機(jī)位g(一個(gè)方案只可被指派給一個(gè)機(jī)位)，則其等于1，否則為0；bpi表示若停機(jī)位方案i中包含飛機(jī)p，則其等于1，否則為0；neari表示若停機(jī)位方案i所指派的機(jī)位為近機(jī)位，則其等于1，否則為0；UAPp表示若飛機(jī)p未被指派，則其等于1，否則為0；Mp為未指派飛機(jī)的罰成本，筆者取Mp=10 000。

限制主問題的數(shù)學(xué)模型如下：

(1)

(2)

(3)

UAPp=0,1

(4)

模型目標(biāo)函數(shù)式(1)為最大化近機(jī)位使用率；式(2)為停機(jī)位使用約束，每個(gè)停機(jī)位最多被指派一條停機(jī)方案；式(3)為飛機(jī)指派約束，每個(gè)飛機(jī)只能被指派給一個(gè)機(jī)位或不指派；式(4)限制了未被指派的飛機(jī)數(shù)量必須為整數(shù)，即飛機(jī)只能被指派或不被指派。

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

列生成算法的關(guān)鍵是構(gòu)造子問題模型，因?yàn)樽訂栴}模型在求解過程中需要被反復(fù)迭代計(jì)算，所以構(gòu)造的子問題必須求解方便，并且能簡(jiǎn)潔地表達(dá)主問題的簡(jiǎn)約成本。因?yàn)橄拗浦鲉栴}的目標(biāo)函數(shù)為最大，取負(fù)轉(zhuǎn)化為最小目標(biāo)函數(shù)后限制主問題中非基變量的簡(jiǎn)約成本CRi=-neari-πpbpi-πg(shù)agi。若minCRi<0，則將子問題生成的CR值為負(fù)的停機(jī)位方案加入到限制主問題；若minCRi=0，則限制主問題求得最優(yōu)解。

為求得minCRi，通過構(gòu)建飛機(jī)連接網(wǎng)絡(luò)來求解最短路徑問題。每一個(gè)停機(jī)位對(duì)應(yīng)著一個(gè)連接網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每條路徑表示一個(gè)該停機(jī)位的停機(jī)位方案，路徑的長度則為對(duì)應(yīng)的簡(jiǎn)約成本。組合機(jī)位因?yàn)槠淇刹鸱中?，連接網(wǎng)絡(luò)的結(jié)構(gòu)與普通機(jī)位不同，筆者采用兩種不同的規(guī)則分別對(duì)每個(gè)機(jī)位g構(gòu)建連接網(wǎng)絡(luò)Gg=(Vg,Eg)。

為方便起見，事先定義兩種沖突參量。①Colid1p1,p2：當(dāng)飛機(jī)p1和p2可被指派到同一普通機(jī)位而不沖突時(shí)(時(shí)間和空間上均不沖突),其值為0，否則為1。②Colid2p1,p2,g：當(dāng)飛機(jī)p1和p2可同時(shí)停在機(jī)位g時(shí)，其值為0，否則為1。

2.2.1 非組合機(jī)位的飛機(jī)連接網(wǎng)絡(luò)構(gòu)建

網(wǎng)絡(luò)中Vg為節(jié)點(diǎn)集合，包括所有可被指派到機(jī)位g上的飛機(jī)對(duì)應(yīng)的節(jié)點(diǎn)vp、源節(jié)點(diǎn)s和匯節(jié)點(diǎn)t：

Vg={s,vp,t|p∈P}

Eg為連接邊集合，若飛機(jī)p1和p2均可被指派到機(jī)位g且不沖突，則建立一條從p1指向p2的有向邊(飛機(jī)p1的占用機(jī)位時(shí)刻早于p2)。此外還包括從s指向所有vp和從所有vp指向t的有向邊：

Eg={(vp1,vp2)|Colid1p1,p2=0}∪

{(s,vp),(vp,t),(s,t)|p∈P}

2.2.2 組合機(jī)位的飛機(jī)連接網(wǎng)絡(luò)構(gòu)建

組合機(jī)位網(wǎng)絡(luò)中的Vg不僅包括所有可被指派到機(jī)位g上的飛機(jī)對(duì)應(yīng)的節(jié)點(diǎn)vp、源節(jié)點(diǎn)s和匯節(jié)點(diǎn)t，還額外加入了新的組合?？抗?jié)點(diǎn)：

因?yàn)榻M合?？抗?jié)點(diǎn)的加入，Eg也會(huì)添加新的指向邊：

{(vp1,vp2,p3)|Colid1p1,p2=0∨Colid1p1,p3=0}∪

{(vp1,p2,vp3)|Colid1p1,p3=0∨Colid1p2,p3=0}∪{(vp1,p2,vp3,p4)|(Colid1p1,p3=0∧Colid1p2,p4=0)∨

(Colid1p1,p4=0∧Colid1p2,p3=0)}

假設(shè)飛機(jī)p1,p2,p3,p4間的沖突關(guān)系為：Colid1p1,p2=1，Colid1p2,p3=1，Colidp1,p4=0，Colidp2,p4=0，Colidp3,p4=0，Colid2p1,p2,g=0，Colid2p2,p3,g=0(見圖2)。在不考慮組合機(jī)位的情況下和考慮組合機(jī)位的情況下它們的連接網(wǎng)絡(luò)差別很大,分別如圖3和圖4所示。

圖2 飛機(jī)占用機(jī)位時(shí)間示例圖

圖3 不考慮組合機(jī)位時(shí)連接網(wǎng)絡(luò)圖

圖4 考慮組合機(jī)位時(shí)連接網(wǎng)絡(luò)圖

構(gòu)建飛機(jī)連接網(wǎng)絡(luò)的最后一步需要為網(wǎng)絡(luò)中每條連接邊賦權(quán)重值，以使每條從s到t的路徑長度等于路徑方案對(duì)應(yīng)的簡(jiǎn)約成本。筆者為每條從s出發(fā)的邊賦權(quán)重-neari-πg(shù)，每條從vp出發(fā)的邊賦權(quán)重-πp(賦權(quán)重時(shí)組合停靠節(jié)點(diǎn)vp1,p2可拆分為兩個(gè)子節(jié)點(diǎn)vp1和vp2，不影響計(jì)算結(jié)果)。賦值后能較容易地計(jì)算出每條路徑的長度為-neari-πpbpi-πg(shù)。

此時(shí)，子問題的數(shù)學(xué)模型可表示為：

(5)

(6)

xmn=0,1m,n∈Va

(7)

式中：(m,n)∈Eg；dmn為邊(m,n)的權(quán)值；xmn為0-1型的決策變量(路徑選擇變量)，邊(m,n)被選中時(shí)xmn=1，否則xmn=0。

2.3 模型求解

整個(gè)數(shù)學(xué)模型求解過程如圖5所示。

圖5 模型求解步驟

限制主問題為線性規(guī)劃問題，子問題為典型的最短路徑問題求解，均不存在太大困難。值得注意的是當(dāng)采用分支定界法求得整數(shù)解時(shí)很可能因?yàn)橄拗浦鲉栴}的決策變量組成比較單一，而導(dǎo)致求解時(shí)間過長或求得的解質(zhì)量較差的問題。為解決該問題，筆者在每回合迭代中不僅為限制主問題加入子問題求得的最優(yōu)路徑方案，還會(huì)加入一些CR值為負(fù)的次優(yōu)方案，以保證分支定界時(shí)的求解速度和解的質(zhì)量。

3 算例分析

筆者以國內(nèi)某機(jī)場(chǎng)一個(gè)航站樓一天內(nèi)的停機(jī)位及航班數(shù)據(jù)作為算例，將65個(gè)航班指派到10個(gè)停機(jī)位上。根據(jù)所獲得的航班信息(見表1)和機(jī)位信息(見表2)，將65個(gè)航班分為5種機(jī)型，包括中小型飛機(jī)：4架B738的航班9個(gè)，4架A319的航班12個(gè)，6架A320的航班10個(gè)；大型飛機(jī)：7架A333的航班20個(gè)，4架A332的航班14個(gè)。10個(gè)機(jī)位中1～4號(hào)機(jī)位為普通近機(jī)位，11～14號(hào)機(jī)位為普通遠(yuǎn)機(jī)位，5、8號(hào)機(jī)位為組合近機(jī)位，其中5號(hào)機(jī)位可拆分為6號(hào)機(jī)位和7號(hào)機(jī)位(小型機(jī)位，不能與5號(hào)機(jī)位共存)，8號(hào)機(jī)位可拆分為9號(hào)機(jī)位和10號(hào)機(jī)位(小型機(jī)位，不能與8號(hào)機(jī)位共存)。

在航班信息表中航班屬性有4種，其中始發(fā)航班表示前一天在該機(jī)場(chǎng)過夜的航班，出發(fā)航班及到達(dá)航班分別代表過站飛機(jī)的進(jìn)港和離港，過夜航班表示今天在該機(jī)場(chǎng)過夜的航班。

表1 航班信息表

筆者在AIMMS平臺(tái)下進(jìn)行模型的建立和求解，AIMMS是以優(yōu)化為目標(biāo)的語言開發(fā)環(huán)境，其主要特點(diǎn)有：①多維的建模語言和先進(jìn)的建模概念，如列生成、隨機(jī)規(guī)劃和現(xiàn)代化的集成開發(fā)環(huán)境(IDE)(包括診斷工具、PROFILER編輯器和數(shù)學(xué)規(guī)劃檢查器)。②集成的圖形化用戶界面創(chuàng)建器(GUI)用來創(chuàng)建與模型中多維標(biāo)識(shí)符緊密關(guān)聯(lián)的控件，如多維表格、圖表、網(wǎng)絡(luò)控件的流程和GIS地圖。③連接針對(duì)不同數(shù)學(xué)規(guī)劃的求解器(線性、整數(shù)、非線性等),AIMMS能把最優(yōu)化的模型傳送到世界級(jí)的求解器，如XA、CONOPT或CPLEX 等。

在考慮組合機(jī)位時(shí)，模型在CPU為Intel(R)Core(TM) i5-3210M，主頻為2.5 GHz，內(nèi)存為4 G的主機(jī)上求解時(shí)，23 s達(dá)到最優(yōu)，列生成算法迭代次數(shù)為28次，最優(yōu)指派方案的甘特圖如圖6所示，圖中每一段長條為航班占用機(jī)位時(shí)間(通過飛機(jī)指派結(jié)果還原即可)，其中G5A、G5B、G6A和G6B為拆分后的小機(jī)位。

為進(jìn)行對(duì)比，同時(shí)采用了不考慮組合機(jī)位的數(shù)學(xué)模型進(jìn)行求解，求解結(jié)果如圖7所示。

不考慮組合機(jī)位時(shí)65個(gè)航班中58個(gè)被分配到了近機(jī)位，靠橋率為89%；在加入組合機(jī)位后，65個(gè)航班中60個(gè)被分配到了近機(jī)位，靠橋率提升到了92%。通過對(duì)比兩個(gè)指派結(jié)果圖可以看出，F(xiàn)6、F55、F57、F38、F59、F61這6個(gè)航班的占用機(jī)位時(shí)間是沖突的，當(dāng)機(jī)位不可拆分時(shí)，由于機(jī)位資源所限，必然有兩個(gè)航班會(huì)被指派到遠(yuǎn)機(jī)位(見圖7中F59和F61)，而若將大型機(jī)位G5拆分成兩個(gè)小機(jī)位時(shí)，這6個(gè)航班均可被指派到近機(jī)位，從而提高停機(jī)位指派結(jié)果的整體靠橋率。

表2 停機(jī)位信息表

圖6 考慮組合機(jī)位的指派結(jié)果

圖7 不考慮組合機(jī)位的指派結(jié)果

因?yàn)樗憷龜?shù)據(jù)較小，因此與實(shí)際停機(jī)位使用情況尚存在較大差距，但從算例分析結(jié)果中仍可看出，相較于普通停機(jī)位指派模型，所建立的模型可以更準(zhǔn)確地模擬停機(jī)位的組合與拆分使用情況，在某一類型停機(jī)位資源達(dá)到飽和時(shí)，可以通過機(jī)位的組合與拆分對(duì)不同類型停機(jī)位的比例進(jìn)行調(diào)整，從而使停機(jī)位資源的利用率達(dá)到最大。

4 結(jié)論

機(jī)位的拆分和組合是機(jī)場(chǎng)實(shí)際運(yùn)營中常采用的一種手段，可以有效提高機(jī)場(chǎng)停機(jī)位的使用率。筆者在考慮6個(gè)停機(jī)位指派基本約束的基礎(chǔ)上，引入了專有性約束、飛機(jī)拖曳約束、過夜航班約束及組合機(jī)位約束(前3個(gè)約束均在模型求解前的數(shù)據(jù)預(yù)處理中完成)，建立了更符合實(shí)際的停機(jī)位指派模型。通過建立特殊的飛機(jī)連接網(wǎng)絡(luò)來產(chǎn)生組合機(jī)位的飛機(jī)?？糠桨?，并將其與列生成算法相結(jié)合，該算法可求得停機(jī)位指派模型的最優(yōu)解。最后采用實(shí)際數(shù)據(jù)的算例分析表明，相較于未考慮組合機(jī)位的停機(jī)位指派模型，加入組合機(jī)位規(guī)則后模型的指派結(jié)果更優(yōu)，且更加切合實(shí)際，對(duì)提高機(jī)場(chǎng)運(yùn)行效率具有積極的意義。

[1] 朱金福.航空運(yùn)輸規(guī)劃[M]. 西安:西北工業(yè)大學(xué)出版社，2009:136-177.

[2] BRAAKSMA J P, SHORTREED J H. Improving airport gate usage with critical path[J]. Transportation Engineering Journal, 1971,97(2):187-203.

[3] DREXL A, NIKULIN Y. Multicriteria airport gate assignment and Pareto simulated annealing[J]. IIE Transactions, 2008,40(4):385-397.

[4] DORNDORF U, JAEHN F, PESCH E. Modelling robust flight-gate scheduling as a clique partitioning problem[J]. Transportation Science, 2008,42(3):292-301.

[5] NEUMAN U M, ATKIN J A D. Airport gate assignment considering ground movement[J] .Computational Logistics, 2013(8197):184-198.

[6] 文軍,孫宏,徐杰,等.基于排序算法的機(jī)場(chǎng)停機(jī)位分配問題研究[J].系統(tǒng)工程,2004,22(7):102-105.

[7] 衛(wèi)東選,劉長有.機(jī)場(chǎng)停機(jī)位再分配[J].南京航空航天大學(xué)學(xué)報(bào),2009,41(2):257-261.

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

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

SHENG Zheng:Postgraduate; School of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China.

[編輯：王志全]

Gate Assignment Problem under Consideration of Combined Gate Restriction

SHENGZheng,CAIBijin,WANGYanhua

The optimization degree of existing studies on gate assignment is not high enough. The application of combined gate to gate assignment was analyzed. Based on column generation, the gate assignment model suitable for combined gates was built by designing independent aircraft network for those gates. The example in reality shows that this model is effective and practical. The optimization degree of assignment result of the model is higher than that of traditional models.

gate assignment; combined gate; column generation methods

2015-04-03.

盛政(1989-)，男，湖南衡陽人，南京航空航天大學(xué)民航學(xué)院碩士研究生.

南京航空航天大學(xué)研究生創(chuàng)新基地(實(shí)驗(yàn)室)開放基金資助項(xiàng)目(kfjj201445).

2095-3852(2015)05-0616-05

A

V351.11

10.3963/j.issn.2095-3852.2015.05.020