楊新湦， 屈琮博， 王梓旭

(1.中國民航大學(xué)中歐航空工程師學(xué)院， 天津 300300； 2.中國民航大學(xué)空中交通管理學(xué)院， 天津 300300)

航空運輸系統(tǒng)是一個復(fù)雜的巨系統(tǒng)，航班不正常是每個航空公司不可避免會面臨的問題。航空公司大面積不正常航班恢復(fù)是困難問題，一般而言，航空公司不正常航班恢復(fù)可分為分階段恢復(fù)與一體化恢復(fù)。分階段恢是將整個恢復(fù)問題分為飛機恢復(fù)、機組恢復(fù)、旅客恢復(fù)三個階段逐步求解；一體化恢復(fù)則是綜合考慮飛機、機組、旅客因素。

對不正常航班恢復(fù)的研究多數(shù)集中于分階段恢復(fù)研究。Teodorovic等[1-4]在1984～1995年先后對飛機停運、機場關(guān)閉航班恢復(fù)問題、旅客恢復(fù)和機組恢復(fù)問題進行了研究。分別使用分支定界、動態(tài)規(guī)劃、啟發(fā)式算法進行了求解，奠定了不正常航班分階段恢復(fù)的基礎(chǔ)。吳剛等[5]提出一種改進列生成算法，每次迭代過程中加入多個列，并對加入的多個列需要滿足的條件進行了分析，最后給出的算例驗證了該方法的正確性和有效性。田倩南等[6]改進時空網(wǎng)絡(luò)算法，給出占優(yōu)準(zhǔn)則，有效減少了可恢復(fù)航線的組合數(shù)量，提升計算效率。

已有文獻中多采用時空網(wǎng)絡(luò)進行建模，時空網(wǎng)絡(luò)中不僅有描述航班銜接的航班邊，還有機場節(jié)點和時間節(jié)點。當(dāng)進行一體化建模時導(dǎo)致模型過于復(fù)雜。Sherali等[12]系統(tǒng)介紹了航班網(wǎng)絡(luò)的使用，相比時空網(wǎng)絡(luò)模型復(fù)雜度低，但是不能將時間、地點等屬性表現(xiàn)在圖中，諸如飛機維修約束、機組執(zhí)勤時間約束、客票取消操作不易表達。對于巡航速度控制的策略，Aktürk等[13]在飛機恢復(fù)問題中首次使用，并分析了巡航速度控制的優(yōu)勢，Arkan等[14]基于此研究進一步將旅客行程加入模型，但是都沒有達到真正的一體化恢復(fù)。

基于以上文獻中的不足，現(xiàn)做出如下工作：①改進航班網(wǎng)絡(luò)的弊端，并設(shè)計一種基于廣度優(yōu)先搜索的網(wǎng)絡(luò)生成算法；②建立巡航速度控制下的一體化恢復(fù)模型；③使用雙曲不等式修正模型，符合二階錐規(guī)劃條件后進行求解并通過算例說明巡航速度控制在一體化恢復(fù)中的作用。

1 航班網(wǎng)絡(luò)改進與算法設(shè)計

1.1 航班網(wǎng)絡(luò)改進

針對航班網(wǎng)絡(luò)相較于時空網(wǎng)絡(luò)不能表達出飛機維修、調(diào)機、客票取消、加機組等操作的劣勢進行改進。傳統(tǒng)航班網(wǎng)絡(luò)如圖1所示，其中包括三類節(jié)點和三類弧，改進航班網(wǎng)絡(luò)中有四類節(jié)點和五類弧，新加入必經(jīng)節(jié)點和必經(jīng)弧、添加弧，具體如下。

sr為初始節(jié)點；tr為沉沒節(jié)點；Mr為必經(jīng)節(jié)點集合；f、g為航班

源節(jié)點：表示飛機、機組或旅客初始狀態(tài)的點，有時間、地點屬性。地點屬性是飛機、機組、旅客行程的首發(fā)機場，時間屬性是首發(fā)時間。

