劉禹汐,劉繼新,田 文

(1. 南京航空航天大學(xué) 民航學(xué)院,南京 211106;2.國家空管飛行流量管理技術(shù)重點實驗室,南京211106)

近年來,民航業(yè)發(fā)展迅猛且取得了重大成效,但仍然存在關(guān)鍵資源不足,基礎(chǔ)設(shè)施保障能力面臨容量和效率雙瓶頸等問題.解決機位資源短缺問題通常對機場現(xiàn)有機位資源進行科學(xué)的預(yù)分配和實時調(diào)整,以提高機位資源的利用率、增強機場保障能力[1-2].

機位資源預(yù)分配階段會受到多種因素限制,停機位分配方案作為運控人員基于機場、航空公司以及旅客三方利益的決策載體,傳統(tǒng)的停機位預(yù)分配方法難以滿足現(xiàn)實需要的協(xié)同決策[3].而我國民航運輸運力主要分布在大型樞紐機場,航班流量較大,航司和旅客多樣化顯著,機坪運行態(tài)勢復(fù)雜,集中特點明顯,在機坪內(nèi)部產(chǎn)生的運行沖突較多.因此針對這種普遍存在的問題,如何在保證航空器運行安全和充分利用機位資源的條件下實現(xiàn)大型樞紐機場停機位分配的多目標(biāo)協(xié)同優(yōu)化已經(jīng)成為亟須解決的難題[4-5].

2010年,劉長有、翟乃鈞[6]在兼顧系統(tǒng)運行安全和效率方面進行了有效的初步探索,將航班推出沖突作為安全性約束,建立了可以避免推出沖突的多目標(biāo)停機位優(yōu)化模型.2011年,劉長有[7]等在模型中加入避免潛在推出沖突的約束條件,建立多目標(biāo)停機位分配模型,并采用遺傳算法進行求解.2013年,Kim[8]等人以最小化乘客的步行時間、最小化飛機的滑行時間和最小化機位沖突的持續(xù)時間為目標(biāo)建立了平衡三者的停機位優(yōu)化模型,結(jié)果表明此優(yōu)化方案在每個目標(biāo)上都優(yōu)于當(dāng)前的分配方案.2014年,Prem[9]等人首次將乘客連接收入、區(qū)域使用成本、停機位調(diào)度的魯棒性及其相關(guān)約束一起納入多目標(biāo)停機位指派模型中.2018年,徐思敏[10]等人為通過優(yōu)化停機位分配方案來實現(xiàn)綜合利益最大化,以航空公司運行成本、旅客步行距離、航班沖突概率綜合最小化以及航空公司公平性最大化為優(yōu)化目標(biāo),建立多目標(biāo)停機位分配模型,并用NSGA-II進行高效求解.2019年,高陽[11]運用“安全關(guān)口前移”的思想,以最小化航班沖突次數(shù)和最大化航班靠橋率作為優(yōu)化目標(biāo),設(shè)置同機位和相鄰機位的最小安全時間間隔作為約束條件,建立隨機擾動航班時刻下的停機位分配優(yōu)化模型,運用改進的全局人工蜂群算法進行求解.同年,馬思思[12]在建立滑行道和停機位聯(lián)合調(diào)度模型時,考慮了停機坪推出、進位約束,對機位之間避免沖突發(fā)生要保持的最小安全時間間隔進行較為具體的計算,將其代入約束中.2022年,李龍海[13]等人建立雙層規(guī)劃模型,以最大化機場運行效率作為上層模型的優(yōu)化目標(biāo),以同一停機位相鄰航班推出沖突時間最少作為下層模型的優(yōu)化目標(biāo),利用遺傳算法進行求解,降低停機位運行風(fēng)險.

