基于協(xié)同進(jìn)化遺傳算法的航班進(jìn)港優(yōu)化調(diào)度

張 勰，趙嶷飛，劉宏志

（中國民航大學(xué)天津市空管運(yùn)行規(guī)劃與安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津300300）

基于協(xié)同進(jìn)化遺傳算法的航班進(jìn)港優(yōu)化調(diào)度

張 勰＊，趙嶷飛，劉宏志

（中國民航大學(xué)天津市空管運(yùn)行規(guī)劃與安全技術(shù)重點(diǎn)實(shí)驗(yàn)室，天津300300）

航班進(jìn)港調(diào)度問題是一個(gè)典型的組合優(yōu)化問題，具有多約束復(fù)雜特性.針對遺傳算法求解航班進(jìn)港調(diào)度問題時(shí)多約束難以處理、運(yùn)算量大、易陷入局部最優(yōu)的不足，本文應(yīng)用協(xié)同進(jìn)化思想，構(gòu)建航班進(jìn)港調(diào)度問題決策解種群和懲罰因子種群，通過種群間的競爭、協(xié)作改善算法性能；設(shè)計(jì)一種帶約束處理的編碼策略，將安全間隔約束納入編碼過程，降低了問題的約束復(fù)雜度，進(jìn)而提出一種改進(jìn)的協(xié)同進(jìn)化遺傳算法(Co-evolutionary Genetic Algorithm，CoGA)，并應(yīng)用首都機(jī)場的實(shí)際運(yùn)行數(shù)據(jù)進(jìn)行了仿真.結(jié)果表明，本文方法能夠有效處理航班進(jìn)港調(diào)度問題中的大量約束，在優(yōu)化效果與GA算法相當(dāng)?shù)那闆r下，有效降低了計(jì)算時(shí)間，克服了問題規(guī)模劇增導(dǎo)致的計(jì)算效率低下的難題.

航空運(yùn)輸；協(xié)同進(jìn)化；遺傳算法；航班進(jìn)港調(diào)度；空中交通流量管理

1 引 言

空中交通流量管理是保障航空運(yùn)輸安全、高效、流暢運(yùn)行的重要手段.航班進(jìn)港調(diào)度作為空中交通流量管理的核心問題之一，其目的在于為機(jī)場附近等待降落的航班安排合理的著陸順序和著陸時(shí)刻，在確保安全的前提下提高航班進(jìn)港運(yùn)行效率[1].

航班進(jìn)港調(diào)度問題是一個(gè)典型的組合優(yōu)化問題，具有多約束復(fù)雜特性，而優(yōu)化調(diào)度中對算法實(shí)時(shí)性的要求使得該問題的求解難度進(jìn)一步增加.目前實(shí)際運(yùn)行中先到先服務(wù)方法應(yīng)用最為廣泛.雖然簡單、易用且公平，但由于忽略了眾多有用的信息與條件，導(dǎo)致先到先服務(wù)方法實(shí)際運(yùn)行效率低、靈活性差.隨著航空運(yùn)輸業(yè)的蓬勃發(fā)展，特別是進(jìn)入21世紀(jì)以來，航班進(jìn)港調(diào)度問題得到了越來越多各國學(xué)者的關(guān)注，紛紛開展相關(guān)研究[2-15].Coumba等提出了基于時(shí)間窗口的著陸航班調(diào)度方法[2]. Beasley等學(xué)者建立了航班進(jìn)港調(diào)度問題的線性規(guī)劃模型，提出了一種基于混合整數(shù)線性規(guī)劃的樹搜索算法以解決靜態(tài)航班調(diào)度問題[3].也有學(xué)者采用分支界定法[4]、模糊規(guī)劃方法[5]對該調(diào)度問題進(jìn)行求解.Dear提出約束位置交換（Constrained Position Shifting,CPS）概念，規(guī)定優(yōu)化前后單架航班在隊(duì)列中的位置變動(dòng)不能超過某一固定范圍[6].CPS思想使得調(diào)度結(jié)果易于管制員操作，并可以縮小搜索空間，加快搜索速度.之后Balakrishnan等人建立了基于CPS的網(wǎng)絡(luò)圖，提出了一種動(dòng)態(tài)規(guī)劃算法，并采用實(shí)際運(yùn)行數(shù)據(jù)進(jìn)行了仿真，取得了較好的效果[7,8].朱星輝等構(gòu)建了該問題的網(wǎng)絡(luò)流模型，并采用約束編程方法對模型進(jìn)行了求解[9].