末節(jié)點：表示飛機、機組或旅客的終止?fàn)顟B(tài)的點，有時間、地點屬性。地點屬性是對飛機停場過夜機場的限制，時間屬性是過夜機場的宵禁時間。

航班節(jié)點：表示飛機、機組執(zhí)行的航班或旅客在其行程中要乘坐的航班。

必經(jīng)節(jié)點：表示飛機在特定時段在特定機場維修的節(jié)點，或機組規(guī)定在特定機場休息。

出發(fā)?。哼B接源節(jié)點與航班節(jié)點的弧，表示飛機、機組、旅客執(zhí)行首個航班。

沉沒?。哼B接航班節(jié)點與末節(jié)點的弧，表示飛機、機組、旅客執(zhí)行完最后一個航班。

航班?。汉桨喙?jié)點之間的弧，表示飛機、機組、旅客執(zhí)行完上游航班后執(zhí)行下游航班。

必經(jīng)?。哼B接航班節(jié)點與必經(jīng)節(jié)點之間的弧，表示飛機維修、機組休息等。

添加?。罕硎竞桨嗷謴?fù)的特殊操作，如加機組、調(diào)機操作(航班節(jié)點之間、源節(jié)點與末節(jié)點之間、源節(jié)點與航班節(jié)點、航班節(jié)點與末節(jié)點之間)；乘客客票取消操作(源節(jié)點與末節(jié)點之間、航班節(jié)點與末節(jié)點之間)。

1.2 航班網(wǎng)絡(luò)生成算法設(shè)計

一體化恢復(fù)包含飛機、機組、旅客三種子網(wǎng)絡(luò)，用r表示。算法設(shè)計中，F(xiàn)為航班集合；closetimedown為機場開始關(guān)閉時間；closetimeup為結(jié)束關(guān)閉時間；curfew為機場宵禁時間；Ntemp為航班暫時存儲器中符合條件的航班f集合；Nnext為航班暫時存儲器中符合條件的航班g集合；Orig為航班g的始發(fā)地，Desf為航班f的目的地；ctfg為航班銜接時間；Nr為節(jié)點集合；Vr為弧集合；Er為添加弧集合。航班網(wǎng)絡(luò)生成算法由Generatesubnetwork(r)，Generatepath(Ntemp)和Insert(Ntemp) 三部分組成。具體步驟如下：

Step1 初始化節(jié)點集合Nr，弧集合Vr，Ntemp=sr。

Step2 Generatesubnetwork(r)，航班網(wǎng)絡(luò)生成主程序如下。

Procedure Generatesubnetwork(r)

Gr=(Nr,Vr)←Generatepath(Ntemp) #為第二部分程序

Vr=Vr∪Er

Return Gr=(Nr,Vr)

end Procedure

Step3 Generatepath(Ntemp)，基于廣度優(yōu)先搜索可銜接航班，即航班網(wǎng)絡(luò)路徑中的節(jié)點。

Procedure Generatepath(Ntemp)

WhileNtemp≠?

f←first element ofNtemp

ifclosetimedown≤[dtf,atf]≤closetimeuporatf≤curfew

Updatedtfandatf#修改航班的OD時間

ifdtf-sdtf> 最長延誤時間

continue

else

Nnext←(g∈FOrig=Desfandsdtg≥atf+ctfg)

#當(dāng)前航班的可銜接航班

for eachginNnext

Ntemp=Ntemp∪{g}

ifg∈Nr

Insert(Ntemp) #第三部分節(jié)點/弧生成程序

else

if Desf=Desr

end if

end if

end for

end if

end if

end procedure

Step4 Insert(Ntemp)，得到航班網(wǎng)絡(luò)中的所有弧與節(jié)點。

Procedure Insert(Ntemp)

