用于跑道調(diào)度的約束多目標(biāo)遺傳模擬退火算法*

張書琴　夏洪山　姜雨　戰(zhàn)緒仁

(1.南京航空航天大學(xué) 民航學(xué)院, 江蘇 南京 211106; 2.膠州市規(guī)劃局, 山東 膠州 266300)

?

用于跑道調(diào)度的約束多目標(biāo)遺傳模擬退火算法*

張書琴1夏洪山1姜雨1戰(zhàn)緒仁2

(1.南京航空航天大學(xué) 民航學(xué)院, 江蘇 南京 211106; 2.膠州市規(guī)劃局, 山東 膠州 266300)

摘要：為獲得較優(yōu)跑道調(diào)度方案,以提高跑道運(yùn)行效率,建立了約束多目標(biāo)多跑道進(jìn)離場航班調(diào)度模型.在分析遺傳算法與模擬退火算法特征的基礎(chǔ)上,提出遺傳模擬退火組合算法.分別采用Pareto支配及理想點(diǎn)法對跑道調(diào)度目標(biāo)函數(shù)進(jìn)行處理,采用懲罰目標(biāo)函數(shù)值及可行解占優(yōu)的方式處理約束條件,并確定了不同條件下新粒子更新機(jī)制及最優(yōu)粒子篩選原則.文中還通過設(shè)置溫度自適應(yīng)改變機(jī)制控制算法收斂速度,以提高最優(yōu)解性能.最后,以國內(nèi)某大型機(jī)場跑道調(diào)度為例,對文中算法的有效性進(jìn)行驗(yàn)證.結(jié)果表明:基于Pareto支配的約束多目標(biāo)遺傳算法能獲得跑道調(diào)度多組較優(yōu)可行解,且時效性強(qiáng).

關(guān)鍵詞：航空運(yùn)輸;近距平行跑道;約束多目標(biāo)優(yōu)化;遺傳模擬退火算法;Pareto最優(yōu);理想點(diǎn)法

跑道構(gòu)型日趨復(fù)雜,在處理跑道調(diào)度問題時,目標(biāo)函數(shù)及約束條件日趨龐大,對約束多目標(biāo)跑道調(diào)度問題求解技術(shù)提出了新挑戰(zhàn).目前約束多目標(biāo)優(yōu)化算法可分為兩大類:①單一的優(yōu)化算法,如蟻群算法[1]、模擬退火算法[2]、動態(tài)約束生成算法[3]、動態(tài)規(guī)劃[4]、決策樹算法[5]及多目標(biāo)線性規(guī)劃[6]等;②組合優(yōu)化算法,如生態(tài)分散搜索算法[7]、遺傳模擬退火算法[8]、啟發(fā)式貪婪算法[9]、差分粒子群算法[10]、分支定界與禁忌搜索組合的優(yōu)化算法[11]、混沌模擬退火粒子群算法[12]及改進(jìn)的粒子群遺傳算法[13]等.

單一的優(yōu)化算法主要是求解約束單目標(biāo)優(yōu)化問題,且算法獲得可行解的時間長,不具備動態(tài)調(diào)度航班的可行性;組合算法主要是針對多目標(biāo)無約束的優(yōu)化問題而設(shè)計的,算法缺乏約束懲罰機(jī)制.實(shí)際優(yōu)化問題一般均是約束優(yōu)化問題,無約束的優(yōu)化算法適應(yīng)范圍小.針對約束多目標(biāo)的進(jìn)離港航班跑道調(diào)度問題,文中設(shè)計了改進(jìn)的遺傳模擬退火算法,分別用Pareto支配及理想點(diǎn)法處理多個目標(biāo)函數(shù),用懲罰函數(shù)值對約束條件加以約束.Pareto支配同時采用可行解占優(yōu)對約束條件進(jìn)行雙重約束,確保粒子不斷向可行的最優(yōu)粒子逼近,用溫度來控制算法收斂的速度.

1約束多目標(biāo)跑道調(diào)度模型

文中以航班延誤成本及跑道調(diào)度時間跨度最小為目標(biāo)函數(shù)建立了航班跑道調(diào)度模型:

(1)

(2)

s.t.

Ei≤ti≤Li,i=1,2,…,N