從以上研究可以看出,在研究以航空器運行安全為重點的多目標(biāo)停機位分配問題時,大部分學(xué)者僅僅對同一停機位、或相鄰?fù)C位之間的航班設(shè)置避免推出沖突的約束,少部分學(xué)者將最小化航班沖突作為優(yōu)化目標(biāo),但是這兩種方法都沒有考慮機坪的實際運行規(guī)則,只針對相同或相鄰機位航空器的推出進位進行限制,缺乏實際意義,得到的分配方案會增加運控人員實時分配停機位的工作負(fù)荷.目前,我國大中型機場廣泛使用多指廊式的停機坪構(gòu)型,港灣U型區(qū)數(shù)量較多.對于此類復(fù)雜機坪,通過停機位分配來保障運行安全的難點在于剖析航空器在港灣U型區(qū)域里的運行.U型區(qū)指的是兩條平行指廊之間的停機坪以及滑行通道等站坪區(qū)域,其中的航空器自行滑入機位,借助牽引車頂推出位,并采用機頭向內(nèi)的方式停放.港灣U型區(qū)域一直是機坪盲區(qū)的聚焦點,其空間有限,停機位密集,運行模式較復(fù)雜,容易產(chǎn)生運行沖突,航空器與航空器、航空器與其他保障車輛等很容易發(fā)生刮蹭相撞的事故.因此為協(xié)同機場、旅客、航司三方的利益,兼顧機坪運行效率和運行安全,本文以武漢天河國際機場(以下簡稱“天河機場”)作為大型樞紐機場的典型案例,首先針對機場中主用客運機坪構(gòu)型的運行方案進行分析,然后以最小化?？吭谶h(yuǎn)機位的航班數(shù)量(即最大化飛機靠橋率)、最小化旅客步行距離以及最小化同機位航班沖突值作為目標(biāo)函數(shù),綜合考慮復(fù)雜機坪的運行模式、航班對應(yīng)運營區(qū)域的限制等符合實際情況的約束,建立多目標(biāo)停機位分配協(xié)同優(yōu)化模型,并采用適合該問題的多目標(biāo)遺傳算法——帶精英策略的非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm-Ⅱ, NSGA-Ⅱ)對模型進行有效求解,最后結(jié)合天河機場的數(shù)據(jù)進行實例驗證.

1 機場主用客運機坪構(gòu)型運行方案分析

航站樓構(gòu)型是制約機坪機位布局的關(guān)鍵因素.大型樞紐機場一般建有多座構(gòu)型不同的航站樓,使得連接的機坪區(qū)域的空間結(jié)構(gòu)和機位布局方式具有多樣性,由此導(dǎo)致不同構(gòu)型機坪下航空器的運行方案具有較大差異性.本文以天河機場為例進行不同構(gòu)型機坪的運行方案分析.天河機場主用客運機坪構(gòu)型如圖1所示,包含5個港灣U型區(qū)域、1個港灣半U型區(qū)域以及1個直線型區(qū)域,其中港灣U型區(qū)域占天河機場客運主用保障機位的70%.

圖1 天河機場整體布局

1.1 運行安全原則

1)在機坪內(nèi)滑行道滑行時航空器前后機必須滿足航空器地面滑行縱向間隔;

2)在機坪內(nèi)滑行道滑行時航空器之間必須滿足航空器地面滑行側(cè)向間隔;

3)航空器在U型區(qū)內(nèi)運行時,必須滿足相應(yīng)機型開車時的尾流安全間隔.

下面分別針對U型機坪和直線型機坪的運行模式進行分析.

1.2 U型機坪“雙通道”運行模式

本模式下,根據(jù)民航規(guī)定航空器運行的相關(guān)間隔,將每個U型機坪分為“外”、“中”、“內(nèi)”三個分區(qū),U型區(qū)內(nèi)兩條滑行道看作一條滑行道使用,進離港航班均不允許與另一架U型區(qū)內(nèi)航空器側(cè)向交錯滑行,以此確保航空器運行時滿足各項安全間隔規(guī)定.圖2為在雙通道分區(qū)運行模式下,U型區(qū)的航班運行離港方式示意圖.

