劉 暢, 郝 路, 高 峰, 許 幸, 張文成, 石麗娜

(上海工程技術(shù)大學(xué) 航空運輸學(xué)院, 上海201620)

0 引 言

空中交通機場管理協(xié)同決策機制已經(jīng)成為提高我國空中交通機場管理網(wǎng)絡(luò)和機場運行管理效率的重要因素。 截至2019 年,空中交通機場吞吐量排名前列的機場包括：北京首都國際機場、上海浦東國際機場、廣州白云機場。 旅客起降吞吐量高達1 億100 萬人次,標(biāo)志著我國的民航業(yè)快速發(fā)展的同時,也給空中交通的指揮運營和現(xiàn)有系統(tǒng)資源綜合調(diào)度帶來了巨大的機遇和挑戰(zhàn)。 合理的停機位設(shè)置和分配能夠有效提高機場的容量、降低航班延誤率、減少事故的發(fā)生,是影響民航機場的系統(tǒng)容量和機場服務(wù)運行效率的一個關(guān)鍵因素。

1 機場協(xié)同決策機制

在機場多航站樓停機位模型與實時指派的算法問題上,國內(nèi)外的學(xué)者已經(jīng)對機場進行了很多模型與實時指派算法的分析與研究［1-9］。 機場協(xié)同支持決策機制是歐洲民航會議機場運輸部長在2000 年歐洲民航會議空中交通管理戰(zhàn)略中提出的新決策概念之一［10］。 各機場協(xié)同決策是以減少航班延誤率、提高正點率、優(yōu)化機場資源配置和利用為主要目的,提高一定機場范圍內(nèi)的空中交通流管理能力和機場總?cè)萘俊?各機場通過協(xié)同決策,使各機場參與者(包括機場運營經(jīng)理、飛機運營商、地勤人員和空中交通管制員)了解其他機場參與者的局限性、現(xiàn)狀和預(yù)期狀態(tài),做出正確的空中交通決策,并與其他機場參與者合作。 為了確保機場繼續(xù)做出高質(zhì)量的決策,所有機場參與者都應(yīng)正確設(shè)定共同目標(biāo)［11］。 機場的目標(biāo)是在完成運營計劃的同時最大限度地提高吞吐量和效率。 地面服務(wù)的目標(biāo)是最大限度地提高資源管理效率,并簽署協(xié)議以確保機場的服務(wù)質(zhì)量水平［11］。 現(xiàn)有機場設(shè)施的最佳合理利用,取決于進出機場的航班預(yù)測的準(zhǔn)確性。 空中交通管制的主要目標(biāo)之一是確保安全,并實現(xiàn)現(xiàn)有基本機場設(shè)施(跑道和滑行道)的最佳合理利用。 為保證機場設(shè)施評價指標(biāo)的正確實施和效果,引入機場設(shè)施性能評價方法,對現(xiàn)有機場設(shè)施的安全性和完整性進行評價。

2 停機位分配問題概述

停機位分配問題是指綜合考慮機場運行的規(guī)則、飛機的機型、停機位的類型、航班時刻等各種影響因素,為機場入港和離港的國際航班分配合適的跑道和停機位。 機位自動分配管理是機場信息運行管理系統(tǒng)的一個重要組成部分,機位自動分配的準(zhǔn)確性直接影響到整個機場的實際運行管理效率和旅客服務(wù)滿意度。 國內(nèi)機場信息運行管理系統(tǒng)對于停機位的分配做不到全自動,只發(fā)展到半自動化程度,即先自動給出機位分配的方案,再用自動或者人工的程序進行分配和處理,對不恰當(dāng)?shù)姆峙溥M行更改,經(jīng)常造成部分航班無機位可分配,或分配到遠機位,采用擺渡車等方式對旅客進行接送,影響了旅客滿意度,還會造成資源的浪費和額外費用的增加。

許多文獻都在討論使用哪種算法或混合算法來減少模型的運行時間,提高效率。 其次是注重模型的仿真。 在獲得仿真的基礎(chǔ)數(shù)據(jù)后,建立了各種仿真系統(tǒng),利用先進的仿真技術(shù)對多跑道機場的停車位分配算法進行實時分析和仿真,有效地解決多跑道機場停機位分配的沖突和控制問題展臺上的飛機。 同時,提出了基于規(guī)則和網(wǎng)絡(luò)仿真技術(shù)的AGAP 仿真分配模型和Yan s 的仿真模型［12］。 停機位模擬分配模型結(jié)合了兩種相似的最小總乘客、機場步行距離和啟發(fā)式基本分配算法。

