馮興杰，劉 東

（中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院，天津 300300）

基于改進免疫粒子群算法的動態(tài)航班著陸調(diào)度

馮興杰，劉 東

（中國民航大學(xué)計算機科學(xué)與技術(shù)學(xué)院，天津 300300）

為改進機場終端區(qū)空中交通流量管理,對動態(tài)航班著陸次序進行適當(dāng)調(diào)整,使機場和空域的可用容量達到最有效利用,減少航班延誤造成的經(jīng)濟損失,提出一種新穎的動態(tài)免疫粒子群優(yōu)化算法（DIPSO）,重點針對待著陸航班的動態(tài)變化,結(jié)合滑動時間窗,多方面考慮現(xiàn)實約束,在確保航班延誤成本最小的同時,兼顧航班著陸的公平性和管制員的工作負荷。仿真結(jié)果表明,在處理動態(tài)航班著陸問題上與先來先服務(wù)相比有效降低了延誤成本。

免疫粒子群優(yōu)化;航班著陸調(diào)度;動態(tài);最小延誤成本

隨著世界航空運輸?shù)难该桶l(fā)展，急劇增長的空中交通需求與有限的樞紐機場空域資源間的矛盾日益尖銳，如何提高機場終端區(qū)航班調(diào)度自動化水平已成為一個亟待解決的難題。僅通過空中交通管制設(shè)施的改善已不能作為提高空中交通流量的主要方法。對跑道容量起決定性作用的因素是連續(xù)航班流之間的間隔，它與天氣、導(dǎo)航設(shè)施、航班類型等因素密切相關(guān)。因此，合理安排不同類型航班的降落順序，對提高機場容量、增大機場流量意義很大。

飛機著陸調(diào)度（aircraft landing scheduling，ALS）問題是具有多約束特性的典型NP難問題，國內(nèi)外學(xué)者廣泛研究ALS問題，提出了較多優(yōu)化解決方案，但由于ALS問題本身的復(fù)雜性，至今未能得出完善的理論和方法。目前中國飛機調(diào)度基本采用先來先服務(wù)FCFS（first-come，first-served）的方式進行。該方法的不足之處是不能綜合考慮飛機的多方面因素，如機型、延誤成本等[1-3]。近年來，在智能優(yōu)化領(lǐng)域?qū)ふ乙环N可行有效的調(diào)度方案，一直是研究的熱點和難點，為解決大規(guī)模的ALS問題提供了相對可行的方法，主要包括遺傳算法（genetic algorithm，GA）[4-6]、粒子群算法、禁忌搜索、模擬退火、蟻群算法等[7-8]。

本文分析了標準PSO（particleswarmoptimization）[9]算法原理，通過引入生物免疫機制思想，提出了一種新的動態(tài)免疫粒子群優(yōu)化（dynamic immune particle swarm optimization，DIPSO）算法。并建立由滑動時間窗控制的動態(tài)航班優(yōu)化模型，以航班總的延誤成本最小為目標函數(shù)，綜合考慮兼顧公平，在多種約束條件限制下，最終給出與標準粒子群、先來先服務(wù)FCFS相比具有明顯優(yōu)勢的合理調(diào)度方案。

1 問題建模

1.1 變量描述

1）P={x1，x2，…，xn}表示動態(tài)進入終端區(qū)等待降落的航班序列；

2）Ei為航班i的最早著陸時間（i=1，2，…，n）；

3）Li為航班i的最晚著陸時間（i=1，2，…，n）；

4）Ti為航班i的最佳著陸時間（i=1，2，…，n）；

5）Si為航班i的實際著陸時間（i=1，2，…，n）；

6）TPi為航班i的機型（i=1，2，…，n）；

7）gi為航班i早于Ti著陸的單位時間成本（i= 1，2，…，n）；

8）hi為航班i晚于Ti著陸的單位時間成本（i= 1，2，…，n）；

9）αi為航班i早于Ti著陸的最大時間；

10）βi為航班i晚于Ti著陸的最大時間；

表示航班i不能在最佳著陸時間降落所造成的額外耗費成本。

