基于魯棒性提高的航班計(jì)劃優(yōu)化模型

高 謙，王世瑞，高 強(qiáng)

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

2004 年Rosenberger[1]為了減少航班鏈上的延誤和波及延誤，通過(guò)采取了減少航班鏈長(zhǎng)度和降低樞紐機(jī)場(chǎng)連通性的方法建立了魯棒性?xún)?yōu)化模型，并且成功增加了航班計(jì)劃的魯棒性且減少了運(yùn)營(yíng)成本。Claudine[2]以增加非樞紐機(jī)場(chǎng)航班計(jì)劃魯棒性為目標(biāo)，通過(guò)區(qū)別非樞紐機(jī)場(chǎng)的種類(lèi)，建立了機(jī)組排班和機(jī)型指派的魯棒性?xún)?yōu)化模型，并且成功增加了非樞紐機(jī)場(chǎng)航班計(jì)劃的魯棒性。Lan 等[3]提出了站在航空公司和旅客角度兩種新的方法提高航班計(jì)劃魯棒性，分別以減少航班鏈長(zhǎng)度和最小化延誤影響的旅客數(shù)量為目標(biāo)建立模型，兩種方法都不同程度的減少了延誤帶來(lái)的成本增加。 Dunbar M[4]為了減少延誤的總時(shí)間和延誤總成本，提出了一種合并了飛機(jī)路線和機(jī)組規(guī)劃魯棒性的增強(qiáng)模型，并且有效的減少了延誤成本。 Lee L H[5]為了解決魯棒性求解問(wèn)題，采用了多目標(biāo)遺傳算法對(duì)其通過(guò)仿真建立的多目標(biāo)航班計(jì)劃的魯棒性?xún)?yōu)化模型進(jìn)行求解，這種方法的優(yōu)勢(shì)在于可以在多重標(biāo)準(zhǔn)的情況下都可以求出最優(yōu)解， 但這個(gè)最優(yōu)解并不完全符合實(shí)際意義。 目前，國(guó)內(nèi)學(xué)者朱新輝[6]提出了基于飛機(jī)排班的一體化魯棒優(yōu)化模型，通過(guò)設(shè)置雙目標(biāo)分別量化了整體航班計(jì)劃的魯棒性和運(yùn)營(yíng)成本，但是其模型并未考慮航班更改而產(chǎn)生的成本。 針對(duì)現(xiàn)有模型的不足，在這些模型的基礎(chǔ)上建立基于魯棒性提高的航班計(jì)劃優(yōu)化模型。

1 魯棒性及運(yùn)營(yíng)成本計(jì)算

1.1 魯棒性的定義及計(jì)算

魯棒性（Robustness）是指當(dāng)系統(tǒng)處于外界干擾時(shí)可以保持原系統(tǒng)狀態(tài)的不變的能力和當(dāng)系統(tǒng)狀態(tài)改變時(shí)可以快速恢復(fù)系統(tǒng)狀態(tài)的能力的綜合能力。 針對(duì)航班計(jì)劃來(lái)說(shuō)，如果在制訂航班計(jì)劃時(shí)考慮到抵御航班延誤和在已產(chǎn)生延誤的基礎(chǔ)上恢復(fù)航班狀態(tài)，這就是提高航班計(jì)劃的魯棒性。 目前提高航班計(jì)劃的魯棒性的方法主要有：增加過(guò)站松弛時(shí)間、提高機(jī)型純度、減少航班鏈長(zhǎng)度。 由于提高機(jī)型純度這種方法相對(duì)于航空公司來(lái)說(shuō)短期實(shí)行成本巨大，故僅針對(duì)增加過(guò)站松弛時(shí)間和減少航班鏈來(lái)設(shè)計(jì)模型。 魯棒性直接掛鉤的變量為航班的起飛延誤和到達(dá)延誤， 故可以將魯棒性的計(jì)算公式（1）進(jìn)行定義[7]

