郭倩倩，王振宇，林柏梁

(1.石家莊鐵道大學(xué) 河北省交通安全與控制重點(diǎn)實(shí)驗(yàn)室，河北 石家莊 050043；2.石家莊鐵道大學(xué) 交通運(yùn)輸學(xué)院， 河北 石家莊 050043；3.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京 100044)

動(dòng)車(chē)組交路計(jì)劃是編制動(dòng)車(chē)運(yùn)用計(jì)劃與檢修計(jì)劃的基礎(chǔ),是列車(chē)運(yùn)行圖車(chē)次合理接續(xù)的依據(jù)。在運(yùn)輸實(shí)踐中,一般先根據(jù)列車(chē)運(yùn)行圖勾畫(huà)出動(dòng)車(chē)組交路,然后以動(dòng)車(chē)組交路為基礎(chǔ)編制運(yùn)用與檢修計(jì)劃。故優(yōu)化動(dòng)車(chē)組交路,可以有效地減少動(dòng)車(chē)組運(yùn)用數(shù)量,科學(xué)地配置動(dòng)車(chē)組資源。此外,對(duì)于提高動(dòng)車(chē)組的運(yùn)用與檢修管理水平亦具有重要的意義。科學(xué)地安排動(dòng)車(chē)組交路是完成圖定運(yùn)輸任務(wù)的前提,也是保障動(dòng)車(chē)組列車(chē)安全運(yùn)行和提高動(dòng)車(chē)組運(yùn)用效率的關(guān)鍵。截至2021年底,我國(guó)高速鐵路(以下簡(jiǎn)稱(chēng)“高鐵”)營(yíng)業(yè)里程超過(guò)4萬(wàn)km,動(dòng)車(chē)組保有量達(dá)4 153標(biāo)準(zhǔn)組。為保證動(dòng)車(chē)組安全高效運(yùn)行,其交路與檢修計(jì)劃優(yōu)化問(wèn)題得到業(yè)內(nèi)研究人員的廣泛重視。

目前,國(guó)內(nèi)外學(xué)者對(duì)動(dòng)車(chē)組交路計(jì)劃優(yōu)化問(wèn)題進(jìn)行了大量深入的研究。國(guó)內(nèi)外學(xué)者分別考慮動(dòng)車(chē)組的檢修[1-10]、多車(chē)型[1,5]、多基地[1,4-5]、可改編(重聯(lián))[6,12-15]、空車(chē)回送[6]、動(dòng)車(chē)所的庫(kù)存能力[6,10]、列車(chē)路徑[5,11]等條件建立數(shù)學(xué)模型,并設(shè)計(jì)不同的優(yōu)化算法進(jìn)行求解。耿敬春等[1]構(gòu)造了在考慮綜合維修條件下多基地、不同型號(hào)的動(dòng)車(chē)組周期性運(yùn)用計(jì)劃編制的數(shù)學(xué)模型,并運(yùn)用計(jì)算機(jī)模擬方法研究給定運(yùn)行圖條件下合理配置動(dòng)車(chē)組套數(shù)、存車(chē)線數(shù)量及動(dòng)車(chē)段設(shè)備規(guī)模等問(wèn)題。王忠凱等[2]以減少動(dòng)車(chē)組使用數(shù)量、降低檢修成本為優(yōu)化目標(biāo),建立動(dòng)車(chē)組運(yùn)用計(jì)劃和檢修計(jì)劃一體化編制的整數(shù)規(guī)劃模型,并設(shè)計(jì)了求解模型的模擬退火算法。李華等[3]設(shè)計(jì)接續(xù)的里程累計(jì)變量和時(shí)間累計(jì)變量為檢修約束,建立動(dòng)車(chē)組交路計(jì)劃的整數(shù)規(guī)劃模型,運(yùn)用粒子群算法思想,設(shè)計(jì)求解算法。江政杰等[4]建立考慮動(dòng)車(chē)段/所一級(jí)檢修能力約束的多目標(biāo)整數(shù)規(guī)劃模型,采用基于重要性分級(jí)的分層序列法求解模型。鐘慶偉等[5]以降低綜合運(yùn)營(yíng)成本和總空駛里程等為優(yōu)化目標(biāo),建立基于列車(chē)車(chē)次的可改編動(dòng)車(chē)組運(yùn)用優(yōu)化混合整數(shù)線性規(guī)劃模型,并設(shè)計(jì)了一個(gè)基于路徑生成的迭代逼近算法,能夠快速得到滿足日常維修限制的動(dòng)車(chē)組運(yùn)用計(jì)劃。鄭亞晶等[6]在考慮動(dòng)車(chē)組的檢修、空車(chē)回送、重聯(lián)編組等約束條件的基礎(chǔ)上,以最少動(dòng)車(chē)組運(yùn)用數(shù)目為目標(biāo),提出動(dòng)車(chē)組流量模型,用Cplex軟件求解得到全局最優(yōu)解。Giacco等[7]研究短期維修條件下全網(wǎng)鐵路的動(dòng)車(chē)組運(yùn)用計(jì)劃。Marti等[8]通過(guò)引入動(dòng)車(chē)組維修的約束條件,調(diào)整動(dòng)車(chē)組交路計(jì)劃。Bornd?rfer等[9]考慮動(dòng)車(chē)組運(yùn)用的時(shí)間和距離檢修等約束,以復(fù)合網(wǎng)絡(luò)為基礎(chǔ)描述動(dòng)車(chē)組運(yùn)用問(wèn)題。Chung等[10]針對(duì)韓國(guó)鐵路列車(chē)運(yùn)行計(jì)劃問(wèn)題,考慮車(chē)輛段存放能力和檢修能力等約束條件,以交路運(yùn)行里程均衡性為目標(biāo),建立了一個(gè)混合整數(shù)規(guī)劃模型,設(shè)計(jì)基于改進(jìn)精英策略的混合遺傳算法求解,并用韓國(guó)鐵路實(shí)際數(shù)據(jù)驗(yàn)證了算法的有效性。Cadarso等[11]建立列車(chē)路徑與動(dòng)車(chē)組分配的綜合優(yōu)化模型,并提出基于benders分解的啟發(fā)式算法求解,最后利用西班牙鐵路的數(shù)據(jù)驗(yàn)證了該算法的穩(wěn)定性和可行性。Abbink等[12]以早高峰期座位短缺最少化為目標(biāo),研究動(dòng)車(chē)組的分配問(wèn)題。Alfieri等[13]在單線鐵路上建立整數(shù)規(guī)劃模型,優(yōu)化動(dòng)車(chē)組周轉(zhuǎn)計(jì)劃。Peeters等[14]考慮旅客運(yùn)輸服務(wù)、計(jì)劃的魯棒性以及動(dòng)車(chē)組周轉(zhuǎn)費(fèi)用等因素,建立動(dòng)車(chē)組周轉(zhuǎn)日計(jì)劃的數(shù)學(xué)模型,并設(shè)計(jì)分支定價(jià)法進(jìn)行求解。Fioole等[15]在引入動(dòng)車(chē)組改編作業(yè)的基礎(chǔ)上,結(jié)合列車(chē)運(yùn)行圖和旅客實(shí)際數(shù)量,研究動(dòng)車(chē)組運(yùn)用計(jì)劃的編制問(wèn)題。