各類型的航班都有最佳著陸時間（preferred time），按照此時間著陸的額外費用為0，如果航班加速提前或延遲著陸都會造成額外的費用，圖1說明了某架航班在飛行中帶來的額外費用變化情況。

圖1 航班著陸時間額外費用Fig.1 Extra cost of flight landing time

為方便計算，規(guī)定航班的機型大小S為輕型，L為中型，H為重型，各機型的額外損耗成本如表1所示。

1.2 優(yōu)化目標

在安全調(diào)度的前提下以航班總額外耗費成本為首要考慮要素，有

表1 各機型消耗成本（元/min）Tab.1 Cost of various aircraft types

由于航班調(diào)度問題的目標函數(shù)越小越好，而通常的進化算法中，適應(yīng)度大的個體適應(yīng)性越好。因此，設(shè)計適應(yīng)度函數(shù)為

其中：fmax（x）、fmin（x）為本次迭代計算中最大、最小目標函數(shù)值。

1.3 約束條件

1）位置約束

λij表示航班i與航班j的位置關(guān)系，i在j之前降落；λji表示航班j在航班i之前降落；λij=1表示航班i早于航班j降落，否則航班i晚于航班j降落。

2）安全間隔

該式表示若航班i早于航班j降落，則航班i與航班j之間的間隔不小于最小安全尾流間隔加一個冗余間隔；Δij由現(xiàn)場管制員的經(jīng)驗決定，MSSij由表2確定。

表2 最小安全尾流間隔時間Tab.2 Minimum safe turbulance seperation

3）實際著陸時間窗約束

受到航班的性能、所剩燃油的數(shù)量等因素影響，航班的實際著陸時間不能無限制提前或滯后，因此航班i的實際著陸時間為最早著陸時間和最晚著陸時間之間的離散時間段，即Ei≤Si≤Li。

4）管制員工作負荷約束

在滿足安全調(diào)度的前提下，若沒有較大幅度的改進，則盡可能減少航班著陸序列的變更，減少管制員的工作負荷。

5）最大位移限制

各航班的最大位移MPS=3，即每個航班提前或推后的相對位移不得超過3個以上航班。

6）航班加速限制

且航班j與其在一個時間片段內(nèi)的航班有著陸時間沖突時，航班j加速飛行，但加速時間不超過相應(yīng)安全規(guī)定。

7）同一類型的航班相對位置不發(fā)生調(diào)換

在FCFS序列中的λij值，若TPi=TPj，則在算法調(diào)整后的序列中，λij的值不發(fā)生變化。

8）間接時間窗限制

式（6）、式（7）表示航班i早于最佳著陸時間Ti著陸時，最佳著陸時間Ti與實際著陸時間Si的差值不大于αi，而αi是不大于Ti-Ei的非負值；同理，式（8）、式（9）表示航班i晚于最佳著陸時間Ti著陸時，實際著陸時間Si與最佳著陸時間Ti的差值不小于βi，而βi是不大于Li-Ti的非負值；式（10）表示航班i的實際著陸時間Si受到αi和βi的限制，向最佳著陸時間Ti靠近。

2 動態(tài)調(diào)度算法及其優(yōu)化

2.1 滑動時間窗策略

就當(dāng)前時間間隔，根據(jù)目前有效信息，對進入時間窗的問題通過免疫粒子群優(yōu)化算法進行優(yōu)化。如圖2所示，時間窗開始時間為T（k）、結(jié)束時間為T（k）+ nt，這一時段就是一個滑動時間窗的長度，它由n個長度為t的時間片段組成，稱為第k個滑動時間窗。利用免疫粒子群優(yōu)化算法，每次優(yōu)化計算一個時間窗內(nèi)的航班序列，在符合約束條件的情況下只執(zhí)行前5個架次航班的結(jié)果（結(jié)果不足5個時全部執(zhí)行），此后將時間窗向后推進一個長度為t的時間片，否則重新計算并檢驗結(jié)果。重復(fù)執(zhí)行上述相同優(yōu)化。這樣就形成一個動態(tài)效果，在有航班安排著陸的同時，又有新的航班進入終端區(qū)等待優(yōu)化排序。將已經(jīng)排好序列進入凍結(jié)區(qū)的航班信息刪除，加入新進的航班信息，采用算法重新優(yōu)化計算。