(3)

tk+1-tk≥Tk(k+1),k=1,2,…,N-1

(4)

V≤G

(5)

(6)

(7)

(8)

式(2)中的航班單位時間延誤成本等于飛機(jī)單位時間延誤成本加上旅客單位時間延誤成本乘以飛機(jī)實(shí)際載客數(shù),其中飛機(jī)單位時間延誤成本分為“續(xù)航”飛機(jī)單位時間延誤成本與“非續(xù)航”飛機(jī)單位時間延誤成本.文中將距此次飛行任務(wù)3 h后仍有飛行任務(wù)的航班稱為“續(xù)航”航班.“續(xù)航”航班未能按照計劃時間執(zhí)行任務(wù)將會影響之后的航班任務(wù),因此,文中對“續(xù)航”航班的飛機(jī)單位時間延誤成本乘以一系數(shù)進(jìn)行修正.式(3)表示的是航班調(diào)度時間窗約束;式(4)是相繼運(yùn)行的航班時間間隔約束;式(5)是調(diào)度區(qū)間內(nèi)的跑道實(shí)際容量不能超過跑道最大理論容量;式(6)-(8)表示同一時間一條跑道上最多只能有一架航班運(yùn)行,且每個航班有且只能分配一條跑道.文中研究的機(jī)場有兩條近距平行跑道,且跑道采用一起一降的起降模式,靠近航站樓的跑道用于起飛,遠(yuǎn)離航站樓的跑道用于降落.

表1進(jìn)離港航班最小時間間隔要求1)[14]

Table 1The minimum time interval requirements between arrivals and departures

航班相繼離港航班時間間隔/s相繼進(jìn)港航班時間間隔/sSMHSHSMHSHS7060606082705955M70606060131705955H1201201201201971399555SH120120120120328222142131

1)S為輕型航班,M為中型航班,H為重型航班,SH為超重型航班.

2遺傳模擬退火算法

遺傳算法具有很強(qiáng)的全局搜索能力,但局部搜索能力差;模擬退火算法局部搜索能力較強(qiáng).利用模擬退火算法增加粒子局部搜索范圍,使不可行解向可行解發(fā)展,可行解盡量逼近最優(yōu)解.文中融合遺傳算法(GA)與模擬退火算法(SA)的優(yōu)勢,求解約束多目標(biāo)跑道調(diào)度模型.

2.1　約束條件的處理

Pareto支配通過懲罰目標(biāo)函數(shù)值及個體優(yōu)先級對不滿足條件的粒子進(jìn)行雙重約束;理想點(diǎn)法用懲罰函數(shù)法對約束條件進(jìn)行處理.設(shè)xr粒子不滿足mr個約束條件,在對兩粒子進(jìn)行取舍時,首先,比較粒子不滿足條件的個數(shù),促使不可行粒子向可行粒子發(fā)展；其次,對粒子的目標(biāo)函數(shù)加以約束:粒子xr的目標(biāo)函數(shù)值為其自身值加上10mr倍同數(shù)量級的值,即zr=zr+10mrqs(zr)、fr=fr+10mrqs(fr),其中qs(·)表示取目標(biāo)函數(shù)值的數(shù)量級函數(shù).

2.2　粒子更新原則

將Pareto支配概念進(jìn)行推廣:設(shè)兩個解x1、x2,若滿足x1的任何目標(biāo)函數(shù)值都不大于x2的目標(biāo)函數(shù)值,且x1至少有1個目標(biāo)函數(shù)值小于x2的目標(biāo)函數(shù)值,則稱x1支配x2,記作x1x2.

2.2.1粒子更新原則——Pareto支配

(2)若父代粒子是可行解、子代粒子是不可行解,則舍棄新粒子,保存父代粒子進(jìn)入下一代.

(3)若兩個粒子均是不可行解,保留違反約束條件個數(shù)少的粒子;若兩粒子違反約束條件個數(shù)相同,當(dāng)父代粒子與子代粒子之間存在支配關(guān)系時,則按照支配原則選擇粒子進(jìn)入下一代;當(dāng)父代粒子與子代粒子之間不存在支配關(guān)系時,則按照Metropolis機(jī)制對新解進(jìn)行取舍.