以上對(duì)動(dòng)車(chē)組交路優(yōu)化方面的研究,大多數(shù)僅從檢修約束,如動(dòng)車(chē)所檢修能力、動(dòng)車(chē)組檢修時(shí)間、檢修里程以及檢修成本等方面考慮,幾乎沒(méi)有在離所時(shí)間約束下動(dòng)車(chē)組交路計(jì)劃編制的文獻(xiàn)。但在實(shí)際運(yùn)營(yíng)中動(dòng)車(chē)組如果離所時(shí)間過(guò)晚,則會(huì)造成動(dòng)車(chē)組運(yùn)行時(shí)間較短,無(wú)法承擔(dān)長(zhǎng)距離交路任務(wù)。舉個(gè)比較極端的例子,動(dòng)車(chē)組22:00離所,24:00回所理論上也是交路方案的備選之一,但是從動(dòng)車(chē)所管理人員角度考慮,他們認(rèn)為這是顯然不合理方案,不予考慮。

本文基于列車(chē)接續(xù)網(wǎng)絡(luò)圖,建立離所時(shí)間約束下動(dòng)車(chē)組交路優(yōu)化模型,以滿足動(dòng)車(chē)組日常運(yùn)用需求為基礎(chǔ),以縮短動(dòng)車(chē)組接續(xù)總時(shí)間與降低動(dòng)車(chē)組交路總損失里程為雙重目標(biāo),提高動(dòng)車(chē)組的運(yùn)用效率。

1 離所時(shí)間限制下動(dòng)車(chē)組交路問(wèn)題的背景