2.2 標準粒子群算法

圖2 滑動時間窗優(yōu)化示意圖Fig.2 Optimization of sliding time window

初始化微粒為一群隨機粒子（隨機解），通過迭代算法找出問題的最優(yōu)解或滿意的解，每個個體看作N維搜索空間中的一個質(zhì)點，在搜索空間中以一定的速度飛行，個體速度根據(jù)自我認知經(jīng)驗和群體的社會認知經(jīng)驗進行動態(tài)調(diào)整。第i個粒子表示為：Xi=（xi1，xi2，…，xiN），它所經(jīng)歷的最好位置記為pbest=（pi1，pi2，…，piN），在群體中所有微粒經(jīng)歷過的最好值記為gbest=（g1，g2，…，gN），微粒i的速度記為Vi=（vi1，vi2，…，viN）。每次迭代按如下公式進行速度和位置的變更，即

式中：ω為慣性權(quán)重，控制著上次迭代粒子的速度對本次迭代的影響；c1、c2為加速常數(shù)（accelerationconstant），也稱為學(xué)習(xí)因子；r1、r2為[0，1]之間的隨機數(shù)，c1r1構(gòu)成的系數(shù)影響粒子從pbest獲取更新信息，c2r2構(gòu)成的系數(shù)影響粒子從gbest獲取更新信息；1≤j≤N，k為迭代次數(shù)。

粒子的種群多樣性影響全局搜索能力，分析標準PSO算法得出，在算法迭代過程中，種群多樣性逐漸減小，導(dǎo)致出現(xiàn)早熟現(xiàn)象，同時算法收斂到一定精度，陷入局部最優(yōu)，無法繼續(xù)優(yōu)化。為解決該問題，對標準PSO算法做以下改進：①通過PSO與免疫算法機制的結(jié)合，增加PSO粒子種群多樣性；②調(diào)整慣性權(quán)重。

2.3 與免疫算法結(jié)合

免疫系統(tǒng)是維護生物體健康的防御系統(tǒng)，生物利用該系統(tǒng)抵抗各種病菌入侵，該系統(tǒng)通過識別“自我”和“異己”抗原、免疫應(yīng)答排除抗原性異物，維持生理平衡。在免疫調(diào)節(jié)過程中，濃度較低且與抗原的親和力較大的抗體將會得到促進，反之，將會受到抑制，從而保證了抗體的多樣性。免疫系統(tǒng)將與入侵的抗原反應(yīng)，部分抗體作為記憶細胞被保留，當(dāng)同類抗原再次入侵時，相應(yīng)的記憶細胞被激活而產(chǎn)生抗體[10-12]。

借鑒該思想，在優(yōu)化算法中創(chuàng)建一個記憶庫，保留歷次迭代中的全局最優(yōu)個體。通過濃度選擇和粒子更新，替換掉種群每代進化中的較差個體，提高算法種群多樣性，較大程度上降低算法陷入局部最優(yōu)的可能。粒子濃度選擇公式為

結(jié)合免疫思想的改進粒子群算法在航班著陸調(diào)度中的實現(xiàn)步驟如下：

1）檢查是否有特殊航班需要及時安排著陸，若有則優(yōu)先調(diào)度。

2）設(shè)定滑動時間窗的相應(yīng)參數(shù)。

3）讀取當(dāng)前時間窗內(nèi)的航班信息。

4）確定參數(shù)值：學(xué)習(xí)因子c1和c2，種群規(guī)模為N，粒子（抗體）維度為n，最大迭代次數(shù)為runmax，免疫記憶庫的記憶粒子個數(shù)為m。

