基于多目標(biāo)動(dòng)態(tài)規(guī)劃的多跑道進(jìn)港排序研究

幸小燕

摘 ?要：伴隨社會(huì)的全面發(fā)展，現(xiàn)代化的交通事業(yè)得到關(guān)注與發(fā)展，航空運(yùn)輸作為現(xiàn)代交通工具的典型代表，對(duì)促進(jìn)社會(huì)的發(fā)展起著重要的作用。伴隨航空運(yùn)輸行業(yè)的發(fā)展，航班出現(xiàn)晚點(diǎn)、延誤的情況越來(lái)越多，除去氣象等自然原因的影響，飛機(jī)進(jìn)港排序是影響航班正常運(yùn)行的關(guān)鍵因素。由于多跑道進(jìn)港排序是一項(xiàng)復(fù)雜的工程，所以現(xiàn)階段針對(duì)此問(wèn)題沒(méi)有形成長(zhǎng)效的解決方案。文章以多跑道進(jìn)港排序?yàn)檠芯恳暯?，以?shí)現(xiàn)多目標(biāo)動(dòng)態(tài)規(guī)劃為出發(fā)點(diǎn)炸開(kāi)討論，旨在為飛機(jī)進(jìn)港排序優(yōu)化升級(jí)提供意見(jiàn)。

關(guān)鍵詞：進(jìn)港排序;多跑道調(diào)度;多目標(biāo)優(yōu)化

前言

飛機(jī)進(jìn)港排序是提高終端機(jī)場(chǎng)吞吐量、減少能源消耗、減少航班延誤的有效措施，在優(yōu)化航班終端管理體制中發(fā)揮重要作用。面對(duì)越來(lái)越復(fù)雜、多元化的航空發(fā)展形式，國(guó)內(nèi)外專家學(xué)者對(duì)優(yōu)化進(jìn)港排序問(wèn)題的研究在逐步深入，呈現(xiàn)百家爭(zhēng)鳴的狀態(tài)，但是縱觀其結(jié)果，主要針對(duì)但跑道，單目標(biāo)進(jìn)行。隨著計(jì)算機(jī)技術(shù)的不斷發(fā)展，飛機(jī)進(jìn)港排序應(yīng)該實(shí)現(xiàn)質(zhì)的飛躍，實(shí)現(xiàn)多目標(biāo)動(dòng)態(tài)式的規(guī)劃模式。因此，作者針對(duì)“基于多目標(biāo)動(dòng)態(tài)規(guī)劃的多跑道進(jìn)港排序”具有現(xiàn)實(shí)意義，希望通過(guò)文章的闡述，能夠?yàn)楹娇者\(yùn)輸事業(yè)的發(fā)展注入新鮮血液。

1 問(wèn)題描述

由于各機(jī)場(chǎng)的具體狀況不同，所以無(wú)法全面涵蓋所有狀況進(jìn)行進(jìn)港排序的設(shè)計(jì)，作者現(xiàn)針對(duì)特定條件下進(jìn)行多目標(biāo)動(dòng)態(tài)規(guī)劃的多跑道進(jìn)港排序，現(xiàn)將各部分限定條件闡述如下：

1.1 飛機(jī)降落時(shí)間窗

機(jī)場(chǎng)終端服務(wù)區(qū)內(nèi)的飛機(jī)必須滿足一定的限定速度條件，那么根據(jù)飛機(jī)在機(jī)場(chǎng)各節(jié)點(diǎn)的飛行速度可以計(jì)算飛機(jī)最早的降落時(shí)間、最晚降落期限、預(yù)計(jì)降落時(shí)間等信息?，F(xiàn)令飛機(jī)降落時(shí)間參數(shù)為ETi;飛機(jī)最早的降落時(shí)間設(shè)定為L(zhǎng)Ti;飛機(jī)最晚的降落時(shí)間表示為ETAi;飛機(jī)的預(yù)計(jì)降落時(shí)間表示為STAi;根據(jù)上述設(shè)定條件，飛機(jī)的降落時(shí)間窗即為[ETi，LTi]。

1.2 FCFS序列

FCFS序列是建立在飛機(jī)最晚降落時(shí)間的基礎(chǔ)之上的一種具有一般性特征的系列，F(xiàn)CFS序列一般根據(jù)飛機(jī)的具體位置進(jìn)行命名，現(xiàn)規(guī)定以下涉及到的FCFS系列按照終端服務(wù)區(qū)最大吞吐量產(chǎn)生[1]。

1.3 最大位置平偏移

