基于可接受調(diào)整量水平的航班時(shí)刻優(yōu)化研究*

汪夢(mèng)蝶 胡明華 趙 征

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

0 引 言

20世紀(jì)80年代,國(guó)內(nèi)外學(xué)者開(kāi)始研究和開(kāi)發(fā)地面等待策略，而后將成果拓展至了航班時(shí)刻優(yōu)化領(lǐng)域.Zografos等[1]通過(guò)制定符合歐盟規(guī)范和IATA時(shí)隙分配指南的模型來(lái)解決單機(jī)場(chǎng)的戰(zhàn)略階段航班優(yōu)化問(wèn)題，并應(yīng)用于三個(gè)希臘機(jī)場(chǎng)的實(shí)際數(shù)據(jù).結(jié)果表明,航班調(diào)整總量在14%～95%的范圍內(nèi)降低.Castelli等[2]建立了考慮航班起降時(shí)刻和相應(yīng)航線的多機(jī)場(chǎng)網(wǎng)絡(luò)優(yōu)化模型.Pyrgiotis等[3]設(shè)計(jì)了考慮聯(lián)程航班限制的整數(shù)規(guī)劃兩階段模型，旨在求出一個(gè)最小化航班調(diào)整量的時(shí)刻表，同時(shí)將總體調(diào)整量保持在盡可能低的水平，以提高單機(jī)場(chǎng)容量利用率.Jacquillat等[4]提出了結(jié)合容量動(dòng)態(tài)規(guī)劃模型和航班延誤排隊(duì)模型的單機(jī)場(chǎng)航班時(shí)刻綜合調(diào)配方法，從而聯(lián)合優(yōu)化戰(zhàn)略階段的航班時(shí)刻表和戰(zhàn)術(shù)階段的容量利用策略.胡明華等[5]基于多元受限地面等待策略建立了多元受限航班時(shí)刻優(yōu)化模型，并提出改進(jìn)啟發(fā)式算法.彭瑛等[6]分析了航班時(shí)刻編排對(duì)跑道延誤的影響，建立了平均跑道延誤時(shí)間最少、總時(shí)間片調(diào)整最少、總延誤航班架次最少的多目標(biāo)航班時(shí)刻優(yōu)化排序模型.曾奇[7]在傳統(tǒng)航班時(shí)刻優(yōu)化模型上改進(jìn)了三種給予補(bǔ)償機(jī)制的模型，采用Xpress-MP建模和優(yōu)化工具進(jìn)行求解.王湛等[8]以協(xié)同決策理論為基礎(chǔ)，在降低延誤時(shí)間的前提下優(yōu)化了進(jìn)場(chǎng)航班，提高了機(jī)場(chǎng)之間時(shí)空資源使用的公平性.王倩等[9]在滿(mǎn)足延誤水平的基礎(chǔ)上，從航空公司公平性的角度構(gòu)建了模型，并設(shè)計(jì)了基于粒子群算法的布谷鳥(niǎo)搜索算法.

綜上，目前航班時(shí)刻優(yōu)化的相關(guān)研究主要集中在以航班調(diào)整總量、最大航班調(diào)整量、航班延誤時(shí)間等函數(shù)的組合作為優(yōu)化目標(biāo)的多元受限模型，并沒(méi)有考慮航班可接受調(diào)整量水平，也沒(méi)有針對(duì)時(shí)刻表功效性和可接受性之間關(guān)系的研究,因此，本文旨在分析優(yōu)化過(guò)程對(duì)功效性和可接受性的影響，使配置結(jié)果更加符合現(xiàn)實(shí)運(yùn)行需求，從而真正提高資源使用效率.

1 航班時(shí)刻優(yōu)化的功效性與可接受性分析

我國(guó)航班時(shí)刻管理遵循以政府為主導(dǎo)的行政配置模式，這可能會(huì)導(dǎo)致調(diào)整后的航班時(shí)刻所在的時(shí)段不夠吸引航空公司進(jìn)行實(shí)際運(yùn)行，從而出現(xiàn)航空公司空置、虛占航班時(shí)刻或者售票時(shí)刻與批復(fù)時(shí)刻不一致的情況，見(jiàn)表1.這類(lèi)情況的根源配置過(guò)程中沒(méi)有預(yù)先考慮實(shí)際運(yùn)行航班時(shí)刻表的可接受性.

表1 西南地區(qū)2011/2012年冬春季繁忙機(jī)場(chǎng)航班時(shí)刻監(jiān)管通報(bào)部分內(nèi)容