5）初始化：隨機產(chǎn)生N個粒子Xi及“飛行”速度Vi，Xi為待著陸航班的隨機排列，Vi為隨機產(chǎn)生的調(diào)整序，含1個調(diào)整因子，將粒子i的初始化位置記為歷史最優(yōu)位置pbesti，i=1，2，…，N，將初始化中位置整體最優(yōu)的粒子記為全局最優(yōu)gbest，形成初始粒子種群S0。

6）迭代計算形成免疫記憶庫：為減小管制員的工作負荷，使調(diào)整后的航班序列與FCFS序列盡量一致，將FCFS序列作為免疫記憶庫中的常駐粒子。由式（11）、式（12）迭代計算，每次迭代將各粒子的迭代結(jié)果與當(dāng)前的pbesti進行適應(yīng)度值比較，若比當(dāng)前pbesti優(yōu)，則用本次迭代結(jié)果替換當(dāng)前pbesti；同理選出適應(yīng)度值最大的粒子和當(dāng)前全局最優(yōu)粒子gbest比較，如果較優(yōu)，則將其作為全局最優(yōu)粒子，更新全局最優(yōu)位置gbest，并將其加入到免疫記憶庫中，如果記憶庫已滿，則將該粒子替換記憶庫中除FCFS序列以外的適應(yīng)度最差粒子。

7）粒子庫的生成：①由粒子群優(yōu)化算法速度和位置的更新產(chǎn)生N個粒子；②隨機產(chǎn)生M個新粒子。

8）粒子濃度選擇：用濃度選擇式（13）計算步驟4）中生成的N+M個粒子的選擇概率，根據(jù)大小選擇N個粒子形成種群。

9）粒子更新：用記憶庫中的m個粒子替換步驟5）中得到的N個粒子中適應(yīng)度較差的m個粒子，得到更新后的種群Sk+1。

10）迭代終止判斷：若達到最大迭代次數(shù)，或者相鄰兩次迭代結(jié)果誤差絕對值小于ε=0.001，則終止迭代，否則轉(zhuǎn)步驟3）。

11）對上面提供的結(jié)果進行檢驗，若滿足章節(jié)1.3中的8個約束條件，則執(zhí)行前5個航班，不足5個則全部執(zhí)行。其他航班進入下一個時間窗。否則放棄本次結(jié)果，重新計算。

12）判斷航班調(diào)度是否完畢，若完畢，則結(jié)束運算，否則，將時間窗向后滑動一個時間片段，如圖2所示，并返回步驟3）。

在免疫粒子群（DIPSO）算法基礎(chǔ)上，航班著陸調(diào)度流程如圖3所示。

圖3 航班著陸調(diào)度流程圖Fig.3 Scheduling flowchart of flight landing

2.4 改進粒子群算法系數(shù)

為避免算法過早收斂并加快收斂速度，Shi等[13]提出了慣性權(quán)重的方法，慣性權(quán)重決定了對粒子當(dāng)前速度的繼承，較大的慣性權(quán)重將使粒子具有較大的速度，從而具有較強的全局探索能力；較小的慣性權(quán)重將使粒子具有較強的局部開發(fā)能力。在標準粒子群中慣性權(quán)重是線性減小的，即

其中：ωmax為最大慣性權(quán)重；ωmin為最小慣性權(quán)重；run、runmax分別為當(dāng)前迭代次數(shù)和最大迭代次數(shù)。但對于一些較為復(fù)雜的非線性問題，ω的變化并非都是線性的，找到一種針對解具體問題的曲線變化，對算法的改進至關(guān)重要。

就航班著陸排序問題，通過理論和實驗的共同研究得出較大的慣性權(quán)重ω，能夠使得粒子群算法有著較強的全局搜索能力，從而搜索較大的區(qū)域，便于更好地確定最優(yōu)解的大概位置；而較小的ω則使得算法具有更強的局部搜索能力，即小的ω使得PSO算法的速度變化減慢，在局部小范圍中能夠進行精細的搜索，如此便能更好地確定最優(yōu)解。對于不同的復(fù)雜優(yōu)化問題，都有著與各自問題相適應(yīng)的慣性權(quán)重ω變化曲線。本文針對航班著陸調(diào)度優(yōu)化問題就PSO算法中ω的變化參考了文獻[14]，結(jié)合團隊合作精神，即利用多條曲線減小函數(shù)，產(chǎn)生一組由大到小的變化曲線，根據(jù)這組曲線函數(shù)制定了一組ω，就航班著陸調(diào)度的同一數(shù)據(jù)進行了多次重復(fù)試驗。經(jīng)實驗結(jié)果對比，不同ω所得結(jié)果都有差別，結(jié)合航班著陸調(diào)度問題的綜合考慮，最后對慣性權(quán)重ω做出以下改進，即