航班進(jìn)港調(diào)度問題是一個(gè)典型的NP-hard問題[10].線性規(guī)劃算法缺乏全局搜索能力，很多情況下難以找到最優(yōu)解[11].計(jì)算智能方法由于具備很強(qiáng)的全局尋優(yōu)能力，近年來被廣泛應(yīng)用于解決航班進(jìn)港調(diào)度問題[10-19].Ciesielski和Scerri采用標(biāo)準(zhǔn)遺傳算法和帶滑動(dòng)窗的遺傳算法求解動(dòng)態(tài)航班調(diào)度問題[10,12].Pinol將散布算法和生態(tài)算法應(yīng)用于解決多跑道航班調(diào)度問題[13].Zhan等學(xué)者提出了基于滾動(dòng)時(shí)域控制思想的蟻群算法，該算法具有很強(qiáng)的全局搜索能力[14].王世東等將降落過程建模成單機(jī)多目標(biāo)規(guī)劃問題，并利用蟻群算法進(jìn)行了求解[15].此外，模擬退火算法[16]、免疫粒子群算法[17]、Memetic算法[18]、人工魚群算法[19]也被用于求解此問題.雖然計(jì)算智能方法相較線性規(guī)劃方法擁有更佳的全局搜索性能，但航班進(jìn)港調(diào)度問題對于算法實(shí)時(shí)性的要求很高，上述計(jì)算智能方法由于計(jì)算代價(jià)過大，特別是在機(jī)場高峰運(yùn)行時(shí)段，往往無法在合理的時(shí)間范圍內(nèi)給出調(diào)度方案，因而需要改進(jìn)算法性能，如結(jié)合啟發(fā)式知識，提高計(jì)算效率，以更好地應(yīng)對航班進(jìn)港調(diào)度問題.

遺傳算法是一種模擬生物自然進(jìn)化過程與機(jī)制的智能計(jì)算方法，具有并行性、魯棒性強(qiáng)等優(yōu)點(diǎn)，已在自動(dòng)控制、組合優(yōu)化、圖像處理、函數(shù)優(yōu)化及生產(chǎn)調(diào)度問題等領(lǐng)域得到廣泛應(yīng)用.雖然較傳統(tǒng)方法具有諸多優(yōu)勢，但標(biāo)準(zhǔn)遺傳算法存在收斂速度慢、易早熟等不足，并且在處理約束優(yōu)化問題時(shí)往往難以取得理想的效果[20].本文應(yīng)用協(xié)同進(jìn)化思想，構(gòu)建航班進(jìn)港調(diào)度問題決策解種群和懲罰因子種群，通過種群間的競爭、協(xié)作改善算法性能；設(shè)計(jì)一種帶約束處理的編碼策略，將安全間隔約束納入編碼過程，降低了問題的約束復(fù)雜度，進(jìn)而提出一種改進(jìn)的協(xié)同進(jìn)化遺傳算法(Co-evolutionary Genetic Algorithm，CoGA)來解決航班進(jìn)港調(diào)度問題.

2 問題描述

航班進(jìn)港調(diào)度是對機(jī)場附近臨近降落的航班隊(duì)列進(jìn)行順序和時(shí)間上的優(yōu)化，從而得到高效的航班著陸次序與時(shí)刻，以達(dá)到減小飛行延誤、提高跑道吞吐量和飛行安全的目的.調(diào)度過程需要考慮諸多限制因素，例如兩架航班間的安全間隔取決于其相對位置及機(jī)型，不同的降落順序?qū)?dǎo)致不同的運(yùn)行成本.因此，航班進(jìn)港調(diào)度問題可以描述為，對于準(zhǔn)備在某一機(jī)場降落的航班集合與機(jī)場跑道集合，已知航班的預(yù)計(jì)降落時(shí)間、降落時(shí)間窗、機(jī)型等信息，在滿足一系列約束的情況下給出一個(gè)合理的調(diào)度方案，該方案包括航班隊(duì)列的降落順序和每架航班的降落時(shí)間.顯然，航班進(jìn)港調(diào)度是一類大規(guī)模優(yōu)化問題.

2.1 優(yōu)化目標(biāo)