圖2 U型區(qū)航班運行離港方式

此方案中U型區(qū)內(nèi)部頂端機位離港航空器直線向后推出,停止時姿態(tài)垂直于區(qū)域內(nèi)滑行道.除U型區(qū)內(nèi)其余機位離港航班就近推出至區(qū)域內(nèi)滑行道,停止時姿態(tài)平行于U型區(qū)內(nèi)滑行道機頭朝港灣口方向.圖2(A)表示每次只能在外區(qū)和內(nèi)區(qū)各推出一架航空器,中區(qū)如有正在推出開車的航空器則內(nèi)區(qū)、外區(qū)所處航空器不得推開.內(nèi)區(qū)航空器推出到達指定位置后,兩架航空器均可開車;圖2(B)表示優(yōu)先將中區(qū)的航空器推入內(nèi)區(qū)后外區(qū)航空器才可推出,兩架航空器均到達指定位置后方可開車.圖2(C)表示優(yōu)先將中區(qū)的推出的航空器拉入外區(qū)再推出內(nèi)區(qū)航空器,兩架航空器均到達指定位置后方可同時開車.

圖3為在雙通道分區(qū)運行模式下,U型區(qū)的航班運行進港方式示意圖.當(dāng)U型區(qū)內(nèi)有航班正在開車,開車航空器區(qū)域往港灣口的相鄰區(qū)域機位可以正常入位,進港航班機位不得與區(qū)域內(nèi)正在運行的離港航班機位相鄰.圖3(A)表示當(dāng)中區(qū)航班開時外區(qū)機位可以入位;圖3(B)表示當(dāng)內(nèi)區(qū)航班開時中區(qū)、外區(qū)所有機位可以正常入位.而外區(qū)推開時停外區(qū)的進港航班需在港灣區(qū)域外的主滑上等待,待外區(qū)沒有正在活動的航空器后方可入位.

圖3 U型區(qū)航班運行進港方式

1.3 直線型機坪運行模式

天河機場直線型機坪的運行模式相對來說比較單一,只規(guī)定了相鄰機位的航空器禁止同時活動.

1.4 區(qū)域機位組合

根據(jù)上述分析的大型樞紐機場中存在的典型機坪構(gòu)型和運行模式,本文提出“區(qū)域機位組合”的概念來表征不同機坪構(gòu)型下的航空器進離港運行模式.基于機坪構(gòu)型和機位、滑行通道的相對位置關(guān)系,將同一機坪區(qū)域內(nèi)具有相同進離港滑行路徑且受到規(guī)則限制彼此影響的若干機位視為一組,稱為“區(qū)域機位組合”.同一區(qū)域機位組合中的停機位之間不能同時推出/進入航班,不同區(qū)域機位組合中的停機位之間互相不受約束.

2 多目標(biāo)停機位分配協(xié)同優(yōu)化模型

2.1 符號說明

見表1.

表1 模型符號說明

2.2 數(shù)學(xué)模型

從協(xié)同機場、旅客、航司三方利益和提升機坪運行效率及運行安全的角度出發(fā),建立機場指標(biāo)、旅客指標(biāo)、安全指標(biāo)等度量停機位綜合效能,構(gòu)建以下多目標(biāo)停機位分配協(xié)同優(yōu)化模型.

(1)

(2)

(3)

(4)

?i∈F, ?j∈F, ?k∈G

(5)

(6)

(7)

(8)

G(Fa)?Ga

(9)

?i,j∈F,?k,l∈G

(10)

?i,j∈F,?k,l∈G

(11)

?i,j∈F,?k,l∈G

(12)

?i,j∈F,?k,l∈G

(13)

Yik∈{0,1}, 1≤i≤n, 1≤k≤m

(14)

φijk∈{0,1}, 1≤i

(15)

3 基于NSGA-II算法的多目標(biāo)停機位協(xié)同分配仿真驗證