最大位置偏移量是指序列進(jìn)行成功優(yōu)化之后產(chǎn)生的FCFS序列中飛機(jī)位置的變化程度，設(shè)定優(yōu)化后的序列為A，最大位置偏移為k，那么會(huì)|Ai-i|≦k的結(jié)論。

1.4 降落時(shí)間間隔

同一跑道的兩架不同飛機(jī)實(shí)現(xiàn)先后降落，中間必須間隔一定的時(shí)間，而且時(shí)間間隔必須滿足特定的安全范圍，現(xiàn)規(guī)定以下方案設(shè)計(jì)中必須滿足國(guó)際航空組織對(duì)于不同類型飛機(jī)在統(tǒng)一跑道上實(shí)現(xiàn)降落的間隔時(shí)間標(biāo)準(zhǔn)。最小尾流間隔標(biāo)準(zhǔn)：重型飛機(jī)與重型飛機(jī)之間必須滿足尾流為94;重型飛機(jī)與中型飛機(jī)間隔尾流為114;重型飛機(jī)與輕型飛機(jī)尾流間隔為167。

1.5 平行跑道

作者限定研究的機(jī)場(chǎng)類型為平行跑道模式，是指飛機(jī)降落的跑道與跑道之間處于平行的狀態(tài)，而且能夠達(dá)到距離較近的要求。那么可以理解為飛機(jī)在到達(dá)兩條跑道需要的時(shí)間基本不會(huì)有太大差別，而且相鄰跑道上降落的飛機(jī)能夠保證安全的時(shí)間差。令雙跑道同時(shí)運(yùn)行過(guò)程中的安全時(shí)間間隔為40秒。

1.6 優(yōu)化目標(biāo)

飛機(jī)進(jìn)港排序進(jìn)行優(yōu)化升級(jí)的總體目標(biāo)是一致的，都是為實(shí)現(xiàn)吞吐量達(dá)到最大化、飛機(jī)延誤時(shí)間降到最低、消耗的燃料成本盡可能減少。作者進(jìn)行的設(shè)計(jì)方案規(guī)定進(jìn)港飛機(jī)均可以早于最晚降落時(shí)間實(shí)現(xiàn)降落，用公式可以描述為：

ETi

那么此時(shí)吞吐量最大化可以表示為：

maxf1=n/（STAAn-t0）

上述公式中，STAAn表示最晚實(shí)現(xiàn)降落的飛機(jī)降落時(shí)間;t0表示規(guī)定的調(diào)度時(shí)間，如果t0的值是0，那么實(shí)現(xiàn)吞吐量最大的方式是保證最后降落飛機(jī)的降落時(shí)間最小化[2]。

降落消耗最小化的公式：

Minf2=c（STA）

上述公式中，ci（STAi）表示第i各飛機(jī)實(shí)現(xiàn)降落過(guò)程中的多余消耗部分;額外消耗部分會(huì)根據(jù)不同類型的飛機(jī)發(fā)生變化，現(xiàn)規(guī)定ci（STAi）=|STAi-ETAi|。

1.7 結(jié)果權(quán)重

在進(jìn)行多目標(biāo)動(dòng)態(tài)規(guī)劃進(jìn)港排序優(yōu)化的過(guò)程中，根據(jù)優(yōu)化目標(biāo)往往能夠產(chǎn)生多個(gè)Pareto個(gè)優(yōu)化結(jié)論。作者現(xiàn)設(shè)定結(jié)果權(quán)重為：首先要求對(duì)Pareto曲線上的多個(gè)節(jié)點(diǎn)進(jìn)行統(tǒng)一化的處理;然后抽取Pareto曲線上凸出優(yōu)化點(diǎn);最后以抽取的凸點(diǎn)與其相鄰的兩個(gè)凸點(diǎn)進(jìn)行連線并取其平均值。

1.8 離港排序

在進(jìn)行飛機(jī)進(jìn)港排序設(shè)計(jì)的同時(shí)，需要對(duì)機(jī)場(chǎng)離港飛機(jī)進(jìn)行有效考慮，文章中將離港飛機(jī)的花費(fèi)與進(jìn)港飛機(jī)的花費(fèi)按照同一時(shí)段同一跑道狀況下相同予以考慮。

2 優(yōu)化策略

2.1 CPS動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃算法主要由兩類方式實(shí)現(xiàn)：一是深度優(yōu)先搜索，主要是通過(guò)對(duì)每條路徑進(jìn)行不同的規(guī)劃，然后因公剪枝等手法尋求最優(yōu)解決途徑的搜索方式;而是寬度有限搜索方式，是指按照不同路徑的具體特征進(jìn)行逐步深入式的搜索方式。在進(jìn)港排序優(yōu)化設(shè)計(jì)中，由于不盡相同的路徑之間存在一定的交叉節(jié)點(diǎn)，所以，深度有限搜索在運(yùn)用過(guò)程中將產(chǎn)生諸多重復(fù)性的工作。因此，規(guī)劃方法的選擇上應(yīng)該運(yùn)用寬度有限搜索的方式[3]。