迭代代數(shù)結(jié)束之后,對于多個可行解按以下原則選擇最優(yōu)解:

forr=1:n%n表示種群大小

s(r)=0;u(r)=0;%s(r)表示第r個個體支配的粒子數(shù)

forb=1:n%u(r)表示支配第r個個體的粒子數(shù)

ifr≠b

ifxrxb

s(r)=s(r)+1;

end

ifxa?xb

u(r)=u(r)+1;

end

end

end

l=0*rand(1,n);%l(r)表示第r個粒子優(yōu)先級

forr=1:(n-1)

forb=(r+1):n

ifu(r)

l(b)=l(b)+1;

end

ifu(r)≥u(b)

ifu(r)>u(b)

l(r)=l(r)+1;

else

ifs(r)≥s(b)

l(b)=l(b)+1;

else

l(r)=l(r)+1;

end

end

end

end

end

根據(jù)以上思路得到的最小的l(r)對應(yīng)的第r個粒子即為最優(yōu)粒子.

2.2.2粒子更新原則——理想點(diǎn)法

2.3　算法步驟

遺傳模擬退火算法(GASA)采取內(nèi)外雙層循環(huán),具體操作步驟如下:

(1)初始化種群.創(chuàng)建一個列滿秩矩陣A,實(shí)現(xiàn)種群多樣性.初始化迭代代數(shù)M為250,變異概率為0.01;最高溫度θmax=1 000 ℃,最低溫度θmin=0.01 ℃,溫度損耗百分?jǐn)?shù)(down)為 5%;并且計算粒子的目標(biāo)函數(shù)z1,z2,…,zn和f1,f2,…,fn，及粒子違反約束條件的個數(shù)m1,m2,…,mn或J1,J2,…,Jn.

(2)迭代代數(shù)是否超過最大迭代代數(shù).若是則轉(zhuǎn)至步驟(8),否則按照更新每一代的初始溫度,再進(jìn)入下一步.

(3)交叉.將矩陣A給矩陣B,且對B執(zhí)行如下操作:

forr=1:n

隨機(jī)產(chǎn)生兩個介于1~n之間的數(shù)n1、n2,且n1≠n2;

將粒子n1與n2位置上的值互換;

end

(4)變異.隨機(jī)產(chǎn)生0~1之間的1個數(shù),若該數(shù)大于變異概率,則隨機(jī)對粒子的一位置值進(jìn)行變異.

(5)更新粒子.計算B種群粒子的目標(biāo)函數(shù)及約束違反度,并按照2.2節(jié)中粒子更新原則更新粒子.

(6)更新溫度.θ=θ*(1-down).

(7)判斷溫度是否大于最小溫度.若是,則轉(zhuǎn)至步驟(3);否則,y=y+1,轉(zhuǎn)至步驟(2).

(8)按照2.2節(jié)最優(yōu)解的定義輸出最優(yōu)解.

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

文中在Intel(R)、CPU為3.40 GHz、內(nèi)存為8 192 MB的計算機(jī)和Win 7.0環(huán)境下采用Matlab編程.國內(nèi)某個大型機(jī)場8:00—10:00航班數(shù)據(jù)及其中一次的實(shí)驗(yàn)結(jié)果如表2所示.算法在編程實(shí)現(xiàn)時限制航班最大延誤時間為30 min,以避免航班發(fā)生長時間延誤,造成大面積航班延誤;同時滿足航班調(diào)度時間窗約束.

航班延誤成本分布(見圖1)顯示Pareto支配及理想點(diǎn)法獲得的航班延誤成本分布比實(shí)際調(diào)度獲得的航班延誤成本分布均衡,一方面是由于遺傳模擬退火算法在編碼有航班調(diào)度時間窗約束,另外一方面說明遺傳模擬退火算法在尋優(yōu)過程中有航班調(diào)度公平性的保障機(jī)制.