動(dòng)車(chē)組交路計(jì)劃[16]是基于給定列車(chē)運(yùn)行圖,規(guī)定列車(chē)任務(wù)間動(dòng)車(chē)組接續(xù)關(guān)系及一級(jí)檢修地點(diǎn),將列車(chē)運(yùn)行圖中列車(chē)任務(wù)組合成若干運(yùn)用交路的計(jì)劃,是編制日常動(dòng)車(chē)組運(yùn)用計(jì)劃的基礎(chǔ)性計(jì)劃。動(dòng)車(chē)組的交路計(jì)劃主要與動(dòng)車(chē)組的一級(jí)檢修關(guān)聯(lián),根據(jù)動(dòng)車(chē)組交路的定義可以將其理解為動(dòng)車(chē)組在兩次一級(jí)檢修之間所擔(dān)當(dāng)?shù)牧熊?chē)車(chē)次有序接續(xù)集合。而動(dòng)車(chē)組的二級(jí)修則與動(dòng)車(chē)組的上線計(jì)劃相關(guān)聯(lián),動(dòng)車(chē)組上線運(yùn)用計(jì)劃就是安排動(dòng)車(chē)組去擔(dān)當(dāng)列車(chē)車(chē)次或交路的問(wèn)題,同時(shí),要考慮動(dòng)車(chē)組二級(jí)修各個(gè)檢修項(xiàng)目的檢修周期。相對(duì)于一級(jí)檢修和二級(jí)檢修,動(dòng)車(chē)組的高級(jí)檢修的檢修周期和扣修周期都比較長(zhǎng),對(duì)動(dòng)車(chē)組的交路計(jì)劃和運(yùn)用計(jì)劃影響相對(duì)較小,其往往與春、暑運(yùn)相關(guān)聯(lián)。因此,本文在研究動(dòng)車(chē)組交路計(jì)劃時(shí),僅考慮動(dòng)車(chē)組的一級(jí)檢修。

根據(jù)動(dòng)車(chē)組管理的實(shí)際情況,動(dòng)車(chē)組擔(dān)當(dāng)完一條交路后,需要進(jìn)行一級(jí)檢修。以包含4個(gè)車(chē)站,1個(gè)動(dòng)車(chē)所,12個(gè)列車(chē)的實(shí)例來(lái)說(shuō)明,研究離所時(shí)間約束下動(dòng)車(chē)組交路計(jì)劃優(yōu)化問(wèn)題的必要性。A站列車(chē)車(chē)次的相關(guān)信息見(jiàn)表1,其中A站為動(dòng)車(chē)所相連接的車(chē)站,B、C、D站為折返站。

表1 A站列車(chē)車(chē)次相關(guān)信息

基于上述車(chē)次數(shù)據(jù)分別給出2種交路方案,見(jiàn)圖1、圖2。圖1由3個(gè)交路構(gòu)成,交路1為:1—2—9—10,交路2為11—12—5—6,交路3為7—8—3—4。需要注意的是,交路3的開(kāi)始車(chē)次為7,即其開(kāi)始時(shí)刻為17:19,這也意味著擔(dān)當(dāng)該交路任務(wù)的動(dòng)車(chē)組在17:19離所開(kāi)始執(zhí)行該任務(wù)。圖1中的交路計(jì)劃沒(méi)有考慮動(dòng)車(chē)組最晚離開(kāi)動(dòng)車(chē)所的時(shí)刻要求,因此會(huì)存在17:19開(kāi)始的交路,但是這在鐵路運(yùn)營(yíng)組織中顯然是不符合實(shí)際的。在實(shí)際運(yùn)營(yíng)中,動(dòng)車(chē)所一般對(duì)動(dòng)車(chē)組最晚離所時(shí)間有要求。圖2有兩個(gè)交路,車(chē)次1—2—3—4構(gòu)成交路1(紅色線條),該交路的開(kāi)始時(shí)刻為第一天的10:05,即車(chē)次1的始發(fā)時(shí)刻,擔(dān)當(dāng)完車(chē)次1和2后回到動(dòng)車(chē)所過(guò)夜,第二天分別擔(dān)當(dāng)車(chē)次3和4的任務(wù),最終回到動(dòng)車(chē)所進(jìn)行一級(jí)檢修。車(chē)次5—6—7—8—9—10—11—12(藍(lán)色線條)構(gòu)成交路2,該交路的開(kāi)始時(shí)刻為第一天8:05,擔(dān)當(dāng)完車(chē)次5、6、7、8后回到動(dòng)車(chē)所過(guò)夜,第二天擔(dān)當(dāng)車(chē)次9、10、11、12的任務(wù),最終回到動(dòng)車(chē)所進(jìn)行一級(jí)檢修。不同于圖1,圖2的交路方案中,交路的開(kāi)始時(shí)刻均在14:00之前,滿足實(shí)際運(yùn)營(yíng)條件。在實(shí)際的運(yùn)營(yíng)組織中,各個(gè)動(dòng)車(chē)所離所時(shí)刻要求有所不同,例如,某鐵路局要求的動(dòng)車(chē)組最晚離所時(shí)刻為14:00。

圖1 不考慮離所時(shí)間限制的動(dòng)車(chē)組交路

圖2 最晚離所時(shí)刻為14:00的動(dòng)車(chē)組交路

