考慮容量不確定性的航班時(shí)刻優(yōu)化模型研究

問 濤，張 穎，田 文，張曉潔

(南京航空航天大學(xué) 國家空管飛行流量管理技術(shù)重點(diǎn)實(shí)驗(yàn)室，南京 211106)

近年來我國民航運(yùn)輸業(yè)持續(xù)高速發(fā)展，日益增長的空中交通需求不斷沖擊有限的空域容量資源，為繁忙機(jī)場的正常運(yùn)行帶來巨大挑戰(zhàn).因此，如何進(jìn)一步緩解擁擠和延誤問題，是新形勢下推動民航高質(zhì)量發(fā)展的重要課題之一.一方面，我國正擴(kuò)建、新建機(jī)場，加強(qiáng)民航基礎(chǔ)設(shè)施建設(shè)，直接有效地增加系統(tǒng)容量；另一方面，可以采取流量管理策略，通過控制空中交通需求的時(shí)空分布，在中短期內(nèi)改善機(jī)場容量短缺和航班延誤現(xiàn)象[1].

航班時(shí)刻優(yōu)化策略是一種戰(zhàn)略規(guī)劃階段實(shí)施的流量管理策略，它通過科學(xué)、合理地分配航班時(shí)刻實(shí)現(xiàn)改善對機(jī)場容量的使用，以減少空中交通沖突，增加飛行流量，提高社會效益[2].在眾多文獻(xiàn)中， 航班時(shí)刻優(yōu)化策略問題有多種說法， 包括時(shí)隙分配問題、 時(shí)隙調(diào)度問題等，它們的本質(zhì)是一樣的.

世界多國研究者針對航班時(shí)刻優(yōu)化策略問題進(jìn)行了相關(guān)研究.例如，2017年，Jacquillat等提供的優(yōu)化方法在傳統(tǒng)效率目標(biāo)外，提出了如何度量時(shí)刻可靠性、公平性等其他種類的目標(biāo)[3].2017年，Pellegrini等研究了機(jī)場網(wǎng)絡(luò)在多種時(shí)刻調(diào)整量優(yōu)化目標(biāo)下的時(shí)隙分配[4].2018年，Zografos等提出了考慮時(shí)刻計(jì)劃可接受度的雙目標(biāo)優(yōu)化模型[5].2018年，Ribeiro等研究了基于優(yōu)先級的多目標(biāo)時(shí)刻分配模型及計(jì)算方法，使得優(yōu)化更加貼近實(shí)際規(guī)則[6].2018年，裔田園探究了一種基于航路走向的航班時(shí)刻優(yōu)化方法[7].總體上，已有成果主要集中于對確定型問題的研究，對不確定性問題的研究則相對較少.2013年，Churchill等從宏觀排隊(duì)系統(tǒng)的角度建立了容量不確定性下優(yōu)化機(jī)場時(shí)刻安排水平的模型[8].2014年，Corolli等研究了不確定容量下機(jī)場網(wǎng)絡(luò)的航班時(shí)刻優(yōu)化模型[9].2014年，曾奇初步探索了單個(gè)機(jī)場的魯棒性航班時(shí)刻優(yōu)化[10].2019年，亓堯、岳仁田等研究了只考慮一個(gè)運(yùn)行日的容量不確定性的航班時(shí)隙分配[11-12].

確定型航班時(shí)刻優(yōu)化問題假設(shè)空域系統(tǒng)是理想、靜態(tài)的，不受外界環(huán)境的影響，沒有考慮實(shí)際每日運(yùn)行過程中機(jī)場容量受天氣等因素影響下的隨機(jī)性，得到的航班時(shí)刻在機(jī)場實(shí)際運(yùn)行時(shí)若遇到較低的容量會產(chǎn)生較多的航班延誤.因此，有必要對不確定型航班時(shí)刻優(yōu)化問題進(jìn)行研究，將航班時(shí)刻的戰(zhàn)略協(xié)調(diào)規(guī)劃與實(shí)際運(yùn)行可能的環(huán)境條件相互關(guān)聯(lián)，得到潛在航班延誤更少的時(shí)隙分配結(jié)果.

本文則在前人研究的基礎(chǔ)上，建立了能夠考慮多個(gè)機(jī)場多個(gè)運(yùn)行日的容量不確定性的兩階段隨機(jī)規(guī)劃時(shí)隙分配模型，模型增加了對機(jī)場進(jìn)離場容量的優(yōu)化選擇決策，彌補(bǔ)了既有研究將機(jī)場進(jìn)場容量、離場容量和總?cè)萘抗铝⒖紤]的不足，并設(shè)計(jì)使用了樣本均值近似方法對具有大量場景的大規(guī)模實(shí)例進(jìn)行求解計(jì)算.

