基于機場協同決策機制下的停機位資源分配研究

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

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

0 引 言

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

1 機場協同決策機制

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

2 停機位分配問題概述

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

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

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

3 停機位分配問題模型

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

該模型定義了如下變量：

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

M 為機場可用的機位數目；

n 為飛機的總數目；

m 為機位的總數；

Ai為飛機i 的到達時間；

di為飛機i 的離開時間；

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

fij為從航班i 到j 的旅客人數；

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

加入兩個虛擬停機位：

0 為機場的入口或出口；

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

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

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

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

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

4 機場停機位分配遺傳算法設計

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

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

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

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

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

(5) 給出了個體目標適應度的函數值評價和計算方法,建立了目標適應度函數值與目標個體適應度的函數值轉換和計算關系。

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

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

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

4.1 適應度函數設計

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

value 表示的是一個目標適應度函數的值,N 調整適應度函數值的范圍,系數a 決定了算法復制的強迫性,A 越小,適應值的強制函數微分越大。

4.2 交叉算子設計

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

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

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

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

4.3 變異算子

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

5 結束語

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