同理學(xué)習(xí)因子c1、c2對繼承個體最優(yōu)和全局最優(yōu)起著很大作用，c1越大，則受個體最優(yōu)的影響越大，反之越?。籧2越大，則受全局最優(yōu)的影響越大，反之越?。凰惴ㄩ_始迭代時，個體最優(yōu)有利于全局搜索，迭代后期全局最優(yōu)有利于局部搜索，所以個體最優(yōu)和全局最優(yōu)呈反比趨勢更有利于算法搜索最優(yōu)值，因此本文對學(xué)習(xí)因子c1、c2也做了相應(yīng)的改進，即

實驗數(shù)據(jù)證明，本文的改進取得了較好的結(jié)果。

3 實驗結(jié)果分析

本文算法在visual studio2010環(huán)境中，采用C++編碼實現(xiàn)，實驗微機的CPU主頻為2.0 GHz，表3的航班數(shù)據(jù)為首都國際機場2007年6月13日上午9：40至11：00間的真實數(shù)據(jù)。算法參數(shù)如下：粒子群規(guī)模N為30，記憶庫中的免疫記憶粒子個數(shù)m為8，每一代隨機產(chǎn)生的新粒子的個數(shù)M為15，最大迭代次數(shù)為2 000。

對航班數(shù)據(jù)經(jīng)過多次運行計算，分別就先來先服務(wù)（FCFS）和免疫粒子群算法（DIPSO）的結(jié)果進行對比，獲得兩種算法的調(diào)度方案及總的延誤費用，為方便與FCFS作對比，在表3中本文算法的序列值是相對于FCFS的序列經(jīng)DIPSO算法計算后調(diào)整的序列。

調(diào)度結(jié)果表明，改進的免疫粒子群算法與傳統(tǒng)的先來先服務(wù)（FCFS）相比較，有效降低了航班的總延誤費用。此外為了進一步驗證本文的算法，就同一航班調(diào)度問題，分別利用粒子群算法（PSO）、FSFC和本文提到的免疫粒子群（DIPSO）運算結(jié)果的各項性能指標做了對比，如圖4和表4所示。

從圖4和表4可以看出，動態(tài)免疫粒子群算法（DIPSO）的運算結(jié)果明顯優(yōu)于PSO和FCFS算法，DIPSO算法結(jié)果的穩(wěn)定性較好、收斂效率較高，管制員的工作負荷得到有效減小，由此可見，引入免疫機制的DIPSO算法能夠較為穩(wěn)定的獲得最優(yōu)解，更加適用于航班著陸調(diào)度問題。

表3 航班數(shù)據(jù)及調(diào)度結(jié)果Tab.3 Flight data and scheduling result

圖4 迭代收斂對比圖Fig.4 Comparison of iteration restrains

表4 算法性能比較Tab.4 Performance comparison of 3 algorithms

4 結(jié)語

本文針對現(xiàn)實航班著陸調(diào)度多約束問題，結(jié)合滑動時間窗，解決動態(tài)航班著陸問題，借鑒生物免疫系統(tǒng)的免疫機制，引入免疫記憶庫和粒子濃度選擇對傳統(tǒng)PSO算法進行改進，同時，以額外耗費成本最小為目標函數(shù)，在保證安全且較為公平的原則下有效安排著陸航班的序列。DIPSO在航班著陸調(diào)度問題中的進一步研究方向包括：①航班著陸調(diào)度問題是一個多約束調(diào)度，在實際調(diào)度中往往較為復(fù)雜，仍需繼續(xù)探索DIPSO算法在更多現(xiàn)實約束條件下ALS問題中的應(yīng)用；②大型機場的跑道往往不止一條，需綜合考慮航班的起飛與著陸在多跑道中的合理利用。