1 問題描述

在航空運(yùn)輸系統(tǒng)的實(shí)際運(yùn)營中，為適應(yīng)季節(jié)變化，每年要制定兩次航班計(jì)劃，分為冬春航季和夏秋航季，每個(gè)航季的航班時(shí)刻均要在航季開始前幾個(gè)月提前協(xié)調(diào)好.由于天氣這一主要不確定性因素的存在，由航班時(shí)刻協(xié)調(diào)人在航季開始前協(xié)調(diào)分配好的航班時(shí)刻在機(jī)場實(shí)際運(yùn)行時(shí)往往會受到機(jī)場容量等條件的隨機(jī)變化的影響而不能正常如期執(zhí)行，此時(shí)需要實(shí)施地面等待等戰(zhàn)術(shù)流量管理策略來處理發(fā)生的交通沖突.本文采用兩階段隨機(jī)規(guī)劃方法來考慮容量不確定性，時(shí)刻協(xié)調(diào)人根據(jù)未來機(jī)場網(wǎng)絡(luò)運(yùn)行時(shí)一系列可能的容量場景做出最佳的協(xié)調(diào)決策.

如圖1所示，本文不確定性問題的優(yōu)化依據(jù)包括兩個(gè)階段—協(xié)調(diào)階段和運(yùn)行階段.第一階段為協(xié)調(diào)階段，協(xié)調(diào)人根據(jù)協(xié)調(diào)規(guī)則配置航班時(shí)刻；第二階段為航班時(shí)刻在不同容量場景下的戰(zhàn)術(shù)運(yùn)行過程，航班根據(jù)機(jī)場網(wǎng)絡(luò)容量場景施行戰(zhàn)術(shù)流量管理.本文中機(jī)場容量指機(jī)場在單位時(shí)間能夠執(zhí)行的航空器架次.關(guān)于容量場景，單個(gè)機(jī)場一天的典型容量場景及其發(fā)生概率可以通過分析長期的歷史容量數(shù)據(jù)得到[8]，本文假設(shè)機(jī)場之間的天氣是相互獨(dú)立的，暫不考慮它們之間的相關(guān)性，因此，機(jī)場網(wǎng)絡(luò)的一個(gè)場景是各機(jī)場各運(yùn)行日容量場景的一種組合[9].

圖1 航班時(shí)刻協(xié)調(diào)與運(yùn)行過程

兩階段隨機(jī)規(guī)劃是處理含有不確定性參數(shù)的優(yōu)化問題的常用方法之一，通過陳列展開不確定性場景，即可以得到其等價(jià)的確定性問題.兩階段隨機(jī)規(guī)劃模型的一般形式和確定型等價(jià)形式可見文獻(xiàn)[13].本文針對航班時(shí)刻分配問題建立的優(yōu)化模型如下.

2 兩階段隨機(jī)規(guī)劃航班時(shí)刻優(yōu)化模型

2.1 模型假設(shè)

本文建立的考慮容量不確定性的航班時(shí)刻優(yōu)化模型為方便起見，做出如下假設(shè)：

1)以天氣為主的隨機(jī)因素只對機(jī)場空側(cè)容量造成影響，帶來不確定性；

2)運(yùn)行階段對交通沖突采取的戰(zhàn)術(shù)流量管理手段均為地面等待策略；

3)暫不考慮本地機(jī)場的航班延誤傳播以及來自上游機(jī)場的航班延誤傳播.

2.2 決策變量

2.2.1 協(xié)調(diào)階段決策變量

根據(jù)航班計(jì)劃制定規(guī)則，協(xié)調(diào)后的航班時(shí)刻t必須為5 min的整數(shù)倍時(shí)間點(diǎn)，一個(gè)時(shí)刻t對應(yīng)的是一個(gè)5 min長度的時(shí)間片，一天24 h共為288個(gè)時(shí)間片.

2.2.2 運(yùn)行階段決策變量

不同于一般的考慮不確定性的時(shí)隙分配模型，本文將進(jìn)離場服務(wù)率也作為決策變量.

2.3 目標(biāo)函數(shù)

本文建立的考慮容量不確定性的航班時(shí)刻優(yōu)化模型的目標(biāo)函數(shù)為

