基于遺傳算法的列車調(diào)度仿真研究

高速鐵路采用“一臺快線”的運輸模式，運營密度大，運營速度快。列車在行駛過程受到的不確定外界干擾(如風(fēng)、雨、線路設(shè)備故障等)往往會造成眾多的列車晚點,給列車運行調(diào)整帶來較大的困難。與既有線的行車調(diào)度相比,高速鐵路的行車調(diào)度具有高實時性和整體性兩大特點。高實時性:列車的高速運行要求行車調(diào)度系統(tǒng)在盡可能短的時間內(nèi)對異常情況做出判斷。整體性:高速鐵路上運行的高速列車和中速列車均為旅客列車,因此高速列車的行車調(diào)整策略不能采用高速列車無限占用中速列車時間資源的調(diào)整策略,對于高速鐵路的列車調(diào)整必須全盤考慮,以保證列車安全正點運行。對于既有線的列車運行調(diào)整算法,國內(nèi)眾多學(xué)者進行了詳細地研究,在理論上提出了各種不同的調(diào)整策略和調(diào)整模型。文獻將列車運行調(diào)整問題看作一類有序加工的動態(tài)工件調(diào)度問題,對列車運行調(diào)整進行了分析,并建立了以列車運行時間為優(yōu)化目標的數(shù)學(xué)模型。數(shù)學(xué)模型在理論上具有一定的意義,但卻忽略了一個重要的方面:列車運行調(diào)整的目標不應(yīng)單純以列車的運行時間為優(yōu)化目標,而應(yīng)該以列車計劃運行圖為目標,保證調(diào)整后的列車能夠盡可能地“按圖行車”,以減少列車的晚點時間。文獻在利用離散事件動態(tài)系統(tǒng)理論的基礎(chǔ)上,建立了調(diào)整系統(tǒng)事件驅(qū)動的狀態(tài)空間模型,用分層決策和滾動優(yōu)化的方法設(shè)計了調(diào)整的通用算法。該算法在理論上具有重要的意義,但不適合高速鐵路的行車調(diào)度,原因是算法所采用的分層決策有可能造成中速列車無限避讓高速列車的局面。文獻分別基于圖論和模糊決策理論提出了不同的調(diào)整算法,但這些算法在實現(xiàn)時均具有相當大的難度。對于高速鐵路的列車運行調(diào)整算法,國內(nèi)的學(xué)者也進行了研究,但基本上只是基于決策支持系統(tǒng)思想提出了一些調(diào)整原則,并沒有明確提出優(yōu)化目標及相應(yīng)的優(yōu)化模型。本文在對高速鐵路列車運行調(diào)整問題進行分析的基礎(chǔ)上,以計劃運行圖為優(yōu)化目標,提出基于遺傳算法的行車調(diào)整優(yōu)化模型,并在高速鐵路綜合調(diào)度仿真系統(tǒng)中進行應(yīng)用。1行車調(diào)整問題的分類高速鐵路列車運行調(diào)整涉及到工務(wù)、電務(wù)、機務(wù)、車輛以及運輸?shù)缺姸嗖块T,它不但涉及到列車的運行狀態(tài)、線路狀況、鐵路沿線的氣候以及眾多部門,而且涉及到有關(guān)規(guī)章制度,如計規(guī)、調(diào)規(guī)及站細等。可以說調(diào)度工作是運輸生產(chǎn)過程與各種有關(guān)規(guī)章制度相結(jié)合的體現(xiàn),是一項必須有人工參與的復(fù)雜工作。在理想情況下,每列列車按照計劃運行圖給定的時刻表運行以完成運輸生產(chǎn)任務(wù)。但在實際的運輸生產(chǎn)過程中,不可避免地發(fā)生一些難以預(yù)料的情況,例如機車車輛故障、固定設(shè)備故障、鐵路沿線惡劣的氣候、中速列車上線晚點等。這些難以預(yù)料的情況往往導(dǎo)致列車不能按照預(yù)定的時刻表運行,甚至導(dǎo)致全線停車等。高速鐵路行車調(diào)整的工作目的就是當列車運行秩序發(fā)生紊亂時,通過對列車進行調(diào)整來恢復(fù)列車的運行秩序,盡量保證列車按圖行車,做到“接晚不增晚,晚點趕正點”。根據(jù)外界因素對列車造成晚點的嚴重程度,可將調(diào)整問題分為2種情況。①不可恢復(fù)的晚點情況:例如,由于線路遭到破壞而造成的列車晚點、具有破壞性的自然災(zāi)害(如地震)而造成的全線停車等情況。②可恢復(fù)的晚點情況:外界因素對列車造成晚點的嚴重程度比較輕微,調(diào)度員可以通過在區(qū)間“趕點”而恢復(fù)列車的正常運行。對于第1種情況,行車調(diào)整問題是一個非結(jié)構(gòu)化問題,要建立一個能夠?qū)ζ溥M行描述的數(shù)學(xué)模型是比較困難的事情,可采用專家系統(tǒng)或者決策支持系統(tǒng)的方法進行解決。對于第2種情況,行車調(diào)整問題實質(zhì)是根據(jù)列車的運行情況重新確定列車時刻表的問題。運輸部門在編制列車計劃運行圖時已對生產(chǎn)效率、設(shè)備利用率、區(qū)間通過能力等進行了充分的考慮,因此在重新確定時刻表時不必考慮效率問題,只需考慮在安全的基礎(chǔ)上如何使得調(diào)整后的運行圖盡可能地接近計劃運行圖。2行車調(diào)整問題的建模定義下列標識。m:調(diào)度區(qū)段內(nèi)的車站數(shù)。n:在調(diào)整時間段內(nèi)參與調(diào)整的列車數(shù)。g*:計劃運行圖。g*={(ga*i?j?gd*i?j)|i=1?2???ng?={(ga?i?j?gd?i?j)∣∣i=1?2???n;j=1,2,…,m},其中g(shù)a*i?ja?i?j,gd*i?j分別表示列車i原計劃在車站j的到達時刻和出發(fā)時刻。G:所有運行圖所構(gòu)成的集合。G={g|g為運行圖},其中g(shù)={(gai?j?gdi?j)|i=1?2???n;j=1,2,…,m},gai,j,gdi,j分別表示列車i在車站j的到達時刻和出發(fā)時刻。定義?p,q∈G,定義p,q之間的距離d(p,q)如下:d(p?q)=n∑i=1m∑j=1√(pai?j-qai?j)2+(pdi?j-qdi?j)2可以證明,上述定義的距離滿足以下3個條件:1)對于?p,q∈G,有唯一確定的實數(shù)d(p,q)與之相對應(yīng);2)d(p,q)≥0,d(p,q)=0的充分必要條件為p=q;3)d(p,q)≤d(p,r)+d(r,q),對?r∈G?？梢?集合G在上述定義下為度量空間,完全可以利用距離d(p,q)對2個運行圖之間的差距進行度量。在上述定義下,可將行車調(diào)整問題轉(zhuǎn)換為如下的數(shù)學(xué)問題:f=min?p∈Gd(p?g*)列車運行調(diào)整問題即是在運行圖空間中尋找一個運行圖,該運行圖與計劃運行圖之間具有最小的距離。考慮到高速鐵路上列車的運行等級,加入權(quán)重因子,定義行車調(diào)整的優(yōu)化模型如下:minf=n∑i=1m∑j=1ωi?√(pai?j-ga*i?j)2+(pdi?j-gd*i?j)2(1)式中:ωi為列車i的權(quán)重因子,ωi>0,ωi越大,表明列車i的級別越高;pai,j,pdi,j為優(yōu)化變量。按照列車的發(fā)車時刻不能早于計劃發(fā)車時刻的規(guī)定,有pdi,j≥gd*i?j(j=1,2,…,m)(2)設(shè)sti?j={1?t時刻列車i占用或者即將占用車站j的一條到發(fā)線0?其他根據(jù)股道數(shù)量約束,有n∑i=1sti?j≤Dj(j=1?2???m)(3)式中:Dj為車站j的到發(fā)線數(shù)量。根據(jù)列車在區(qū)間的運行時分,有式中:Tmin為列車i在區(qū)間[j,j+1]的最小運行時分。根據(jù)追蹤運行間隔時間的要求,有|pdi?j-pdk?j|≥Ιz(i≠k?j=1?2???m)(5)式中:Iz為最小追蹤列車間隔時間。根據(jù)維修天窗的時間要求,有或式中:tb,te分別為維修天窗的開始時間和結(jié)束時間。式(1)—式(6)表明,列車運行調(diào)整問題實質(zhì)上是優(yōu)化問題。優(yōu)化模型的目標函數(shù)為式(1),約束條件為式(2)—式(6)。3非線性優(yōu)化問題由上述分析可知,列車運行調(diào)整問題實質(zhì)上是一個有約束的非線性優(yōu)化問題。傳統(tǒng)的優(yōu)化方法由于采用梯度技術(shù)而受到許多局限。因此,本文在對數(shù)學(xué)模型改進的基礎(chǔ)上,提出一種基于遺傳算法的調(diào)整模型。3.1代表個別時段所通過的秒數(shù)列車運行調(diào)整問題實質(zhì)上是重新確定列車時刻表的過程,即重新確定式(1)中的變量。為簡單起見,可用從午夜零點到某個時刻所經(jīng)過的秒數(shù)來代表某個時刻,例如,4000代表01:06:40。因此,對于列車運行調(diào)整問題,可采用染色體整數(shù)編碼,編碼格式如圖1所示。在這種編碼格式中,染色體的最大長度為2nm。3.2約束條件式的認定適應(yīng)度函數(shù)是對染色體適應(yīng)環(huán)境能力的評價函數(shù),一個染色體的適應(yīng)度值越大,表明該染色體的適應(yīng)環(huán)境的能力越強,即性能越好。在定義適應(yīng)度函數(shù)之前,首先對約束條件進行處理。按約束條件式(2)要求,列車在車站的出發(fā)時間不能早于計劃發(fā)車時間。根據(jù)目標函數(shù)可以證明列車的出發(fā)時間越接近計劃出發(fā)時間,則調(diào)整計劃圖越接近計劃運行圖。因此,對于約束條件式(2)可以采取罰函數(shù)的方法進行處理。約束條件式(3)—式(6)與約束條件式(2)不同,對于約束條件式(3)—式(6)只有2種情況:要么滿足,要么不滿足。凡滿足約束條件式(3)—式(6)的調(diào)整運行圖都有可能成為最優(yōu)的調(diào)整運行圖。因此,對于約束條件式(3)—式(6)必須加以改進,以適應(yīng)遺傳算法。對于約束條件式(3),定義函數(shù):f1={0?n∑i=1sti?j≤Dj(j=1?2???m)Μ?其他對于約束條件式(4),定義函數(shù):f2={0?pai?j+1≥pdi?j+Τmin(i=1?2???n；j=1?2???m)Μ?其他對于約束條件式(5),定義函數(shù):f3={0?|pdi?j-pdk?j|≥Ιz(i≠k?j=1?2???m)Μ?其他對于約束條件式(6),定義函數(shù):f4={0?pai?j?pdi?j≤tb或pai?j?pdi?j≥te(i=1?2???n；j=1?2???m)Μ?其他式中:M為正整數(shù)。在定義f1—f4的基礎(chǔ)上,定義適應(yīng)度函數(shù)如下:f(→p1???→pi???→pn)=Cmax-n∑i=1m∑j=1ωi√(pai?j-ga*i?j)2+(pdi?j-gd*i?j)2-wn∑i=1m∑j=1(pdi?j-gd*i?j)sgn(pdi?j-gd*i?j)-f1-f2-f3-f4式中:Cmax為計算機所能表達的最大正實數(shù);→pi=(pai?1?pdi?1???pai?m?pdi?m)?i=1?2???n;w為約束條件式(2)的懲罰因子;sgn為符號函數(shù)。實際上,對約束條件式(3)—式(6)的處理也是采用了罰函數(shù)的方法:要么不進行處罰,要么進行處罰,懲罰因子為M。3.3交叉處理交叉算子是遺傳算法區(qū)別于其他算法的主要特征,它是產(chǎn)生下一代群體的主要方法。根據(jù)編碼格式,采用兩點交叉算子,如圖2所示。3.4變異算子群體經(jīng)過多次交叉以后,群體中的染色體經(jīng)常會趨于單一而產(chǎn)生過早收斂的現(xiàn)象。為克服這種現(xiàn)象,可采用變異算子。變異算子的作用是以一定的概率使染色體中的某些基因發(fā)生突變,以增加群體中染色體的多樣性。根據(jù)染色體的編碼格式,定義變異算子:S:p→p+αα∈[-30,30]且α為均勻分布的隨機變量。變異算子即以一定的概率對優(yōu)化變量p加以擾動,擾動的左右幅度不超過1min。3.5復(fù)制算子復(fù)制算子的目的是根據(jù)預(yù)先確定的策略在當前群體中選取某些染色體作為下一代群體中的染色體。對于復(fù)制算子,可采用賭輪盤的策略進行復(fù)制。3.6基于群體遺傳模型的運行在確定編碼、適應(yīng)度函數(shù)以及3個算子的基礎(chǔ)上,基于遺傳算法的調(diào)整算法流程如圖3所示?；谏鲜鏊枋龅哪Ｐ?開發(fā)列車運行調(diào)度仿真子系統(tǒng)。實際使用時的遺傳參數(shù)設(shè)置為:群體的規(guī)模