以實施“美麗鄉(xiāng)村小康水”行動計劃為主抓手，貴州省全面推進民生水利建設(shè)，讓更多群眾在水利發(fā)展中得到實惠。2013年全省預(yù)計解決300萬農(nóng)村人口及學(xué)校師生的飲水安全問題，實施中小河流項目129個，治理水土流失面積2 200km2，實施病險水庫治理271座，新增小水電裝機20萬kW，新增小型農(nóng)田水利重點縣22個，新增有效灌溉面積73萬畝，全面完成年初預(yù)定的各項目標(biāo)。

Nr=Nr∪Ntemp∪Mr

fori=1:len(Ntemp)

Vr=Vr∪{fi,fi+1}

end for

end procedure

Step5 對Vr進行分類得到出發(fā)弧、沉沒弧、航班弧、必經(jīng)弧、添加??；對Nr進行分類得到初始節(jié)點、航班節(jié)點、沉沒節(jié)點。

Step6 如果是機組子網(wǎng)絡(luò)，額外刪除不滿足機組執(zhí)勤時間和飛行時間的弧與節(jié)點。

2 巡航速度控制與一體化恢復(fù)模型

2.1 巡航速度與燃油消耗

飛機在最大航程速度(maximum ragne cruise，MRC)下最省油，在巡航速度大于MRC速度時燃油消耗隨速度增加而增加。速度控制綜合考慮加速與減速研究速度控制對航班恢復(fù)的影響，減速考慮飛機的反常操作，按照文獻[15-16]的建議巡航速度調(diào)整范圍在MRC速度的[-10%,+10%]。將巡航速度納入模型需要速度與燃油消耗之間的關(guān)系以計算恢復(fù)成本，歐洲交通管理組織的飛機數(shù)據(jù)基礎(chǔ)(base of aircraft data, BADA)項目中開發(fā)的巡航階段燃料流模型，提出給定質(zhì)量和高度，可以計算出飛機巡航階段的燃油消耗率fcr(v)(kg / min)與速度v(km / min)的關(guān)系[17]為

(1)

式(1)中：c1、c2、c3、c4分別為與飛機阻力、油耗系數(shù)、給定高度的空氣密度和重力加速度相關(guān)的系數(shù)，這些系數(shù)可以從399種飛機的BADA用戶手冊中獲得。給定燃油消耗率可以計算出巡航階段總?cè)加拖?，假設(shè)飛行距離固定為d，那么可以得到巡航總耗油為

(2)

飛機以MRC巡航最省油，但是實際運行中MRC速度接近反常操縱區(qū)，常采用經(jīng)濟巡航或LRC巡航，假設(shè)航班的計劃飛行速度都為經(jīng)濟巡航速度vECON(按照MRC巡航速度的1.02倍計算)，那么巡航速度調(diào)整后，航班燃油成本ΔFuelcost變化為

ΔFuelcost=pfuel[F(v)-F(vECON)]

(3)

式(3)中：pfuel為單位燃油價格；F(vECON)為經(jīng)濟巡航速度下總耗油。

2.2 巡航速度與碳排放

飛機巡航階段不僅是飛行時間、燃油消耗最多的階段，也是污染物排放最多的階段。國際民航組織(International Civil Aviation Organization，ICAO)根據(jù)發(fā)動機廠家審定的數(shù)據(jù)，定義了標(biāo)準(zhǔn)起飛著陸循環(huán)(land take-off，LTO)，包括起飛、滑行、爬升、著陸4個階段[18]，在基礎(chǔ)排放模型中給出4個階段的基礎(chǔ)排放數(shù)據(jù)見表1。Tamara使用ICAO數(shù)據(jù)結(jié)合波音公司的BM2方法對英國一天的流量樣本的燃油消耗與二氧化碳排放進行了分析，并與英國最廣泛使用的NETCEN估算進行了對比，確定了其實用性[19]。從表1可以看出，CO2的排放指數(shù)與飛行階段無關(guān)，魏志強等[20]研究指出CO2的排放量與燃油消耗成正比，占飛機排放物總量的99%以上，同時也是節(jié)能減排關(guān)注的重點。巡航速度的改變使燃油消耗變化導(dǎo)致二氧化碳排放的因素在模型中也將予以考慮，二氧化碳排放量Δcarboncost可以按照式(4)計算。