圖1和圖2分別表示不考慮離所時(shí)刻約束的動(dòng)車(chē)組交路圖和最晚離所時(shí)刻為14:00的動(dòng)車(chē)組交路圖。對(duì)比兩種方案可以看出,圖1中交路3的發(fā)車(chē)時(shí)刻過(guò)晚,即,同一列車(chē)運(yùn)行圖,不同的車(chē)次組合方案構(gòu)成的交路計(jì)劃也不盡相同,使得交路開(kāi)始的時(shí)刻存在差異。如果對(duì)動(dòng)車(chē)組的最晚發(fā)車(chē)時(shí)刻加以限制,從優(yōu)化理論看,增加該約束可以減少尋優(yōu)的搜索范圍。因此,在研究動(dòng)車(chē)組交路計(jì)劃優(yōu)化問(wèn)題時(shí),有必要考慮離所時(shí)刻這一約束條件,這在動(dòng)車(chē)組運(yùn)營(yíng)組織中是真實(shí)存在且具有實(shí)際意義的。離所時(shí)刻約束下動(dòng)車(chē)組交路計(jì)劃就是對(duì)于給定列車(chē)運(yùn)行圖一個(gè)周期內(nèi)的所有列車(chē),在滿足動(dòng)車(chē)組最晚離開(kāi)動(dòng)車(chē)所時(shí)刻、一級(jí)檢修的時(shí)間和里程等約束條件下,實(shí)現(xiàn)一定優(yōu)化目標(biāo)時(shí),合理確定列車(chē)車(chē)次之間的接續(xù)關(guān)系。

2 數(shù)學(xué)模型構(gòu)建

2.1 列車(chē)接續(xù)網(wǎng)絡(luò)圖

通過(guò)引入網(wǎng)絡(luò)理論,以列車(chē)車(chē)次為網(wǎng)絡(luò)的節(jié)點(diǎn),以列車(chē)車(chē)次接續(xù)關(guān)系和一級(jí)檢修作為網(wǎng)絡(luò)的弧,構(gòu)建動(dòng)車(chē)組列車(chē)接續(xù)網(wǎng)絡(luò)[16]。因?yàn)榻宦返钠瘘c(diǎn)和終點(diǎn)都是動(dòng)車(chē)所,每一條交路實(shí)際上是由列車(chē)車(chē)次節(jié)點(diǎn)、列車(chē)車(chē)次接續(xù)弧和一級(jí)檢修弧構(gòu)成的閉合回路。動(dòng)車(chē)組列車(chē)接續(xù)網(wǎng)絡(luò)示意圖見(jiàn)圖3,根據(jù)圖2中的動(dòng)車(chē)組交路,可以構(gòu)建兩條列車(chē)車(chē)次接續(xù)回路,見(jiàn)圖3(a)。為了便于后續(xù)數(shù)學(xué)模型的建立,將列車(chē)接續(xù)網(wǎng)絡(luò)中的各條閉合回路通過(guò)一級(jí)檢修弧連接起來(lái),形成一條由所有列車(chē)車(chē)次節(jié)點(diǎn)、列車(chē)車(chē)次接續(xù)弧和一級(jí)檢修弧構(gòu)成的閉合回路,見(jiàn)圖3(b)。

本文所研究的動(dòng)車(chē)組交路優(yōu)化問(wèn)題,基于圖3(b)中列車(chē)接續(xù)網(wǎng)絡(luò)構(gòu)建思想,先構(gòu)造一個(gè)包含所有列車(chē)車(chē)次接續(xù)的閉合回路,然后在回路中通過(guò)確定哪些列車(chē)車(chē)次之間安排一級(jí)檢修,在一級(jí)檢修弧處進(jìn)行“切割”,得到的每一條由列車(chē)車(chē)次構(gòu)成的接續(xù)片段,即是所求的各個(gè)動(dòng)車(chē)組交路。

2.2 構(gòu)建模型的假設(shè)

為進(jìn)一步把問(wèn)題抽象和簡(jiǎn)化,建模前作如下假設(shè):

1)不考慮動(dòng)車(chē)所對(duì)一級(jí)檢修能力的限制,對(duì)于動(dòng)車(chē)組集中到達(dá)動(dòng)車(chē)所的情況,通過(guò)人工干預(yù)進(jìn)行調(diào)整。

2)每天開(kāi)行列車(chē)的數(shù)量及信息是相同的,所有列車(chē)的基本屬性、一級(jí)檢修周期等基礎(chǔ)數(shù)據(jù)均已知,且在交路計(jì)劃編制中保持不變。

3)只考慮動(dòng)車(chē)組的單車(chē)種、單基地問(wèn)題,對(duì)于多車(chē)種、多基地問(wèn)題,可以采用本文研究的思路將其轉(zhuǎn)化為多個(gè)子問(wèn)題求解。

2.3 符號(hào)定義

模型涉及的相關(guān)符號(hào),包括集合、參數(shù)、變量的定義見(jiàn)表2。

2.4 數(shù)學(xué)模型