式中：Rf表示某個(gè)航班f 的魯棒性；IDDf代表航班f的固有起飛延誤；IDAf代表航班f 的固有到達(dá)延誤；TDDf代表航班f 的實(shí)際起飛延誤；TDAf代表航班f的實(shí)際到達(dá)延誤；F 代表航班集合。 具體含義如圖1所示[7]。

圖1 航班延誤示意圖Fig.1 Schematic diagram of flight delays

圖1 中STD 為計(jì)劃起飛時(shí)間；SCT 為計(jì)劃過(guò)站時(shí)間；TDD 為實(shí)際起飛延誤；STA 為計(jì)劃到達(dá)時(shí)間；MCT 為最小過(guò)站時(shí)間；TDA 為實(shí)際到達(dá)延誤；ATD為實(shí)際起飛時(shí)間；IDD 為固有起飛延誤；ATA 為實(shí)際到達(dá)時(shí)間；PD 為波及延誤；IDA 為固有到達(dá)延誤。

由于不考慮波及延誤，故可將魯棒性定義公式改為

式中：CDDf代表航班f 的更改起飛延誤；CDAf代表航班f 的更改到達(dá)延誤。 具體含義如圖2 所示。

圖2 更改航班計(jì)劃示意圖Fig.2 Sketch map of changing flight schedule

更改起飛延誤為當(dāng)更改起飛延誤和更改到達(dá)延誤的總和小于實(shí)際起飛延誤和實(shí)際到達(dá)延誤的總和時(shí)，總延誤減少，Rf的值為正，航班f 魯棒性增加；反之，總延誤增加，Rf為負(fù)，航班f 魯棒性減少。

1.2 航班計(jì)劃運(yùn)營(yíng)成本的計(jì)算

航班計(jì)劃運(yùn)營(yíng)成本分為計(jì)劃運(yùn)行成本和航班恢復(fù)成本兩個(gè)部分。 計(jì)劃運(yùn)行成本為航班運(yùn)行時(shí)所產(chǎn)生的固有成本，包括燃油成本、機(jī)組成本、折舊成本、維修成本、起降成本和航路成本等。

不同的機(jī)型每小時(shí)消耗的燃油體積不等，通過(guò)查閱資料得知目標(biāo)航司的機(jī)型為波音737-800、波音737-300 和ERJ-145 的耗油量分別為2 650，2 800，1 200 L/h， 并且設(shè)置當(dāng)下航空燃油成本為6元/L，就可以得出所有航班的燃油成本，計(jì)算公式如

機(jī)組成本通過(guò)查閱相關(guān)資料可知該公司目標(biāo)機(jī)型波音737-800、波音737-300 和ERJ-145 的機(jī)組人員數(shù)量分別為6，6，5 人。 根據(jù)機(jī)組人員每小時(shí)的工資可知，波音737-800 和波音737-300 每小時(shí)機(jī)組花費(fèi)730 元，ERJ-145 每小時(shí)機(jī)組花費(fèi)670元。 機(jī)組成本計(jì)算公式如

式中：Pairplane為購(gòu)買(mǎi)飛機(jī)價(jià)格；Yyear為折舊年限Pengine為單臺(tái)發(fā)動(dòng)機(jī)價(jià)格；Rj為機(jī)型j 的殘值率，一般按飛機(jī)售價(jià)的5%計(jì)算；U 為年輪擋小時(shí)數(shù)。

通過(guò)查閱相關(guān)資料可知該公司目標(biāo)機(jī)型波音737-800， 波音737-300 和ERJ-145 的每小時(shí)的折舊成本分別為11 083，10 298，3 314 元。

式中：Wemp為飛機(jī)空重；tflight為飛機(jī)飛行小時(shí)數(shù)；Wmax為最大起飛重量。

通過(guò)查閱相關(guān)資料可知該公司目標(biāo)機(jī)型波音737-800， 波音737-300 和ERJ-145 的每小時(shí)維修成本為3 180，3 360，1 440 元。