表1 CFM56-7B26 發(fā)動機基準(zhǔn)排放數(shù)據(jù)[18]

Δcarboncost=pCO2k[F(v)-F(vECON)]

(4)

式(4)中：pCO2為單位燃油二氧化碳排放量；k為二氧化碳指數(shù)。

2.3 一體化恢復(fù)模型

在模型提出之前做如下假設(shè)。

(1)飛機除座位數(shù)之外的性能差異不大，即不同飛機對巡航速度調(diào)整的限制相同，航班被不同飛機執(zhí)行若沒有速度調(diào)整其計劃巡航時間保持不變。

(2)飛機的計劃巡航速度設(shè)為MRC的1.02倍，且不考慮航線上風(fēng)和溫度變化的影響，速度調(diào)整范圍在[-10%，+10%]。

(3)對于多段行程的旅客不能使其到達中間地點后無后續(xù)航班，在恢復(fù)期內(nèi)對旅客行程受到擾動的旅客進行轉(zhuǎn)到其他航班調(diào)整，不受擾動的航班上的旅客不可調(diào)整后受擾。

(4)飛行中的非巡航部分如滑行、起飛、爬升、下降的總時間為40 min。

模型算法中的集合參數(shù)變量定義如下：

集合

ac飛機集合MidN中間節(jié)點集合

cr機組集合MN必經(jīng)節(jié)點集合

ps旅客行程集合arcs弧集合

Rr∈ac，cr，pssrarcs出發(fā)弧集合

N節(jié)點集合trarcs沉沒弧集合

SN首節(jié)點sr集合midarcs中間弧集合

TN末節(jié)點tr集合cntarcs聯(lián)程航班弧集合

F航班集合psnumber安排到航班的人數(shù)之和

參數(shù)

atf航班f計劃到達時間tf航班f飛行時間

DTf航班f實際起飛時間Np行程p的旅客人數(shù)

ATf航班f實際到達時間Nf原航班上旅客人數(shù)

df航班f的巡航飛行距離S飛機可用座位數(shù)

ctfg中轉(zhuǎn)銜接時間etr飛機或機組的最早可用時間

客客票取消成本

Cfd航班f取消成本CCO2碳排放成本

δtf航班f巡航縮短時間Cfuel燃油成本

Cps旅客單位延誤成本

變量

對于每種網(wǎng)絡(luò)要滿足網(wǎng)絡(luò)的流平衡約束和節(jié)點閉合約束。流平衡約束指每個網(wǎng)絡(luò)的源節(jié)點到中間節(jié)點的弧有且只有一個，每個網(wǎng)絡(luò)的中間節(jié)點到沉默節(jié)點的弧有且只有一個，中間節(jié)點的進入弧與出發(fā)弧數(shù)量相等。節(jié)點閉合約束指若弧fg被執(zhí)行則ac與cr中的弧fg必有且只有一個被執(zhí)行。如約束(5)～約束(10)。約束(5)～約束(7)是經(jīng)典圖論模型的基本約束，約束(8)表示若弧fg被經(jīng)過則飛機、機組網(wǎng)絡(luò)中必同時有弧fg被執(zhí)行，約束(9)與約束(10)表示航班f只能被一架飛機和一個機組執(zhí)行，由于旅客行程可以將旅客分配到任一或多個OD相同的航班因此無此約束。

(5)

(6)

(7)

(8)

(9)

(10)

對于不同的飛機有飛機特性約束，如飛機座位數(shù)約束，旅客行程被安排到航班f時的人數(shù)之和不能大于執(zhí)行這個航班飛機的座位數(shù)如約束(11)。被分配旅客行程的人數(shù)與旅客行程取消人數(shù)之和等于原旅客行程人數(shù)如約束(12)。不同的飛機對于速度的調(diào)整限度相同，但是由于各飛機的MRC速度不一樣因此巡航時間調(diào)整并不相同，不同航線上的速度調(diào)整限制不同，如約束(13)。約束(14)表示機組僅可以執(zhí)行執(zhí)照允許的飛機任務(wù)，ac(cr)表示可以執(zhí)行飛機ac的機組集合，約束(15)表示飛機不可以執(zhí)行規(guī)定之外的航線(如高原航線由特定飛機執(zhí)飛)，ac(f)表示飛機ac可以執(zhí)行的航線集合。