為表述動(dòng)車(chē)組交路計(jì)劃中列車(chē)車(chē)次接續(xù)關(guān)系、一級(jí)檢修作業(yè)安排及修程標(biāo)準(zhǔn)約束,需要給出以下變量的表達(dá)式。

若車(chē)次i的到達(dá)車(chē)站等于車(chē)次j的始發(fā)車(chē)站,并且車(chē)次j的始發(fā)時(shí)刻與i的到達(dá)時(shí)刻相差時(shí)間間隔大于列車(chē)之間接續(xù)的最小時(shí)間標(biāo)準(zhǔn),則tij等于車(chē)次j的始發(fā)時(shí)刻減去車(chē)次i的到達(dá)時(shí)刻;同理,若車(chē)次i的到達(dá)車(chē)站等于車(chē)次j的始發(fā)車(chē)站,但是車(chē)次j的始發(fā)時(shí)刻與i的到達(dá)時(shí)刻相差時(shí)間間隔小于列車(chē)之間接續(xù)的最小時(shí)間標(biāo)準(zhǔn),那么可以考慮接續(xù)第二天的相同列車(chē)車(chē)次,此時(shí)接續(xù)時(shí)間增加1 440 min;若兩個(gè)列車(chē)車(chē)次不滿足接續(xù)地點(diǎn)的要求,規(guī)定車(chē)次的接續(xù)時(shí)間為無(wú)窮大。tij為

( 1 )

( 2 )

( 3 )

動(dòng)車(chē)組交路優(yōu)化問(wèn)題的目標(biāo)函數(shù)一般為動(dòng)車(chē)組使用數(shù)量最少、接續(xù)時(shí)間最少、檢修次數(shù)最少和動(dòng)車(chē)組交路損失里程最少等。在列車(chē)運(yùn)行圖確定的情況下,所有列車(chē)的運(yùn)行時(shí)間和運(yùn)行里程是不變的,動(dòng)車(chē)組接續(xù)時(shí)間最少和動(dòng)車(chē)組使用數(shù)量最少是等價(jià)的,動(dòng)車(chē)組交路損失里程最少和檢修次數(shù)最少是等價(jià)的,可任選其一作為目標(biāo)函數(shù)[17]。本文選擇動(dòng)車(chē)組交路中列車(chē)車(chē)次接續(xù)時(shí)間Z1與動(dòng)車(chē)組交路總損失里程Z2作為優(yōu)化目標(biāo)函數(shù),即

( 4 )

( 5 )

為將兩個(gè)目標(biāo)的量綱統(tǒng)一,將目標(biāo)式( 4 )和式( 5 )進(jìn)行加權(quán)(權(quán)重系數(shù)為w1和w2),取最小值作為目標(biāo)函數(shù),即

minZ=w1Z1+w2Z2

( 6 )

1)列車(chē)車(chē)次接續(xù)唯一性約束

對(duì)于每一個(gè)列車(chē)車(chē)次,只能有一個(gè)緊前車(chē)次和一個(gè)緊后車(chē)次,這種關(guān)系在邏輯上表現(xiàn)為唯一性約束,即

( 7 )

( 8 )

2)動(dòng)車(chē)組一級(jí)檢修邏輯約束

若在車(chē)次i與j之間安排一級(jí)檢修,則車(chē)次i與j既要前后接續(xù),又要滿足一級(jí)檢修條件,即

yij≤xijθiji,j=1,2,…,ni≠j

( 9 )

3)動(dòng)車(chē)組一級(jí)檢修里程周期和時(shí)間周期約束

在實(shí)際運(yùn)營(yíng)組織中,動(dòng)車(chē)組的運(yùn)行里程一般允許存在超期檢修,但是不同級(jí)別的檢修作業(yè)有著不同的超期檢修比例,一級(jí)檢修作業(yè)的超期檢修比例λ一般為10%,即

lj≤(1+λ)Lcyclej=1,2,…,n

(10)

與里程周期約束不同,時(shí)間周期不存在超期的情況,即要嚴(yán)格滿足檢修時(shí)間周期約束,因此不存在超期檢修百分比,即

tj≤Tcyclej=1,2,…,n

(11)

4)動(dòng)車(chē)組最晚離所時(shí)間約束

動(dòng)車(chē)組的離所時(shí)刻要早于要求的最晚離所時(shí)刻,即交路的開(kāi)始時(shí)刻要早于要求的最晚開(kāi)始時(shí)刻,即

(12)

5)避免子回路邏輯約束

本文的建模思路是先構(gòu)造一個(gè)包含所有列車(chē)車(chē)次的回路,這種接續(xù)關(guān)系通過(guò)變量xij體現(xiàn),然后在回路中通過(guò)確定哪些列車(chē)車(chē)次之間安排一級(jí)檢修,通過(guò)變量yij體現(xiàn),最后得到各個(gè)交路。則需要注意的是,在尋求包含所有車(chē)次的回路時(shí)要避免出現(xiàn)子回路。在這個(gè)層面上,可以通過(guò)引入TSP問(wèn)題中避免出現(xiàn)子回路的經(jīng)典約束,即