其余的成本包括飛機(jī)起降成本和航路成本。 通過(guò)查閱相關(guān)資料可知該公司目標(biāo)機(jī)型波音737-800， 波音737-300 和ERJ-145 的每架次起降成本為3 360，2 200，2 000 元； 每 公 里 航 路 成 本 為0.39，0.23，0.11 元。

由以上推算可知航班計(jì)劃運(yùn)營(yíng)成本為如式（7）所示。 其中定值a 為航班起降成本與航路成本的和，具體到每一個(gè)航班來(lái)說(shuō)為定值。

1.3 航班恢復(fù)成本的計(jì)算

航班計(jì)劃恢復(fù)成本由延誤成本， 取消成本，換機(jī)成本和調(diào)機(jī)成本組成[7]，由于換機(jī)和調(diào)機(jī)的成本過(guò)高，發(fā)生條件比較苛刻，故發(fā)生概率較低，暫不對(duì)換機(jī)成本和調(diào)機(jī)成本進(jìn)行計(jì)算。

1.3.1 延誤成本

式中：N 為機(jī)型載客量；T 為延誤時(shí)間； 延誤成本UCdelay設(shè)定為每延誤一分鐘虧損1 200 元；N 基于不同機(jī)型而不同。

1.3.2 取消成本

通常情況下航空公司不會(huì)輕易取消航班，因?yàn)槿∠桨嗟某杀揪薮?，并且后續(xù)航班很難得到有效的執(zhí)行，還降低了航空公司的聲譽(yù)，航班取消的成本表示方法如

式中：N 為機(jī)型載客量；P 為綜合票價(jià)。 N 和P 均可以通過(guò)機(jī)型求出。

1.3.3 航班的期望恢復(fù)成本計(jì)算

航班的期望恢復(fù)成本由上文的兩個(gè)個(gè)成本組成，如

式中：pdelay為延誤發(fā)生的概率；pcancellation為航班取消發(fā)生的概率。 其中由于不考慮換機(jī)和調(diào)機(jī)的情況，則認(rèn)為換機(jī)和調(diào)機(jī)發(fā)生的概率為0[9]，由此可總結(jié)為式（11），其中pregular為正常航班的概率。

(1)確保PCL控制系統(tǒng)運(yùn)用環(huán)境干燥。雖然PCL控制系統(tǒng)的環(huán)境適應(yīng)能力較強(qiáng)，但是由于其為電氣設(shè)備，因此應(yīng)當(dāng)保證應(yīng)用PCL控制系統(tǒng)的環(huán)境的干燥，確保PCL控制技術(shù)在金礦山電氣設(shè)備中的安全穩(wěn)定性。

2 基于魯棒性提高的航班計(jì)劃優(yōu)化模型

本模型在時(shí)空網(wǎng)絡(luò)模型的基礎(chǔ)上進(jìn)行了變換，以整體航班計(jì)劃的魯棒性最大化為目標(biāo)，模型參數(shù)和變量的含義為：Rf代表航班f 的魯棒性；F 代表航班集合，f∈F；K 代表機(jī)型集合k∈K；S 代表航班鏈集合，s∈S；Cfopr代表計(jì)劃運(yùn)行成本；Cfrec代表期望恢復(fù)成本；r 代表航班成本增加比率；Cmin為不考慮魯棒性的情況下航班計(jì)劃運(yùn)行成本最小值；xf為決策變量，當(dāng)航班被執(zhí)行時(shí)取值為1，反之為0；afs為指示變量，當(dāng)航班f 在航班鏈s 上時(shí)，afs為1，反之為0；xsk為決策變量， 當(dāng)航班鏈s 被選中并且由機(jī)型k所執(zhí)飛時(shí)，xsk為1，反之為0；ydk-和ydk+分別代表在整個(gè)航班計(jì)劃中任意時(shí)刻前后起飛的機(jī)型k 的數(shù)量；yak-和yak+分別代表在整個(gè)航班計(jì)劃中任意時(shí)刻前后到達(dá)的機(jī)型k 的數(shù)量[9]。