10次實(shí)驗(yàn)結(jié)果如表3所示,Pareto支配獲得的最優(yōu)解z=151.2 min,f=540 936.5元,理想點(diǎn)法獲得的最優(yōu)解z=155.5 min,f=463 863.7元.兩種方法獲得的最優(yōu)解之間不存在支配關(guān)系,但Pareto支配每次均能獲得多組可行解供調(diào)度者選擇,相反,理想點(diǎn)法獲得可行解的概率只有20%,在實(shí)際航班調(diào)度中不具備實(shí)踐價值.兩種遺傳模擬退火算法得到的跑道調(diào)度最優(yōu)解與實(shí)際跑道調(diào)度方案之間均不存在支配關(guān)系,但Pareto支配及理想點(diǎn)法獲得的航班延誤成本比實(shí)際調(diào)度的航班延誤成本分別降低了24.6%及35.3%.實(shí)驗(yàn)結(jié)果表明犧牲少量的時間可獲得可觀的航班延誤成本.

表2某大型機(jī)場8:00—10:00進(jìn)離港航班數(shù)據(jù)1)

Table 2Flight information of one hug airport between 8:00-10:00

航班號計劃時間機(jī)型運(yùn)行方式延誤時間/minASTOPSISParetoMU74518:00Hd38-9-11FM95378:00Hd1272FM91778:05Md2313-7MU56278:10Md23109FM94618:10Md20-2017FM91718:10Md26120MU2128:15Ma-26-71MU56498:15Md31-21-15FM94078:25Md1014-14MU28818:30Ma-111-24FM92058:30Md4612-13FM93438:35Md13-910FM92158:35Md182014MU56238:45Md24-413MU52638:45Md19248MU54418:45Hd12-9-14MU55128:50Ma7141MU55058:50Md232922MU56018:50Md292227MU55868:55Ma-520MU54178:55Md1622-9FM93119:00Hd13-2-4JL8729:00Hd2139MU54689:05Ma-12-3-24MU54019:05Md2217-6MU55349:15Ma-38-28MU56609:15Ma-14-16-14MU5179:15Ma-19-276MU96799:15Md15-288MU2129:15Md22-2428MU55069:20Ma-22-10-6MU54669:20Ha-1307FM92589:20Ma-4138MU51299:20Md22-711MU53759:20Md23-2626FM94059:20Md20-515KE8759:25Ma-14-9-9MU55449:35Ma-2721-29MU24029:40Ma-6-9-29FM93289:40Ma-11-1220KE8939:40SHa-47-4MU2949:40Ma3115MU21799:40Md2413-21

續(xù)表2

1)a、d分別表示進(jìn)港航班與離港航班;AS代表實(shí)際調(diào)度方案;航班延誤時間一欄中數(shù)據(jù)的正、負(fù)分別表示航班推遲調(diào)度時間及提前調(diào)度時間.

圖1　航班延誤成本分布

1)AS方案z=147 min,f=717 187．0元.

用循環(huán)代數(shù)計量算法的復(fù)雜度得理想點(diǎn)法與Pareto支配復(fù)雜度分別為

OTOPSIS=vn(2w+1)(M-1)+n(2w+1)

(9)

OPareto=vn(w+1)(M-1)+nw+n(n-1)/2

(10)

式中,v為退火次數(shù),w為目標(biāo)函數(shù)的數(shù)目.

Pareto支配與理想點(diǎn)法復(fù)雜度相差wvn(2w+1)(M-1)+nw+(n-n2)/2,由公式知隨著目標(biāo)函數(shù)數(shù)目的增加,理想點(diǎn)法的復(fù)雜度較Pareto支配成二次函數(shù)遞增.獲得模型的最優(yōu)解之前,理想點(diǎn)法首先要將多目標(biāo)問題分解成單目標(biāo)問題來獲得每個目標(biāo)函數(shù)值的理想值,導(dǎo)致程序運(yùn)行時間成w倍增加.在跑道調(diào)度實(shí)際過程中,獲得調(diào)度方案要及時,再次證明通過理想點(diǎn)法獲得最終的調(diào)度方案沒有投入實(shí)踐使用的價值.理想點(diǎn)法獲得的各個目標(biāo)函數(shù)的理想值的大小最終也影響多目標(biāo)優(yōu)化問題獲得的最優(yōu)解,降低了算法的精確度.

