基于遺傳算法的航班著陸調(diào)度的設計與實現(xiàn)

張子陽 ， 張曉瑋 ， 何 彬 ， 郝賓賓 ， 張啟升

（1.地下信息探測技術(shù)與儀器教育部重點實驗室 北京 100083；2.中國地質(zhì)大學（北京）地球物理與信息技術(shù)學院，北京 100083；3.中國地質(zhì)大學（北京）信息工程學院，北京 100083）

航班著陸調(diào)度是機場管理的重要組成部分，旨在為待著陸的航班安排合理的著陸調(diào)度方案，保證機場的秩序，減少早到或者晚到造成的經(jīng)濟損失。因此研究航班的調(diào)度問題對提高機場的運行效率以及飛行效益具有重大意義。著陸調(diào)度問題是一個典型的組合優(yōu)化問題[1]，其可能的排序數(shù)隨著航班數(shù)量的增多而呈指數(shù)型增長，屬于NP-hard問題，而且此問題還涉及各種限制條件[2]，比如機型，飛速，風速，突發(fā)狀況等，導致其帶有有限數(shù)量的可行解。

目前許多學者提出了解決航班調(diào)度的方法，Beasley J E等[3]通過建立混合整數(shù)線性規(guī)劃模型，用分支定界法求解，Hu等人[4]在文獻中采用了基于二進制表達的遺傳算法解決了機場調(diào)度問題，Beasley J E[6]等運用人口啟發(fā)式算法來解決航班調(diào)度問題，Cheng V H L[7]等通過遺傳搜索技術(shù)解決了航班著陸調(diào)度問題，Chou等人[5]采用基于不均等策略的多目標遺傳算法解決了航班著陸安排問題，Xu Xiaohao等[8]和John E[9]都采用模糊算法來對航班調(diào)度問題求解。文中介紹了靜態(tài)航班調(diào)度模型和先來先服務的動態(tài)航班調(diào)度模型，并在此基礎上設計和實現(xiàn)了基于遺傳算法的航班著陸調(diào)度模型。

1 航班著陸調(diào)度模型

1.1 靜態(tài)模型

航班著陸調(diào)度是指針對給定的待降落航班隊列，在滿足各種約束條件的情況下對其中的航班進行排序并且給出一個高效合理的調(diào)度方案，包括著陸的次序和時間。約束條件包括航班的時間窗限制和航班之間的最小安全間隔的限制。

首先每個航班必須在特定的時間窗內(nèi)降落，它由最早降落時間和最遲降落時間決定，最早降落時間是指航班以其最大飛行速度飛行的降落時間，最遲降落時間主要考慮到航班攜帶的燃料量。其次從空氣動力學考慮，任意兩家航班降落之間都應該滿足最小安全時間間隔的約束。如果某個航班在飛行過程中產(chǎn)生大尾流，導致后面離的太緊的航班失去平衡，就可能造成航班事故。航班調(diào)度的約束示意圖如圖1所示。

圖1 航班調(diào)度的約束示意圖Fig.1 Diagram of the flight scheduling

假設有n架航班進入終端區(qū)，TEi代表航班最早到達時間，TLi代表航班最晚到達時間，TAi代表航班實際到達時間，TXi代表航班目標到達時間，Sij代表航班i和航班j降落的最短時間間隔，PUi代表早到或者晚到單位時間的懲罰值，PUS代表總的懲罰值。

由此可知，航班 i的時間窗是[TEi，TLi]，由于實際降落時間要在其時間窗內(nèi)，所以約束條件必須滿足：

對于任意兩個航班，假設航班i在航班j之前降落，則其時間隔約束為：

從給出的時間窗口的角度分析，航班沒有在目標時間到達的，會有懲罰，這個懲罰值就是每分鐘的懲罰值乘以到達的時間與目標時間的間隔，把每架航班的懲罰值加起來就得到了總的懲罰值，也就得到了目標函數(shù)：

1.2 動態(tài)模型

動態(tài)模型是一個離散事件系統(tǒng)（Discrete Event System）模型，只有當一架航班到達終端區(qū)后，航班的排序隊列才會發(fā)生變化。動態(tài)模型對航班隊列進行重排可以分為以下3個步驟：首先，把新的航班加入到已經(jīng)排好的隊列尾端；其次，已經(jīng)到達機場著陸的航班從隊列中刪除；更新后的隊列按照靜態(tài)算法重新排列。

先到先服務模型是一種經(jīng)典的動態(tài)排序模型，其基本思想類似于貪心算法的思想：假設有n架航班，首先根據(jù)這n架航班的目標時間按照從小到大的順序來排序得到航班序列（a1，a2，…，ai，…，an），然后基于先到先服務的思想，則排在第一位的航班就要先到達，并且基于貪心的思想是要讓第一個航班的懲罰值最小，也就是說應讓第一個航班在目標時間準時到達：