ui-uj+nxij≤n-1i,j=1,2,…,n

(13)

0≤ui≤n-1i=1,2,…,n

(14)

式中:ui和uj分別為車(chē)次i和j在回路中的位置編號(hào)。

式(14)表示位置編號(hào)的取值范圍,考慮0到第n-1個(gè)位置。若i和j在回路中前后接續(xù),那么ui-uj必然等于-1,此時(shí)式(13)成立;若二者不接續(xù),則式(13)恒成立。式(13)和式(14)確保得到的回路中避免出現(xiàn)子回路。

6)0-1變量約束

xij,yij∈{0,1}i,j=1,2,…,ni≠j

(15)

綜上所述,考慮離所時(shí)間約束下的動(dòng)車(chē)組交路計(jì)劃優(yōu)化模型為

minZ=w1Z1+w2Z2

s.t. 式( 7 )～式(15)

3 模擬退火算法

2.4節(jié)模型中的lj和tj存在累乘的非線性高次項(xiàng),使得所建模型為非線性0-1整數(shù)規(guī)劃模型,不易用數(shù)學(xué)規(guī)劃求解器精確求解,因此本文選用模擬退火算法對(duì)模型進(jìn)行求解。模擬退火算法是一種基于Metropolis Monte Carlo迭代求解策略的啟發(fā)式隨機(jī)搜索算法,其思想是通過(guò)對(duì)模型中的復(fù)雜約束進(jìn)行預(yù)處理,將其作為懲罰項(xiàng)添加到目標(biāo)函數(shù)中,與目標(biāo)函數(shù)共同構(gòu)成能量函數(shù),然后通過(guò)模擬物理界中的退火過(guò)程實(shí)現(xiàn)對(duì)模型的啟發(fā)式求解,主要包括以下幾個(gè)部分。

3.1 能量函數(shù)

為了降低模型的求解復(fù)雜程度,需要將模型中的復(fù)雜約束條件作為懲罰項(xiàng)加入到目標(biāo)函數(shù)中。這里的復(fù)雜約束主要是約束式(10)～式(12),將其乘以懲罰系數(shù)作為懲罰項(xiàng)添加到目標(biāo)函數(shù)中。3個(gè)約束對(duì)應(yīng)的3個(gè)懲罰項(xiàng)分別為

(16)

(17)

(18)

式中:β1、β2、β3分別為相應(yīng)的懲罰系數(shù);H1、H2、H3分別為3個(gè)復(fù)雜約束對(duì)應(yīng)的懲罰項(xiàng)。

原模型的目標(biāo)函數(shù)為

(19)

將其與上述懲罰項(xiàng)結(jié)合,所得能量函數(shù)為

G(X)=Z+H1+H2+H3

(20)

3.2 初始溫度的確定

在確定初始溫度T0時(shí),利用Aarts等[18]提出的方法,先隨機(jī)地產(chǎn)生m個(gè)解,則有

(21)

(22)

式中:ρ0為給定的初始接受率,一般取0.9～0.99;m+、m-分別為能量函數(shù)G(Xn)值增加、減少的解數(shù);Δavg為m+個(gè)能量函數(shù)增加值的平均值。

3.3 初始解的生成

首先定義兩個(gè)集合Ω1、Ω2,其中Ω1用來(lái)存放始發(fā)站為檢修站(運(yùn)用所連接站)的車(chē)次,Ω2用來(lái)存放終到站為檢修站的車(chē)次,然后為每個(gè)車(chē)次生成一個(gè)集合,該集合內(nèi)存放可以與該車(chē)次相接續(xù)的其他車(chē)次,最后額外定義一個(gè)集合Ω3用來(lái)存放已經(jīng)得到的可行解。

從Ω1集合中隨機(jī)選取一個(gè)車(chē)次作為整體回路的首位,然后根據(jù)約束式( 7 )～式( 9 )在首位車(chē)次確定的基礎(chǔ)上,依照上述邏輯約束隨機(jī)確定一條回路。即在首位車(chē)次確定的基礎(chǔ)上,從該車(chē)次對(duì)應(yīng)的集合中隨機(jī)選取一個(gè)車(chē)次進(jìn)行接續(xù),同時(shí)確保該車(chē)次在該回路中沒(méi)有出現(xiàn)過(guò),按照該種思路,依次選取車(chē)次接續(xù),若選中車(chē)次已經(jīng)存在于當(dāng)前回路中,則重新隨機(jī)選取直至所有車(chē)次均被包含在回路中。在確定回路中的最后一個(gè)車(chē)次時(shí),要確保該車(chē)次的終到站為檢修站,即確保最后一個(gè)車(chē)次來(lái)源于Ω2。最后把該回路存放到Ω3中,記為一個(gè)可行解。