(11)

(12)

(13)

(14)

(15)

(16)

(17)

(18)

0≤DTf-dtf≤480

tfd=ATf-atf,f∈F

(19)

0≤atf≤curfewf,f∈F

(20)

根據(jù)第2.1節(jié)的闡述，將速度變化帶來的燃油消耗變化納入約束中，為了減少模型中的變量將速度用距離除以巡航時間表示，系數(shù)c1、c2、c3、c4也相應(yīng)改變，如約束(21)～約束(24)，其中Tfc是計劃巡航時間，當(dāng)不考慮巡航速度時，則沒有約束(21)～約束(24)。

(21)

(22)

(23)

(24)

模型的目標(biāo)函數(shù)以最小化成本表示，成本分為航空公司延誤運營成本(Cop，包括航班運營延誤成本與機組空閑成本)、航班取消成本(Cfd)、旅客延誤成本(Cpd)、客票取消成本(Cpc)、速度變化帶來的額外燃油(Cfuel)與碳排放(Cco2)成本。民航局在《航班延誤經(jīng)濟補償指導(dǎo)意見》中的賠償建議，延誤8 h以上給出的賠償標(biāo)準(zhǔn)已經(jīng)接近于取消航班的賠償，所以我們認為航班取消成本是航班延誤8 h的運營成本；旅客客票取消成本是旅客延誤8 h經(jīng)濟損失加上客票價格。

(25)

3 基于二階錐優(yōu)化的模型求解

二階錐規(guī)劃(second-order cone programming，SOCP)可以視作線性規(guī)劃的推廣, 本質(zhì)上是一種凸規(guī)劃, 解的最優(yōu)性和計算高效性都有優(yōu)良特性。利用現(xiàn)有的CPLEX等算法包可以獲得較好的求解結(jié)果, 諸多基于SOCP的優(yōu)化問題可以在多項式時間內(nèi)完成。本節(jié)用到相關(guān)定義如下。

(2)上鏡圖：函數(shù)f：Rn→R的圖像定義為{[x,f(x)]|x∈domf},它是Rn+1空間上的一個子集，則epif={(x,t)|x∈domf，f(x)≤t}是該函數(shù)上鏡圖[21]。還有定理，函數(shù)f是凸函數(shù)當(dāng)且僅當(dāng)epif是凸集。

(3)雙曲不等式：如u2≤v1v2，易證明雙曲不等式可寫成二階錐不等式‖(2u,v1-v2)‖≤v1+v2。

一體化恢復(fù)模型中約束(21)是非線性約束，是非線性不連續(xù)的，因此其上鏡圖是非凸的，約束非凸，模型中的目標(biāo)函數(shù)與其他約束條件也受約束(21)的影響。為了簡化說明刪除了變量索引，約束(21)的上鏡圖可表示為

t≥df(c1λ1+c2λ2+c3λ3+c4λ4)

(26)

y4≤λ1t2y

(27)

y2≤λ2t

(28)

t2≤λ3y

(29)

t4≤λ4y2t

(30)

(31)

式(28)、式(29)是雙曲不等式，式(27)與式(30)都可以寫成如下雙曲不等式：

y2≤st,s2≤λ1y

(32)

t2≤sy，s2≤λ4t

(33)

由雙曲不等式可以寫為二階錐不等式的性質(zhì)可知，模型可以重構(gòu)為一個混合整數(shù)二階錐規(guī)劃問題，模型有線性目標(biāo)函數(shù)，二階錐約束，重構(gòu)后的模型可以使用CPLEX求解得到結(jié)果。

4 仿真算例