安全運(yùn)行的前提下，經(jīng)濟(jì)效益是航班進(jìn)港調(diào)度中的重要考量因素.航班提前或者延誤都會(huì)帶來額外的開銷，相等的時(shí)間提前量或延誤量，由于機(jī)型或優(yōu)先級別的不同，所造成的經(jīng)濟(jì)損失也不相同.為此，引入提前/延誤代價(jià)系數(shù)和航班的優(yōu)先級系數(shù)計(jì)算總損失，并將航班隊(duì)列的總額外代價(jià)作為優(yōu)化目標(biāo).對于航班集合F，有

式中 DTi=STAi-ETAi為航班i的優(yōu)化降落時(shí)間與預(yù)計(jì)降落時(shí)間之差，表示航班i優(yōu)化前后的時(shí)間差；PCi表示航班i的優(yōu)先級系數(shù)；ACi與DCi分別表示航班i提前代價(jià)系數(shù)與延誤代價(jià)系數(shù)；C為單位延誤成本.

2.2 約束條件

2.2.1 安全間隔約束

從空氣動(dòng)力學(xué)角度，所有飛機(jī)都會(huì)在其后部產(chǎn)生尾流.通常較大的機(jī)型所產(chǎn)生的尾流也較大，這對尾隨飛行的飛機(jī)非常危險(xiǎn)，甚至?xí)?dǎo)致飛行事故.因此，為保證飛行安全，任意兩架飛機(jī)之間的時(shí)間間隔必須滿足安全飛行需要的最低限度.國際民航組織對不同類型飛機(jī)間的最小尾流安全間隔做出了規(guī)定，如表1所示.

表1最小安全間隔（單位：秒）Table 1 Minimum safe separation(in seconds)

本約束旨在保證降落過程中任意兩架航班之間的間隔需求，若航班i早于航班 j降落，則

2.2.2 降落時(shí)間窗約束

受飛行性能和進(jìn)場程序等條件限制，航班只能在特定降落時(shí)間窗內(nèi)降落在跑道上，如式(3)，式中ETAi-TAmax為最早著陸時(shí)間，ETAi+TDmax為最晚著陸時(shí)間.此外，航班還可進(jìn)行空中盤旋等待，因此降落時(shí)間窗擴(kuò)展為若干個(gè)離散時(shí)間段，如式(4).

式中 N表示盤旋圈數(shù)；Th為航班在空中盤旋一周所需的平均時(shí)間.

2.2.3 CPS約束

考慮到管制員工作負(fù)荷和運(yùn)行安全，Dear指出[6]，降落調(diào)度中過大的位置調(diào)整在管制運(yùn)行中是不實(shí)際的，即調(diào)度前后航班位置的變動(dòng)幅度不能超過一定的范圍.例如最大位置偏移量為2，若某架航班在先到先服務(wù)的隊(duì)列中排在第5位，則它在新隊(duì)列中只能占據(jù)第3，4，5，6，7位.這不僅保證了一定的公平性，還可極大地縮小解空間.

設(shè)k為最大位置偏移量，航班i在初始隊(duì)列中的位置為Ai，在新隊(duì)列中的位置為A*i，則

2.2.4 進(jìn)近航線約束

航班進(jìn)港優(yōu)化調(diào)度是通過調(diào)整航班序列來縮小延誤的，即改變航班的前后位置，因而會(huì)發(fā)生航班超越的情況.而在實(shí)際運(yùn)行中，由于終端區(qū)空域自由度低、冗余度小，除非必要，否則應(yīng)盡可能避免大范圍的調(diào)整，尤其是同航線航班后機(jī)超越前機(jī)情形，因?yàn)檫@不但會(huì)增加運(yùn)行成本，而且也會(huì)增大管制員工作負(fù)荷，甚至降低運(yùn)行安全.

為此，引入進(jìn)近航線約束旨在航班優(yōu)化調(diào)度過程中，為屬于同一進(jìn)近航線上的航班建立先到先服務(wù)法則，即航班位置交換只發(fā)生在所屬不同進(jìn)近航線之間的航班，在保證優(yōu)化調(diào)度方案有效性的同時(shí)，提高調(diào)度方案的可操作性.式(6)表明同航線航班不得發(fā)生超越行為.用ARi表示航班i所處的進(jìn)近航線，若ARi=ARj，則

3 求解算法

3.1 算法的基本原理

航班進(jìn)港調(diào)度問題是一個(gè)多約束、高動(dòng)態(tài)的非線性系統(tǒng)的組合優(yōu)化問題，如何高效處理約束并快速求解是研究的難點(diǎn)[21].

