劉禹汐,劉繼新,田 文

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

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

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

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

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

1 機(jī)場(chǎng)主用客運(yùn)機(jī)坪構(gòu)型運(yùn)行方案分析

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

圖1 天河機(jī)場(chǎng)整體布局

1.1 運(yùn)行安全原則

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

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

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

下面分別針對(duì)U型機(jī)坪和直線型機(jī)坪的運(yùn)行模式進(jìn)行分析.

1.2 U型機(jī)坪“雙通道”運(yùn)行模式

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

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

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

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

圖3 U型區(qū)航班運(yùn)行進(jìn)港方式

1.3 直線型機(jī)坪運(yùn)行模式

天河機(jī)場(chǎng)直線型機(jī)坪的運(yùn)行模式相對(duì)來說比較單一,只規(guī)定了相鄰機(jī)位的航空器禁止同時(shí)活動(dòng).

1.4 區(qū)域機(jī)位組合

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

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

2.1 符號(hào)說明

見表1.

表1 模型符號(hào)說明

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

從協(xié)同機(jī)場(chǎng)、旅客、航司三方利益和提升機(jī)坪運(yùn)行效率及運(yùn)行安全的角度出發(fā),建立機(jī)場(chǎng)指標(biāo)、旅客指標(biāo)、安全指標(biāo)等度量停機(jī)位綜合效能,構(gòu)建以下多目標(biāo)停機(jī)位分配協(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)停機(jī)位協(xié)同分配仿真驗(yàn)證

3.1 算法設(shè)計(jì)

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

1)個(gè)體編碼

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

2)快速非支配排序

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

3)適應(yīng)度評(píng)價(jià)

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

4)進(jìn)化操作

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

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

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

5)精英策略

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

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

3.2 實(shí)例驗(yàn)證

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

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

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

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

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

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

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

圖7 停機(jī)位分配甘特圖

4 結(jié) 語

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