3.1 算法設(shè)計

停機位分配問題是一種解空間的規(guī)模很大、會帶來“組合爆炸”的組合優(yōu)化問題,需要用啟發(fā)式算法解決.因此,本文采用帶精英策略的非支配排序遺傳算法(NSGA-II)[14-15]對模型進行求解,可以加快收斂速度,提高優(yōu)化結(jié)果的準(zhǔn)確度.

1)個體編碼

采用基于正整數(shù)編碼的策略:個體中的每一個基因位代表一個航班,個體編碼的總長度等于所有航班的數(shù)目總和加上目標(biāo)函數(shù)的個數(shù),前一段基因位上的數(shù)值代表此航班分配到的停機位序號,后一段基因位上的數(shù)值代表三個目標(biāo)函數(shù)的值.

2)快速非支配排序

通過循環(huán)比較,將所有不能被任何其他的解支配的個體挑出來,賦予其非支配等級為1,然后將這些個體從種群中排除,考慮剩下的所有不能被任何其他的解支配的個體,將它們的非支配等級設(shè)為2,……對這些個體重復(fù)上述操作,直至所有個體都被賦予非支配等級.

3)適應(yīng)度評價

利用種群個體的支配關(guān)系以及擁擠度的比較來評價個體的優(yōu)劣,種群中所處非支配層低的個體的適應(yīng)度好于所處非支配層高的個體.對于同一非支配層的個體,擁擠距離大的個體具有更優(yōu)的適應(yīng)度值.

4)進化操作

a)選擇:根據(jù)二進制錦標(biāo)賽法隨機從當(dāng)前種群中選擇兩個個體,保留非支配等級較高的個體,若二者等級相同,則保留擁擠度較大的個體,直到種群規(guī)模達到設(shè)置值.

b)交叉:采用雙點交叉方式,在個體編碼中隨機設(shè)置了兩個交叉點,然后進行交換交叉點之間的部分基因.

c)變異:采用均勻變異方式,分別用某一范圍內(nèi)均勻分布的隨機數(shù),以一個較小的概率來替換個體編碼串中各個基因座上原有的基因值.

5)精英策略

將父代個體與子代個體合并后進行非支配排序,擴大了生成下一代個體時的篩選范圍,達到保留優(yōu)秀個體淘汰劣等個體的目的.具體的NSGA-II算法流程圖如圖4所示.

圖4 NSGA-Ⅱ算法求解流程圖

3.2 實例驗證

以天河機場典型日全天的航班數(shù)據(jù)為例進行驗證分析,研究范圍內(nèi)共有可用停機位75個,其中包括遠(yuǎn)機位14個、近機位61個,航班對298個,將數(shù)據(jù)和具體運行規(guī)則的限制代入本文構(gòu)建的多目標(biāo)停機位協(xié)同分配優(yōu)化模型中,并采用NSGA-II算法對實例進行求解.在算法中,設(shè)置種群數(shù)量為100,迭代次數(shù)6 000次,交叉概率0.8,變異概率0.05.

迭代過程中三個目標(biāo)函數(shù)的變化曲線如圖5所示.由于數(shù)據(jù)較大、約束較多、模型復(fù)雜度較高,在迭代將近5 800次的時候目標(biāo)函數(shù)才趨于收斂.由三條曲線可知,隨著迭代次數(shù)的增加,所得到的Pareto最優(yōu)解對應(yīng)的目標(biāo)函數(shù)值逐漸減小,說明解的質(zhì)量在逐代提高.

圖5 目標(biāo)函數(shù)的迭代變化曲線

