基于魯棒性提高的航班計劃優化模型

高 謙，王世瑞，高 強

（南京航空航天大學民航學院，江蘇 南京211106）

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

1 魯棒性及運營成本計算

1.1 魯棒性的定義及計算

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

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

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

圖1 中STD 為計劃起飛時間；SCT 為計劃過站時間；TDD 為實際起飛延誤；STA 為計劃到達時間；MCT 為最小過站時間；TDA 為實際到達延誤；ATD為實際起飛時間；IDD 為固有起飛延誤；ATA 為實際到達時間；PD 為波及延誤；IDA 為固有到達延誤。

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

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

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

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

1.2 航班計劃運營成本的計算

航班計劃運營成本分為計劃運行成本和航班恢復成本兩個部分。 計劃運行成本為航班運行時所產生的固有成本，包括燃油成本、機組成本、折舊成本、維修成本、起降成本和航路成本等。

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

機組成本通過查閱相關資料可知該公司目標機型波音737-800、波音737-300 和ERJ-145 的機組人員數量分別為6，6，5 人。 根據機組人員每小時的工資可知，波音737-800 和波音737-300 每小時機組花費730 元，ERJ-145 每小時機組花費670元。 機組成本計算公式如

式中：Pairplane為購買飛機價格；Yyear為折舊年限Pengine為單臺發動機價格；Rj為機型j 的殘值率，一般按飛機售價的5%計算；U 為年輪擋小時數。

通過查閱相關資料可知該公司目標機型波音737-800， 波音737-300 和ERJ-145 的每小時的折舊成本分別為11 083，10 298，3 314 元。

式中：Wemp為飛機空重；tflight為飛機飛行小時數；Wmax為最大起飛重量。

通過查閱相關資料可知該公司目標機型波音737-800， 波音737-300 和ERJ-145 的每小時維修成本為3 180，3 360，1 440 元。

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

由以上推算可知航班計劃運營成本為如式（7）所示。 其中定值a 為航班起降成本與航路成本的和，具體到每一個航班來說為定值。

1.3 航班恢復成本的計算

航班計劃恢復成本由延誤成本， 取消成本，換機成本和調機成本組成[7]，由于換機和調機的成本過高，發生條件比較苛刻，故發生概率較低，暫不對換機成本和調機成本進行計算。

1.3.1 延誤成本

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

1.3.2 取消成本

通常情況下航空公司不會輕易取消航班，因為取消航班的成本巨大，并且后續航班很難得到有效的執行，還降低了航空公司的聲譽，航班取消的成本表示方法如

式中：N 為機型載客量；P 為綜合票價。 N 和P 均可以通過機型求出。

1.3.3 航班的期望恢復成本計算

航班的期望恢復成本由上文的兩個個成本組成，如

式中：pdelay為延誤發生的概率；pcancellation為航班取消發生的概率。 其中由于不考慮換機和調機的情況，則認為換機和調機發生的概率為0[9]，由此可總結為式（11），其中pregular為正常航班的概率。

(1)確保PCL控制系統運用環境干燥。雖然PCL控制系統的環境適應能力較強，但是由于其為電氣設備，因此應當保證應用PCL控制系統的環境的干燥，確保PCL控制技術在金礦山電氣設備中的安全穩定性。

2 基于魯棒性提高的航班計劃優化模型

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

根據以上參數以及變量，建立以下基于魯棒性提高的航班計劃優化模型

該模型中，式（12）目標函數表示使得整個航班計劃魯棒性最大化；式（13）為航班計劃運行成本與期望恢復成本之和最小化；式（14）為航班覆蓋約束；式（15）和式（17）為航班網絡模型的節點流平衡約束；式（19）和式（20）為變量約束[11]。

3 基于十日航班數據的模型求解

由于模型是雙目標函數，在求解過程中有一定的困難，故通過將模型簡化為單目標函數來進行計算[12]。 求解思路如圖3 所示。

3.1 將雙目標函數模型轉換為單目標函數模型

由于調整完航班計劃后會減少延誤的時長，但是變相增加了航班調整和取消的次數， 導致了Cfrec的增加，所以為了防止一味的增加魯棒性而忽視航班計劃成本的增加，將成本的目標函數轉為約束以限制成本的無限制增長[13]。 轉換后成本目標函數變為以下約束

式中：可以發現計算結果與r 的取值直接相關，在理想狀態下r=0 時式子無解，即不增加成本而提高航班計劃魯棒性的結果不存在，同時通過航班經驗得知航空延誤成本一般是總成本的20%～28%， 這里通過取下限20%來約束r 的取值范圍為[0,0.2]。

3.2 通過原數據求解Cmin 與Ccancellation

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

由于已知某航司在冬春航班上某月十天的航班數據，可以通過第一節里面介紹的方法對每一天的航班運營成本進行計算，因為航司在不計算延誤的情況下航班計劃是按照最小運營成本制訂的，所以可以認為Cmin即為每一天的運營成本[14]。 計算結果如表1 所示。

表1 每日最小運營成本Tab.1 Minimum daily operating costs

求出Cmin以后便可以通過Cmin對單目標模型進行求解，目標函數為max∑f∈FRf。

由于已知航班計劃的情況下，當前航班計劃不考慮延誤成本即為航司運營實際最小成本。 故約束式（21）可以簡化為式（22）

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

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

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

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

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

3.3 通過Lingo 軟件求魯棒性最大值

在已知上述條件下， 通過Lingo 進行建模對航班計劃魯棒性進行求解。

通過對Lingo 的求解結果描點作圖， 可得到魯棒性R 隨著比率r 變化的曲線圖， 這里采用Day1的數據進行作圖。 實驗結果如圖4 所示。

圖4 實驗結果Fig.4 Experimental results

從圖4 可知隨著r 的增長， 航班計劃的魯棒性隨之增長，并且在r=0.2 時到達最高點。

通過Lingo 計算得到當r=0.2 時10 天的魯棒性如表3 所示。

根據表3 的結果可以發現在模型優化這10 天中的八天魯棒性都得到了不同程度的提高。而day7與Day9 的魯棒性為0.10 和0.15， 結果相較于其他天數較小，通過對數據的觀察發現缺少部分航班計劃延誤時間，導致產生了一定程度的異常。 Day1 和Day6 都沒有數據缺失，但是結果差值較大，通過數據觀察發現由于Day1 的延誤時間最長，而Day6 的延誤時間最短，由此可見該模型在較短時間內的延誤下可以極大的增加航班計劃魯棒性。

4 結論

1） 航班計劃遭遇延誤的情況是無法避免的，通過設置模型，將航班計劃的魯棒性最大化，并且通過十日的航班數據來驗證模型的正確性。 該模型可以幫助航空公司在制訂航班計劃時考慮魯棒性這個因素，從而在設計之初增加過站裕度時間以減少航班延誤的發生。

2） 通過功能強大的Lingo 軟件建模求解，并將結果繪圖，得到了當r=0.2 時魯棒性最大的結論。

3） 本模型的不足在于沒有考慮調機和飛機交換的成本， 導致在計算時會產生魯棒性偏高的結果，綜合考慮所有期望恢復成本并進行建模計算是接下來研究的重點。