下一架航班到達后要考慮它的目標時間和第一架航班的時間間隔，由此得到第二架航班的實際到達時間為：

由此推廣可以得到其他航班的實際降落時間的表達式：

其算法流程圖如圖2所示。

圖2 先來先服務算法的流程圖Fig.2 Flow chart of the first come first service algorithm

2 遺傳算法的設計與實現(xiàn)

目前在航班的調(diào)度問題中，很多智能算法得到了一定的應用。原因是調(diào)度問題本身有很多的限制條件，而且要求解決方案具有較強的時效性和動態(tài)性。而傳統(tǒng)的方法對于這類問題要么是束手無策，要么有很強的局限性而只能給出部分條件下的最優(yōu)解，不具有全局性。遺傳算法是一種應用比較廣泛的智能算法，它是一類借鑒生物界自然選擇和自然遺傳機制的隨機搜索算法，非常適用于組合優(yōu)化等問題。該模型提供了求解非線性規(guī)劃問題的通用框架，從隨機產(chǎn)生的通用解開始搜索，通過一定規(guī)則的選擇、交叉和變異操作逐步迭代以產(chǎn)生新的解。群體中的每個個體代表問題的一個解，稱為染色體，染色體的好壞通過適應度值來衡量，根據(jù)適應的好壞從上一代中選擇一定數(shù)量的優(yōu)秀個體，通過交叉變異形成下一代個體。經(jīng)過若干代的進化之后算法收斂于最好的染色體。系統(tǒng)的遺傳算法的簡化流程如圖3所示。

圖3 遺傳算法的流程圖Fig.3 Flow chart of the genetic algorithms algorithm

2.1 編碼方法