因此，文中提出航班時(shí)刻表可接受調(diào)整量水平的概念，在模型中用可接受調(diào)整量表示，并將超過(guò)可接受調(diào)整量的航班數(shù)量作為目標(biāo)函數(shù)之一，定量分析時(shí)刻表的可接受性，作為航空公司對(duì)航班時(shí)刻優(yōu)化結(jié)果滿(mǎn)意程度的度量；航班時(shí)刻優(yōu)化的功效性則用航班調(diào)整總量來(lái)表示，從而構(gòu)建以配置效率和可接受度為雙目標(biāo)的優(yōu)化模型，研究二者之間的關(guān)系，力圖從根源上減少航空公司取消或不執(zhí)行分配的航班時(shí)刻的情況，增加繁忙機(jī)場(chǎng)稀缺容量資源的利用率和航班執(zhí)行率.

假設(shè)六個(gè)航班r1～r6必須配置在時(shí)間片1～15，r1～r3申請(qǐng)的時(shí)間片為7，r4-r6申請(qǐng)的時(shí)間片為10，每個(gè)航班的可接受調(diào)整量為±2個(gè)時(shí)間片，容量約束是每三個(gè)時(shí)間片二個(gè)航班，暫不考慮周轉(zhuǎn)時(shí)間限制.

表2為僅優(yōu)化航班調(diào)整總量的情況.灰色陰影表示航空公司申請(qǐng)的時(shí)間片，而優(yōu)化后分配的時(shí)間片用“#”表示.表3為考慮優(yōu)化航班調(diào)整總量和超過(guò)可接受調(diào)整量的航班數(shù)量的情況.由表2～3可知，為將超過(guò)可接受調(diào)整量的航班數(shù)量減少一個(gè)，航班調(diào)整總量將增加一個(gè)時(shí)間片.即由于航班r6向左移動(dòng)一個(gè)時(shí)間片，需要將航班r1和r4分別向左移動(dòng)一個(gè)時(shí)間片，以滿(mǎn)足容量限制.

如果減少超過(guò)可接受調(diào)整量的航班數(shù)量，則所有航班的調(diào)整量將更均勻地分布，航班調(diào)整總量可能增加，即二者是互相矛盾的優(yōu)化目標(biāo)，因此需要尋找適當(dāng)?shù)哪Ｐ秃退惴▉?lái)探究二者之間的權(quán)衡關(guān)系.

表2 優(yōu)化航班調(diào)整總量

表3 優(yōu)化航班調(diào)整總量和超過(guò)可接受調(diào)整量的航班數(shù)量

2 航班時(shí)刻優(yōu)化模型

2.1 參量定義

決策變量：

式中：r∈R,t∈T.

附加變量：

式中：r∈R.

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

1) 通過(guò)最小化航班調(diào)整總量實(shí)現(xiàn)要求配置達(dá)到整體最優(yōu)性的功效性目標(biāo).

(1)

2) 通過(guò)最小化超過(guò)可接受調(diào)整量的航班數(shù)量實(shí)現(xiàn)要求航空公司對(duì)優(yōu)化結(jié)果滿(mǎn)意的可接受性目標(biāo).

(2)

2.3 約束條件

1) 每個(gè)航班只能分配一個(gè)時(shí)間片.

(3)

2) 滾動(dòng)進(jìn)場(chǎng)/離場(chǎng)/總?cè)萘考s束.

(4)

(5)

(6)

式中：Δt∈{1,3,12}，Ts={t∈T|s≤t≤s+Δt}，s∈[0,n-Δt+1).

在模型中若只對(duì)機(jī)場(chǎng)小時(shí)容量進(jìn)行限制，會(huì)導(dǎo)致某些時(shí)段的時(shí)間片航班過(guò)于密集.為了讓模型更精細(xì)化，本文將分別對(duì)時(shí)間區(qū)間長(zhǎng)度為5，15和 60 min的進(jìn)場(chǎng)、離場(chǎng)和總?cè)萘窟M(jìn)行限制.此外，由于滾動(dòng)小時(shí)容量約束是對(duì)每個(gè)開(kāi)始于前一個(gè)約束5 min之后的小時(shí)容量進(jìn)行限制，從而滾動(dòng)遍及整個(gè)優(yōu)化時(shí)間段，因此相比于常見(jiàn)的以自然小時(shí)劃分的容量約束，它可以確保容量飽和的情況在一天內(nèi)不會(huì)持續(xù)很長(zhǎng)時(shí)間，從而允許在運(yùn)行高峰期間進(jìn)行系統(tǒng)恢復(fù).

3) 聯(lián)程航班的最小過(guò)站時(shí)間約束.

(ra,rd)∈P，k∈[tad,n)

(7)

以下約束用于定義超過(guò)可接受調(diào)整量的航班數(shù)量(yr).

4) 統(tǒng)計(jì)分配給航班r的時(shí)間片超過(guò)可接受航班調(diào)整量的情況.

如果分配的時(shí)間片小于下限τr-qr，則yr=1.