[1]VOLCKERS U.Arrival Planning and Sequencing with COMPAS-OP at the Frankfurt ATC-Center[C]//Proceedings of the 1900 American Control Conference，California，San Diego，1900：496-501.

[2]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.

[3]BEASLEY J E，KRISHNAMOORTHY M，SHARAIHA Y M，et al.Displacement problem and dynamically scheduling aircraft landings[J]. Journal of the Operational Research Society，2004，55：54-64.

[4]張 偉，王 宏.求解機場終端區(qū)航班著陸調(diào)度問題的遺傳算法[J].計算機工程與應(yīng)用，2012（12）：931-938.

[5]馮興杰，孟 欣.基于遺傳算法的動態(tài)航班著陸調(diào)度優(yōu)化[J].計算機與現(xiàn)代化，2012（1）：181-187.

[6]劉 朕，李 銳.飛機著陸調(diào)度優(yōu)化的混合免疫克隆算法[J].計算機應(yīng)用與軟件，2013，30（2）：116-121.

[7]余 靜，楊紅雨，馬博敏，等.證據(jù)理論在機場動態(tài)容量預(yù)測模型中的研究[J].電子科技大學(xué)學(xué)報，2010，39（1）：141-144.

[8]劉 洪，楊紅雨，彭莉娟.基于分組的MPS進近航班著陸調(diào)度算法研究[J].電子科技大學(xué)學(xué)報，2013，42（4）：1230-1236.

[9]KENNEDY J，EBERHART R.Particle Swarm Optimization[C]//Proceedings of International Conference on Neural Networks.Perth：IEEE，1995：1942-1948.

[10]段 富，蘇同芳.免疫粒子群算法的改進及應(yīng)用[J].計算機應(yīng)用，2010，30（7）：1183-1188.

[11]阮旻智，李慶民，王紅軍，等.人工免疫粒子群算法在系統(tǒng)可靠性優(yōu)化中的應(yīng)用[J].控制理論與應(yīng)用，2010，27（9）：1253-1258.

[12]馮 琳，毛志忠，袁 平.一種改進的多目標粒子群優(yōu)化算法及其應(yīng)用[J].控制與決策，2012，27（9）：1312-1319.

[13]SHI Y，Eberhart R C.Fuzzy Adaptive Particle Swarm Optimization[C]// Proceedings of the 2001 Congress on Evolutionary Computation.Piscataway，NJ：IEEE Press，2001：101-106.

[14]雷開友.粒子群算法及其應(yīng)用研究[D].重慶：西南大學(xué)，2006.

（責(zé)任編輯：黨亞茹）

Dynamic aircraft landing scheduling based on improved immune particle swarm optimization

FENG Xing-jie，LIU Dong
（College of Computer Science&Technology，CAUC，Tianjin 300300，China）

In order to improve the air traffic flow management in airport terminal area，the dynamic flight landing sequence is adjusted to achieve the most effective use of the airport and airspace capacity.To reduce the economic loss of flight delays，a novel dynamic immune particle swarm optimization（DIPSO）is designed，focusing on dynamic change of the aircraft landing scheduling，combining with the sliding time window and considering various realistic constraints，ensuring minimum flight delay cost while taking into consideration the work load of controllers and flight landing fairness.Simulation results show that this model effectively reduces the delay cost in dealing with dynamic flight landing compared with first-come，first-served principle.

immune particle swarm optimization；scheduling of flight landing；dynamic；minimum delay cost

V355.2;TP391.9

:A

:1674-5590(2015)02-0018-06

2013-12-24；

:2014-01-15

:國家自然科學(xué)基金項目（U1233113）

馮興杰（1969—），男，河北邢臺人，教授，博士，研究方向為數(shù)據(jù)倉庫、數(shù)據(jù)挖掘與智能信息處理理論與技術(shù).