劉鑫哲

（中國民用航空華北地區(qū)空中交通管理局）

空中交通流量管理中飛機隊列優(yōu)化算法研究與實現(xiàn)

劉鑫哲

（中國民用航空華北地區(qū)空中交通管理局）

為了能夠更好的實現(xiàn)對于快速增長的空中交通流量的管理，我們不僅僅需要對交通管制的設(shè)施進行完善，更加需要的是從交通管制的方式入手，對交通流量的管制程序來進行合理的優(yōu)化，進而保證在空中交通的過程當中，能夠?qū)罩械馁Y源進行合理的利用。

空中交通；流量管理；飛機隊列優(yōu)化；算法；實現(xiàn)

引言

隨著我國經(jīng)濟以及社會的快速發(fā)展，我國的空中交通量開始快速的增加?？罩薪煌靠焖僭黾拥拇蟊尘跋?，傳統(tǒng)的交通管制系統(tǒng)已經(jīng)完全沒有辦法滿足當前龐大的空中交通流量的需求。在當前空中交通自動化管理的完善以及優(yōu)化的過程當中，對于準備進行起降的飛機隊列進行優(yōu)化排序是非常重要的一個方向。真正有意義的飛機隊列優(yōu)化算法需要做到的就是對所有的需要進行排序的飛機都進行合理的計算，這樣就能夠在通過對總成本進行計算以及比較之后，從所有的排序當中選擇最優(yōu)的方法來進行。隨著現(xiàn)在我國的交通流量的迅速的增加，導(dǎo)致了飛機的數(shù)量呈現(xiàn)了飛速的增長，進而使得這種循環(huán)排列算法進行計算的過程當中計算量開始呈現(xiàn)指數(shù)型的增長，大運算量使得在隊列優(yōu)化排序當中出現(xiàn)了運算問題。

1 國內(nèi)外的主要算法介紹

首先我們針對國內(nèi)外的主要的幾種算法進行簡要的闡述與分析，希望能給大家?guī)砣舾伤伎肌?/p>

1.1 先到先服務(wù)（FCFS）算法

所謂的先到先服務(wù)的算法就是通過對飛機的到達的時間進行預(yù)計，然后根據(jù)飛機到達時間的次序來進行飛機的著陸次序的決定。采用這種方法的時候，一旦當需要著陸的飛機進入到了終端區(qū)當中的排序區(qū)域的時候，排序的系統(tǒng)就會根據(jù)飛機進入到終端區(qū)的時間以及飛機的具體的性能以及飛機的初始狀態(tài)等來對飛機到達目標點的ETA來進行相應(yīng)的計算，然后根據(jù)計算的ETA的結(jié)果終端系統(tǒng)就能夠結(jié)合飛機鏈的排序情況來對飛機的計劃的到達機場的時間來進行確定。如果說在確定的飛機鏈的間隔當中無法插入一輛新的飛機來進行著陸，那么這個時候系統(tǒng)就會在保證飛機著陸時間的間隔符合標準的情況之下來對這架飛機之后的飛機來進行重新的排序，也就是說需要進行延遲處理。如果說在進行延遲處理的時候后面的飛機不能夠進行延遲處理，必須要準時進行降落的時候，我們就需要對這一架新到達的飛機來實行等待的策略，使得這一架飛機在末一個固定的空域當中進行等待，等可以進行降落的時候在安排進行降落。

1.2 約束位置交換（CPS）算法

約束位置交換法與前面的方法是不同的，這種方法所需要進行依據(jù)的就是所有不同的類型的飛機之間必須要保持著最小的安全間隔標準，然后我們依據(jù)這個來對飛機隊列的次序進行重新的排序，在進行排序的過程當中我們需要對所有有可能的飛機的排序方式進行搜尋，通過搜尋從所有的飛機排序方式當中找到成本最小的排序方式來進行排序，這種排序方式就是我們需要的飛機的最佳的排序方式。但是這種算法的缺點就是通過這種算法確定的最佳的排序方式可能會使得原來的飛機的隊列次序產(chǎn)生非常大的變化，這種對原飛機隊列進行較大的改變的方法不僅僅會對管制員的負擔(dān)造成極大的增加，而且還會與先到先服務(wù)的原則產(chǎn)生很大的沖突，對于航班飛機的公平性進行了降低，并且還會對實現(xiàn)的難度進行增加。所以說需要帶約束的進行位置交換，也就是說飛機的最終的位置需要保持在最初的初始位置前后的一定范圍之內(nèi)的適當位置之上。