3.4 鄰域解的生成

鄰域解的生成與初始解的生成方法思路一致,采用生成初始解的方法生成鄰域解。若生成的新解已經(jīng)存放在Ω3中,則從當(dāng)前新解中隨機(jī)選中一個(gè)車(chē)次,擾動(dòng)其緊后車(chē)次,即在當(dāng)前車(chē)次對(duì)應(yīng)的集合中重新選取一個(gè)車(chē)次,然后按照相同思路接續(xù),直至所有車(chē)次都被包含在整體的回路中。

3.5 溫度的更新策略

降溫方法為

(23)

式中:參數(shù)δ一般取0.4;α一般取0.95;kd為高低溫迭代次數(shù)的分界點(diǎn),一般為70;φ(Tk)為T(mén)k溫度下能量函數(shù)期望值的標(biāo)準(zhǔn)差。

3.6 算法步驟

Step1確定初始溫度T0。記當(dāng)前的降溫次數(shù)k=0,轉(zhuǎn)Step2。

Step2記迭代次數(shù)n=0。初始溫度下,按照3.3節(jié)的方法生成初始解。

Step3當(dāng)經(jīng)過(guò)k次降溫后,在溫度Tk下,記第n-1次迭代后的解為Xn-1,按照3.4節(jié)中的方法生成鄰域解,計(jì)算出對(duì)應(yīng)的函數(shù)值能量G(Xn),轉(zhuǎn)Step4。

Step4利用Metroplis抽樣準(zhǔn)則對(duì)當(dāng)前解進(jìn)行檢驗(yàn),若G(Xn)-G(Xn-1)<0,則無(wú)條件接受Xn代替Xn-1;若G(Xn)-G(Xn-1)>0,則以概率γn(Tk)接受鄰域解。γn(Tk)為

(24)

轉(zhuǎn)Step5。

Step6算法收斂終止判定。本文設(shè)置了兩個(gè)終止準(zhǔn)則:一種是接受率小于給定的閾值時(shí),另一種是能量函數(shù)在多次迭代過(guò)程中保持不變,兩個(gè)準(zhǔn)則滿足一個(gè)即結(jié)束該算法。否則,轉(zhuǎn)Step7。

Step7按3.5節(jié)中的內(nèi)容進(jìn)行降溫,記降溫次數(shù)k=k+1,置迭代步數(shù)n=0,返回Step3。

4 算例分析

4.1 數(shù)據(jù)

本文以太原南動(dòng)車(chē)所配屬的CRH2A動(dòng)車(chē)組車(chē)型為例,選取2021年10月該車(chē)型擔(dān)當(dāng)?shù)牟糠周?chē)次作為基本數(shù)據(jù),進(jìn)行算例驗(yàn)證分析。太原南站部分列車(chē)車(chē)次見(jiàn)表3,所研究車(chē)次的開(kāi)行區(qū)段覆蓋車(chē)站11個(gè)。動(dòng)車(chē)所與太原南站相連,采用單點(diǎn)檢修方式,可為本動(dòng)車(chē)所的動(dòng)車(chē)組提供一級(jí)檢修。

表3 太原南站部分列車(chē)車(chē)次

根據(jù)TG/CL 127—2017《鐵路動(dòng)車(chē)組運(yùn)用維修規(guī)則》[22],CRH2A型動(dòng)車(chē)組的一級(jí)檢修時(shí)間周期Tcycle為48 h,里程周期Lcycle為4 000 km,動(dòng)車(chē)組超期檢修的百分比λ為10%,列車(chē)接續(xù)時(shí)間標(biāo)準(zhǔn)tconnect為15 min。

4.2 優(yōu)化計(jì)算

本文所提出的考慮最晚離所時(shí)間具有實(shí)際背景意義,為了突出構(gòu)建模型的有效性,在求解算例,分別考慮了兩種場(chǎng)景進(jìn)行計(jì)算。首先是不考慮最晚離所時(shí)間約束,即忽略模型中的約束條件式(12),利用所提出的模擬退火算法對(duì)模型進(jìn)行求解;同理,在考慮最晚離所時(shí)刻約束的基礎(chǔ)上,對(duì)算例進(jìn)行重新計(jì)算,最終對(duì)比兩種場(chǎng)景下的計(jì)算結(jié)果,從而說(shuō)明本文所建模型的有效性和真實(shí)性。