研究優(yōu)化模型,應(yīng)用最為廣泛的當(dāng)屬以最小機位旅客行走的距離和等待的時間為主要優(yōu)化的目標(biāo)。 將國際機場最小化遠機位數(shù)的利用率問題作為主要的考慮目標(biāo)對象時,主要應(yīng)用是以旅客利益最小化機位旅客空閑的時間和旅客最小化遠機位數(shù)的利用率做為主要優(yōu)化的目標(biāo)。 越來越多的學(xué)者開始注重在優(yōu)化算法上的突破和創(chuàng)新,對優(yōu)化方法和目標(biāo)的選擇上往往傾向于選擇單一的優(yōu)化方法和目標(biāo)。 在實際的機場停機位分配問題中,優(yōu)化的目標(biāo)應(yīng)該都是多目標(biāo)的,若只以旅客最小行走的距離作為其優(yōu)化的目標(biāo),往往會造成部分虛擬停機位相對繁忙,而其他虛擬停機位相對空閑；若只考慮其他機位相對空閑的時間,又往往會導(dǎo)致部分旅客對航班滿意度的明顯下降。

3 停機位分配問題模型

停機位優(yōu)化配置的基本目標(biāo)之一,是將給定的虛擬航班合理分配到多個不同的虛擬停機位,使航班之間不發(fā)生任何沖突,旅客從機場步行的時間和距離最短［12-13］。 由于飛機進出口到其他虛擬停機坪的時間和距離遠大于其他虛擬機位的時間和距離,應(yīng)合理分配進出口到其他機位的航班。 所有虛擬機位在分配后只能同時為機場分配一架虛擬機(其他虛擬機坪分配除外)。 由于不同的機位分配問題可以直接劃分為若干個相同的虛擬機位分配問題,本文假設(shè)所有可供機場使用的虛擬機位和飛機分配所需的虛擬機位是相同的,提出一個虛擬機位分配問題的數(shù)學(xué)模型［14-15］。

該模型定義了如下變量：

N 為飛機(到達或離開) 集合；

M 為機場可用的機位數(shù)目；

n 為飛機的總數(shù)目；

m 為機位的總數(shù)；

Ai為飛機i 的到達時間；

di為飛機i 的離開時間；

Wkj為旅客從機位k 到機位j 的距離；

fij為從航班i 到j(luò) 的旅客人數(shù)；

gi為飛機i 分配到的機位.

加入兩個虛擬停機位：

0 為機場的入口或出口；

m ＋1 為無機位可用時飛機分配到停機坪；

Yik= 1 為航班i 分配到入口k,否則為0?(i.j)yik= yik= 1(k ≠m ＋1),

當(dāng)且僅當(dāng)(ai- dj)*(ai- di) ＜0.

優(yōu)化目標(biāo)公式(1)：

④yik∈｛0,1｝(?i,1 ≤i ≤n,?k,1 ≤k ≤m ＋1).

4 機場停機位分配遺傳算法設(shè)計

遺傳算法從發(fā)現(xiàn)問題開始到結(jié)束都需要非常繁瑣的過程,因此需要對算法過程進行詳細的梳理。遺傳算法主要包括以下基本步驟：

(1) 根據(jù)實際問題,確定染色體優(yōu)化的方法,即目標(biāo)函數(shù)及其約束條件、解的數(shù)學(xué)描述。

(2) 根據(jù)該問題,建立了染色體優(yōu)化模型,即啟動時間的目標(biāo)函數(shù)及其約束條件的數(shù)學(xué)描述。

(3) 分別給出每個染色體的基因型和編碼方法,即分別給出個體基因型和染色體搜索空間。

(4) 建立染色體解碼方法,實現(xiàn)基因型與表現(xiàn)型的轉(zhuǎn)化。

(5) 給出了個體目標(biāo)適應(yīng)度的函數(shù)值評價和計算方法,建立了目標(biāo)適應(yīng)度函數(shù)值與目標(biāo)個體適應(yīng)度的函數(shù)值轉(zhuǎn)換和計算關(guān)系。

(6) 給出了遺傳算子的具體操作過程和方法,包括基因選擇、交叉、變異等各種遺傳算子的詳細操作過程。

(7) 給出了遺傳算法過程中的停機位和運行參數(shù)。

本文提出了一種基于遺傳算法的航班機位長度分配編碼算法。 為避免增加機位,采用實數(shù)編碼方法。 為了簡化討論,一個機場設(shè)3 個機位,只需分配10 個機位。 簡化描述假設(shè)所有航班1,分配到1 號、3 號、4 號、5 號,分配到1 號、6 號、7 號、8 號,分配到2 號和3 號,以及9 號、10 號,分配到航班和停機坪,基因組站的編碼方法如下：

4.1 適應(yīng)度函數(shù)設(shè)計

直接選取目標(biāo)函數(shù)作為適應(yīng)度函數(shù),不同的目標(biāo)函數(shù)值相差不大,會導(dǎo)致適應(yīng)度算法收斂速度慢,影響計算時間。 因此,本文引入了模擬退火的思想,設(shè)計的適應(yīng)度函數(shù)公式(2)為：