2.2 優(yōu)化CPS動(dòng)態(tài)規(guī)劃算法

為達(dá)到多跑道動(dòng)態(tài)的進(jìn)港排序，遞推過(guò)程中的各個(gè)層級(jí)結(jié)點(diǎn)上飛機(jī)數(shù)量應(yīng)該降到最低限度，能夠達(dá)到掌握有效信息的目的視為成功。在進(jìn)行進(jìn)港排序的過(guò)程中，已經(jīng)實(shí)現(xiàn)降落的飛機(jī)和具體跑道上最后需要降落的飛機(jī)類型是其關(guān)鍵因素，所以應(yīng)該在飛機(jī)節(jié)點(diǎn)后面標(biāo)注沒(méi)條跑道最后一架飛機(jī)的類型信息。針對(duì)飛機(jī)的飛機(jī)的降落時(shí)間信息，應(yīng)該在以往r維矩陣進(jìn)行有效有效的優(yōu)化和升級(jí)，將以往的r維時(shí)間矩陣進(jìn)行離散化處理，讓其功能更加全面，進(jìn)而有效的提高運(yùn)算的速度和準(zhǔn)確率。

2.3 貪心策略

在進(jìn)行算法優(yōu)化的過(guò)程中，需要融入一定的貪心操作。在優(yōu)化的CPS動(dòng)態(tài)規(guī)劃算法中，遞推矩陣已經(jīng)實(shí)現(xiàn)了三元組化，有利于進(jìn)行三元組的選擇工作，為貪心操作提供了可能性。融入貪心策略的總體指導(dǎo)思想是將每一個(gè)f|m||s||type1||type2|下設(shè)的某個(gè)三元組進(jìn)行分析和優(yōu)化，產(chǎn)生一種側(cè)重于未排序飛機(jī)的最優(yōu)化狀態(tài)。如果通過(guò)一定的運(yùn)算程序已經(jīng)判定了一個(gè)或者一類三元組屬于等同狀態(tài)，那么可以將其進(jìn)行處理之后進(jìn)行刪除，有效的節(jié)約解空間，提高運(yùn)算效率[4]。

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

實(shí)現(xiàn)多目標(biāo)動(dòng)態(tài)規(guī)劃的多跑道進(jìn)港排序是航空運(yùn)輸業(yè)長(zhǎng)足發(fā)展需求，是提高航空和運(yùn)輸效率的要求，是繼續(xù)推動(dòng)現(xiàn)代化建設(shè)有序進(jìn)行的要求。希望通過(guò)文章的闡述，能夠引發(fā)相關(guān)部門(mén)航空工作者針對(duì)優(yōu)化飛機(jī)進(jìn)港排序的共同關(guān)注，變革傳統(tǒng)觀念，優(yōu)化算法，整合國(guó)際范圍內(nèi)的高級(jí)技術(shù)成果，全面優(yōu)化升級(jí)飛機(jī)進(jìn)港排序，促進(jìn)航空運(yùn)輸事業(yè)的穩(wěn)固發(fā)展，使航空運(yùn)輸業(yè)為社會(huì)發(fā)展貢獻(xiàn)更多的力量。

參考文獻(xiàn)

[1]張啟錢(qián)，胡明華，張洪海.基于RHC-GA的多跑道進(jìn)離場(chǎng)航班多目標(biāo)動(dòng)態(tài)優(yōu)化模型[J].交通運(yùn)輸工程學(xué)報(bào)，2015，10（2）：70-78.

[2]馮翔，楊紅雨.進(jìn)港飛機(jī)調(diào)度多目標(biāo)優(yōu)化問(wèn)題的改進(jìn)NSGA-II算法[J].電子科技大學(xué)學(xué)報(bào)，2014，9（1）：66-70.

[3]梁曼，馬蘭，鄒飛.基于混合動(dòng)態(tài)規(guī)劃算法的進(jìn)場(chǎng)航班排序[J].廣西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，5（1）：44-50.

[4]李丹程，曹斌，鐘華剛，等.改進(jìn)GA-PSO算法在多跑道航班著陸調(diào)度中的應(yīng)用[J].小型微型計(jì)算機(jī)系統(tǒng)，2014，11（9）：2110-2115.