分布式全局調度動態反饋自由飛算法

摘 要：在諸多空管算法基礎上，提出了分割空域航線和時間并壓縮的研究范式。單機根據空域航線點陣和時間窗矩陣的環境參數進行全局路徑尋優，然后沿全局路徑模擬飛行進行局部路徑尋優，并將獲得的環境參數隨時回寫空域航線點陣和時間窗矩陣，使得全局優化和局部優化動態反饋并逼近收斂一致。算法突破傳統算法難以兼顧分布優化與集中優化的局限。

關鍵詞：算法; 空管調度; 全局優化; 局部優化

中圖分類號：

TN96-34

文獻標識碼：A

文章編號：1004-373X(2011)19

-0165

-03

Distributed Global Scheduling Algorithm Based on Dynamic Feedback in Free Flight

CHENG Bi-bo

(Civil Aviation Management Institute of China， Beijing 100102， China)

Abstract： Based on many air traffic control scheduling algorithms， the segmentation and compression paradigms of time and spatial routes are proposed. A plane made global route optimization according to the spatial routes lattice and the environment parameters of time windows matrix， then performed simulated flight along the global route for local path optimization， obtained environmental parameters and updated them to spatial routes lattice and time windows matrix， which created feedback and convergence between global optimization and local optimization. The free flight algorithm can solve the problem that the traditional algorithms are difficult to achieve both global optimization and distribution optimization.

Keywords： algorithm; air traffic control scheduling; global optimization; local optimization

收稿日期：2011-06-21

0 引 言

目前空中交通流量控制算法可大致分為兩類。一是局部優化算法。1994年Varnas， Bertsimas和Odoni利用0~1整數規劃研究了確定型的多機場地面等待［1］。1998年我國學者胡明華使用線性規劃研究了多元受限的地面等待問題［2］。Gilbo E.P使用先到先服務( FCFS) 算法決定飛機進近和著陸次序［3］。2007年張鵬、徐肖豪采用memetic算法對飛機著陸次序和時間進行仿真優化［4］。1998年Bertsimas和Patterson利用0~1整數規劃研究空中交通流管理［5］。2008年姚玲提出空中交通擁擠評價指標體系及“狀態空間分類評價法”與“動態綜合評價”相結合的綜合評價方法［6］。2009年葉博嘉探討了多任務動態算法和遺傳算法［7］。2002年許越、楊國慶研究了自由飛行計劃的五項核心技術［8］。2008年何春豪建立了自由飛行的簡化模型［9］。2009年劉維維建立建立水平和垂直方向沖突模型及其算法［10］。

局部優化算法可具體到飛機排序，但不能優化整個航路。全局優化算法則只能計算大致流量，無法計算排序、機型組合等具體飛行數據。本文目的則是將全局優化和局部優化結合在一起。

1 分布式全局調度動態反饋算法原理

本算法采用交通仿生學原理，構建全局調度優化與局部調度優化間的動態反饋收斂關系，逼近全局優化和局部優化的一致。若各航空區域能事先標注堵塞標志，飛機可提前避開堵塞區域，在非堵塞區域內選擇自己的全局優化航線。然后在此航線上模擬飛行，實現局部航線平滑化及排隊優化，獲得實際飛行參數，并修改路線未來容量和流量數據，調整路線的堵塞信息，從而使全局優化路線與局部優化路線不斷反饋收斂。調整各飛機的全局路線優化順序，可調整飛機全局優先級，以保障飛機全局需求；調整各飛機的隊列排序優先級，可保障局部路線平滑化及隊列排序效率，滿足飛機局部優化需求。

2 航線區域和時間的分割

在空域自由飛情況下，要對航線區域標志阻塞信息，并且根據阻塞信息確定將要飛行的航線，必然要求航線單位區域不能過大，以免飛機無法在單位區域中根據碰撞探測和解脫算法確定航線(極端情況下，整個空域就是一個單位空域，這種單位區域劃分顯然意義不大)。但航線單位區域又不能過小，否則數據存儲和計算量都將過大。僅為原理講解之目的，以下暫以二維空間的點陣壓縮進行演示。如圖1將此二維空間劃為32個點區域，區域中有兩條局部航線。

然后設計其每個點的屬性之數據結構。其中一個很重要的屬性是時間窗。時間窗是將一天或幾天的時間，依照一定的時間間隔(例如15 min)進行分割，每單位間隔的時間為一個時間窗。然后在每個時間窗下面，設置這個時間窗內發生的事情。其數據結構簡單舉例見表1。

表1是區域點陣中各單位區域及時間窗的基本數據結構。里面包括各點在各時間窗的實際流量、容量等。由于點域有一定步長，故點陣必然有一定失真。所以在各點各時間窗記錄了每個航班飛機進入此點區域的精確位置、速度，飛出此點區域的精確位置、速度，從而降低對模擬飛行時的局部優化分析之影響。通過此矩陣及點元素屬性中的堵塞信息(實際流量大于最大容量，就是堵塞標志)，可以使用A*算法尋找全局優化路徑。

此點陣為稀疏矩陣，可以進一步壓縮。一般在計算機中，常令矩陣元素第1列為行下標，第2列為列下標，第3列為非零元素值，來完成壓縮。