遺傳算法是目前解決大規(guī)模組合優(yōu)化問題常采用的智能算法，該算法模擬自然遺傳過程中的繁殖、雜交、突變等現(xiàn)象，通過選擇、交叉、變異等作用機(jī)制優(yōu)化種群，具有很強(qiáng)的全局搜索能力.傳統(tǒng)遺傳算法適合求解無約束優(yōu)化問題，而對于約束優(yōu)化問題，由于進(jìn)化過程中會(huì)出現(xiàn)不可行解，因而必須采取新的方法來解決.

罰函數(shù)法[22-24]是求解約束優(yōu)化問題常用的方法.罰函數(shù)的一般形式為

式中 Gi(x)和Hi(x)分別表示優(yōu)化問題中個(gè)體違反第i個(gè)不等式約束和等式約束的程度，ri和si分別表示相應(yīng)的懲罰因子.

通過調(diào)整懲罰因子平衡目標(biāo)與約束，是罰函數(shù)方法處理約束優(yōu)化問題的重要手段，但懲罰因子的選擇往往比較困難.若懲罰因子選擇過大，將導(dǎo)致優(yōu)化曲面變得異常復(fù)雜，加之無法利用不可行解提供的有用信息，算法很容易陷入局部最優(yōu)，很難找到全局最優(yōu)解；若懲罰因子選擇過小，則很可能收斂到不可行域.

鑒于此，本文提出基于協(xié)同進(jìn)化的遺傳算法.協(xié)同進(jìn)化遺傳算法包含航班進(jìn)港調(diào)度問題決策解和懲罰因子兩類種群.算法不僅考慮了兩類種群內(nèi)部個(gè)體之間的協(xié)作與競爭，還充分考慮了兩類種群之間在進(jìn)化過程中的協(xié)同影響與相互作用，如在進(jìn)行個(gè)體評價(jià)時(shí)，需要利用其它種群的個(gè)體信息.CoGA算法通過兩類種群的協(xié)同進(jìn)化，自適應(yīng)地調(diào)整懲罰因子，并得到航班進(jìn)港調(diào)度問題的最優(yōu)解.

航班進(jìn)港調(diào)度問題的CoGA算法中包含兩類種群，一類是用于進(jìn)化決策解的種群X，此類種群包含M1個(gè)子種群Xj( j=1,2,…,M1)，子種群規(guī)模為M2，種群中的個(gè)體xi(i =1,2,…,M1×M2)表示航班調(diào)度問題的決策解；另一類種群是懲罰因子種群Y，其種 群規(guī) 模 為 M1，種 群 中 的 個(gè) 體yj( j=1,2,…,M1)用于表征Xj中個(gè)體所對應(yīng)的懲罰因子.決策解子種群Xj中的每個(gè)個(gè)體利用對應(yīng)的yj所表示的懲罰因子對該子種群的適應(yīng)度函數(shù)進(jìn)行計(jì)算，并進(jìn)行遺傳操作，進(jìn)化t1代后獲得新決策解子種群；根據(jù)決策解子種群Xj中所有解的優(yōu)劣信息，對種群Y中個(gè)體yj，即懲罰因子的優(yōu)劣進(jìn)行評價(jià)；并對懲罰因子種群Y進(jìn)行遺傳操作，獲得下一代懲罰因子種群.在每一代協(xié)同進(jìn)化完成后，決策解子種群Xj采用新一代懲罰因子種群Y進(jìn)行種群適應(yīng)值計(jì)算，直到滿足算法終止條件.最后通過比較所有歷史最優(yōu)解作為航班調(diào)度問題的解，同時(shí)，種群Y中所對應(yīng)的最優(yōu)個(gè)體即為最佳懲罰因子.

3.2 編碼方法

遺傳算法的編碼方式是設(shè)計(jì)遺傳算法的關(guān)鍵.航班進(jìn)港調(diào)度問題約束數(shù)量巨大，求解困難，因此，對基于降落時(shí)間的編碼方式進(jìn)行改進(jìn)，提出一種帶約束處理的編碼方式，有利于降低約束復(fù)雜度.

對于航班降落時(shí)間序列(S TA1,STA2,…,STAn)，其降落順序表示為(s1,s2,…,sn)，是(1 ,2,…,n)的一個(gè)排列；相鄰航班的降落時(shí)間差為(d1,d2,…,dn)，其中di=STAsi-STAsi-1.用C=(S ,D)表示染色體，即(s1,s2,…,sn,d1,d2,…,dn).由于需要滿足最小安全間隔 di-MSSsisi-1≥0,(i =1,2,…,n)，則染色體可以重新表示為C=(S ,V )，即(s1,s2,…,sn,v1,v2,…,vn)，其中vi=di-MSSsisi-1，V=(v1,v2,…,vn).令

