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

劉鑫哲

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

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

劉鑫哲

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

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

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

引言

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

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

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

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

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

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

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

2 滑動(dòng)排序窗算法設(shè)計(jì)實(shí)現(xiàn)

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

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

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

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

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

3 結(jié)語

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

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

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

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

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

V355.1

A

1004-7344（2016）02-0281-01

2015-12-22

劉鑫哲（1988-），男，漢族，北京人，管制員，本科，研究方向?yàn)榻煌ㄟ\(yùn)輸。