根據(jù)以上參數(shù)以及變量，建立以下基于魯棒性提高的航班計(jì)劃優(yōu)化模型

該模型中，式（12）目標(biāo)函數(shù)表示使得整個(gè)航班計(jì)劃魯棒性最大化；式（13）為航班計(jì)劃運(yùn)行成本與期望恢復(fù)成本之和最小化；式（14）為航班覆蓋約束；式（15）和式（17）為航班網(wǎng)絡(luò)模型的節(jié)點(diǎn)流平衡約束；式（19）和式（20）為變量約束[11]。

3 基于十日航班數(shù)據(jù)的模型求解

由于模型是雙目標(biāo)函數(shù)，在求解過(guò)程中有一定的困難，故通過(guò)將模型簡(jiǎn)化為單目標(biāo)函數(shù)來(lái)進(jìn)行計(jì)算[12]。 求解思路如圖3 所示。

3.1 將雙目標(biāo)函數(shù)模型轉(zhuǎn)換為單目標(biāo)函數(shù)模型

由于調(diào)整完航班計(jì)劃后會(huì)減少延誤的時(shí)長(zhǎng)，但是變相增加了航班調(diào)整和取消的次數(shù)， 導(dǎo)致了Cfrec的增加，所以為了防止一味的增加魯棒性而忽視航班計(jì)劃成本的增加，將成本的目標(biāo)函數(shù)轉(zhuǎn)為約束以限制成本的無(wú)限制增長(zhǎng)[13]。 轉(zhuǎn)換后成本目標(biāo)函數(shù)變?yōu)橐韵录s束

式中：可以發(fā)現(xiàn)計(jì)算結(jié)果與r 的取值直接相關(guān)，在理想狀態(tài)下r=0 時(shí)式子無(wú)解，即不增加成本而提高航班計(jì)劃魯棒性的結(jié)果不存在，同時(shí)通過(guò)航班經(jīng)驗(yàn)得知航空延誤成本一般是總成本的20%～28%， 這里通過(guò)取下限20%來(lái)約束r 的取值范圍為[0,0.2]。

3.2 通過(guò)原數(shù)據(jù)求解Cmin 與Ccancellation

圖3 模型求解思路Fig.3 Model solution idea

由于已知某航司在冬春航班上某月十天的航班數(shù)據(jù)，可以通過(guò)第一節(jié)里面介紹的方法對(duì)每一天的航班運(yùn)營(yíng)成本進(jìn)行計(jì)算，因?yàn)楹剿驹诓挥?jì)算延誤的情況下航班計(jì)劃是按照最小運(yùn)營(yíng)成本制訂的，所以可以認(rèn)為Cmin即為每一天的運(yùn)營(yíng)成本[14]。 計(jì)算結(jié)果如表1 所示。

表1 每日最小運(yùn)營(yíng)成本Tab.1 Minimum daily operating costs

求出Cmin以后便可以通過(guò)Cmin對(duì)單目標(biāo)模型進(jìn)行求解，目標(biāo)函數(shù)為max∑f∈FRf。

由于已知航班計(jì)劃的情況下，當(dāng)前航班計(jì)劃不考慮延誤成本即為航司運(yùn)營(yíng)實(shí)際最小成本。 故約束式（21）可以簡(jiǎn)化為式（22）

將約束式（22）帶入原模型，即可得到化簡(jiǎn)之后的模型。 模型如下

式（23）中的Rf通過(guò)第一章里面的公式進(jìn)行替換；式（14）為航班覆蓋約束；式（20）為變量約束。