由于遺傳算法不能直接處理問題空間的參數(shù)，因此必須通過編碼把所求問題的可行解表示為遺傳空間的染色體或者個體。其編碼方法分為二進制編碼方法，整數(shù)編碼方法，實數(shù)編碼方法和一般數(shù)據(jù)結(jié)構(gòu)編碼方法?；诤桨嗾{(diào)度問題的特點，采用實數(shù)編碼方法即數(shù)字序號編碼方法。每架航班bi代表一個基因值i，各航班序號排列成一個序列，即代表一種調(diào)度方案。如染色體2 3 1 6 4 5，代表航班 2為第一個著陸，3，1，6，4，5依次著陸。 此編碼方法中實數(shù)代表個體基因型，航班的序列代表個體的表現(xiàn)型，兩者是一一對應關(guān)系。

2.2 適應度函數(shù)

問題求解的目標函數(shù)與適應度函數(shù)一般有一定的關(guān)系。航班著陸調(diào)度問題是求目標函數(shù)的最小值，因此將函數(shù)的倒數(shù)作為個體的適應度值。目標函數(shù)值越小的個體其適應度越大，個體越優(yōu)。因此染色體x對應的適應度函數(shù)為：

i=1

2.3 遺傳算子

2.3.1 選擇算子

選擇操作是從上一級的數(shù)據(jù)中以一定的概率選擇優(yōu)良個體組成新的種群，并且繁殖得到下一代個體，其目的是使對生存環(huán)境適應度高的物種將有更多機會將優(yōu)良基因復制到下一代，文中采用Holland提出的具有隨機采樣特點的輪盤賭選擇。其原理是如果某個個體i的適應度為Fi，那么其被選擇的概率為：

2.3.2 交叉算子

交叉操作是指從種群中隨機選擇兩個個體，通過給染色體的交換組合，把父代的優(yōu)秀特征傳給子串，從而產(chǎn)生新的優(yōu)秀個體。由于個體采用實數(shù)編碼，所以交叉操作采用實數(shù)交叉法。先產(chǎn)生0到1的隨機數(shù)b，則第k個染色體ak和第l個染色體a1在j位的交叉操作方法為：

2.3.3 變異算子

變異操作是為了改善遺傳算法的局部搜索能力，避免陷入局部最優(yōu)解，同樣是保持群體多樣性的重要手段。從種群中隨機選取一個個體，選擇個體中的一點進行變異操作，以便產(chǎn)生更加優(yōu)秀的個體。amax是基因aij的上界，amin是aij的下界，f （g）=r2* （1-g/Gmax）2，r2是一個隨機數(shù)，g 是當前的迭代次數(shù)，Gmax是最大進化次數(shù)，r為0到1區(qū)間產(chǎn)生的隨機數(shù)。第i個個體的第j個基因進行變異操作的方法為：

2.4 約束條件的處理

由于航班著陸調(diào)度受到航班的時間窗限制和航班之間的最小安全間隔的限制。文中采用罰函數(shù)處理約束條件[10]。由于航班i與航班j的最小著陸間隔為Sij，我們采用增加延誤時間作為罰函數(shù)，對不滿足約束條件的航班增加2Sij的延誤。設航班i的原本延誤時間為Li，若不滿足約束條件，則罰后的延誤時間為 Li’，Z代表符合約束條件的集合，則:

2.5 非線性尋優(yōu)

遺傳算法每進行一定的代數(shù)以后，以所得到的結(jié)果為初始值，采用Matlab2012優(yōu)化工具箱里的線性規(guī)劃函數(shù)fmincon進行局部的尋優(yōu)，并將尋到的局部最優(yōu)值作為新個體的染色體繼續(xù)優(yōu)化。

3 仿真結(jié)果與分析

采用Matlab2012編寫遺傳算法程序，以10架航班時刻表（表1）為原始數(shù)據(jù)，采用了傳統(tǒng)的先到先服務（FCFS）算法和本文的遺傳算法進行測試和計算，得出實際到達時間以及懲罰費用，并對其進行分析。根據(jù)計算，采用FCFS算法計算出的懲罰費用為1 210元，而采用遺傳算法通過設置不同的參數(shù)經(jīng)過多次網(wǎng)絡培訓之后，得到最優(yōu)的一組解，其損失費用為823元。算法的個體數(shù)目為20，最大遺傳代數(shù)為100，代溝為0.95，交叉概率為0.5，變異概率為0.02，分配適應度為函數(shù)值的倒數(shù)，訓練10次。得到的遺傳進化曲線圖如圖4所示，仿真結(jié)果如表1所示。

圖4 遺傳進化曲線圖Fig.4 Diagram of the genetic evolution

表1 仿真結(jié)果表Tab.1 Chart of simulation results

從仿真結(jié)果可以看出，采用遺傳算法能夠很好滿足航班調(diào)度之間的約束條件，與傳統(tǒng)的FCFS方法的調(diào)度結(jié)果相比，其懲罰總費用明顯減少?？梢娫撍惴ㄔ诩s束條件下得到了損失費用相當少的多種優(yōu)化方案，這就為工作人員在其他的約束條件下提供了更多的選擇，從而有利于該模型的推廣，具有更廣的使用空間。

4 結(jié) 論

文中對航班著陸調(diào)度問題進行了探討和分析，并采用遺傳算法通過Matlab2012編程對其進行求解。仿真結(jié)果表明采用遺傳算法進行優(yōu)化，能夠在滿足約束條件下給出有效合理的次序和時間，相對傳統(tǒng)先到先服務算法，明顯減少了懲罰費用和延誤時間。此算法設計合理，實現(xiàn)簡單，能適應不同的約束情況，具有很高的實用價值。

[1]程曉航，薛惠鋒，洪鼎松，等.進港航班調(diào)度的精華自適應遺傳算法[J].交通與計算機，2006，24（6）:91-94.

CHENG Xiao-hang，XUE Hui-feng，HONG Ding-song，et al.Design of elitist adaptive genetic algorithm in arrival aircrafts schedul ing[J].Computer and Communication，2006，24（6）:91-94.

[2]張偉，王宏.求解機場終端區(qū)航班著陸調(diào)度問題的遺傳算法[J].計算機工程與應用，2012，48（12）:229-232.

ZHANG Wei，WANG Hong.Genetic algorithm on scheduling aircraft landing in aircraft terminal area[J].Computer Engineering and Applications，2012，48（12）:229-232.

[3]Beasley J E，Krishnamoorthy M，Sharaiha Y M，et al.Scheduling aircraft landings the static case[J].Transport Science，2000（34）:180-197.

[4]HU Xiao-Bing，Di P E.Binary-representation-based genetic algorithm for aircraft arrival sequencing and scheduling[J].IEEE Trans on Intelligent Transportation System，2008，9（2）:301-310.

[5]Chou Ta-Yuan，Liu Tung-Kuan，Lee Chung-Nan，etal.Method of inequality-based multi objective genetic algorithm for do-mestic daily aircraft routing[J].IEEE Trans on Systems，Man， and Cybernetics A:Systems and Humans，2008，38（2）:299-308.

[6]Beasley J E，Sonander J，Havelock P.Scheduling aircraft landings at London Heathrow using a population heuristic[J].Journal of the Operational Research Society，2001（52）:483-493.

[7]Cheng V H L，Crawford L S，Menon P K.Air traffic control using genetic search techniques[C]//Proceedings of the 1999 IEEE International Conference on Lontrol Applications，1999（1）:249-254.

[8]XU Xiao-hao，HUANG Ba-jun.Study of fuzzy integrated judge method applied to the aircraft sequencing in the terminal area[J].Acta Aeronautica et Astronautica Sinica，2001，22（3）:259-261.

[9]John E.Fuzzy reasoning-based sequencing of arrival aircraft in the terminal area[C]//AIAA Guidance，Navigation and Control Conference， New Orleans， LA，1997:1-11.

[10]玄光男，程潤偉.遺傳算法與工程優(yōu)化[M].北京：清華大學出版，2002:26-29.