三維立體空域及航線的壓縮同理可得。若是航線網絡既定的自由飛，則其航線矩陣表示將更簡單。所以本算法不但前瞻未來完全的自由飛算法，也與當前我國的空管體制接軌。

3 利用A*算法在點陣中尋找全局航線

本研究中，由于點陣中可能包括多種性質空域及地面的連接，路徑長度并非優化決策的惟一標準(例如地面路徑長度與空中航線長度不是一個概念)，所以f(n)的設計應是考慮全局權衡的取值。此外，與一般最優尋路不同的是，點陣中的堵塞信息是未來時間窗的變量，因此飛行路線的堵塞情況與飛行速度相關。理論上速度可無級變化，最優路徑取值范圍無窮大。所以還要根據A*算法h(n)的原理，構造飛機速度的追趕函數，例如若飛機到目的地的時間越延遲，則追趕函數越大，使飛機提高速度(但受限于空域及機型允許的速度范圍)。并在飛機遇到堵塞時，可調整局部速度避過堵塞。尋徑算法無須特別區分空中航線和地面道路，所以可對空地一體化尋徑。

4 構建全局優化和局部優化的動態反饋

飛機沿全局航線模擬飛行，通過碰撞探測和解脫算法，調整局部航線和速度矢量，并根據模擬情況改寫環境參數入點陣，以實現反饋收斂，便于重新決策或其他飛機決策。

本步驟有兩個重要指標。一是效率指標，它體現單機的優化目標，例如有的飛機以節省時間為目標，有的飛機以省油為目標。當模擬飛行過程中效率指標超標時，表明全局航線不合理，需要重新選擇全局航線。一是全局優化級別。飛機局部優化級別設置算法已相對成熟，但若不考慮全局優化級別就可能失衡。例若為縮短間隔，重型飛機在局部優化中總排在輕型飛機之后，可能導致重型飛機誤點，導致更大的不經濟。一般而言，越早啟動全優化程序的飛機，顯然擁有航線及隊列選擇的優先權。由此可平衡局部優化級別的失衡。全局優化級別越高，在選擇全局航線時就越有優先權。顯然，極端情況下如果某飛機第一個選擇航線，那它不會遇到任何堵塞。本步驟還有反饋收斂的重要性質。模擬飛行如果順暢，則會修改點陣中相關點實際流量、最大容量和航班信息，如果不順暢，則會修改點陣中相關點的最大容量。隨著優化次數的增加，航線及飛行參數將收斂到更為準確。

將前述算法思想進行整合，其構成一個流量、容量等未來環境參數與飛機優化路線選擇間連續反饋收斂的動態系統如圖2所示。各單機根據系統的公共環境參數數據庫進行全局優化決策，同時又把自己模擬全局決策獲得的環境參數改寫入系統的公共環境參數數據庫，并根據單機的實際情況，調節單機優化級別，實現分布式與集中式的統一。

圖2 動態系統結構

5 結 論

本算法中各飛機只計算與自己相關的數據，大大降低計算復雜度。傳統的空管算法常使用線性規劃等方法，集中輸入所有飛機及環境數據，集中優化計算所有飛機的飛行數據，這不但抹殺單機優化個性，也極大增加了計算復雜度。當部分環境參數意外改變時，常須把所有數據重新計算一遍，缺乏靈活性。本算法以全局優化為基礎，局部優化細到處理飛機航線、各型飛機的間隔、速度等飛行數據。傳統空管算法若細到飛行數據，常只能處理單個環節的優化問題；若要處理多環節的優化問題，則常只能獲得大致流量數據，不能細化到發出飛行控制指令的程度。同時，本算法能適應動態變化，突破傳統全局性算法的靜態分析局限。因此對于自由飛理論的發展，具有重要意義。

參 考 文 獻

［1］VEANAS P B， BERTSIMAS D， ODONI A R. The multi-airport ground-holding problem in air traffic control \\. Operation Research， 1994， 42 (2): 249-261.

［2］胡明華，陳愛民.多元受限的地面等待策略問題研究\\.南京航空航天大學學報，1998，30(1):42-46.

［3］GILBO E P. Optimizing airport capacity utilization in air traffic flow management subject to constrains at arrival and departure fixes \\. IEEE Transaction on Control Systems Technology， 1997， 5(5): 490-503.

［4］張鵬，徐肖豪.基于memetic算法的飛機著陸調度優化\\.中國民航大學學報，2007，25(1):19-23.

［5］BERTSIMAS D， PATTERSON S S. The air traffic flow management problem with enroute capacities \\. Operations Res.， 1998， 46: 406-422.

［6］姚玲.空中交通擁擠評價方法研究［D］.天津：中國民航大學，2008.

［7］葉博嘉.空管動態網絡流模型及實現算法研究［D］.南京：南京航空航天大學，2008.

［8］許越，楊國慶.FAA自由飛性計劃核心技術［J］.航空科學技術，2002(5):38-40.

［9］何春豪.沖突探測與解脫技術在未來空中交通管理中的應用［D］.南京：南京航空航天大學，2008.

［10］劉維維.空中交通防撞算法的研究［D］.成都：電子科技大學，2009.