采用某航空公司一天的運營數(shù)據(jù)，數(shù)據(jù)包含120 個航班，26 架飛機，6 種機型，32 個機場，16 473名旅客。機型參數(shù)如表2所示。針對既有長時間機場關(guān)閉又有飛機故障設(shè)置兩個場景。設(shè)場景一是浦東機場從該日應(yīng)開放時刻關(guān)閉至12:00，機尾號為

表2 機型的參數(shù)

5113飛機故障4 h，分別使用本文模型與不考慮巡航速度控制的模型(即去除速度相關(guān)的約束與目標(biāo)成本)進行求解構(gòu)成算例1、算例2。場景二是浦東機場從該日應(yīng)開放時刻關(guān)閉至下午16:00，機尾號為5113飛機故障8 h，分別使用本文模型與不考慮巡航速度控制的模型(即去除速度相關(guān)的約束與目標(biāo)成本)進行求解構(gòu)成算例3、算例4。規(guī)定航班最長延誤時間為8 h；機組最長執(zhí)勤時間為14 h，最長飛行時間為8 h；航班之間最短銜接時間為40 min；航班單位運營延誤按機型尾流強度分為，重型機4 167元/h，中型機2 916元/h，輕型機208元/h，本文算例中包含中型機 24架，重型機2 架；旅客單位延誤經(jīng)濟損失，國內(nèi)旅客50 元/h，國際旅客100元 /h；機組空閑成本50 元/min。算例信息如表3所示，求解結(jié)果如表4所示。

表4 求解結(jié)果

表3 場景算例信息

算例1、算例3與算例2、算例4對比可以看到巡航速度控制的最優(yōu)成本小于不考慮速度控制。但當(dāng)恢復(fù)場景復(fù)雜，受到擾動航班較多，考慮巡航速度控制，恢復(fù)成本減少更加明顯。圖2與圖3表示4個算例的旅客延誤分布與恢復(fù)成本分布，考慮巡航速度控制后算例2較算例1在0～1 h的延誤人數(shù)減少448人，旅客延誤成本減少20 690元，額外燃油成本6 224元，碳排放成本915元。算例4較算例3少取消1班航班，旅客行程取消人數(shù)減少52人，客票取消成本46 956元，旅客延誤成本減少8 643元。

圖2 旅客延誤分布Fig.2 Passenger delay distribution

圖3 成本分布Fig.3 Cost distribution

各機場的延誤情況如圖4與圖5所示。算例2較算例1將湛江與成都的延誤人數(shù)清零，在武漢機場的延誤人數(shù)從788 人降到637 人，武漢機場累計延誤時間下降95 min，浦東機場累計延誤時間下降22 min。算例4較算例3將成都、曼谷的延誤人數(shù)清零，武漢機場累計延誤時間下降57 min。從成本分布來看，巡航速度控制將等時間的旅客延誤成本轉(zhuǎn)化為燃油消耗與碳排放成本，兩者之間的差值使總成本減小，而這個差值的大小當(dāng)受擾航班較多時會比較明顯。

圖4 各機場延誤人數(shù)Fig.4 Delays by airport

圖5 各機場累計延誤時間Fig.5 Cumulative delays at airports

5 結(jié)論

以航班擾動恢復(fù)為目的，考慮飛機、機組、旅客一體化恢復(fù)。根據(jù)提出的航班網(wǎng)絡(luò)生成算法，應(yīng)用改進后的航班網(wǎng)絡(luò)，將巡航速度控制策略應(yīng)用于航班恢復(fù)建立一體化恢復(fù)建立模型。模型易于理解算法容易計算機編程實現(xiàn)，通過擾動場景模擬，可在短時間內(nèi)獲得調(diào)整方案。結(jié)果表明巡航速度控制策略通過將等時間的旅客延誤成本轉(zhuǎn)化為燃油消耗與碳排放成本，在恢復(fù)場景復(fù)雜，受到擾動航班較多時可明顯減少恢復(fù)成本，對航班延誤恢復(fù)問題由一定實際意義。