Pareto支配10次實(shí)驗(yàn)獲得的可行解及平均最優(yōu)解與AS方案及理想點(diǎn)法獲得的可行解如圖2所示.結(jié)果顯示:Pareto支配獲得的可行解分布較集中,且可行解中有多個支配AS的解,其他大部分解的航班延誤成本比AS獲得的航班延誤成本小.根據(jù)不同的調(diào)度環(huán)境,調(diào)度者可以選擇當(dāng)下最適用的調(diào)度方案以獲得全局最優(yōu)調(diào)度方案.當(dāng)機(jī)場開放時間有限時,機(jī)場可以選擇更多的靠左的調(diào)度方案;當(dāng)機(jī)場開放時間長,跑道容量充裕,則可以選擇靠右的調(diào)度方案以獲得較低的航班延誤成本.因此,Pareto支配在針對約束多目標(biāo)跑道調(diào)度時較理想點(diǎn)法更優(yōu),不僅能100%獲得可行解,而且可提供多組可行解供調(diào)度者選擇.

圖2Pareto支配可行解分布

Fig.2Distribution of feasible Pareto’s solution

Pareto支配的目標(biāo)函數(shù)演變?nèi)鐖D3所示(為增加圖形的美觀度,在每次迭代結(jié)束之后根據(jù)解的優(yōu)先級的降序?qū)αＷ舆M(jìn)行了排序),從第一代到最大迭代代數(shù),目標(biāo)函數(shù)值不斷收斂,且前50代收斂速度快,表明自適應(yīng)設(shè)置的初始溫度可控制算法起初以較快的速度收斂于可行解,隨著迭代代數(shù)的增加,算法以較慢的速度在可行區(qū)域進(jìn)行搜索以獲得最優(yōu)解.圖像下降的梯度顯示:可行粒子目標(biāo)函數(shù)值變化梯度小,不可行粒子目標(biāo)函數(shù)值變化梯度大,說明算法能使不可行粒子以較快的速度收斂于可行粒子,可行粒子以較慢的速度在可行域搜索全局最優(yōu)解.

圖3Pareto支配目標(biāo)函數(shù)演變圖

Fig.3Objective functions evolution of Pareto dominance

圖4給出了理想點(diǎn)法目標(biāo)函數(shù)隨迭代代數(shù)的演變,結(jié)果顯示:理想點(diǎn)法收斂速度較Pareto支配較快,不利于全局最優(yōu)解的獲得.Pareto支配對可行解有保障機(jī)制,使可行解與不可行解收斂速度不同,有利于擴(kuò)大全局最優(yōu)解的搜索范圍,但理想點(diǎn)法的可行解與不可行解的保障機(jī)制沒Pareto支配顯著.

圖4理想點(diǎn)法目標(biāo)函數(shù)演變圖

Fig.4Objective functions evolution of TOPSIS

4結(jié)語

文中設(shè)計了基于Pareto支配及理想點(diǎn)法的遺傳模擬退火算法求解約束多目標(biāo)跑道調(diào)度算法.其中,Pareto支配用懲罰函數(shù)法及可行解占優(yōu)的方式處理約束條件,用Pareto支配機(jī)制來處理多目標(biāo)函數(shù),最后設(shè)計了相應(yīng)的最優(yōu)解選擇機(jī)制選擇Pareto支配最優(yōu)解.實(shí)驗(yàn)結(jié)果表明:基于理想點(diǎn)法的遺傳模擬退火算法能以較小的概率獲得可行解,對航班跑道預(yù)調(diào)度有指導(dǎo)作用;基于Pareto支配的遺傳模擬退火算法能獲得一系列的可行解供調(diào)度者選擇,且實(shí)時性強(qiáng),能用于實(shí)時航班跑道調(diào)度,比理想點(diǎn)法更具有實(shí)際應(yīng)用價值.但是,Pareto支配獲得可行解之后,在一定的迭代代數(shù)內(nèi)很難改變其支配地位,將來應(yīng)設(shè)計使用支配可行解信息且使支配可行解在有限的迭代代數(shù)內(nèi)不斷向更優(yōu)方案進(jìn)化的優(yōu)化算法.

參考文獻(xiàn)：

[1]Wang S,Zhang Y,Zhang Z,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.

[2]Jungai T,Hongjun X.Optimizing arrival flight delay sche-duling based on simulated annealing algorithm [J].Physics Procedia,2012,33:348- 353.

