匯聚航路航班排序的遺傳算法研究

趙嶷飛　王惠斌（中國民航大學空管學院，天津 300300）

匯聚航路航班排序的遺傳算法研究

趙嶷飛王惠斌
（中國民航大學空管學院，天津 300300）

基于匯聚航路的特點，結合區域流量控制的實際情況，建立了匯聚航路航班排序模型，并設計了相應的遺傳算法。在模型中提出了多路編碼算法，并對交叉算子和變異算子進行了改進，提高了算法的求解性能。解決了在流量控制情況下，匯聚航路上的航班排序問題。最后對算法進行了仿真驗證。結果表明，該遺傳算法在較快求得全局最優解的前提下，能有效減小匯聚航路航班的空中延誤。

航班排序 遺傳算法 流量控制

隨著民航運輸量的迅速增長，航班量的不斷增大，由于有限的空域資源而導致的流量控制次數和時長也在不斷地增加。如何有效地解決由于流量控制原因而導致的空中航班延誤成為當務之急。流量控制通常是由于某一區域，機場或航路點的容量下降而產生的。常見的控制形式有點控制和區域控制。控制的方式多為限制飛機以一定的時間間隔或者距離間隔通過某一航路點。然而無論采用那種方式都會對實施流量控制所在航路點的上游航班造成影響，隨著延誤的傳播，往往還會對相鄰管制區的航班造成影響。解決這一問題的方法有兩種：（1）通過合理的設置流量控制值來減少航班的空中延誤。（2）通過合理的航班排序來減少航班的空中延誤。本文主要針對第二種方法進行研究。

而以往的航班排序問題多是針對終端區航班排序或是地面等待問題的航班排序，對由于流量控制原因導致的航路上飛行的航班延誤排序的研究卻較少。然而傳統的航班排序算法又并不適合此問題的求解，而且運行效率較低，收斂速度較慢。因此本文對解決傳統排序問題遺傳算法進行了改進，并針對匯聚航路的特點提出了多路編碼的編碼方式，根據流量控制的實際情況，進行了建模。本文的結構如下：首先對流量控制點上游的航路特點進行了分析，提出了匯聚航路航班排序模型，其次，對傳統的遺傳算法進行了改進，最后，對算法進行了仿真，并與傳統的排序算法進行了比較，證明了算法的有效性。

1　問題描述

圖1　匯聚航路結構示意圖

圖2　三條航路匯聚示意圖

飛往流量控制點的航班通常經由多條匯聚于流量控制點的航路到達，如圖1所示。圖中A點為流量控制點，1-N對應了匯聚于A點的N條航路，其中2，3航路的航班匯聚于B后再飛往A點，4，5航路的航班匯聚于C點后再飛往A點。對下游實施流量控制往往會對上游的航班造成延誤影響，如果延誤過大，超出了流量控制點所在管制區對延誤的吸收能力，延誤將會沿著航路向上游管制區傳播。這時如何合理的對空中航班進行排序，減少空中的延誤顯得尤為重要。管制區對飛行中的航班延誤，多采用雷達引導，調速，空中等待等方式進行處理。而空中等待不僅十分耗油，需要較大的空域進行實施，而且會增加管制員的工作負荷，因此對航路上飛行航班的排序時，在保證航班總延誤最小的情況下，還要盡量減少航班空中的等待的發生。

2　匯聚航路航班排序模型建立

綜合以上分析，建模方法如下：

（1）以流量控制點的流量控制時間長度為基準，凡是在此時間長度區間內飛行的航班即為所要進行排序的航班，記航班總數為n。

（2）每一條匯聚于流量控制點的航路記為1路，設總共有m條航路匯聚于流量控制點，即共有m路。選擇標準為所需要進行排序的航班經過的航路，如果航路在流量控制點前交匯于某航路點，以該航路點上游的航路作為區分，如第2路，第4路，該航路點到流量控制點之間的航班標記為編號較小的路的航班。