求解結(jié)果如圖6所示,圖6中有一組近乎均勻的Pareto最優(yōu)前沿,該前沿上有53個解,每個解都代表一種停機位分配方案,互相非支配.隨著同機位航班沖突值的減少,使用遠(yuǎn)機位的航班數(shù)量和旅客步行距離在逐漸增加,這說明優(yōu)化目標(biāo)(1)和(2)的變化趨勢是一致的,而目標(biāo)(3)與(1)、(2)是矛盾的.由于目標(biāo)函數(shù)是離散分布的,因此Pareto最優(yōu)前沿由幾個非連續(xù)的區(qū)域組成.

為驗證本文建立的模型和使用的算法對停機位分配方案優(yōu)化的有效性,在Pareto最優(yōu)前沿中分別取優(yōu)化目標(biāo)(1)和目標(biāo)(2)最優(yōu)、目標(biāo)(3)最優(yōu)以及兼顧三個目標(biāo)的3個方案,與人工分配的結(jié)果進行比較,如表2所示.

由表2可知,方案2的分配結(jié)果中使用遠(yuǎn)機位的航班數(shù)量為46,比方案1、方案3和方案4分別減少35.21%、16.36%和9.80%;方案2的旅客步行距離為50 542 523 m,比方案1、方案3和方案4分別減少7.54%、2.29%和1.04%.同理,方案3的分配結(jié)果中同機位航班沖突值為68.29,比方案1、方案2和方案4分別減少53.55%、43.44%和22.48%,在運行沖突方面方案3對于人工分配方案和另兩個分配目標(biāo)最優(yōu)的方案都有很大的改進;即便是對于使用遠(yuǎn)機位的航班數(shù)量和旅客步行距離這兩個優(yōu)化目標(biāo),方案3的結(jié)果也比方案1分別減少了22.54%和5.37%.而同時兼顧三個優(yōu)化目標(biāo)的方案4的分配結(jié)果相比于方案1,也有較大的提升.可見經(jīng)過NSGA-II算法優(yōu)化的結(jié)果總體遠(yuǎn)遠(yuǎn)好于人工指派的結(jié)果.

在對多目標(biāo)問題進行協(xié)同決策時,往往很難存在一個調(diào)度方案使得多個目標(biāo)同時最優(yōu),所以在現(xiàn)實中決策者需要根據(jù)實際情況選擇具體的調(diào)度方案.本文采用的方法對于機場工作人員有針對性地根據(jù)不同的側(cè)重點選擇符合機場實際運行情況的停機位分配方案提供了科學(xué)合理的依據(jù).圖7給出了同機位航班沖突值最小時的停機位分配方案,可以看出,在加入?yún)^(qū)域機位組合安全受限約束后,得到的停機位分配方案滿足機場的實際運行規(guī)則.

圖7 停機位分配甘特圖

4 結(jié) 語

針對我國大型樞紐機場廣泛使用的包含多個港灣U型區(qū)的停機坪構(gòu)型,將武漢天河國際機場作為典型實例,對U型機坪進離港航空器的運行方案進行重點分析,以最小化停靠在遠(yuǎn)機位的航班數(shù)量、最小化旅客步行距離以及最小化同機位航班沖突值作為目標(biāo)函數(shù),綜合考慮復(fù)雜機坪的運行模式、航班對應(yīng)運營區(qū)域的限制等符合實際情況的約束,建立一體化多目標(biāo)停機位分配協(xié)同優(yōu)化模型.本文采用NSGA-II算法求解模型,以NSGA-II算法為框架,將所有航班所分配的停機位集合設(shè)計為染色體,進行快速非支配排序、適應(yīng)度評價、進化操作等.以天河機場為實際背景,將典型日航班數(shù)據(jù)代入模型和算法進行求解.對結(jié)果的分析表明,所建立的多目標(biāo)模型能夠協(xié)同機場、旅客和航司三方的利益,兼顧機坪運行效率與安全,滿足實際約束.采用的算法能夠有效求解模型,得到相對均勻的Pareto 前沿,對于機場相關(guān)工作人員如何根據(jù)不同現(xiàn)實需要選擇平衡各目標(biāo)的停機位分配方案提供了極大的幫助.