根據(jù)本文設(shè)計(jì)的求解步驟,采用VC++程序設(shè)計(jì)實(shí)現(xiàn),在Core 2.4 GHz的個(gè)人計(jì)算機(jī)上運(yùn)行。這里ρ0取值為0.9,β1、β2均取值為50(通過(guò)多次試驗(yàn)計(jì)算確定),w1、w2取值為0.5。結(jié)合實(shí)際情況,要求動(dòng)車(chē)組離開(kāi)動(dòng)車(chē)運(yùn)用所的最晚時(shí)刻為14:00,即Tlatest取值為14:00,晚點(diǎn)懲罰系數(shù)β3取值為99(通過(guò)多次試驗(yàn)計(jì)算取值)。兩種場(chǎng)景下的動(dòng)車(chē)組交路優(yōu)化方案見(jiàn)表4。

表4 兩種場(chǎng)景下的動(dòng)車(chē)組交路優(yōu)化方案

由表4可知,兩種場(chǎng)景下得到的交路數(shù)量一樣,均為7個(gè)交路,但具體的交路方案存在差異。對(duì)比表4中結(jié)果可以發(fā)現(xiàn),場(chǎng)景二與場(chǎng)景一相比,僅有交路2、3、6有所變化,其余交路方案則相同。此外,場(chǎng)景一的交路方案中,交路2的離所時(shí)刻為15:12,即過(guò)晚發(fā)車(chē),這正是由于沒(méi)有考慮離所時(shí)刻約束所導(dǎo)致的情況。相反,場(chǎng)景二的交路方案中均滿足最晚離所時(shí)刻限制,即離所時(shí)刻均早于14:00。

同時(shí),由于列車(chē)車(chē)次是已知的,并且得到的交路數(shù)量也一樣,則說(shuō)明兩種場(chǎng)景下交路方案的檢修里程利用率相等,但是總運(yùn)行時(shí)間則有所不同。從表4可以看到,場(chǎng)景一中交路運(yùn)行時(shí)間最短為1 226 min,最長(zhǎng)為2 308 min;場(chǎng)景二中交路運(yùn)行時(shí)間最短為1 528 min,最長(zhǎng)為2 288 min。從運(yùn)行時(shí)間指標(biāo)來(lái)看,雖然場(chǎng)景一得到的交路方案較好,但是存在過(guò)晚發(fā)車(chē)的情況。此外,還統(tǒng)計(jì)分析了兩種場(chǎng)景下交路方案的總接續(xù)時(shí)間。列車(chē)車(chē)次數(shù)量一定,各個(gè)車(chē)次的圖定運(yùn)行時(shí)間一定,則總運(yùn)行時(shí)間的不同體現(xiàn)在總接續(xù)時(shí)間上。經(jīng)計(jì)算,場(chǎng)景一中動(dòng)車(chē)組的總接續(xù)時(shí)間為5 153 min,而場(chǎng)景二中動(dòng)車(chē)組的總接續(xù)時(shí)間為5 205 min。場(chǎng)景二的總接續(xù)時(shí)間僅比場(chǎng)景一多52 min,但是場(chǎng)景二中得到的交路方案可以很好地避免動(dòng)車(chē)組過(guò)晚離所。

綜上分析,在考慮動(dòng)車(chē)組離所時(shí)間約束下,本文所建模型可以很好地避免動(dòng)車(chē)組的過(guò)晚離所發(fā)車(chē),使動(dòng)車(chē)組的運(yùn)營(yíng)更加符合實(shí)際運(yùn)輸生產(chǎn)需求。

5 結(jié)論

本文研究離所時(shí)間限制下的動(dòng)車(chē)組交路優(yōu)化計(jì)劃,在建立數(shù)學(xué)模型時(shí)將動(dòng)車(chē)組最晚離開(kāi)動(dòng)車(chē)所時(shí)刻作為約束條件,以動(dòng)車(chē)組接續(xù)總時(shí)間最少和動(dòng)車(chē)組交路總損失里程最少為優(yōu)化目標(biāo),構(gòu)建離所時(shí)刻約束下的動(dòng)車(chē)組交路優(yōu)化模型。所建立模型為非線性0-1整數(shù)規(guī)劃模型,為提高求解效率,設(shè)計(jì)模擬退火啟發(fā)式算法。最終通過(guò)算例分析驗(yàn)證本文提出模型和算法的有效性。結(jié)果表明:與不考慮離所時(shí)刻約束相比,離所時(shí)刻約束下的動(dòng)車(chē)組交路優(yōu)化方案,可以很好地避免動(dòng)車(chē)組的過(guò)晚離所發(fā)車(chē),更加符合運(yùn)輸生產(chǎn)實(shí)際需求。

本文所建模型是非線性規(guī)劃模型,求解有一定的難度,因此,在建模前做了簡(jiǎn)化,如僅考慮單車(chē)種、單基地的動(dòng)車(chē)組以及列車(chē)運(yùn)行圖是已知的情況等,今后可在考慮多車(chē)種、多基地動(dòng)車(chē)組情況下,研究動(dòng)車(chē)組交路和列車(chē)運(yùn)行圖的協(xié)調(diào)優(yōu)化問(wèn)題。