value 表示的是一個目標(biāo)適應(yīng)度函數(shù)的值,N 調(diào)整適應(yīng)度函數(shù)值的范圍,系數(shù)a 決定了算法復(fù)制的強迫性,A 越小,適應(yīng)值的強制函數(shù)微分越大。

4.2 交叉算子設(shè)計

在進化的不同階段,根據(jù)適應(yīng)度函數(shù)值的比例進行選擇。 在同一遺傳過程的早期進化階段,通常會出現(xiàn)一些超常量的初始個體。 這些個體由于具有突出的群體競爭力,嚴(yán)重地控制了算法選擇的速度和過程,影響了算法朝著全局最優(yōu)解的方向搜索。在種群遺傳進化的后期,由于種群算法適應(yīng)度的收斂性和種群中個體間的差異較小,使得全局優(yōu)化算法的持續(xù)性大大降低。

(1) 該算法處理了種群中數(shù)量隨速度變化的情況。 如果一條染色體中的停止碼數(shù)量減少或增加,從后一條染色體交叉點的停止到前一條染色體交叉點的停止,尋找一個包含0 個代碼的位置。 在某個地區(qū)有這樣的十字路口。 這個位置的停止碼為0,另一條染色體上的停止碼不為0,交換這個交叉位置的兩個亞染色體的停止碼的數(shù)目；如果停止碼的數(shù)目增加或減少,必須再次增加另一個亞染色體的停止碼的數(shù)目,并且這個亞染色體的停止碼可以被處理。 重復(fù)這一過程,直到亞染色體數(shù)目沒有及時改變。

(2) 處理同一立場中兩個染色體立場的沖突。從最后一個染色體交叉點的終點到前一個染色體交叉點的終點,搜索染色體,并將染色體飛行停止點所在的第一個子染色體的飛行替換為當(dāng)前未出現(xiàn)在子染色體支架上的最小第一個飛行,重復(fù)此過程進行排序,直到每個支架的飛行被分配到同一個支架上。

(3)解決同一亞色系航班在停站時間發(fā)生停站沖突時的停站編碼問題。 同時分配給每個次染色體架的航班根據(jù)每次進入次染色體架的時間長度進行排序,并根據(jù)時間約束條件③調(diào)整每個航班分配條件。 另一個不需要滿足約束條件的航班被隨機分配給一個停機坪,利用貪心算法對調(diào)整后的航班分配條件進行隨機優(yōu)化,使停機坪上每個航班的分配基因數(shù)最少。

4.3 變異算子

從飛行染色體中隨機選擇兩個分配基因進行選擇交換,將分配給每個飛行臺的所有飛行按進入該飛行臺一段時間的順序隨機排序,并根據(jù)滿足約束條件③調(diào)整每個系統(tǒng)的飛行臺,將不能滿足機位約束協(xié)同決策條件的機位分配給相應(yīng)的停機坪。 對上述算法設(shè)計過程進行了分析,結(jié)合機場協(xié)同決策模型系統(tǒng)中的停機位航班實時分配,確定了停機位航班分配的數(shù)據(jù)集,最后得到了機位航班的分配方案。

5 結(jié)束語

本文進一步研究了目前機場協(xié)同決策機制條件下,基于旅客最小停機位行走距離的基礎(chǔ),進行停機位航班實時分配,通過遺傳算法建立以旅客最小行走的距離為基礎(chǔ)進行優(yōu)化的目標(biāo),建立了機場協(xié)同約束條件下的停機位航班實時分配的模型,通過分析結(jié)合遺傳算法的特性以及目前機場協(xié)同決策機制在部分國際機場已經(jīng)實現(xiàn)的停機位信息資源共享的基礎(chǔ)上,對該協(xié)同決策模型的停機位進行了合理的遺傳算法結(jié)構(gòu)設(shè)計,充分考慮停機位航班實時的分配以及停機位航空公司對航班停機位利用效益的最大化,為進一步優(yōu)化部分停機位的資源配置,提高部分機場飛行場面的容量,降低停機位航班的延誤率和沖突發(fā)生次數(shù)及縮短航班延誤的時間奠定了基礎(chǔ)。 本文主要針對技術(shù)和模型的基礎(chǔ)建立進行研究,對該技術(shù)和模型的充分應(yīng)用以及可行性的研究,還有待進一步的研究和實例的驗證。 該技術(shù)和模型主要是考慮在一定的時間內(nèi),對于延誤航班的時隙進行優(yōu)化、對分配進行了考慮,停機位臨時指派的分配是一個復(fù)雜且實時的動態(tài)管理過程,可能受到空管、機場、航空公司以及機組等可控因素的控制和影響,還可能受到惡劣天氣等各種自然條件的影響和限制,對于延誤航班停機位的分配有待進一步的研究。