汪夢蝶 胡明華 趙 征

(南京航空航天大學國家空管飛行流量管理技術(shù)重點實驗室 南京 210016)

0 引 言

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

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

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

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

表1 西南地區(qū)2011/2012年冬春季繁忙機場航班時刻監(jiān)管通報部分內(nèi)容

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

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

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

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

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

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

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

2.1 參量定義

決策變量：

式中：r∈R,t∈T.

附加變量：

式中：r∈R.

2.2 目標函數(shù)

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

(1)

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

(2)

2.3 約束條件

1) 每個航班只能分配一個時間片.

(3)

2) 滾動進場/離場/總?cè)萘考s束.

(4)

(5)

(6)

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

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

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

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

(7)

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

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

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

(8)

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

(9)

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

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

(10)

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

(11)

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

yr≤wr+vr，r∈R

(12)

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

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

根據(jù)上述目標函數(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)

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

minfh(X)

(14)

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

(15)

X∈Xf

(16)

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

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

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

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

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

(17)

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

3.2 改進粒子群算法

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

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

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

選取南京祿口國際機場2017-08-18的航班時刻，期間共起降航班621架次.應(yīng)用matlab7.0軟件編寫并運用上述ε-約束法和改進粒子群算法，取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)程航班的最小過站時間為60 min.為分析可接受調(diào)整量水平對優(yōu)化目標的影響，分別取q的值為3，6，9，12對模型進行求解.

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

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

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

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

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

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

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

表4 Airtop仿真結(jié)果

5 結(jié) 束 語

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

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