馮興杰，劉 東

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

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

馮興杰，劉 東

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

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

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

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

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

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

1 問(wèn)題建模

1.1 變量描述

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

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

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

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

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

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

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

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

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

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

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

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

圖1 航班著陸時(shí)間額外費(fèi)用Fig.1 Extra cost of flight landing time

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

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

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

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

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

其中：fmax（x）、fmin（x）為本次迭代計(jì)算中最大、最小目標(biāo)函數(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之間的間隔不小于最小安全尾流間隔加一個(gè)冗余間隔；Δij由現(xiàn)場(chǎng)管制員的經(jīng)驗(yàn)決定，MSSij由表2確定。

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

3）實(shí)際著陸時(shí)間窗約束

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

4）管制員工作負(fù)荷約束

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

5）最大位移限制

各航班的最大位移MPS=3，即每個(gè)航班提前或推后的相對(duì)位移不得超過(guò)3個(gè)以上航班。

6）航班加速限制

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

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

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

8）間接時(shí)間窗限制

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

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

2.1 滑動(dòng)時(shí)間窗策略

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

2.2 標(biāo)準(zhǔn)粒子群算法

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

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

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

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

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

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

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

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

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

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

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

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

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

6）迭代計(jì)算形成免疫記憶庫(kù)：為減小管制員的工作負(fù)荷，使調(diào)整后的航班序列與FCFS序列盡量一致，將FCFS序列作為免疫記憶庫(kù)中的常駐粒子。由式（11）、式（12）迭代計(jì)算，每次迭代將各粒子的迭代結(jié)果與當(dāng)前的pbesti進(jìn)行適應(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，并將其加入到免疫記憶庫(kù)中，如果記憶庫(kù)已滿(mǎn)，則將該粒子替換記憶庫(kù)中除FCFS序列以外的適應(yīng)度最差粒子。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

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

圖4 迭代收斂對(duì)比圖Fig.4 Comparison of iteration restrains

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

4 結(jié)語(yǔ)

本文針對(duì)現(xiàn)實(shí)航班著陸調(diào)度多約束問(wèn)題，結(jié)合滑動(dòng)時(shí)間窗，解決動(dòng)態(tài)航班著陸問(wèn)題，借鑒生物免疫系統(tǒng)的免疫機(jī)制，引入免疫記憶庫(kù)和粒子濃度選擇對(duì)傳統(tǒng)PSO算法進(jìn)行改進(jìn)，同時(shí)，以額外耗費(fèi)成本最小為目標(biāo)函數(shù)，在保證安全且較為公平的原則下有效安排著陸航班的序列。DIPSO在航班著陸調(diào)度問(wèn)題中的進(jìn)一步研究方向包括：①航班著陸調(diào)度問(wèn)題是一個(gè)多約束調(diào)度，在實(shí)際調(diào)度中往往較為復(fù)雜，仍需繼續(xù)探索DIPSO算法在更多現(xiàn)實(shí)約束條件下ALS問(wèn)題中的應(yīng)用；②大型機(jī)場(chǎ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]張 偉，王 宏.求解機(jī)場(chǎng)終端區(qū)航班著陸調(diào)度問(wèn)題的遺傳算法[J].計(jì)算機(jī)工程與應(yīng)用，2012（12）：931-938.

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

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

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

[8]劉 洪，楊紅雨，彭莉娟.基于分組的MPS進(jìn)近航班著陸調(diào)度算法研究[J].電子科技大學(xué)學(xué)報(bào)，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]段 富，蘇同芳.免疫粒子群算法的改進(jìn)及應(yīng)用[J].計(jì)算機(jī)應(yīng)用，2010，30（7）：1183-1188.

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

[12]馮 琳，毛志忠，袁 平.一種改進(jìn)的多目標(biāo)粒子群優(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]雷開(kāi)友.粒子群算法及其應(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

:國(guó)家自然科學(xué)基金項(xiàng)目（U1233113）

馮興杰（1969—），男，河北邢臺(tái)人，教授，博士，研究方向?yàn)閿?shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)挖掘與智能信息處理理論與技術(shù).