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

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

0 引 言

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

1 機(jī)場(chǎng)協(xié)同決策機(jī)制

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

2 停機(jī)位分配問(wèn)題概述

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

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

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

3 停機(jī)位分配問(wèn)題模型

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

該模型定義了如下變量：

N 為飛機(jī)(到達(dá)或離開(kāi)) 集合；

M 為機(jī)場(chǎng)可用的機(jī)位數(shù)目；

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

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

Ai為飛機(jī)i 的到達(dá)時(shí)間；

di為飛機(jī)i 的離開(kāi)時(shí)間；

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

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

gi為飛機(jī)i 分配到的機(jī)位.

加入兩個(gè)虛擬停機(jī)位：

0 為機(jī)場(chǎng)的入口或出口；

m ＋1 為無(wú)機(jī)位可用時(shí)飛機(jī)分配到停機(jī)坪；

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 機(jī)場(chǎng)停機(jī)位分配遺傳算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

4.2 交叉算子設(shè)計(jì)

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

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

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

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

4.3 變異算子

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

5 結(jié)束語(yǔ)

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