MinZ=CST+W·COP

(1)

其第一部分為協(xié)調(diào)階段航班時(shí)刻調(diào)整成本CST，第二部分為權(quán)重系數(shù)W和運(yùn)行階段航班延誤期望成本COP的乘積.權(quán)重系數(shù)的取值范圍為W≥0，本文將其定義為對運(yùn)行延誤的控制程度，用來權(quán)衡協(xié)調(diào)成本和運(yùn)行期望成本之間的關(guān)系.當(dāng)W=0時(shí)，即等價(jià)于確定型航班時(shí)刻優(yōu)化模型，航班時(shí)刻協(xié)調(diào)人不考慮不確定性帶來的潛在運(yùn)行延誤.當(dāng)W>0時(shí)，協(xié)調(diào)人開始考慮整個(gè)機(jī)場網(wǎng)絡(luò)容量的不確定性，W取值越大，則越重視控制運(yùn)行延誤期望的大小，越傾向于安排更多的時(shí)刻調(diào)整以減少運(yùn)行延誤期望成本.其中：

(2)

(3)

式(2)表示協(xié)調(diào)成本為總航班調(diào)整時(shí)間量，其中daysf為航班f的計(jì)劃運(yùn)行天數(shù)，deptf為航班f申請的計(jì)劃起飛時(shí)刻，arrtf為航班f申請的計(jì)劃降落時(shí)刻.式(3)表示運(yùn)行成本為各容量場景的總航班運(yùn)行延誤時(shí)間的數(shù)學(xué)期望，其中p(ω)為機(jī)場網(wǎng)絡(luò)容量場景ω的發(fā)生概率，ck為機(jī)場k延誤一個(gè)航班估計(jì)所需的時(shí)間成本.

2.4 約束條件

2.4.1 戰(zhàn)略協(xié)調(diào)約束

1)航班時(shí)刻分配約束

保證每一個(gè)航班的起飛和降落申請都分配到時(shí)刻，即：

(4)

(5)

2)機(jī)場額定容量約束

保證機(jī)場計(jì)劃的起飛、降落和總航班數(shù)量不超過對應(yīng)的機(jī)場額定容量，即：

?k∈K,r∈R,t∈T,h∈H

(6)

?k∈K,r∈R,t∈T,h∈H

(7)

?k∈K,r∈R,t∈T,h∈H

(8)

3)飛行時(shí)間約束

保證所有航班的計(jì)劃飛行時(shí)間不變，即：

(9)

其中：lf為航班f的計(jì)劃飛行時(shí)間.

4)周轉(zhuǎn)時(shí)間約束

保證對于銜接航班，前一個(gè)航班的降落操作與后一個(gè)航班的起飛操作之間的時(shí)刻間隔不小于所需的最小周轉(zhuǎn)時(shí)間，即：

(10)

其中：qff′為銜接航班對(f,f′)∈P的允許最小周轉(zhuǎn)時(shí)間，f對應(yīng)降落航班，f′對應(yīng)起飛航班.

2.4.2 戰(zhàn)術(shù)運(yùn)行約束

1)運(yùn)行延誤定義約束

定義起飛延誤、降落延誤航班數(shù)量分別為超出進(jìn)場和離場服務(wù)能力的航班架次，即

?k∈K,r∈R,t∈T,h∈H

(11)

?k∈K,r∈R,t∈T,h∈H

(12)

2)進(jìn)離場服務(wù)率優(yōu)化選擇約束

機(jī)場運(yùn)行時(shí)可達(dá)到的進(jìn)場服務(wù)率和離場服務(wù)率之間存在一定的關(guān)系，即：

(13)

圖2 進(jìn)離場服務(wù)率優(yōu)化選擇原理圖

機(jī)場跑道既要用于起飛，又要用于降落，研究表明，機(jī)場進(jìn)離場率之間存在包絡(luò)線形狀的制約關(guān)系，該包絡(luò)線表征了機(jī)場運(yùn)行容量，其形狀、大小取決于跑道配置和天氣條件[14]，如圖2所示.根據(jù)容量的定義，機(jī)場運(yùn)行過程中，能夠執(zhí)行的航班量應(yīng)該是在包絡(luò)線范圍之內(nèi)，圖2中圓點(diǎn)表示某機(jī)場假想的一些計(jì)劃航班量，實(shí)線包絡(luò)線表示該機(jī)場某時(shí)段假想的容量，在該容量情況下，包絡(luò)線內(nèi)的計(jì)劃需求完全可以滿足，對于包絡(luò)線外的計(jì)劃需求，機(jī)場實(shí)際運(yùn)行時(shí)管制員會決定合適的服務(wù)率，只執(zhí)行部分航班，以實(shí)現(xiàn)容流平衡，如圖2中箭頭所示.