式(8)還可以進(jìn)一步寫成

通過這種帶約束處理的編碼策略，將安全間隔約束納入編碼過程，成功地降低了航班進(jìn)港調(diào)度問題中的約束復(fù)雜度.

3.3 決策個(gè)體的適應(yīng)度函數(shù)

式(7)罰函數(shù)中僅包含個(gè)體違反約束的程度，對于違反約束程度相等的兩個(gè)個(gè)體，其違反約束的數(shù)量可能不同，實(shí)際上違反約束數(shù)量較少的個(gè)體可能離可行域更近一些.因此，罰函數(shù)同時(shí)是個(gè)體違反約束程度與違反約束數(shù)量的函數(shù)，其優(yōu)化效果要更好[20].考慮到上述情況，決策種群中個(gè)體xi的適應(yīng)度函數(shù)為越小，則P() yj越小，量.易知，

式中 f() xi表示航班調(diào)度優(yōu)化問題的目標(biāo)函數(shù)；q(xi)是個(gè)體xi違反約束的程度；n(xi)是個(gè)體違反約束的數(shù)量；ω1和ω2分別是Y種群中個(gè)體yj所對應(yīng)的懲罰因子.

3.4 懲罰因子的適應(yīng)度函數(shù)

（1）若Xj中包含至少一個(gè)可行解，則yj為有效個(gè)體，適應(yīng)度函數(shù)為有利于算法向著違反約束程度較低和違反約束數(shù)量較少的方向進(jìn)化.

3.5 交叉變異

由于固定比率的交叉與變異操作易導(dǎo)致算法早熟，因此，本文應(yīng)用一種自適應(yīng)方法調(diào)節(jié)交叉率與變異率值.

式中 λ=Fmax-F，用以表示早熟程度；Fmax表示種群中個(gè)體最大的適應(yīng)值；F表示大于種群個(gè)體平均適應(yīng)值的所有個(gè)體適應(yīng)值的均值.

3.6 CoGA算法流程

航班進(jìn)港調(diào)度問題中兩類種群采用相同的遺傳操作，具體算法流程如圖1所示.

步驟1初始化決策解種群X，t1=0，初始化懲罰因子種群Y，t2=0；

步驟2X種群適應(yīng)值評價(jià)；

步驟3Y種群適應(yīng)值評價(jià)；

步驟4Y種群遺傳操作；

步驟5到達(dá)Y種群極值則更新Y種群，轉(zhuǎn)步驟6；否則t2=t2+ 1，轉(zhuǎn)步驟3；

步驟6對各決策解子種群，分別以相應(yīng)懲罰因子種群中的個(gè)體作為懲罰因子，并進(jìn)行遺傳操作，更新決策解種群；

式中 NXj表示Xj中所有可行解的總數(shù)，其適應(yīng)值之和為.從式(11)可知，可行解數(shù)量越多或適應(yīng)值之和越大，則P() yj越小，有利于算法向著可行解多且目標(biāo)值好的區(qū)域進(jìn)化.

（2）若Xj中無可行解，則yj為無效個(gè)體，適應(yīng)度函數(shù)為

圖1 CoGA算法流程Fig.1 The framework of CoGA algorithm

步驟7若滿足算法終止條件，輸出最優(yōu)解；否則t1=t1+ 1，t2= 0轉(zhuǎn)步驟2.

4 仿真實(shí)驗(yàn)與分析

為證明本文協(xié)同進(jìn)化遺傳算法的有效性，對北京首都國際機(jī)場某日某時(shí)段內(nèi)25架航班進(jìn)港數(shù)據(jù)進(jìn)行仿真驗(yàn)證，并將本算法與標(biāo)準(zhǔn)遺傳算法、先到先服務(wù)算法進(jìn)行對比.CoGA算法的參數(shù)設(shè)置如下：懲罰因子種群規(guī)模M1=50，決策解子種群規(guī)模M2=100，決策種群迭代步數(shù)T1=100，懲罰因子種群迭代步數(shù)T2=100，種群初始交叉率Pc=0.8，初始變異率Pm=0.1.