2 滑動排序窗算法設(shè)計實現(xiàn)

以下，我們以滑動排序窗算法的設(shè)計以及實現(xiàn)為例，進行探討分析：

在機場當中的終端區(qū)的飛機流往往都是由不同飛機類型的飛機來進行組成的，并且這些飛機的前后的順序是不同的，每一架飛機的尾流間隔也是不同的。ICAO對于無風(fēng)條件之下的飛機的最小的間隔標準進行了一定的規(guī)定，這樣就能夠得到最小的時間間隔。

我們在對排序的問題進行考慮的時候首先需要考慮到的原則就是先到先服務(wù)原則，以及不同類型的飛機需要保持著不同的最小安全間隔標準來進行入手，我們通過對飛機的隊列次序來進行重新的排列，然后對所有的有可能的飛機的排序方式來進行搜尋，這樣就能夠找到一種成本最小的排序方式，這種排序方式就是最佳的飛機排序方式。

要想要得到最優(yōu)的序列，我們需要采用最為直觀的方法來對所需要進行排序的飛機來進行循環(huán)排列。就十架飛機來說，我們在硬件PIII600CPU，128M內(nèi)存的條件之下來進行運算，大約需要30s的時間來進行計算。但是隨著飛機的數(shù)量的增加，計算的難度也就增加，現(xiàn)在的硬件情況是沒有辦法進行滿足的。也就是說循環(huán)排列算法的瓶頸就是飛機的數(shù)量的線性增長。下面所提到的排序窗法就是通過限制全排列飛機的數(shù)目來抑制計算量的指數(shù)增長的速度。

這種排序窗算法的理論依據(jù)就是，在進行優(yōu)化排序的過程當中需要對原來的飛機隊列當中的所有的飛機的位置進行重新的排列，對于每一架飛機在新的隊列當中的位置進行確定。我們在對新的隊列進行排序的過程當中，由于某一個或者說某些的位置存在著約束交換范圍的限制，所以說我們不需要對所有的可能產(chǎn)生的排序進行搜索，只需要對那些與所需要確定位置相關(guān)的飛機，然后對他們產(chǎn)生的相關(guān)的可能排序來進行搜索，得出最后的最優(yōu)隊列。這樣通過一定的約束條件能夠極大的降低計算的壓力，提高運算的速度。

3 結(jié)語

綜上所述，隨著我國的空中交通流量的增加，傳統(tǒng)的計算方式已經(jīng)完全沒有辦法滿足這巨大的交通流量的需求了，在本文當中筆者主要闡述了幾種國內(nèi)外比較常見的飛機隊列優(yōu)化算法，然后對飛機隊列優(yōu)化算法的設(shè)計以及實現(xiàn)進行了簡要的分析，希望能給相關(guān)人員帶來一定的啟發(fā)。

[1]田勇.空中交通流量管理關(guān)鍵技術(shù)研究[D].南京航空航天大學(xué)，2009.

[2]景文超.空中交通管理流量戰(zhàn)術(shù)控制研究[D].西南交通大學(xué)，2005.

[3]顧秋麗.空中交通管理中的排序問題研究[D].中國民航大學(xué)，2014.

[4]葉博嘉.空中交通流量管理動態(tài)網(wǎng)絡(luò)流模型及實現(xiàn)算法研究[D].南京航空航天大學(xué)，2008.

V355.1

A

1004-7344（2016）02-0281-01

2015-12-22

劉鑫哲（1988-），男，漢族，北京人，管制員，本科，研究方向為交通運輸。