（3）在第m條路上飛行的航班組成一個隊列，該隊列中的航班不允許出現航班超越，且該隊列的航班在排序前和排序后經過流量控制點的順序不變。

（4）考慮到航路飛行航班的實際情況，針對不同的航班的優先級設置不同的延誤權值。

2.1參數定義

N：匯聚航路的集合；

F：航班的集合；

Cnf：第n條航路上第f航班的延誤權值；

n（f）：第n條匯集航路上的航班集合；

ETAnf：第n條航路上第f航班預計到流量控制點的時刻；

Xnf：第n條航路上第f航班實際到達流量控制點的時刻；

V：流量控制點處的時間間隔；

2.2目標函數

2.3約束條件

（1）航班不可加速提前到達流量控制點：Xnf-ETAnf≥0

（2）到達流量控制點的過點航班滿足間隔約束：

（3）由上游航路到達流量控制點的同一行路上的航班不允許超越：（ETAnf2-ETAnf1）·（Ynf1nf2+1）＞0

（4）航班Xnf實際到達流量控制點的時刻：

表1　FCFS與遺傳算法仿真結果

3　多路編碼遺傳算法設計

根據以上模型并結合約束條件，設計遺傳算法，來實現航路航班的最優排序，并以三條匯聚航路為例對算法進行解釋說明，如圖2所示。

3.1編碼方法設計

以往的遺傳算法在解決航班排序問題時，編碼方式多為格雷編碼，二進制編碼，浮點編碼等，而這些編碼方式在解決該模型下的航班排序問題時并不是最合理的選擇，因此針對該模型中航班排序的問題，提出了多路編碼的編碼方式。

所謂多路編碼是指航班（基因）在染色體中的值，是用該航班所在航路的航路號表示，航路的標號遵循上文中建模方法（2）中的方法進行標記。如圖2所示，三條匯聚航路的標號分別1，2，3。將1航路上的航班都記為1，將2和3航路上的航班分別記為2和3。設第一條航路上有5架航班，第二條航路上有5架航班，第三條航路上有2架航班，則染色體由5個1，5個2，2個3排列組合而成，該染色體共有12個基因。其中5個1代表著1號航路上按順序排列的5架航班。5個2，2個3的意義同上。染色體形式例如：

G=（112122123213）

若有N條航路匯聚于流量控制點，則每個基因可能取值的最大范圍記為1到N。本例中每個基因取值的最大范圍為1到3。對于航路3的情形，假設航路3與航路2的航路交匯點到流量控制點間的航路上有m架航班。為了保障同條航路上不出現航班的超越，則當某一基因取值為3時，必須保證該基因前有m個或m以上個基因取值為2。因此初始化種群時若出現如下基因應予以舍棄。

G=（312311221212）出現航班超越

3.2初始種群

如果在算法開始時能得到一個平均適應度較高的初始群體，再進行進化，將會顯著地提高算法的求解性能。針對這一問題首先引入最大交換位置MPS這一概念。此處最大交換位置指的是以到先服務FCFS原則，依據各航路航班預計到達流量控制點的時間，進行排序所產生的染色體中，不同航路的航班相對位置變化的上限。實際當中航班相對位置的變化會增加管制員的工作負荷，文獻三中對MPS的取值大小選擇對航班排序延誤的影響和管制員工作負荷的關系做了分析，結論表明，當MPS取值大于3時，將顯著的增加管制員的工作負荷。因此此處選MPS值為2。

設計一個以三個基因長度為單位的時間窗，沿著染色體從左到右移動，步進為2，每移動一次，隨機變換時間窗內兩個基因的位置，當時間窗移動到染色體結尾時，將該染色體記為新染色體。對以先到先服務為原則的初始排序航班進行編碼，產生初始染色體。將該染色體進行若干次如上變換，將產生的種群定為初始種群。

3.3交叉算子和變異算子設計