表2給出了三種算法的調(diào)度結(jié)果，前五列分別為航班號、航班所屬航線、機(jī)型、優(yōu)先級和預(yù)計(jì)降落時(shí)間.后續(xù)幾列給出分別使用先到先服務(wù)算法、標(biāo)準(zhǔn)遺傳算法（k=2）、協(xié)同進(jìn)化遺傳算法（k=1,2,3）求解得到的降落順序和優(yōu)化降落時(shí)間.表3給出了三種算法的總額外代價(jià)與計(jì)算時(shí)間，從表中可知，優(yōu)化算法結(jié)果明顯優(yōu)于先到先服務(wù)方法.

與先到先服務(wù)方法相比，GA算法的總額外代價(jià)降低了17.6%；CoGA算法在k=1,2,3時(shí)，總額外代價(jià)分別降低了16.7%、18.9%和20.4%.顯然，當(dāng)k值越大，優(yōu)化效果越好.原因在于，當(dāng)航班可交換位置的約束越寬松，算法則越有可能給出符合約束條件的更好的優(yōu)化序列.

另一方面，隨著k值的增大，計(jì)算時(shí)間也隨之增加，GA算法在k=2時(shí)計(jì)算時(shí)間接近10 min，無法在短時(shí)間內(nèi)得到優(yōu)化解，很難應(yīng)用于實(shí)際；CoGA算法在k=1,2,3時(shí)，計(jì)算時(shí)間分別為33 s、56 s和189 s，完全能夠滿足實(shí)時(shí)調(diào)度的需求.由于FCFS方法無優(yōu)化過程，僅作為總額外代價(jià)優(yōu)化效果的對比基準(zhǔn)，因此其計(jì)算時(shí)間為0.

圖2給出了GA算法與CoGA算法在k=2時(shí)的收斂性能.CoGA算法大約進(jìn)化到20代左右時(shí)，適應(yīng)度函數(shù)基本不變，算法收斂；而GA算法則需要大約50代左右才基本收斂.

表2 原始數(shù)據(jù)與算法仿真結(jié)果（單位：s）Table 2 Original data and simulation results(in seconds)

表3 三種算法的總額外代價(jià)與計(jì)算時(shí)間Table 3 Statistic results of FCFS,GA and CoGA algorithms

為分析不同規(guī)模下CoGA算法的有效性及效率，對航班數(shù)量規(guī)模分別為10、20、30、40架的數(shù)據(jù)進(jìn)行仿真，每種規(guī)模下隨機(jī)產(chǎn)生100個(gè)先到先服務(wù)航班隊(duì)列，對這100個(gè)隊(duì)列進(jìn)行優(yōu)化調(diào)度，并統(tǒng)計(jì)優(yōu)化結(jié)果，取其平均值進(jìn)行比較分析，如表4所示.

圖2 總額外代價(jià)隨進(jìn)化代數(shù)的變化Fig.2 Total costs variations with evolution generation

表4 不同規(guī)模下總額外代價(jià)最小優(yōu)化結(jié)果Table 4 Optimal results of minimum total costs under various scales

由表4可知，CoGA算法優(yōu)化效果隨航班數(shù)量增加有小幅提升，這是由于當(dāng)航班數(shù)量較少時(shí)，其相對于大量航班的可優(yōu)化空間亦相對較小.雖然在不同的k值下運(yùn)算時(shí)間有比較明顯的差別，但即使是40架航班、k=2時(shí)平均用時(shí)也僅為131.53 s，遠(yuǎn)優(yōu)于GA的10 min（25架航班，k=2）.

綜上所述，對于多約束的航班進(jìn)港調(diào)度問題，雖然GA算法全局搜索能力很強(qiáng)，但處理大量約束時(shí)依然存在很大局限，而本文設(shè)計(jì)的帶約束處理的編碼策略和協(xié)同進(jìn)化算法可以有效處理問題中的大量約束，使得CoGA算法能夠有效地解決航班進(jìn)港調(diào)度問題，在優(yōu)化效果與GA算法相當(dāng)?shù)那闆r下，有效降低計(jì)算時(shí)間，克服問題規(guī)模劇增導(dǎo)致的計(jì)算效率低下的難題.

5 研究結(jié)論

航班進(jìn)港優(yōu)化調(diào)度問題是空中交通管理系統(tǒng)關(guān)注和研究的熱點(diǎn)問題，其實(shí)時(shí)性要求和多約束處理是優(yōu)化求解的關(guān)鍵.本文構(gòu)建了進(jìn)港航班調(diào)度模型，并應(yīng)用改進(jìn)的協(xié)同進(jìn)化遺傳算法進(jìn)行了求解.通過一種帶約束處理的編碼策略，降低了問題的約束復(fù)雜度，并通過種群間的競爭、協(xié)作改善算法性能.仿真結(jié)果表明，改進(jìn)后的CoGA算法在航班進(jìn)港優(yōu)化調(diào)度上取得了較好的結(jié)果，同時(shí)運(yùn)算時(shí)間較快，能夠滿足實(shí)際應(yīng)用需要，為多約束、高動(dòng)態(tài)的航班調(diào)度問題的求解提供了一條新的途徑.

