不固定區(qū)段運(yùn)用模式下高速鐵路成對(duì)運(yùn)行圖動(dòng)車(chē)組交路計(jì)劃優(yōu)化方法

不固定區(qū)段運(yùn)用模式下高速鐵路成對(duì)運(yùn)行圖動(dòng)車(chē)組交路計(jì)劃優(yōu)化方法

火車(chē)列車(chē)是中國(guó)長(zhǎng)距離客運(yùn)的重要運(yùn)載工具。由于運(yùn)行速度高、購(gòu)置成本昂貴，如何安全、經(jīng)濟(jì)地使用動(dòng)車(chē)組是我國(guó)鐵路運(yùn)輸企業(yè)和相關(guān)學(xué)者關(guān)注的重點(diǎn)問(wèn)題。動(dòng)車(chē)組運(yùn)用計(jì)劃是在一定時(shí)期內(nèi)，根據(jù)給定列車(chē)運(yùn)行圖、動(dòng)車(chē)組配置狀況、動(dòng)車(chē)組檢修設(shè)施條件、站車(chē)作業(yè)規(guī)定和動(dòng)車(chē)組修程規(guī)定，合理安排動(dòng)車(chē)組擔(dān)當(dāng)運(yùn)行任務(wù)并及時(shí)完成各級(jí)檢修任務(wù)的綜合計(jì)劃。一般分為動(dòng)車(chē)組交路計(jì)劃、動(dòng)車(chē)組分配計(jì)劃和動(dòng)車(chē)組檢修計(jì)劃等3個(gè)部分。其中，動(dòng)車(chē)組交路計(jì)劃規(guī)定列車(chē)間車(chē)底接續(xù)周轉(zhuǎn)關(guān)系和1級(jí)檢修安排，是動(dòng)車(chē)組分配計(jì)劃和檢修計(jì)劃的基礎(chǔ)。國(guó)內(nèi)學(xué)者針對(duì)動(dòng)車(chē)組交路計(jì)劃編制方法進(jìn)行深入研究。文獻(xiàn)以我國(guó)高速鐵路為背景，分析動(dòng)車(chē)組使用的不同方式，指出不固定區(qū)段使用是較好的動(dòng)車(chē)組運(yùn)用方式。該方式也成為后續(xù)研究的基本前提。文獻(xiàn)在不考慮動(dòng)車(chē)組檢修條件約束時(shí)，將動(dòng)車(chē)組交路計(jì)劃優(yōu)化問(wèn)題轉(zhuǎn)化為“指派問(wèn)題”，建立以周轉(zhuǎn)接續(xù)時(shí)間最小為目標(biāo)的動(dòng)車(chē)組周轉(zhuǎn)優(yōu)化模型，利用匈牙利算法求解。當(dāng)考慮動(dòng)車(chē)組檢修條件約束時(shí)，動(dòng)車(chē)組交路計(jì)劃優(yōu)化問(wèn)題是典型的NP-Hard問(wèn)題?；诹熊?chē)運(yùn)行圖構(gòu)建的動(dòng)車(chē)組運(yùn)用網(wǎng)絡(luò)，文獻(xiàn)分別考慮空車(chē)回送、多車(chē)型、多基地、檢修累計(jì)里程約束、檢修累計(jì)時(shí)間約束等條件建立整數(shù)規(guī)劃模型并開(kāi)發(fā)不同種類(lèi)的啟發(fā)式算法。其中，文獻(xiàn)應(yīng)用可變深度局部搜索思想和回溯技術(shù)分別設(shè)計(jì)假日和平日動(dòng)車(chē)組交路計(jì)劃求解算法；文獻(xiàn)在此基礎(chǔ)上針對(duì)多基地動(dòng)車(chē)組交路計(jì)劃開(kāi)發(fā)基于路段交換的局域搜索算法；文獻(xiàn)提出周期性運(yùn)用思想并建立數(shù)學(xué)模型，應(yīng)用可變深度局部搜索思想和回溯策略開(kāi)發(fā)交路計(jì)劃編制模擬軟件進(jìn)行求解；文獻(xiàn)將問(wèn)題歸結(jié)為帶補(bǔ)給的多人旅行商問(wèn)題進(jìn)行建模，并設(shè)計(jì)基于動(dòng)車(chē)組最優(yōu)接續(xù)網(wǎng)絡(luò)的分層遞階優(yōu)化啟發(fā)式算法進(jìn)行求解；文獻(xiàn)設(shè)計(jì)改進(jìn)的螞蟻算法進(jìn)行求解；文獻(xiàn)用全部列車(chē)形成的環(huán)形排列表示動(dòng)車(chē)組交路并建立模型，通過(guò)引入罰值函數(shù)和三交換鄰域結(jié)構(gòu)，設(shè)計(jì)求解模型的模擬退火算法?？梢?jiàn)，既有文獻(xiàn)針對(duì)動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型和算法均進(jìn)行較多的研究，且形成大量的成果，但由于問(wèn)題較為復(fù)雜，還未有成熟有效的方法應(yīng)用于實(shí)際生產(chǎn)，需要繼續(xù)研究和探索。本文基于不固定區(qū)段運(yùn)用模式，對(duì)成對(duì)運(yùn)行圖動(dòng)車(chē)組交路計(jì)劃的優(yōu)化模型和算法進(jìn)行研究。在對(duì)動(dòng)車(chē)組交路計(jì)劃相關(guān)約束條件、優(yōu)化目標(biāo)和編制過(guò)程進(jìn)行分析的基礎(chǔ)上，針對(duì)“人機(jī)交互”過(guò)程中計(jì)算機(jī)編制階段，以“列車(chē)間車(chē)底接續(xù)時(shí)間總和最少”和“檢修次數(shù)最少”為目標(biāo)，考慮簡(jiǎn)化列車(chē)運(yùn)行圖要求和相關(guān)作業(yè)約束建立整數(shù)規(guī)劃模型，重點(diǎn)針對(duì)較難刻畫(huà)的動(dòng)車(chē)組累計(jì)走行里程和時(shí)間變量進(jìn)行設(shè)計(jì)；應(yīng)用粒子群優(yōu)化算法基本思想，通過(guò)對(duì)基本參數(shù)、運(yùn)算規(guī)則的重新定義，提出求解模型的粒子群優(yōu)化算法，并通過(guò)算例驗(yàn)證算法的有效性。1動(dòng)車(chē)組交路計(jì)劃確定動(dòng)車(chē)組完成1級(jí)檢修后至下次同級(jí)檢修前擔(dān)當(dāng)?shù)牧熊?chē)與各種作業(yè)的有序集合稱(chēng)為1條運(yùn)用交路。運(yùn)用交路中按照自然天劃分為若干交路段?；诮o定的列車(chē)運(yùn)行圖，滿(mǎn)足各種約束條件，將所有列車(chē)運(yùn)行線(xiàn)連接成若干運(yùn)用交路后形成的車(chē)底周轉(zhuǎn)接續(xù)方案稱(chēng)為動(dòng)車(chē)組交路計(jì)劃，簡(jiǎn)稱(chēng)交路計(jì)劃。在實(shí)際生產(chǎn)中，完善的交路計(jì)劃需要滿(mǎn)足較多約束條件且具有多重優(yōu)化目標(biāo)，編制過(guò)程也較為復(fù)雜。1.1強(qiáng)制條件與優(yōu)化目標(biāo)的分析交路計(jì)劃應(yīng)滿(mǎn)足的約束條件主要有以下3個(gè)方面：(1)動(dòng)車(chē)組擔(dān)當(dāng)及約束列車(chē)運(yùn)行圖中規(guī)定的所有運(yùn)行任務(wù)都必須由動(dòng)車(chē)組擔(dān)當(dāng)，且動(dòng)車(chē)組型號(hào)、數(shù)量須滿(mǎn)足列車(chē)運(yùn)行線(xiàn)對(duì)列車(chē)速度、運(yùn)能（體現(xiàn)為列車(chē)編組或定員）等方面的要求。(2)交路作業(yè)約束一是列車(chē)接續(xù)作業(yè)約束。動(dòng)車(chē)組連續(xù)擔(dān)當(dāng)2次運(yùn)行任務(wù)之間相關(guān)作業(yè)，需滿(mǎn)足“動(dòng)車(chē)組在后續(xù)列車(chē)始發(fā)前到達(dá)其所在始發(fā)站，且到達(dá)時(shí)刻與后續(xù)列車(chē)始發(fā)時(shí)刻間的時(shí)間間隔需滿(mǎn)足最小作業(yè)時(shí)間要求”。二是1級(jí)檢修作業(yè)約束。我國(guó)針對(duì)各種動(dòng)車(chē)組車(chē)型制定出1～5級(jí)修程。由于尚未落實(shí)到具體動(dòng)車(chē)組，交路計(jì)劃中僅考慮1級(jí)檢修作業(yè)，且在任意動(dòng)車(chē)運(yùn)用所進(jìn)行。該約束內(nèi)容可描述為：“當(dāng)動(dòng)車(chē)組累計(jì)走行里程或時(shí)間達(dá)到或接近該車(chē)型的1級(jí)檢修標(biāo)準(zhǔn)時(shí)，需要入動(dòng)車(chē)運(yùn)用所進(jìn)行檢修，檢修作業(yè)時(shí)間需滿(mǎn)足該車(chē)型最小檢修作業(yè)時(shí)間標(biāo)準(zhǔn)”。在鐵路實(shí)際生產(chǎn)中，為滿(mǎn)足開(kāi)行臨時(shí)客車(chē)、調(diào)整運(yùn)用交路等需要，允許列車(chē)?yán)塾?jì)走行里程或時(shí)間超過(guò)修程標(biāo)準(zhǔn)一定的比例。但在交路計(jì)劃編制過(guò)程中，為保證計(jì)劃在實(shí)際執(zhí)行時(shí)的靈活性，一般嚴(yán)格遵守修程標(biāo)準(zhǔn)約束。(3)交路及運(yùn)行費(fèi)當(dāng)動(dòng)車(chē)組在車(chē)站、動(dòng)車(chē)運(yùn)用所、存車(chē)場(chǎng)進(jìn)行相關(guān)作業(yè)時(shí)，需占用到發(fā)線(xiàn)、檢修線(xiàn)、存車(chē)線(xiàn)等各種固定設(shè)施資源；實(shí)施交路計(jì)劃需要足夠數(shù)量的動(dòng)車(chē)組。因此，在為各種作業(yè)預(yù)留時(shí)間窗時(shí)，需要考慮相關(guān)固定設(shè)施的能力；所用動(dòng)車(chē)組數(shù)量也需滿(mǎn)足動(dòng)車(chē)組配置條件約束，即各種車(chē)型動(dòng)車(chē)組的可用數(shù)量約束。(2）檢修成本和空車(chē)走行成本在滿(mǎn)足運(yùn)行圖需求及相關(guān)作業(yè)約束的前提下，經(jīng)濟(jì)性最優(yōu)是交路計(jì)劃優(yōu)化的主要方向。既有研究成果選用的優(yōu)化目標(biāo)主要包括：動(dòng)車(chē)組使用數(shù)量最少、檢修成本最低、空車(chē)走行成本最低、動(dòng)車(chē)組使用均衡性最好等。其中，對(duì)于“空車(chē)走行成本最低”，由于我國(guó)大多數(shù)高速鐵路列車(chē)開(kāi)行密度大，區(qū)段通過(guò)能力較為緊張，除早晚空閑時(shí)段外，通過(guò)空車(chē)調(diào)撥實(shí)現(xiàn)列車(chē)接續(xù)的難度較大；對(duì)于“動(dòng)車(chē)組使用均衡性最好”，由于交路計(jì)劃編制階段尚未具體到某一動(dòng)車(chē)組，且在后續(xù)階段考慮“動(dòng)車(chē)組使用均衡性”較為有意義。因此，可選擇“動(dòng)車(chē)組使用數(shù)量最少”和“檢修成本最低”作為交路計(jì)劃的優(yōu)化目標(biāo)。1.2準(zhǔn)備過(guò)程分析(1）交路計(jì)劃的優(yōu)化若考慮所有約束條件并采用計(jì)算機(jī)自動(dòng)編制方式，將使問(wèn)題規(guī)模巨大，較難在可接受的時(shí)間內(nèi)求出較優(yōu)解，且生成的交路計(jì)劃一般無(wú)法實(shí)施，須通過(guò)人工調(diào)整滿(mǎn)足一些特殊需求。因此，采用人機(jī)交互方式形成最終方案，即首先對(duì)約束條件及優(yōu)化目標(biāo)進(jìn)行適當(dāng)簡(jiǎn)化，并使用計(jì)算機(jī)求出初始方案；然后通過(guò)人工調(diào)整或與其他運(yùn)輸生產(chǎn)計(jì)劃協(xié)同編制以滿(mǎn)足在計(jì)算機(jī)求解時(shí)未考慮的約束條件。本文提出的動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型和算法即是面向計(jì)算機(jī)編制階段的需求。(2）計(jì)算解算器流程分析(1)交路計(jì)劃編制內(nèi)容簡(jiǎn)化列車(chē)運(yùn)行圖約束。為降低求解難度，將相同速度的列車(chē)視為同類(lèi)車(chē)型，在交路計(jì)劃編制完成后再根據(jù)交路中各次列車(chē)運(yùn)能需求和車(chē)型配置數(shù)量確定具體車(chē)型和編組。包含多個(gè)速度等級(jí)的列車(chē)運(yùn)行圖可以按速度等級(jí)拆分后分別進(jìn)行交路計(jì)劃編制。因此，在交路計(jì)劃編制模型中可以不考慮列車(chē)運(yùn)行線(xiàn)的具體運(yùn)能要求，即僅要求各次列車(chē)有且只有一組動(dòng)車(chē)組擔(dān)當(dāng)。簡(jiǎn)化1級(jí)檢修作業(yè)約束。我國(guó)各車(chē)型動(dòng)車(chē)組1級(jí)檢修修程標(biāo)準(zhǔn)、檢修時(shí)間差異較小，在計(jì)算機(jī)求解時(shí)可采用統(tǒng)一的修程和檢修作業(yè)時(shí)間標(biāo)準(zhǔn)。其中，檢修作業(yè)時(shí)間標(biāo)準(zhǔn)取各種車(chē)型1級(jí)檢修時(shí)間的最大值。簡(jiǎn)化資源約束。對(duì)于固定設(shè)施，能力值是針對(duì)特定時(shí)間范圍而言的，列車(chē)的占用需求在時(shí)間上分布不均勻，模型中無(wú)法用簡(jiǎn)單參數(shù)準(zhǔn)確刻畫(huà)能力約束。對(duì)于動(dòng)車(chē)組資源，通過(guò)計(jì)算機(jī)求得的初始解使用的動(dòng)車(chē)組數(shù)量可視為完成運(yùn)行圖所需要的最小值；若不滿(mǎn)足移動(dòng)設(shè)備資源能力約束，說(shuō)明該運(yùn)行圖無(wú)法實(shí)施。需要首先對(duì)運(yùn)行圖進(jìn)行調(diào)整后再重新編制交路計(jì)劃。因此，計(jì)算機(jī)編制初始解時(shí)可不考慮資源約束。(2)運(yùn)行時(shí)間總參數(shù)首先將列車(chē)運(yùn)行圖轉(zhuǎn)化為以列車(chē)為節(jié)點(diǎn)、列車(chē)間接續(xù)關(guān)系為邊的動(dòng)車(chē)組運(yùn)用網(wǎng)絡(luò)，然后運(yùn)用算法在運(yùn)用網(wǎng)絡(luò)上尋找滿(mǎn)足約束條件且目標(biāo)函數(shù)最優(yōu)的運(yùn)用交路集合。由于“動(dòng)車(chē)組使用數(shù)量=（列車(chē)運(yùn)行時(shí)間總和+列車(chē)間車(chē)底接續(xù)時(shí)間總和）/運(yùn)行圖周期”，且“列車(chē)運(yùn)行時(shí)間總和”與“運(yùn)行圖周期”為定值。因此，“動(dòng)車(chē)組使用數(shù)量最少”優(yōu)化目標(biāo)可轉(zhuǎn)化為“列車(chē)間車(chē)底接續(xù)時(shí)間總和最少”，求解過(guò)程為考慮車(chē)底接續(xù)地點(diǎn)的作業(yè)時(shí)間標(biāo)準(zhǔn)等約束條件，尋找使列車(chē)間車(chē)底接續(xù)時(shí)間總和最少的邊集合過(guò)程?！皺z修成本最低”目標(biāo)可轉(zhuǎn)化為“必須的檢修次數(shù)最少”，求解過(guò)程為考慮動(dòng)車(chē)組1級(jí)檢修修程標(biāo)準(zhǔn)、檢修地點(diǎn)、檢修作業(yè)時(shí)間標(biāo)準(zhǔn)等約束條件，將列車(chē)按順序組合成若干運(yùn)用交路，并使其數(shù)量最少的過(guò)程。其中，前者主要考慮列車(chē)間車(chē)底接續(xù)時(shí)間等確定性變量，是靜態(tài)問(wèn)題，可用精確算法求解最優(yōu)解；后者由于需要根據(jù)動(dòng)車(chē)組累計(jì)走行里程和時(shí)間等不確定性累計(jì)變量確定檢修時(shí)機(jī)，是動(dòng)態(tài)問(wèn)題，目前無(wú)法用精確算法求解最優(yōu)解。因此，累計(jì)變量參數(shù)刻畫(huà)與考慮累計(jì)變量鄰域解生成分別是求解過(guò)程中模型構(gòu)建和算法設(shè)計(jì)的關(guān)鍵。(3)交路連接而成的環(huán)形路徑由于生成的各運(yùn)用交路間也有接續(xù)關(guān)系存在，交路計(jì)劃的解表現(xiàn)為單一或若干由運(yùn)用交路連接而成的環(huán)形路徑，即在運(yùn)用網(wǎng)絡(luò)上的1條或若干條回路。值得注意的是，若回路中動(dòng)車(chē)組在檢修地點(diǎn)停留時(shí)間均不滿(mǎn)足檢修作業(yè)時(shí)間要求或回路不通過(guò)檢修地點(diǎn)，則在該回路中無(wú)法安排檢修，稱(chēng)該類(lèi)回路為“無(wú)檢修回路”，求解時(shí)應(yīng)予以避免。2問(wèn)題目標(biāo)及模型的建立根據(jù)上述分析，基于動(dòng)車(chē)組運(yùn)用網(wǎng)絡(luò)，以“列車(chē)間車(chē)底接續(xù)時(shí)間總和最少”和“必須檢修次數(shù)最少”為目標(biāo)，考慮簡(jiǎn)化后約束條件，設(shè)計(jì)整數(shù)規(guī)劃模型。2.1動(dòng)車(chē)組的使用網(wǎng)絡(luò)根據(jù)給定的成對(duì)列車(chē)運(yùn)行圖，以列車(chē)為節(jié)點(diǎn)，列車(chē)間接續(xù)關(guān)系為邊構(gòu)建動(dòng)車(chē)組運(yùn)用網(wǎng)絡(luò)，表示為加權(quán)有向圖G(V,E），并設(shè)置參數(shù)如下：(1）車(chē)站集合設(shè)S={s|s=1，…，m}為運(yùn)行圖中有列車(chē)始發(fā)和終到作業(yè)的車(chē)站集合；設(shè)SM為連接有動(dòng)車(chē)運(yùn)用所的車(chē)站集合，且(2）vivi屬性設(shè)V={vi}為運(yùn)行圖周期內(nèi)所有列車(chē)集合；vi表示V中第i個(gè)列車(chē)，i=1,2，…，n,n=|V|；vi具有屬性：sid,tid,sia,tia,dir,tir。其中：sid∈S、tid、sia∈S、tia、dir、tir分別表示列車(chē)vi的始發(fā)站、始發(fā)時(shí)刻、終到站、終到時(shí)刻、運(yùn)行里程和運(yùn)行時(shí)間。(3）車(chē)站接接點(diǎn)壓力值cij設(shè)E={eij|eij=(vi,vj）}為動(dòng)車(chē)組運(yùn)用網(wǎng)絡(luò)G的邊集合，邊eij=(vi,vj）表示列車(chē)vi和vj間的接續(xù)關(guān)系。定義邊eij具有如下屬性：cij為邊eij的費(fèi)用值，用列車(chē)間接續(xù)時(shí)間表示，其值按照式（1）計(jì)算；uij為邊eij是否可以進(jìn)行檢修作業(yè)的0-1變量，按照式（2）取值，即當(dāng)接續(xù)關(guān)系所在車(chē)站與動(dòng)車(chē)運(yùn)用所連接且接續(xù)時(shí)間滿(mǎn)足檢修作業(yè)時(shí)間要求時(shí)，可在該接續(xù)時(shí)間窗內(nèi)安排檢修作業(yè)，若uij=1，稱(chēng)該邊為檢修資格邊。式中，常量tsc為動(dòng)車(chē)組在車(chē)站s∈S進(jìn)行接續(xù)作業(yè)需要的最小時(shí)間。式中：常量tsm為動(dòng)車(chē)組在與車(chē)站s∈SM連接的動(dòng)車(chē)運(yùn)用所進(jìn)行1級(jí)檢修需要的最小作業(yè)時(shí)間與出入段走行時(shí)間之和。2.2交路段及列車(chē)走行公里在動(dòng)車(chē)組運(yùn)用網(wǎng)絡(luò)基礎(chǔ)上，為表述交路計(jì)劃中列車(chē)接續(xù)關(guān)系、檢修作業(yè)安排及修程標(biāo)準(zhǔn)約束，定義以下變量：式中：xij為邊eij是否被交路選中的0-1變量，若xij=1，稱(chēng)該邊為交路邊。式中：yij為邊eij是否被交路安排檢修作業(yè)的0-1變量，若yij=1，稱(chēng)該邊為檢修邊，檢修邊必為交路邊。式中：dij為邊eij的里程累計(jì)變量，表示運(yùn)用交路中動(dòng)車(chē)組自上次1級(jí)檢修作業(yè)結(jié)束后至接續(xù)關(guān)系eij發(fā)生時(shí)的累計(jì)走行里程。采用“傳遞”的方式計(jì)算，即根據(jù)緊前邊集合中交路邊（簡(jiǎn)稱(chēng)“緊前交路邊”）相關(guān)變量計(jì)算當(dāng)前邊的里程累計(jì)變量。設(shè)b為運(yùn)用交路中列車(chē)i的緊前列車(chē)，則邊ebi為邊eij的緊前交路邊。當(dāng)邊eij為交路邊（xij=1），同時(shí)緊前交路邊ebi為檢修邊（ybi=1）或里程累計(jì)變量處于傳遞狀態(tài)（dbi>0）時(shí)，邊eij的里程累計(jì)變量dij有效。其中的條件“ybi=1或dbi>0”可以合并為（ybi+dbi)>0。由于在邊eij的緊前邊集合中，交路邊之外的其他邊的yki值和dki值均為0，因此當(dāng)不明確指出緊前交路邊時(shí)，可用求和方式表示緊前交路邊相關(guān)參數(shù)，即則dij值為在緊前交路邊里程累計(jì)變量的基礎(chǔ)上加上列車(chē)i的走行里程，即其中：（1-ybi）表示當(dāng)緊前交路邊為檢修邊時(shí)，里程累計(jì)量清零后重新開(kāi)始統(tǒng)計(jì)。式中：tij為邊eij的時(shí)間累計(jì)變量，表示運(yùn)用交路中動(dòng)車(chē)組自上次1級(jí)檢修作業(yè)結(jié)束至邊eij開(kāi)始時(shí)刻止的累計(jì)走行時(shí)間，計(jì)算過(guò)程與dij類(lèi)似，僅在計(jì)算時(shí)加上緊前交路邊的接續(xù)時(shí)間?；谏鲜鲎兞?，動(dòng)車(chē)組運(yùn)用模型可以描述為式（7）為目標(biāo)函數(shù)，表示列車(chē)間車(chē)底接續(xù)時(shí)間總和與檢修次數(shù)的加權(quán)和最小，w1和w2為權(quán)重系數(shù)。式（8）～式（14）為模型約束條件。其中：式（8）和式（9）保證每個(gè)列車(chē)節(jié)點(diǎn)必須且僅可以被覆蓋一次；式（10）保證只有當(dāng)邊eij被選中且為檢修資格邊時(shí)，可以在邊eij的時(shí)間窗內(nèi)安排檢修作業(yè)；式（11）和式（12）表示動(dòng)車(chē)組擔(dān)當(dāng)任意列車(chē)i后，累計(jì)走行里程和時(shí)間均不超過(guò)1級(jí)檢修修程標(biāo)準(zhǔn)（D1為里程標(biāo)準(zhǔn)，T1為時(shí)間標(biāo)準(zhǔn)），即保證各交路符合檢修約束；式（13）表示在運(yùn)用交路中，動(dòng)車(chē)組擔(dān)當(dāng)任意列車(chē)i后，里程累計(jì)變量和時(shí)間累計(jì)變量不能為0，即禁止“無(wú)檢修回路”存在。3其他解的優(yōu)化由于存在動(dòng)車(chē)組累計(jì)走行里程和時(shí)間變量，交路計(jì)劃不同的可行解之間很難直接相互借鑒。但可以看出，目標(biāo)函數(shù)值較優(yōu)的解包含的接續(xù)關(guān)系在一定程度上有利于目標(biāo)優(yōu)化，可作為其他解的優(yōu)化參考。應(yīng)用粒子群優(yōu)化算法思想，本文設(shè)計(jì)求解算法的主要內(nèi)容如下：(1）基本參數(shù)及運(yùn)算規(guī)則定義。為加強(qiáng)粒子針對(duì)“列車(chē)間車(chē)底接續(xù)時(shí)間總和”目標(biāo)尋優(yōu)的目的性，引入動(dòng)車(chē)組運(yùn)用最優(yōu)接續(xù)網(wǎng)絡(luò)作為粒子運(yùn)動(dòng)參考。(2）粒子適應(yīng)度值計(jì)算方法。針對(duì)粒子位置無(wú)法直接表達(dá)動(dòng)車(chē)組累計(jì)走行里程和時(shí)間變量并計(jì)算檢修次數(shù)的特點(diǎn)，設(shè)計(jì)包括生成初始交路和修正超修程交路的運(yùn)用交路生成方法。(3）總體求解步驟。參照粒子群優(yōu)化算法設(shè)計(jì)完整的交路計(jì)劃求解步驟。3.1交路計(jì)劃特征定義為使粒子群優(yōu)化算法應(yīng)用于求解交路計(jì)劃，需要針對(duì)交路計(jì)劃特征，對(duì)相關(guān)參數(shù)及運(yùn)算規(guī)則進(jìn)行定義，具體包括：粒子位置、適應(yīng)度值、運(yùn)動(dòng)速度的表示和計(jì)算，以及粒子的移動(dòng)規(guī)則和運(yùn)動(dòng)方程。(1）列車(chē)集和列車(chē)數(shù)量一個(gè)粒子位置代表一個(gè)可行解的具體內(nèi)容。對(duì)于交路計(jì)劃優(yōu)化模型，可行解用一組滿(mǎn)足約束條件的邊的集合表示，如式（15）所示。式中：n是列車(chē)數(shù)；第i個(gè)元素li表示列車(chē)集合V中第i列列車(chē)vi的后續(xù)列車(chē)為vli，即邊ei,li被選中，xi,li=1。該表示形式可滿(mǎn)足式（9）的約束。根據(jù)粒子位置表示形式，可直接確定列車(chē)vi的緊前列車(chē)vk(lk=i），則邊ei,li屬性中累計(jì)里程和時(shí)間變量的計(jì)算可分別簡(jiǎn)化為式（16）和式（17）。(2）適應(yīng)度函數(shù)值f粒子適應(yīng)度值是評(píng)價(jià)粒子位置優(yōu)劣的具體指標(biāo)。根據(jù)本文所建模型，粒子的適應(yīng)度函數(shù)值F包括兩部分：第一部分為接續(xù)時(shí)間總和，用C表示；第二部分為1級(jí)檢修作業(yè)總次數(shù)，即檢修邊總數(shù)，用Y表示。根據(jù)粒子位置L表示形式，粒子適應(yīng)度函數(shù)值計(jì)算式為(3）速度ri的定義速度的作用是改變粒子的位置以便產(chǎn)生鄰域解，是不同可行解間互相“借鑒學(xué)習(xí)”的體現(xiàn)。R由2個(gè)位置L2和L1相減得到，表示粒子在位置L1上以速度R移動(dòng)將到達(dá)位置L2。與粒子位置的定義類(lèi)似，速度R也是一個(gè)包含n個(gè)元素的集合，表示為：式中：n是列車(chē)數(shù)。第i個(gè)元素ri的含義如下：比較L1和L2的第i個(gè)元素值，如果相同，表示第i個(gè)元素粒子不需要移動(dòng)，即速度ri=0；否則，表示第i個(gè)元素粒子需要從lia以速度ri移動(dòng)到lib，即速度ri=lib。(4）速度ri約束下的粒子尋優(yōu)若粒子嚴(yán)格按照速度飛行，將很快陷入局部極值。為避免這種情況，對(duì)粒子移動(dòng)過(guò)程定義具有概率意義的數(shù)乘運(yùn)算，表示為式中：μ為速度R執(zhí)行的概率規(guī)則，即計(jì)算時(shí)，對(duì)R中每一個(gè)元素的速度ri生成1個(gè)0～1間的隨機(jī)數(shù)rand，然后根據(jù)概率規(guī)則判斷是否執(zhí)行ri。當(dāng)執(zhí)行速度ri時(shí)，為滿(mǎn)足式（8）的約束，邊ei,li與ep(ri),ri需進(jìn)行交叉操作（p(ri）為動(dòng)車(chē)組擔(dān)當(dāng)ri列車(chē)之前擔(dān)當(dāng)?shù)牧熊?chē)）。速度執(zhí)行的概率規(guī)則是粒子尋優(yōu)的關(guān)鍵。為增強(qiáng)粒子的尋優(yōu)能力，本文引入動(dòng)車(chē)組最優(yōu)接續(xù)網(wǎng)絡(luò)作為粒子速度執(zhí)行的參考。動(dòng)車(chē)組最優(yōu)接續(xù)網(wǎng)絡(luò)是由滿(mǎn)足“列車(chē)間車(chē)底接續(xù)時(shí)間總和最少”的所有最優(yōu)解組成的解空間，是動(dòng)車(chē)組運(yùn)用網(wǎng)絡(luò)的子集。由最優(yōu)接續(xù)網(wǎng)絡(luò)中的邊組成的交路集合自然滿(mǎn)足“列車(chē)間車(chē)底接續(xù)時(shí)間總和最少”的優(yōu)化目標(biāo)。以“最優(yōu)接續(xù)網(wǎng)絡(luò)”為參考有利于粒子尋優(yōu)。設(shè)最優(yōu)接續(xù)網(wǎng)絡(luò)為Gbest(V,Ebest），當(dāng)邊ei,ri∈Ebest時(shí)，給予速度R中第i個(gè)元素較大的執(zhí)行概率μin；當(dāng)邊時(shí)，則給予速度R中第i個(gè)元素較小的執(zhí)行概率μout。速度執(zhí)行的概率規(guī)則可表示為(5）歷史最優(yōu)位置設(shè)群體中的粒子數(shù)為P,p=1,2，…，P；在第q次迭代時(shí)，粒子p的位置為個(gè)體歷史最優(yōu)位置為；整個(gè)粒子群的歷史最優(yōu)位置表示為。粒子的運(yùn)動(dòng)方程具體描述如下：3.2計(jì)及檢邊物質(zhì)邊和檢修邊等時(shí)長(zhǎng)由式（18）可以看出，粒子適應(yīng)度值計(jì)算的關(guān)鍵是確定檢修邊?；诹Ｗ游恢帽硎拘问剑疚脑O(shè)計(jì)確定檢修邊的方法，并以此為基礎(chǔ)計(jì)算粒子適應(yīng)度值。確定檢修邊時(shí)，需要根據(jù)各邊前后順序關(guān)系計(jì)算各邊的動(dòng)車(chē)組累計(jì)走行里程和時(shí)間變量，并根據(jù)修程標(biāo)準(zhǔn)約束確定檢修邊。由于形成粒子位置時(shí)沒(méi)有考慮修程標(biāo)準(zhǔn)約束，可能造成該解不可行或存在超出修程的交路。當(dāng)解不可行時(shí)，令適應(yīng)度值F為極大值；對(duì)于超修程交路，可通過(guò)修正滿(mǎn)足修程標(biāo)準(zhǔn)約束，并且當(dāng)所有交路均滿(mǎn)足修程標(biāo)準(zhǔn)約束時(shí)，按照式（18）計(jì)算適應(yīng)度值F。(1）節(jié)點(diǎn)為起點(diǎn)、至檢修邊初始運(yùn)用交路以檢修邊的末端節(jié)點(diǎn)為起點(diǎn)（即以上次1級(jí)檢修作業(yè)結(jié)束后擔(dān)當(dāng)?shù)氖琢熊?chē)對(duì)應(yīng)節(jié)點(diǎn)為起點(diǎn)），至檢修邊為止（即以本次1級(jí)檢修作業(yè)對(duì)應(yīng)邊為終止）。與正式運(yùn)用交路不同的是它們不能保證滿(mǎn)足1級(jí)檢修修程約束，即存在超修程運(yùn)用交路。定義備選檢修資格邊表示交路搜索過(guò)程中當(dāng)前最適合安排檢修的邊。初始運(yùn)用交路生成的具體步驟如圖1所示。(2）超修程運(yùn)用交路的修正當(dāng)初始運(yùn)用交路集合中存在超修程檢修邊時(shí)，需要對(duì)超修程運(yùn)用交路進(jìn)行修正，具體可采用文獻(xiàn)中3.3部分的方法；若不存在超修程運(yùn)用交路，則按式(18）計(jì)算適應(yīng)度值F。3.3ep2初始粒子群初始位置Step1讀入列車(chē)運(yùn)行圖數(shù)據(jù)，初始化動(dòng)車(chē)組運(yùn)用接續(xù)網(wǎng)絡(luò)G(V,E），根據(jù)文獻(xiàn)的方法生成動(dòng)車(chē)組運(yùn)用最優(yōu)接續(xù)網(wǎng)絡(luò)Gbest(V,Ebest);Step2初始化粒子群規(guī)模P和總迭代次數(shù)Q，當(dāng)前迭代次數(shù)q=0，隨機(jī)生成滿(mǎn)足式（8）約束的列車(chē)間接續(xù)關(guān)系集合作為粒子p初始位置Step3按照3.2的步驟計(jì)算每個(gè)粒子的適應(yīng)度值；Step4對(duì)于每個(gè)粒子，若其當(dāng)前適應(yīng)度值比個(gè)體歷史最優(yōu)解較優(yōu)，更新，否則不更新；若當(dāng)前適應(yīng)度值比全局歷史最優(yōu)解Lgbest較優(yōu)，更新Lgbest，否則不更新；Step5令q=q+1，如果迭代次數(shù)q>Q，則結(jié)束；否則，根據(jù)式（22）更新粒子位置，轉(zhuǎn)Step3。4計(jì)算與分析為測(cè)試算法性能，選取2011年春運(yùn)期間武廣客運(yùn)專(zhuān)線(xiàn)實(shí)際列車(chē)運(yùn)行圖為例編制動(dòng)車(chē)組交路計(jì)劃。(1）相同速度列車(chē)使用同一種植物按照人機(jī)交互過(guò)程中計(jì)算機(jī)編制需求，算例中假設(shè)相同速度列車(chē)使用同一種車(chē)型，不考慮車(chē)站到發(fā)線(xiàn)能力約束和動(dòng)車(chē)運(yùn)用所檢修線(xiàn)能力約束，規(guī)定列車(chē)運(yùn)行時(shí)刻不可調(diào)整。(2）運(yùn)營(yíng)列車(chē)運(yùn)行工況車(chē)站集合：含武漢、長(zhǎng)沙南、廣州南3個(gè)始發(fā)終到站，均與動(dòng)車(chē)運(yùn)用所連接。列車(chē)集合：列車(chē)運(yùn)行最高速度均為350km/h，共有89對(duì)列車(chē)，其中廣州南～武漢間開(kāi)行53對(duì)（確認(rèn)車(chē)1對(duì)，運(yùn)營(yíng)列車(chē)52對(duì)）、廣州南～長(zhǎng)沙南間開(kāi)行36對(duì)（全部為運(yùn)營(yíng)列車(chē)）。列車(chē)總運(yùn)行里程Dall=146860.6km，總運(yùn)行時(shí)間Tall=33535min。作業(yè)參數(shù)：各車(chē)站tsc=15min；各運(yùn)用所tsm=150min；所用動(dòng)車(chē)組1級(jí)檢修修程標(biāo)準(zhǔn)D1=4000km,T1=2880min；運(yùn)行圖周期Tc=1440min。算法參數(shù)：設(shè)粒子數(shù)量為50，迭代次數(shù)為100；參數(shù)w1和w2均為1；粒子速度執(zhí)行規(guī)則中μin=0.6,μou