由于傳統的交叉算子和變異算子，所產生的染色體，會帶來無效解，降低求解效率，因此，需要對傳統的交叉算子和變異算子進行改進，結合本文中提到的基因編碼方式，可將其看成一種單性遺傳，并不考慮交叉操作。新染色體的產生只通過基因的變異來實現。

變異方式為對染色體中的基因以隨機概率向左或向右移動小于MPS位。由于要保證子代種群平均適應度高于父代種群，因此，對父代優良的基因進行變異，比對父代較差的基因進行變異，得到優良基因的概率更大。依據這一原則，采用父代中最優的染色體進行變異，生成子代種群。

3.4適應度函數

將目標函數作為適應度函數，適應度函數公式如下：

3.5計算步驟

Step1.航班編碼，初始化種群gen（t），t=1，設置相應的參數，進化代數GEN，群體大小N等。

Step2.用3.3中的適應函數計算染色體的適應度值，對其大小進行比較，選出適應度最大的染色體，

Step3.對父代最優的染色體進行選擇，進行變異，產生規模同樣為N的子代種群，t=t+1。

Step4.當t>GEN時，算法停止，否則回到step2。

4　仿真結果與分析

仿真時采用三條匯聚航路上共20架航班，如圖2所示。延誤權值化分為0.6，0.3，0.1三個級別，每條航路上的航班，及預計到達流量控制點的時間和延誤權值見表1。采用MATLAB對遺傳算法進行了編程。流量控制的時間間隔設置為2分鐘，種群規模設置為100，進化代數設置為300。

FCFS的目標函數值為13.8，航班延誤時間為37分鐘，而遺傳算法的目標函數值為10.2，航班延誤為38分鐘。結果表明，本文提出的遺傳算法在保證較小延誤的情況下，能有效的減少航班延誤成本。

5　結語

本文所提出的多路編碼遺傳算法可以快速求得最優解，采用數據進行仿真，并與先到先服務的航班排序進行對比，結果表明，該算法得到的航班排序可以有效減小延誤成本。在此研究的基礎上，下一步將對區域中多航路點進行流量控制的情況下航路航班的排序進行研究。

［1］趙嶷飛，金長江.區域空中交通流量控制研究［J］.飛行力學，2002，20（2）：67-70.

Zhao Y F，Jin C J.An approach to area traffic flow control research ［J］.Flight Dynamics，2002，20（2）：76-70.

［2］趙嶷飛，張雯雯.區域空中交通流量控制建模研究［J］.飛行力學，2009，27（5）：86-88.

Zhao Y F，Zhang W W. Modeling area air traffic flow control ［J］. Flight Dynamics，2009，27（5）：86-88.

［3］徐肖豪，姚源.遺傳算法在終端區飛機排序中的應用［J］.交通運輸工程學報，2004，4（3）：121-126.

Xu X H，Yao Y. Application of genetic algorithm to aircraft sequencing in terminal area ［J］.Journal of Transportation Engineering，2004，4（3）：121-126.

［4］Delahaye Daniel，Sofiane Oussedik，Puechmorel Stephane. Airspace Congestion Smoothing by Multi-objective Genetic Algorithm ［C］.ACM Symposium on Applied Computing，2005：907-912.

［5］Aditya P. Saraf ，Gary L. Slater. Optimal Dynamic Scheduling of Aircraft Arrivals at Congested Airports ［C］. Journal of Guidance，Control，And Dynamics，2008，31（1）：53-55.

［6］Shin-Lai Tien，Christine Taylor.A Rout-Based Queuing Network Model for Air Traffic Flow Contingency Management. AIAA Aviation Technology，Integration，and Operations Conference，2011：12-14.

［7］張軍，詹志輝.計算智能［M］.北京：清華大學出版社，2009.

趙嶷飛（1971—），男，湖南常德人，博士，教授，研究方向：空中交通流量管理；

王惠斌（1989—），男，山東濰坊人，碩士研究生，研究方向：交通運輸規劃與管理。