不同于一般的考慮不確定性的時(shí)隙分配研究將進(jìn)離場運(yùn)行容量孤立開來列寫約束，忽略了它們之間固有的關(guān)系，本文在模型中加入進(jìn)離場服務(wù)率優(yōu)化選擇約束，使得模型能夠根據(jù)容量場景ω下各時(shí)段容量包絡(luò)線情況、機(jī)場總的航班計(jì)劃量，優(yōu)化選擇每個(gè)時(shí)段最適宜的進(jìn)離場率的組合，實(shí)現(xiàn)進(jìn)離場率的動態(tài)平衡優(yōu)化，更加符合機(jī)場實(shí)際運(yùn)行操作.

2.5 求解計(jì)算方法

上述模型為整數(shù)線性規(guī)劃模型.本文使用強(qiáng)大的商業(yè)數(shù)學(xué)規(guī)劃求解器CPLEX求解.然而機(jī)場網(wǎng)絡(luò)多運(yùn)行日的容量場景數(shù)量一般呈指數(shù)型增加，往往使得模型的規(guī)模異常龐大，對此，本文在求解中采用一種運(yùn)用統(tǒng)計(jì)近似的簡單、快速的計(jì)算方法—樣本均值近似.

樣本均值近似是一種基于蒙特卡洛仿真的外部采樣方法，它通過隨機(jī)抽取部分容量場景，使用樣本運(yùn)行延誤成本的算術(shù)平均作為總體運(yùn)行延誤成本期望的近似值，并通過多次采樣縮小近似解的范圍.根據(jù)文獻(xiàn)[9]和[15]，結(jié)合本文問題，具體求解計(jì)算步驟設(shè)計(jì)如下：

1)確定采樣次數(shù)M和樣本大小N；

3)根據(jù)容量場景ω的發(fā)生概率按照輪盤賭規(guī)則抽取樣本；

4)M組容量場景樣本分別代入樣本均值近似模型使用CPLEX求解，得到各組樣本的目標(biāo)函數(shù)值Lm；

3 算例實(shí)驗(yàn)

3.1 實(shí)例參數(shù)

采用我國北京首都機(jī)場(ZBAA)和廣州白云機(jī)場(ZGGG)一周的預(yù)先飛行計(jì)劃數(shù)據(jù)進(jìn)行模擬計(jì)算.

兩場所構(gòu)成的機(jī)場網(wǎng)絡(luò)如圖3所示，機(jī)場網(wǎng)絡(luò)考慮在ZBAA和ZGGG起降的航班，其中ZBAA和ZGGG考慮容量約束，外圍機(jī)場假設(shè)容量為無窮大.本算例ZBAA和ZGGG的容量約束類型均選取為整點(diǎn)小時(shí)容量約束，戰(zhàn)略協(xié)調(diào)階段使用民航局頒布的協(xié)調(diào)機(jī)場容量標(biāo)準(zhǔn)作為額定總?cè)萘浚?具體ZBAA為86架次/h，ZGGG為69架次/h；戰(zhàn)術(shù)運(yùn)行階段機(jī)場進(jìn)離場容量，即進(jìn)離場服務(wù)率，使用后文假設(shè)的運(yùn)行容量場景.

圖3 機(jī)場網(wǎng)絡(luò)示意圖

以ZBAA和ZGGG為目標(biāo)機(jī)場選取2018年3月5日～2018年3月11日的預(yù)先飛行計(jì)劃如表1所示，共計(jì)航班申請4 502條.其他機(jī)場參數(shù)包括：選擇優(yōu)化的時(shí)段為各計(jì)劃日的12:00～18:00；兩機(jī)場的航班延誤時(shí)間乘子ck粗定為5 min/架次.

表1 預(yù)先飛行計(jì)劃(部分)

3.2 容量場景

由于沒有機(jī)場歷史運(yùn)行容量數(shù)據(jù)來源可用于分析，本文采用假設(shè)的機(jī)場網(wǎng)絡(luò)容量場景.為方便起見，假設(shè)兩機(jī)場的容量場景和發(fā)生概率相同，各場景每個(gè)小時(shí)的容量也相同，且容量包絡(luò)線均為如圖2中間所示的三段，αb、βb為0或1，γb值具體如表2所示.7個(gè)運(yùn)行日則機(jī)場網(wǎng)絡(luò)共得到2.68億個(gè)容量場景.