隨著航空運(yùn)輸業(yè)的快速發(fā)展，空中交通流量、航班數(shù)量與跑道數(shù)量迅速增加，對運(yùn)行效率的需求越來越高.應(yīng)用CoGA算法對50架航班、4跑道、k=3規(guī)模下的調(diào)度問題進(jìn)行求解時(shí)，由于解空間急劇膨脹，總額外代價(jià)的運(yùn)算量大幅上升，雖然算法依然能夠給出優(yōu)化結(jié)果，但計(jì)算時(shí)間接近12 min，需要加入其它優(yōu)化策略以進(jìn)一步提升運(yùn)算速度，這有待后續(xù)研究努力解決.

參考文獻(xiàn)

[1]Andreussi A,Bianco L,Ricciardelli S.A simulation mod?el for aircraft sequencing in the near terminal area[J]. European Journal of Operational Research,1981,8(4): 345-354.

[2]Coumba D,Babacar M,Diaraf S.Scheduling aircraft landings at LSS airport[J].American Journal of Opera?tions Research,2012,2(2):235-241.

[3]Beasley J E,Krishnamoorthy M,Sharaiha Y M.Schedul?ing aircraft landings-the static case[J].Transportation Science.2000,34(2):180-197.

[4]Stiverson P,Rathinam S.Heuristics for a runway-queue management problem[J].Journal of Aerospace Engineer?ing,2011,225(5):481-499.

[5]Reza T,Mojtaba Y,Farzad R.Scheduling the sequence of aircraft landings for a single runway using a fuzzy pro?gramming approach[J].Journal of Air Transport Manage?ment,2012,25:15-18.

[6]Dear R G.The dynamic scheduling of aircraft in the near terminal area[R].M.I.T,Flight Transportation Laboratory Report,R76-9,1976.

[7]Balakrishnan H,Chandran B.Scheduling aircraft land?ings under constrained position shifting[C]//AIAA Guid?ance,Navigation,and Control Conference and Exhibit. Keystone,Colorado,USA,2006:21-24.

[8]LEE H,Balakrishnan H.Fuel cost delay and throughput tradeoffs in runway scheduling[C]//Proceedings of the American Control Conference.Seattle,USA,2008:2449-2454.

[9]朱星輝，朱金福，高強(qiáng).基于約束編程的飛機(jī)排班問題研究[J].交通運(yùn)輸系統(tǒng)工程與信息,2011,11(6):151-156．[ZHU X H,ZHU J F,GAO Q.Aircraft scheduling based on constraint programming[J].Journal of Transpor?tation Systems Engineering and Information Technology, 2011,11(6):151-156.]

[10]Ciesielski V,Scerri P.An anytime algorithm for schedul?ing of aircraft landing times using genetic algorithms[J]. Australian Journal of Intelligent Information Processing Systems.1997,4(3):206-213.

[11]Cao Y,and Sun D.Greedy-heuristic-aided mixed-inte?ger linear programming approach for arrival scheduling [J].Journal of Aerospace Information Systems,2013,10 (7):323-336.

[12]Ciesielski V,Scerri P.Real time genetic scheduling of aircraft landing times[C]//Proceedings of the IEEE Con?ference on Evolutionary Computation.Anchorage,USA, 1998:360-364.

[13]Pinol H,Beasley J E.Scatter search and bionomic algo?rithms for the aircraft landing problem[J].European Journal of Operational Research.2006,171(2):439-462.

[14]Zhan Z H,Zhang J,Li Y.An efficient ant colony system based on receding horizon control for the aircraft arrival sequencing and scheduling problem[J].IEEE Transac?tions on Intelligent Transportation Systems.2010,11(2): 399-412.

[15]王世東，張?jiān)剑瑥堉呛?，?繁忙機(jī)場航班降落排序的多目標(biāo)優(yōu)化[J].交通運(yùn)輸系統(tǒng)工程與信息,2012,12 (4):135-142.[WANG S D,ZHANG Y,ZHANG Z H,et al.Multi-objectives optimization on flights landing sequence at busy airport[J].Journal of Transportation Systems Engineering and Information Technology,2012, 12(4):135-142]