[3]Faye A.Solving the aircraft landing problem with time discretization approach [J].European Journal of Operational Research,2013,243(3):1028- 1038.

[4]Montoya J,Rathinam S,Wood Z.Multi-objective departure runway scheduling using dynamic programming [J].IEEE Transactions on Intelligent Transportation Systems,2014,15(1):399- 413.

[5]Priyaa R S,Kumar S S.Efficient aircraft traffic scheduling using population heuristics with CART algorithm [J].International Journal of Science and Research,2014,3(1):248- 252.

[6]Ravizza S,Chen J,Atkin J A D,et al.Aircraft taxi time prediction:comparisons and insights [J].Applied Soft Computing,2014,14(Part C):397- 406.

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

[8]Liu Q,Wu T,Luo X.A space-time network model based on improved genetic algorithm for airport taxiing scheduling problems [J].Procedia Engineering,2011,15:1082- 1087.

[9]Hancerlio gullari G,Rabadi G,Al-Salem A H,et al.Greedy algorithms and meta-heuristics for a multiple runway combined arrival-departure aircraft sequencing problem [J].Journal of Air Transport Management,2013,32:39- 48.

[10]徐鵬.基于組合算法的多目標(biāo)優(yōu)化研究 [D].哈爾濱:哈爾濱工程大學(xué)信息與通信工程學(xué)院,2013.

[11]Samà M,D’Ariano A,D’Ariano P,et al.Optimal aircraft scheduling and routing at a terminal control area during disturbances [J].Transportation Research Part C:Emerging Technologies,2014,47:61- 85.

[12]劉愛軍,楊育,李斐,等.混沌模擬退火粒子群優(yōu)化算法研究及應(yīng)用 [J].浙江大學(xué)學(xué)報:工學(xué)版,2013,47(10):1722- 1730.

Liu Ai-jun,Yang Yu,Li Fei,et al.Chaotic simulated annealing particle swarm optimization algorithm research and its application [J].Journal of Zhejiang University:Engineering Science,2013,47(10):1722- 1730.

[13]李丹程,曹斌,鐘華剛,等.改進(jìn)GA-PSO算法在多跑道航班著陸調(diào)度中的應(yīng)用 [J].小型微型計算機(jī)系統(tǒng),2014,35(9):2110- 2115.

Li Dan-cheng,Cao Bin,Zhong Hua-gang,et al.Multi-runway flights landing schedules using an improved GA-PSO algorithm [J].Journal of Chinese Computer Systems,2014,35(9):2110- 2115.

[14]Chandrasekar S,Hwang I.Algorithm for optimal arrival and departure sequencing and runway assignment [J].Journal of Guidance,Control,and Dynamics,2014,38(4):601- 613.

A Constrained Multi-Objective Genetic Simulated Annealing

Algorithm for Runway Scheduling

ZhangShu-qin1XiaHong-shan1JiangYu1ZhanXu-ren2

(1.College of Civil Aviation, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, Jiangsu, China;

2. Jiao Zhou City Planning Bureau, Jiaozhou 266300, Shandong, China)

Abstract:In order to obtain an optimal runway-scheduling scheme to improve the efficiency of runway operation, a constrained multi-objective model for arrivals and departures on multi-runways is constructed, and an improved genetic simulated annealing algorithm is proposed by analyzing the characteristics of both the genetic algorithm and the simulated annealing one. In the proposed algorithm, the objective functions for runway scheduling are processed by means of the Pareto dominance and the ideal point method, and the constraint conditions are handled by using the penalty objective functions and the dominated feasible solution. Furthermore, the mechanisms of updating new particles and selecting the best scheme are determined. For the purpose of improving the performance of the optimal solution, the convergence speed of the proposed algorithm is controlled by changing the temperature adaptively. Finally, the effectiveness of the proposed algorithm is verified by the actual runway scheduling of a domestic huge airport. The results show that the proposed algorithm based on the Pareto dominance can obtain a set of better feasible solutions of runway scheduling and is of a better timeliness.

Key words:air transportation; closely parallel runway; constrained multi-objective optimization; genetic simulated annealing algorithm; Pareto optimal solution; ideal point method

中圖分類號：V 351.11

doi:10.3969/j.issn.1000-565X.2015.10.006