基于多目標動態規劃的多跑道進港排序研究

幸小燕

摘 ?要：伴隨社會的全面發展，現代化的交通事業得到關注與發展，航空運輸作為現代交通工具的典型代表，對促進社會的發展起著重要的作用。伴隨航空運輸行業的發展，航班出現晚點、延誤的情況越來越多，除去氣象等自然原因的影響，飛機進港排序是影響航班正常運行的關鍵因素。由于多跑道進港排序是一項復雜的工程，所以現階段針對此問題沒有形成長效的解決方案。文章以多跑道進港排序為研究視角，以實現多目標動態規劃為出發點炸開討論，旨在為飛機進港排序優化升級提供意見。

關鍵詞：進港排序;多跑道調度;多目標優化

前言

飛機進港排序是提高終端機場吞吐量、減少能源消耗、減少航班延誤的有效措施，在優化航班終端管理體制中發揮重要作用。面對越來越復雜、多元化的航空發展形式，國內外專家學者對優化進港排序問題的研究在逐步深入，呈現百家爭鳴的狀態，但是縱觀其結果，主要針對但跑道，單目標進行。隨著計算機技術的不斷發展，飛機進港排序應該實現質的飛躍，實現多目標動態式的規劃模式。因此，作者針對“基于多目標動態規劃的多跑道進港排序”具有現實意義，希望通過文章的闡述，能夠為航空運輸事業的發展注入新鮮血液。

1 問題描述

由于各機場的具體狀況不同，所以無法全面涵蓋所有狀況進行進港排序的設計，作者現針對特定條件下進行多目標動態規劃的多跑道進港排序，現將各部分限定條件闡述如下：

1.1 飛機降落時間窗

機場終端服務區內的飛機必須滿足一定的限定速度條件，那么根據飛機在機場各節點的飛行速度可以計算飛機最早的降落時間、最晚降落期限、預計降落時間等信息。現令飛機降落時間參數為ETi;飛機最早的降落時間設定為LTi;飛機最晚的降落時間表示為ETAi;飛機的預計降落時間表示為STAi;根據上述設定條件，飛機的降落時間窗即為[ETi，LTi]。

1.2 FCFS序列

FCFS序列是建立在飛機最晚降落時間的基礎之上的一種具有一般性特征的系列，FCFS序列一般根據飛機的具體位置進行命名，現規定以下涉及到的FCFS系列按照終端服務區最大吞吐量產生[1]。

1.3 最大位置平偏移

最大位置偏移量是指序列進行成功優化之后產生的FCFS序列中飛機位置的變化程度，設定優化后的序列為A，最大位置偏移為k，那么會|Ai-i|≦k的結論。

1.4 降落時間間隔

同一跑道的兩架不同飛機實現先后降落，中間必須間隔一定的時間，而且時間間隔必須滿足特定的安全范圍，現規定以下方案設計中必須滿足國際航空組織對于不同類型飛機在統一跑道上實現降落的間隔時間標準。最小尾流間隔標準：重型飛機與重型飛機之間必須滿足尾流為94;重型飛機與中型飛機間隔尾流為114;重型飛機與輕型飛機尾流間隔為167。

1.5 平行跑道

作者限定研究的機場類型為平行跑道模式，是指飛機降落的跑道與跑道之間處于平行的狀態，而且能夠達到距離較近的要求。那么可以理解為飛機在到達兩條跑道需要的時間基本不會有太大差別，而且相鄰跑道上降落的飛機能夠保證安全的時間差。令雙跑道同時運行過程中的安全時間間隔為40秒。

1.6 優化目標

飛機進港排序進行優化升級的總體目標是一致的，都是為實現吞吐量達到最大化、飛機延誤時間降到最低、消耗的燃料成本盡可能減少。作者進行的設計方案規定進港飛機均可以早于最晚降落時間實現降落，用公式可以描述為：

ETi

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

maxf1=n/（STAAn-t0）

上述公式中，STAAn表示最晚實現降落的飛機降落時間;t0表示規定的調度時間，如果t0的值是0，那么實現吞吐量最大的方式是保證最后降落飛機的降落時間最小化[2]。

降落消耗最小化的公式：

Minf2=c（STA）

上述公式中，ci（STAi）表示第i各飛機實現降落過程中的多余消耗部分;額外消耗部分會根據不同類型的飛機發生變化，現規定ci（STAi）=|STAi-ETAi|。

1.7 結果權重

在進行多目標動態規劃進港排序優化的過程中，根據優化目標往往能夠產生多個Pareto個優化結論。作者現設定結果權重為：首先要求對Pareto曲線上的多個節點進行統一化的處理;然后抽取Pareto曲線上凸出優化點;最后以抽取的凸點與其相鄰的兩個凸點進行連線并取其平均值。

1.8 離港排序

在進行飛機進港排序設計的同時，需要對機場離港飛機進行有效考慮，文章中將離港飛機的花費與進港飛機的花費按照同一時段同一跑道狀況下相同予以考慮。

2 優化策略

2.1 CPS動態規劃算法

動態規劃算法主要由兩類方式實現：一是深度優先搜索，主要是通過對每條路徑進行不同的規劃，然后因公剪枝等手法尋求最優解決途徑的搜索方式;而是寬度有限搜索方式，是指按照不同路徑的具體特征進行逐步深入式的搜索方式。在進港排序優化設計中，由于不盡相同的路徑之間存在一定的交叉節點，所以，深度有限搜索在運用過程中將產生諸多重復性的工作。因此，規劃方法的選擇上應該運用寬度有限搜索的方式[3]。

2.2 優化CPS動態規劃算法

為達到多跑道動態的進港排序，遞推過程中的各個層級結點上飛機數量應該降到最低限度，能夠達到掌握有效信息的目的視為成功。在進行進港排序的過程中，已經實現降落的飛機和具體跑道上最后需要降落的飛機類型是其關鍵因素，所以應該在飛機節點后面標注沒條跑道最后一架飛機的類型信息。針對飛機的飛機的降落時間信息，應該在以往r維矩陣進行有效有效的優化和升級，將以往的r維時間矩陣進行離散化處理，讓其功能更加全面，進而有效的提高運算的速度和準確率。

2.3 貪心策略

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

3 結束語

實現多目標動態規劃的多跑道進港排序是航空運輸業長足發展需求，是提高航空和運輸效率的要求，是繼續推動現代化建設有序進行的要求。希望通過文章的闡述，能夠引發相關部門航空工作者針對優化飛機進港排序的共同關注，變革傳統觀念，優化算法，整合國際范圍內的高級技術成果，全面優化升級飛機進港排序，促進航空運輸事業的穩固發展，使航空運輸業為社會發展貢獻更多的力量。

參考文獻

[1]張啟錢，胡明華，張洪海.基于RHC-GA的多跑道進離場航班多目標動態優化模型[J].交通運輸工程學報，2015，10（2）：70-78.

[2]馮翔，楊紅雨.進港飛機調度多目標優化問題的改進NSGA-II算法[J].電子科技大學學報，2014，9（1）：66-70.

[3]梁曼，馬蘭，鄒飛.基于混合動態規劃算法的進場航班排序[J].廣西師范大學學報（自然科學版），2014，5（1）：44-50.

[4]李丹程，曹斌，鐘華剛，等.改進GA-PSO算法在多跑道航班著陸調度中的應用[J].小型微型計算機系統，2014，11（9）：2110-2115.