(8)

如果分配的時(shí)間片大于上限τr+qr，則yr=1.

(9)

5) 統(tǒng)計(jì)分配給航班r的時(shí)間片未超過(guò)可接受航班調(diào)整量的情況.

如果分配的時(shí)間片小于上限τr+qr，則wr=0.

(10)

如果分配的時(shí)間片大于下限τr-qr，則vr=0.

(11)

6) 用wr和vr定義yr，如果分配的時(shí)間片未超過(guò)上下限，則yr=0，即分配的時(shí)間片位于可接受范圍內(nèi).反之，如果wr或vr中的一個(gè)值為1，則航班r被定義為超過(guò)可接受調(diào)整量的航班.

yr≤wr+vr，r∈R

(12)

3 基于ε-約束法和改進(jìn)粒子群算法的模型求解

3.1 基于ε-約束法的優(yōu)化模型

根據(jù)上述目標(biāo)函數(shù)及約束條件，航班時(shí)刻優(yōu)化配置模型為

s.t.

Ts={t∈T|s≤t≤s+Δt},

s∈[0,n-Δt+1)

Ts={t∈T|s≤t≤s+Δt},

s∈[0,n-Δt+1)

Ts={t∈T|s≤t≤s+Δt},

s∈[0,n-Δt+1)

(ra,rd)∈P,k∈[tad,n)

yr≤wr+vr,r∈R

(13)

采用近似有效邊界方法之一的ε-約束法來(lái)求解這個(gè)雙目標(biāo)0-1整數(shù)規(guī)劃問(wèn)題.與其他方法相比，ε-約束法能在無(wú)需額外參數(shù)的情況下高效得到Pareto解集，其原理是依次對(duì)多目標(biāo)問(wèn)題的每個(gè)目標(biāo)進(jìn)行求解，將求出的最優(yōu)解作為約束條件增加在原模型中，其模型為

minfh(X)

(14)

fi(X)≤εi，1≤i≤k，i≠h

(15)

X∈Xf

(16)

式中：fi(X)為第i個(gè)目標(biāo)函數(shù)；εi為第i個(gè)目標(biāo)函數(shù)fi(X)的上界.

因此，根據(jù)ε-約束法將雙目標(biāo)航班時(shí)刻優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題，步驟如下.

步驟1利用目標(biāo)函數(shù)(1)和約束(3)～(12)，建立模型1并求解，其最優(yōu)解為航班調(diào)整總量的最小值(z1)min.

步驟2利用目標(biāo)函數(shù)(2)和約束(3)～(12)，建立模型2并求解，其最優(yōu)解為超過(guò)可接受調(diào)整量的航班數(shù)量的最小值(z2)min.

步驟3利用目標(biāo)函數(shù)(1)和約束(3)～(12)加上(17)，建立具有新參數(shù)ε的模型3，約束(17)如下所示.

(17)

式中：ε從模型2中確定的(z2)min開(kāi)始，每次增加一個(gè)單位，迭代求解一系列z1值，直到其等于(z1)min為止該方法的優(yōu)點(diǎn)在于可以得到兩個(gè)目標(biāo)函數(shù)尋優(yōu)過(guò)程中的一系列數(shù)值，從而便于比較兩個(gè)目標(biāo)函數(shù)在不同可接受調(diào)整量水平下的所有可能值的變化趨勢(shì).

3.2 改進(jìn)粒子群算法

粒子群算法收斂快，具有很強(qiáng)的通用性，但同時(shí)存在容易早熟收斂、后期迭代效率不高等缺點(diǎn).而本文采用的改進(jìn)粒子群算法，借鑒遺傳算法中的變異思想，引入變異操作，從而拓展在迭代中不斷縮小的種群搜索空間，使粒子跳出先前搜索到的最優(yōu)值位置，從而提高找到更優(yōu)值的可能性.算法流程見(jiàn)圖1.

圖1 航班時(shí)刻優(yōu)化算法流程圖

4 模型應(yīng)用和結(jié)果

選取南京祿口國(guó)際機(jī)場(chǎng)2017-08-18的航班時(shí)刻，期間共起降航班621架次.應(yīng)用matlab7.0軟件編寫(xiě)并運(yùn)用上述ε-約束法和改進(jìn)粒子群算法，取N為100，kmax為300，c1、c2取2.0，pm取0.1，慣性權(quán)重區(qū)間[0.4,0.9]，粒子速度區(qū)間[-5,5].其中容量分別為38架次/h，10架次/15 min，4架次/5 min，聯(lián)程航班的最小過(guò)站時(shí)間為60 min.為分析可接受調(diào)整量水平對(duì)優(yōu)化目標(biāo)的影響，分別取q的值為3，6，9，12對(duì)模型進(jìn)行求解.