通過(guò)上文的求解Cmin可以發(fā)現(xiàn)這10 天之內(nèi)的航班數(shù)量并不相同， 這也是導(dǎo)致每天運(yùn)營(yíng)成本差距較大的原因， 對(duì)此可以推算出航司已經(jīng)將所有不適合運(yùn)行的航班進(jìn)行了取消， 對(duì)此約束式（22）里面的由原式（10）可知×Ccancellation。由于在這10 天中第1 天的運(yùn)營(yíng)成本最大，并且航班數(shù)量最多， 假定第1 天的航班計(jì)劃為沒(méi)有航班取消的情況， 通過(guò)觀察航班數(shù)據(jù)得知第4 天也沒(méi)有產(chǎn)生航班取消情況，其余時(shí)間的航班計(jì)劃均產(chǎn)生了不同程度的取消。 通過(guò)式（9）可以計(jì)算出Ccancellation，如表2 所示。 其中波音737-800， 波音737-300 和ERJ-145 載客量分別為164，149 人和50 人[15]，綜合票價(jià)取各個(gè)航班票價(jià)。pcancellation為這十天內(nèi)該航班取消的概率。

表2 每日航班取消成本Tab.2 Daily flight cancellation costs

表3 每日魯棒性Tab.3 Daily robustness

3.3 通過(guò)Lingo 軟件求魯棒性最大值

在已知上述條件下， 通過(guò)Lingo 進(jìn)行建模對(duì)航班計(jì)劃魯棒性進(jìn)行求解。

通過(guò)對(duì)Lingo 的求解結(jié)果描點(diǎn)作圖， 可得到魯棒性R 隨著比率r 變化的曲線圖， 這里采用Day1的數(shù)據(jù)進(jìn)行作圖。 實(shí)驗(yàn)結(jié)果如圖4 所示。

圖4 實(shí)驗(yàn)結(jié)果Fig.4 Experimental results

從圖4 可知隨著r 的增長(zhǎng)， 航班計(jì)劃的魯棒性隨之增長(zhǎng)，并且在r=0.2 時(shí)到達(dá)最高點(diǎn)。

通過(guò)Lingo 計(jì)算得到當(dāng)r=0.2 時(shí)10 天的魯棒性如表3 所示。

根據(jù)表3 的結(jié)果可以發(fā)現(xiàn)在模型優(yōu)化這10 天中的八天魯棒性都得到了不同程度的提高。而day7與Day9 的魯棒性為0.10 和0.15， 結(jié)果相較于其他天數(shù)較小，通過(guò)對(duì)數(shù)據(jù)的觀察發(fā)現(xiàn)缺少部分航班計(jì)劃延誤時(shí)間，導(dǎo)致產(chǎn)生了一定程度的異常。 Day1 和Day6 都沒(méi)有數(shù)據(jù)缺失，但是結(jié)果差值較大，通過(guò)數(shù)據(jù)觀察發(fā)現(xiàn)由于Day1 的延誤時(shí)間最長(zhǎng)，而Day6 的延誤時(shí)間最短，由此可見(jiàn)該模型在較短時(shí)間內(nèi)的延誤下可以極大的增加航班計(jì)劃魯棒性。

4 結(jié)論

1） 航班計(jì)劃遭遇延誤的情況是無(wú)法避免的，通過(guò)設(shè)置模型，將航班計(jì)劃的魯棒性最大化，并且通過(guò)十日的航班數(shù)據(jù)來(lái)驗(yàn)證模型的正確性。 該模型可以幫助航空公司在制訂航班計(jì)劃時(shí)考慮魯棒性這個(gè)因素，從而在設(shè)計(jì)之初增加過(guò)站裕度時(shí)間以減少航班延誤的發(fā)生。

2） 通過(guò)功能強(qiáng)大的Lingo 軟件建模求解，并將結(jié)果繪圖，得到了當(dāng)r=0.2 時(shí)魯棒性最大的結(jié)論。

3） 本模型的不足在于沒(méi)有考慮調(diào)機(jī)和飛機(jī)交換的成本， 導(dǎo)致在計(jì)算時(shí)會(huì)產(chǎn)生魯棒性偏高的結(jié)果，綜合考慮所有期望恢復(fù)成本并進(jìn)行建模計(jì)算是接下來(lái)研究的重點(diǎn)。