[16]Tian J,Xu H.Optimizing arrival flight delay scheduling based on simulated annealing algorithm[C].Physics Procedia,2012,33:348-353.

[17]馮興杰，孟欣.基于免疫粒子群優(yōu)化算法的航班著陸調(diào)度研究[J].計(jì)算機(jī)工程,2012,38(13):273-275,279.[FENG X J,MENG X.Research on flight landing schedule based onimmuneparticleswarmoptimizationalgorithm[J].Com?puterEngineering,2012,38(13):273-275,279.]

[18]孟祥偉，張平，李春錦.到場飛機(jī)排序及調(diào)度問題的Memetic算法[J].西南交通大學(xué)學(xué)報(bào)，2011，46(3):488-493.[MENG X W,ZHANG P,LI C J.Memetic algo?rithm for aircraft arrival sequencing and scheduling problem[J].Journal of Southwest Jiaotong University, 2011,46(3):488-493.]

[19]Dong B,Du W.Scheduling arrival aircrafts on multi-run?way based on an improved artificial Fish Swarm algo?rithm[C]//Proceedings of the 2010 International Confer?ence on Computationaland Information Sciences, Chengdu,Sichuan,China,2010:499-502.

[20]慕彩紅.協(xié)同進(jìn)化數(shù)值優(yōu)化算法及其應(yīng)用研究[D].西安:西安電子科技大學(xué),2010.[MU C H.Co-evolution?ary numerical optimization algorithms and their applica?tions[D].Xi’an:Xidian University,2010]

[21]Zhang X,Zhang X J,Zhang J,et al.Optimization of se?quencing for aircraft arrival based on approach Routes [C]//Proceedings of the 10th International IEEE Confer?ence on Intelligent Transportation Systems.Seattle, USA,2007:592-596.

[22]Thomas P R,Xin Y.Stochastic ranking for constrained evolutionary optimization[J].IEEE Transactions on Evo?lutionary Computation.2000,4(3):284-294.

[23]Tessema B,Yen G G.A Self Adaptive penalty function based algorithm for constrained optimization[C].IEEE Congress on Evolutionary Computation.Vancouver,BC 2006:246-253.

[24]Liu J,Zhong W C,Jiao L C.An organizational evolution?ary algorithm for numerical optimization[J].IEEE Trans?actions on Systems,Man,and Cybernetics—Part B:Cy?bernetics,2007,37(4):1052-1064.

Optimal Scheduling of Aircraft Arrivals Based on Co-evolutionary Genetic Algorithm

ZHANG Xie，ZHAO Yi-fei，LIU Hong-zhi
（Tianjin Key Lab of Operation Programming and Safety Technology ofAir Traffic Management,CivilAviation University of China,Tianjin 300300,China）

Optimal scheduling of aircraft arrivals is a typical combinatorial optimization problem,which features complexity with multi-constraint.In order that the deficiencies can be overcome,which are multiconstraint,huge amount of computation and local optimum attraction,when the scheduling of aircraft arrivals is constituted with generic algorithms,a decision solutions population and a penalty factor population are constructed for the optimal scheduling problem,which is inspired by coevolution.The performance of the algorithm is improved by the competition and the coordination between the two populations.A coding strategy with constraints is designed,into which the safe separation constraint is coded,and the complexity of constraints is lowered with the coding strategy.Furthermore,an improved co-evolutionary genetic algorithm is proposed,and a simulation is conducted with the operational data from Beijing Capital International Airport. It is shown that the huge amount of constraints for the optimal scheduling can be tackled effectively with the approach proposed.When the optimal result corresponds to the result of original genetic algorithm,the time cost is reduced effectively and the difficulty is overcome,that the computation efficiency decreases sharply as the scale of the problem increases.

air transportation;co-evolutionary;genetic algorithm;aircraft arrival scheduling;air traffic flow management

1009-6744（2014）02-0094-08

V355.2

A

2013-08-29

2013-10-29錄用日期：2013-11-18

國家自然科學(xué)基金（61039001）；國家科技支撐計(jì)劃(2011BAH24B10)；中國民航大學(xué)科研基金(2011kyE04)；中國民航大學(xué)科研啟動(dòng)基金(2012QD04X).

張勰（1981-），男，陜西咸陽人，助理研究員，博士.*通訊作者：xiezhang@cauc.edu.cn