表2 機(jī)場假設(shè)容量場景

3.3 結(jié)果與分析

為了考察運(yùn)行延誤控制程度對時(shí)刻協(xié)調(diào)成本的影響，對前述模型采用不同的權(quán)重系數(shù)W進(jìn)行計(jì)算，得到戰(zhàn)略協(xié)調(diào)成本與戰(zhàn)術(shù)運(yùn)行期望成本之間的關(guān)系.所有算例樣本均值近似初始樣本大小N和N′分別定為100和500，初始采樣次數(shù)M定為10，優(yōu)化間隙限定為3%.最終結(jié)果如表3和圖4所示.Z*下界計(jì)算用時(shí)均在1 h左右，上界計(jì)算用時(shí)均在28 min左右.

表3列出了不同權(quán)重系數(shù)下目標(biāo)函數(shù)最優(yōu)值的上下界和標(biāo)準(zhǔn)差，最佳近似解的兩階段成本以及最佳近似解下同W=0時(shí)相比運(yùn)行期望成本優(yōu)化的程度.通過表3可知，下界和上界都非常接近，表明近似結(jié)果精確度高；上下界的標(biāo)準(zhǔn)差都相對較小，說明實(shí)驗(yàn)選擇的樣本大小、數(shù)量合理，所取樣本點(diǎn)分布均勻.

表3 求解計(jì)算結(jié)果

圖4顯示了戰(zhàn)略協(xié)調(diào)成本和運(yùn)行期望成本的帕累托前沿.首先，W=1和W=0時(shí)的結(jié)果一樣，說明W=1時(shí)模型還不足以產(chǎn)生隨機(jī)優(yōu)化的效果，這是由于本文暫時(shí)省略了對波及延誤的計(jì)算；戰(zhàn)略協(xié)調(diào)成本為0，這是因?yàn)轭A(yù)先飛行計(jì)劃由民航局審批后得到，本身已基本滿足公布容量約束.接著，隨著權(quán)重W的遞增，戰(zhàn)略協(xié)調(diào)成本在隨之增加，而運(yùn)行延誤期望成本在不斷減小，且隨著運(yùn)行期望成本的減小，戰(zhàn)略協(xié)調(diào)成本增加得越快.結(jié)合表3，戰(zhàn)略協(xié)調(diào)成本增加435 min，運(yùn)行延誤期望成本即減少22.61%，驗(yàn)證了模型能夠幫助減少運(yùn)行階段預(yù)期的不確定性延誤，航班時(shí)刻協(xié)調(diào)人可以根據(jù)需求和能夠接受的水平對協(xié)調(diào)成本和運(yùn)行期望成本做出權(quán)衡.

圖4 戰(zhàn)略協(xié)調(diào)成本與運(yùn)行期望成本的帕累托前沿

4 結(jié) 論

1)本文建立了基于兩階段隨機(jī)規(guī)劃的航班時(shí)刻優(yōu)化模型，模型能夠處理考慮多個(gè)機(jī)場多個(gè)運(yùn)行日的容量不確定性；

2)所建模型將進(jìn)離場服務(wù)率也作為決策變量，在戰(zhàn)術(shù)運(yùn)行階段加入了進(jìn)離場率優(yōu)化選擇約束，更加貼近機(jī)場運(yùn)行操作實(shí)際；

3)結(jié)合模型設(shè)計(jì)總結(jié)的樣本均值近似方法簡單快速，使得具有大量場景的實(shí)例能在有效時(shí)間內(nèi)求解計(jì)算得到滿意的結(jié)果；

4)結(jié)合實(shí)際數(shù)據(jù)驗(yàn)證了模型的有效性，同時(shí)分析了航班時(shí)刻戰(zhàn)略協(xié)調(diào)成本與運(yùn)行期望成本之間的關(guān)系，可以輔助航班時(shí)刻協(xié)調(diào)人根據(jù)能夠接受的運(yùn)行延誤期望水平做出合適的時(shí)刻協(xié)調(diào)決策；

5)下一步可進(jìn)行的研究包括：尋找可行的間接方法得出我國機(jī)場真實(shí)的典型容量場景；研究延誤波及的計(jì)算從而得到更精確的運(yùn)行延誤期望等.