圖2為不同可接受調(diào)整量水平對(duì)應(yīng)的航班調(diào)整總量z1和超過(guò)可接受調(diào)整量的航班數(shù)量z2的值.

圖2 不同可接受調(diào)整量水平對(duì)比圖

由圖2可知，這兩個(gè)優(yōu)化目標(biāo)之間的權(quán)衡關(guān)系.當(dāng)q=3時(shí)，z1增加9%(從369～333個(gè)時(shí)間片)使z2減少了30%(從57～40個(gè)).而當(dāng)q分別為6，9，12時(shí)，z1只需要增加不超過(guò)5%，z2就可以減少達(dá)到30%.即說(shuō)明通過(guò)航班調(diào)整總量非常小的犧牲，可以實(shí)現(xiàn)超過(guò)可接受調(diào)整量的航班數(shù)量的顯著優(yōu)化.而這個(gè)臨界點(diǎn)則可以為航空公司設(shè)定可接受調(diào)整量水平提供參考.此外，因?yàn)楹娇展旧暾?qǐng)的和最終配置的航班時(shí)刻之間的時(shí)間差明顯縮小，會(huì)激發(fā)他們研究并制定出更貼合實(shí)際需求的航班時(shí)刻.

另一方面，當(dāng)q=3時(shí)，z2減少35%(從57～37個(gè))使z1增加20%(從414～333個(gè)時(shí)間片).對(duì)于q為6、9的情況，z2減少35%會(huì)使z1分別僅提高不到6%、2%；而如果q為12，該值則不到1%.這說(shuō)明z1隨z2的減小而增加的變化率隨著q的逐漸增加而減小.由此可以推論出，航空公司對(duì)可接受調(diào)整量水平的閾值越嚴(yán)格，由航班調(diào)整總量代表的成本就越高.這一發(fā)現(xiàn)可以提醒航空公司，如果虛占航班時(shí)刻或者通過(guò)其他行為變相提高可接受調(diào)整量水平，那么對(duì)于整個(gè)機(jī)場(chǎng)的所有用戶(hù)群而言，超過(guò)可接受調(diào)整量的航班數(shù)量和航班調(diào)整總量將會(huì)增加更多，最終損害的還是航空公司的利益.

此外，本文還選取了按照先來(lái)先服務(wù)(first come first serve, FCFS)原則以及當(dāng)q=6時(shí)模型1、模型2和模型3的最優(yōu)解對(duì)應(yīng)的航班時(shí)刻表，應(yīng)用Airtop仿真軟件對(duì)祿口機(jī)場(chǎng)的實(shí)際運(yùn)行情況構(gòu)建基準(zhǔn)仿真模型，仿真示意圖見(jiàn)圖3.

圖3 南京祿口機(jī)場(chǎng)終端區(qū)航班流仿真示意圖

輸出結(jié)果見(jiàn)表4.由表4可知，雙目標(biāo)優(yōu)化模型3可以兼顧功效性和可接受性準(zhǔn)則，而模型1、模型2則顧此失彼；與FCFS方法的仿真結(jié)果相比，雙目標(biāo)模型3的平均延誤時(shí)間減少了25%，放行正常率提高了11%.

表4 Airtop仿真結(jié)果

5 結(jié) 束 語(yǔ)

文中提出的航班時(shí)刻優(yōu)化配置策略，立足于可接受調(diào)整量水平，給出了考慮滾動(dòng)容量和過(guò)站時(shí)間約束的多目標(biāo)優(yōu)化模型，采用ε-約束法和改進(jìn)粒子群算法對(duì)模型進(jìn)行了求解分析，結(jié)果表明，通過(guò)少量甚至可以忽略不計(jì)的航班調(diào)整總量的犧牲，可以從整體上讓機(jī)場(chǎng)所有的航班時(shí)刻都更接近航空公司的需求；通過(guò)Airtop仿真驗(yàn)證了模型在實(shí)際運(yùn)行中將使機(jī)場(chǎng)平均延誤時(shí)間和放行正常率均得到優(yōu)化.

該模型可以為機(jī)場(chǎng)和管制部門(mén)優(yōu)化航班時(shí)刻提供決策支持，通過(guò)確定適當(dāng)?shù)目山邮芎桨嗾{(diào)整量水平，有利于提高機(jī)場(chǎng)現(xiàn)有資源利用率，也有利于激勵(lì)航空公司對(duì)航班時(shí)刻的高執(zhí)行率，從而緩解擁堵延誤，提高航班正常率.在未來(lái)研究中，將結(jié)合扇區(qū)、航路等空域結(jié)構(gòu)因素對(duì)區(qū)域航班時(shí)刻優(yōu)化問(wèn)題作進(jìn)一步探討.