周曉昭，張 琦，許 偉，王 濤，宋鵬飛

(1. 中國(guó)鐵道科學(xué)研究院，北京 100081； 2. 中國(guó)鐵道科學(xué)研究院 通信信號(hào)研究所，北京 100081；3. 國(guó)家鐵路智能運(yùn)輸系統(tǒng)工程技術(shù)研究中心,北京 100081)

受惡劣天氣、自然災(zāi)害、設(shè)備故障等原因的影響，高速鐵路列車的運(yùn)行將偏離圖定計(jì)劃，這種情況下調(diào)度系統(tǒng)需及時(shí)對(duì)干擾后的運(yùn)行圖進(jìn)行有效調(diào)整，減少晚點(diǎn)時(shí)間，控制晚點(diǎn)傳播范圍，將受晚點(diǎn)影響的列車數(shù)量控制到最小，保證行車安全，提高運(yùn)輸效率。動(dòng)車組的合理接續(xù)可以提高動(dòng)車組使用效率和降低運(yùn)輸成本。目前已有文獻(xiàn)對(duì)動(dòng)車組的接續(xù)優(yōu)化和列車運(yùn)行圖調(diào)整展開(kāi)研究。文獻(xiàn)[1]將動(dòng)車組接續(xù)優(yōu)化視為T(mén)SP問(wèn)題并采用元胞蟻群算法分兩階段求解動(dòng)車組定點(diǎn)檢修和動(dòng)車組接續(xù)方案。文獻(xiàn)[2]采用協(xié)同思想，將高速鐵路列車運(yùn)行計(jì)劃與動(dòng)車組交路計(jì)劃協(xié)同編制，編制基于緊交路的動(dòng)車組接續(xù)方案實(shí)現(xiàn)動(dòng)車組的高效利用。文獻(xiàn)[3]采用蟻群算法求解所構(gòu)建的動(dòng)車組運(yùn)用計(jì)劃問(wèn)題的整數(shù)規(guī)劃模型，實(shí)現(xiàn)快速求解得到有效的動(dòng)車組接續(xù)優(yōu)化方案。文獻(xiàn)[4]采用交路接續(xù)思想構(gòu)建動(dòng)車組接續(xù)網(wǎng)絡(luò)，以最小化動(dòng)車組擔(dān)當(dāng)交路的接續(xù)時(shí)間總和與最大化動(dòng)車組檢修前累計(jì)運(yùn)行里程為目標(biāo)，建立動(dòng)車組運(yùn)用0-1整數(shù)規(guī)劃模型，求解優(yōu)化方案。文獻(xiàn)[5]運(yùn)用馬氏決策過(guò)程構(gòu)建高速鐵路列車運(yùn)行調(diào)整模型，采用策略優(yōu)化方法給出列車順晚開(kāi)行和越行調(diào)整等行動(dòng)的最優(yōu)調(diào)整方案。考慮我國(guó)高速鐵路動(dòng)車組運(yùn)用的特點(diǎn)，一列動(dòng)車組擔(dān)當(dāng)某一車次的運(yùn)輸任務(wù)達(dá)到終點(diǎn)站后會(huì)繼續(xù)擔(dān)當(dāng)另一車次的運(yùn)輸任務(wù)。因此一列列車的晚點(diǎn)不僅會(huì)影響到線路上的后行列車，也會(huì)影響到晚點(diǎn)列車的接續(xù)列車。前續(xù)列車晚點(diǎn)會(huì)造成后續(xù)列車無(wú)法正點(diǎn)始發(fā)。該場(chǎng)景一般會(huì)發(fā)生在具有大量始發(fā)終到作業(yè)車站所在的調(diào)度區(qū)段。

本文建立考慮動(dòng)車組接續(xù)的高速鐵路列車運(yùn)行圖智能調(diào)整多目標(biāo)優(yōu)化模型，采用基于改進(jìn)和聲搜索算法對(duì)所建立的模型進(jìn)行求解，以京津城際延伸線的實(shí)際列車運(yùn)行數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證。

1 動(dòng)車組接續(xù)關(guān)系分析

動(dòng)車組接續(xù)是一趟列車終到后在車站銜接另一趟始發(fā)列車。動(dòng)車組接續(xù)是為了解決動(dòng)車組車底擔(dān)當(dāng)不同車次的運(yùn)營(yíng)任務(wù)在車站的合理銜接問(wèn)題，明確終到動(dòng)車組車底的去向及下一運(yùn)營(yíng)擔(dān)當(dāng)?shù)能嚧?，始發(fā)動(dòng)車組車底的來(lái)源及上一運(yùn)營(yíng)擔(dān)當(dāng)?shù)能嚧巍＞哂写罅渴及l(fā)終到作業(yè)的車站有兩種類型：一種是通過(guò)式車站，另一種是盡頭式車站。通過(guò)式車站可以銜接兩條或兩條以上不同的線路，其正線和到發(fā)線是貫通的，在兩個(gè)咽喉區(qū)能分別辦理接發(fā)車作業(yè)，如天津站城際場(chǎng)、成都東站等。盡頭式車站的到發(fā)線是盡頭式的，只銜接一個(gè)方向，只有一個(gè)咽喉可以辦理接發(fā)車作業(yè)，如于家堡站、峨眉山站等。

動(dòng)車組在車站的接續(xù)運(yùn)用通常有兩種方式：一種是順向接續(xù)，另一種是逆向接續(xù)。順向接續(xù)是指列車從車站一端接入到發(fā)線后接續(xù)下一趟動(dòng)車組列車，列車的進(jìn)出站進(jìn)路均不切割車站咽喉區(qū)，通常只發(fā)生在通過(guò)式車站。逆向接續(xù)是指列車從車站一端接入到發(fā)線后接續(xù)下一趟動(dòng)車組列車，列車的進(jìn)出站進(jìn)路要縱向切割咽喉區(qū)。根據(jù)接發(fā)車進(jìn)路及到發(fā)線使用的不同，逆向接續(xù)方式可再分為順接反發(fā)和反接順發(fā)。動(dòng)車組采用逆向接續(xù)方式時(shí)，接車作業(yè)或發(fā)車作業(yè)時(shí)會(huì)縱向切割車站咽喉，這將會(huì)與其他列車的接發(fā)車進(jìn)路構(gòu)成沖突，當(dāng)車流密度高時(shí)會(huì)降低車站的通過(guò)能力和作業(yè)效率，同時(shí)也構(gòu)成了列車運(yùn)行圖調(diào)整時(shí)的約束條件。

動(dòng)車組的接續(xù)時(shí)間由旅客乘降、司機(jī)換端、座椅調(diào)整、車廂清掃保潔、上水、吸污、送餐、貨物乘降等時(shí)間組成。動(dòng)車組的接續(xù)時(shí)間與旅客數(shù)量、動(dòng)車組的編組形式、動(dòng)車組的性能、車體結(jié)構(gòu)、車站的拓?fù)浣Y(jié)構(gòu)、?？空九_(tái)、進(jìn)出站口的位置及數(shù)量等因素有關(guān)。在動(dòng)車組交路計(jì)劃編制和列車開(kāi)行方案編制過(guò)程中，動(dòng)車組間的接續(xù)時(shí)間一般由最小交路時(shí)間和冗余時(shí)間構(gòu)成。

2 考慮動(dòng)車組接續(xù)的列車運(yùn)行圖智能調(diào)整模型

2.1 建模約定

已知開(kāi)行方案基本圖、動(dòng)車組交路關(guān)系和車站拓?fù)浣Y(jié)構(gòu)。不考慮列車反向運(yùn)行，不改變動(dòng)車組的規(guī)定接續(xù)關(guān)系。

2.2 參數(shù)定義

式中：i為接續(xù)的前車；j為接續(xù)的后車，存在接續(xù)關(guān)系的動(dòng)車組對(duì)數(shù)量為Nconn。

λstart為列車起車附加時(shí)分，λstop為列車停車附加時(shí)分，TR為列車實(shí)際到達(dá)出發(fā)時(shí)刻的m×2n矩陣。

2.3 約束條件

(1)動(dòng)車組接續(xù)需發(fā)生在同一車站的同一股道。

(2)旅客列車在有旅客乘降車站(有作業(yè)的車站)的發(fā)車時(shí)間不得小于圖定發(fā)車時(shí)間。

(3)存在接續(xù)關(guān)系的列車，需滿足動(dòng)車組最小接續(xù)時(shí)間。

(4)某動(dòng)車組車底同一時(shí)刻只能擔(dān)當(dāng)唯一一趟列車的運(yùn)輸任務(wù)。

(5)區(qū)間運(yùn)行時(shí)分不得小于最小區(qū)間運(yùn)行時(shí)分。

(6)同向相鄰列車的發(fā)車時(shí)間間隔和接車時(shí)間間隔約束。

ε取值為3 min。

(7)動(dòng)車組接續(xù)對(duì)車站咽喉區(qū)占用的約束。設(shè)列車i和列車j在車站s存在接續(xù)關(guān)系，列車i為接續(xù)前車，列車j為接續(xù)后車，列車e∈Train。

(8)列車的交會(huì)和越行只能發(fā)生在車站，列車占用區(qū)間順序的約束。

(9)列車在車站的作業(yè)時(shí)間不得小于最小作業(yè)時(shí)間[6]。

(10)車站到發(fā)線使用約束。

2.4 目標(biāo)函數(shù)

(1)總晚點(diǎn)時(shí)間最小，提高正點(diǎn)率。

(2)晚點(diǎn)波及到的列車數(shù)量最少。

3 求解算法

列車運(yùn)行調(diào)整問(wèn)題屬于動(dòng)態(tài)的大規(guī)模組合優(yōu)化問(wèn)題，約束條件多且復(fù)雜，求解難度較大。本文采用改進(jìn)的和聲搜索算法求解考慮動(dòng)車組接續(xù)的列車運(yùn)行圖智能調(diào)整模型。

和聲搜索HS(Harmony Search)算法是2001年由GEEM Z W等人提出的一種啟發(fā)式智能優(yōu)化算法[7]。和聲搜索算法模擬樂(lè)隊(duì)演奏過(guò)程。不斷調(diào)整各種樂(lè)器的音調(diào)尋找一個(gè)最美妙的和聲類比于優(yōu)化算法中通過(guò)不斷迭代求得一個(gè)解使得目標(biāo)函數(shù)最優(yōu)，演奏中最美妙的和聲類比于優(yōu)化問(wèn)題中的最優(yōu)解，美學(xué)評(píng)估類比于目標(biāo)函數(shù)，各種樂(lè)器的音調(diào)類比于各變量的取值，每一次的練習(xí)類比于每一次的迭代?；竞吐曀阉魉惴鞒倘缦拢?/p>

步驟1初始化算法參數(shù)。和聲記憶庫(kù)的規(guī)模HMS、和聲記憶庫(kù)取值概率HMCR、微調(diào)概率PAR、音調(diào)調(diào)節(jié)帶寬BW和算法終止條件NI(最大迭代次數(shù))[8]。

步驟2初始化和聲庫(kù)。隨機(jī)產(chǎn)生HMS個(gè)候選解至和聲庫(kù)。

步驟3基于和聲庫(kù)構(gòu)造新的和聲。以和聲記憶庫(kù)取值概率HMCR在和聲記憶庫(kù)內(nèi)搜索新解，以1-HMCR概率在和聲記憶庫(kù)外自變量值域內(nèi)搜索新解，然后以微調(diào)概率PAR對(duì)新解進(jìn)行局部擾動(dòng)。

步驟4如果新產(chǎn)生的和聲解優(yōu)于和聲記憶庫(kù)中最差和聲解，則用新產(chǎn)生的和聲解代替和聲庫(kù)中的最差和聲解。

步驟5若滿足算法終止條件，則算法結(jié)束，輸出最優(yōu)解，否則返回步驟3繼續(xù)求解。

和聲搜索算法通用性強(qiáng)，無(wú)復(fù)雜理論公式，參數(shù)少，易于收斂，易于編程實(shí)現(xiàn)，適合非線性問(wèn)題的求解；具有群體搜索的特點(diǎn)，能夠記憶最優(yōu)解；同時(shí)也具有協(xié)同搜索的特點(diǎn)，通過(guò)各體局部信息與群體全局信息的交互指導(dǎo)算法的搜索方向，然而基本的和聲搜索算法也存在著一定的缺陷。由于和聲搜索算法主要是基于鄰域搜索進(jìn)行尋優(yōu)的，初始解選取的質(zhì)量對(duì)算法搜索的性能影響較大。在整個(gè)優(yōu)化過(guò)程中HMCR和PAR值固定不變，使得算法容易出現(xiàn)“早熟”收斂，陷入局部最優(yōu)，群體多樣性降低，搜索能力受到限制。

對(duì)于列車運(yùn)行圖調(diào)整問(wèn)題，即求解TR，解是一個(gè)m×2n的矩陣。矩陣中第p行q列變量表示為T(mén)Rp,q，和聲記憶庫(kù)可表示為

針對(duì)基本和聲搜索算法的固有缺陷及結(jié)合列車運(yùn)行圖調(diào)整的特點(diǎn)，從以下幾個(gè)方面進(jìn)行改進(jìn)。

(1)對(duì)于列車運(yùn)行圖調(diào)整問(wèn)題，隨機(jī)解是不可行的。因此由運(yùn)行圖終端程序按不同的區(qū)間運(yùn)緩時(shí)間生成HMS個(gè)初始化和聲庫(kù)中的初始解，以提高算法的執(zhí)行效率。

(2)HMCR在優(yōu)化的不同階段取不同值，HMCR∈[HMCRmin,HMCRmax)，HMCR=HMCRmax-(HMCRmax-HMCRmin)×gn/NI，gn表示當(dāng)前迭代次數(shù)。優(yōu)化初期，較大的HMCR值有利于找到局部最優(yōu)解；優(yōu)化末期，較小的HMCR值可增加提高解的多樣性。

(5)和聲記憶庫(kù)外的變量值取該調(diào)度臺(tái)同時(shí)段的歷史行車數(shù)據(jù)。

改進(jìn)后的和聲搜索算法流程如圖1所示。

4 算例驗(yàn)證與分析

采用北京局管內(nèi)京津城際二臺(tái)(京津城際延伸線)的實(shí)際應(yīng)用情況做仿真驗(yàn)證。京津城際延伸線正線全長(zhǎng)44.75 km，按高速鐵路客運(yùn)專線標(biāo)準(zhǔn)設(shè)計(jì)，設(shè)計(jì)時(shí)速350 km。自天津站城際場(chǎng)引出，沿途經(jīng)機(jī)場(chǎng)西線路所、軍糧城北站、濱海西線路所、塘沽城際場(chǎng)站，終到于家堡站。天津站城際場(chǎng)示意圖如圖2所示，于家堡站示意圖如圖3所示。京津城際二臺(tái)8:00—12:00的基本圖如圖4所示。京津城際二臺(tái)8:00—12:00各列車次在各站的到發(fā)時(shí)刻及端頭站股道使用情況見(jiàn)表1。期間動(dòng)車組交路情況為：C2581-C2584，C2314-C2315-C2318，C2332-C2333，C2583-C2302-C2303，C2316-C2317，C2585-C2586(“-”表示接續(xù))。

圖1 改進(jìn)和聲搜索算法流程圖

圖2 天津城際場(chǎng)示意圖

圖3 于家堡站示意圖

圖4 京津城際二臺(tái)8:00—12:00基本圖

車次站 名天津城際場(chǎng)機(jī)場(chǎng)西線路所軍糧城北城際場(chǎng)濱海西線路所塘沽城際場(chǎng)于家堡到達(dá)出發(fā)股道到達(dá)出發(fā)到達(dá)出發(fā)到達(dá)出發(fā)到達(dá)出發(fā)到達(dá)出發(fā)股道C25817:588:01ⅡG8:098:098:108:108:128:128:198:208:29×2GC2315×8:42Ⅰ7G8:508:508:518:518:538:538:578:579:04×6GC2333×9:03Ⅰ5G9:119:119:159:169:209:209:279:289:37×1GC25839:199:21Ⅰ7G9:299:299:339:349:389:389:459:469:55×2GC2317×10:30Ⅰ6G10:3810:3810:3910:3910:4110:4110:4510:4510:52×5GC258511:0211:04Ⅰ7G11:1211:1211:1311:1311:1511:1511:2211:2311:32×ⅣGC2303×11:12Ⅰ6G11:2011:2011:2411:2511:2911:2911:3611:3711:46×ⅢGCZ3148:11×Ⅰ7G8:038:038:018:017:597:597:567:56×7:506GC23328:35×Ⅰ5G8:278:278:258:258:238:238:208:20×8:141GCZ5849:219:23Ⅰ6G9:139:139:119:119:099:099.:039:04×8:542GCZ31610:08×Ⅰ6G10:0010:009:589:589:569:569:509:51×9:415GC230210:40×Ⅰ6G10:3210:3210:2710:2810:2210:2210:1910:19×10:132GC231811:22×Ⅰ6G11:1411:1411:0911:1011:0411:0411:0111:01×10:556GC258612:2212:25Ⅰ6G12:1412:141212121212:1012:1012:0412:05×11:55ⅣG

基于以上數(shù)據(jù)可以得出，C2315到達(dá)于家堡站進(jìn)入6G縱向切割下行咽喉；C2317由天津城際場(chǎng)Ⅰ6G出發(fā)縱向切割上行咽喉，C2317到達(dá)于家堡站進(jìn)入5G縱向切割下行咽喉；C2303由天津城際場(chǎng)Ⅰ6G出發(fā)縱向切割上行咽喉；C2332由于家堡站1G出發(fā)縱向切割下行咽喉;C2332到達(dá)天津城際場(chǎng)進(jìn)入Ⅰ5G縱向切割上行咽喉；C2854由于家堡站2G出發(fā)縱向切割下行咽喉；C2314到達(dá)天津城際場(chǎng)進(jìn)入Ⅰ7G縱向切割上行咽喉。

模擬4種干擾場(chǎng)景，場(chǎng)景1：C2315由于某種原因在機(jī)場(chǎng)西線路所至軍糧城北城際場(chǎng)下行區(qū)間運(yùn)緩，導(dǎo)致在軍糧城北城際場(chǎng)通過(guò)時(shí)晚點(diǎn)5 min。場(chǎng)景2：C2583由于某種原因在塘沽城際場(chǎng)至于家堡站下行區(qū)間運(yùn)緩，導(dǎo)致在于家堡站到達(dá)晚點(diǎn)2 min。場(chǎng)景3：C2583由于某種原因在塘沽城際場(chǎng)至于家堡站下行區(qū)間運(yùn)緩，導(dǎo)致在于家堡站到達(dá)晚點(diǎn)10 min。場(chǎng)景4：C2332由于某種原因在軍糧城北城際場(chǎng)至機(jī)場(chǎng)西線路所上行區(qū)間運(yùn)緩，導(dǎo)致在機(jī)場(chǎng)西線路所通過(guò)時(shí)間晚點(diǎn)6 min。

將建立的模型和改進(jìn)和聲搜索算法采用VC++編程植入運(yùn)行圖終端自動(dòng)調(diào)整模塊中，設(shè)動(dòng)車組接續(xù)最小交路時(shí)間為15 min，已轉(zhuǎn)實(shí)績(jī)的點(diǎn)不參與調(diào)整，設(shè)置改進(jìn)和聲搜索算法參數(shù)：HWS=10，HMCR=[0.35,0.95]，PAR=[0.1,0.5]，NI=10 000。注入上述4種干擾場(chǎng)景后，經(jīng)運(yùn)行圖終端程序的自動(dòng)調(diào)整后輸出的結(jié)果如圖5～圖8所示。

圖5 場(chǎng)景1調(diào)整結(jié)果

圖6 場(chǎng)景2調(diào)整結(jié)果

圖7 場(chǎng)景3調(diào)整結(jié)果

圖8 場(chǎng)景4調(diào)整結(jié)果

算例仿真分析：場(chǎng)景1中C2315在機(jī)場(chǎng)西線路線路所通過(guò)晚點(diǎn)5 min后，該運(yùn)行線后續(xù)各點(diǎn)均晚點(diǎn)5 min，在于家堡站終到晚點(diǎn)5 min的時(shí)刻為09:09。由于C2315的接續(xù)動(dòng)車組C2318在于家堡站的始發(fā)時(shí)刻為11:05，因此C2315的晚點(diǎn)不會(huì)影響接續(xù)動(dòng)車組C2318。仿真結(jié)果與預(yù)期一致。場(chǎng)景2中C2583在于家堡站終到后接續(xù)C2302，圖定動(dòng)車組接續(xù)時(shí)間為18 min，實(shí)際C2583在于家堡站到達(dá)晚點(diǎn)2 min，由于最小動(dòng)車組接續(xù)時(shí)間為15 min，沒(méi)有對(duì)接續(xù)的C2302在于家堡站的始發(fā)造成影響，仿真結(jié)果與預(yù)期一致。場(chǎng)景3中C2583在于家堡站終到后接續(xù)C2302，圖定動(dòng)車組接續(xù)時(shí)間為18 min，實(shí)際C2583在于家堡站到達(dá)晚點(diǎn)10 min，由于最小動(dòng)車組接續(xù)時(shí)間為15 min，利用動(dòng)車組接續(xù)的冗余時(shí)間將晚點(diǎn)縮小至7 min，C2302在天津城際場(chǎng)到達(dá)晚點(diǎn)7 min，C2302的接續(xù)動(dòng)車組為C2303，圖定動(dòng)車組接續(xù)時(shí)間為32 min，利用該動(dòng)車組接續(xù)的冗余時(shí)間，消除了晚點(diǎn)，C2303在天津城際場(chǎng)可正點(diǎn)發(fā)車。仿真結(jié)果與預(yù)期一致。從場(chǎng)景4的調(diào)整結(jié)果可以看出在天津城際場(chǎng)變更了C2332與C2315的接發(fā)車順序。由于C2332在機(jī)場(chǎng)西線路所通過(guò)晚點(diǎn)6 min，進(jìn)而導(dǎo)致在天津城際場(chǎng)到達(dá)也晚點(diǎn)6 min，即08:41到達(dá)天津城際場(chǎng)，由于C2332進(jìn)入15G時(shí)縱向切割上行咽喉將與圖定08:42由該站17G發(fā)車的C2315發(fā)生進(jìn)路沖突，若不改變C2332和C2315在天津城際場(chǎng)的接車列車順序，將導(dǎo)致C2315在各站都晚點(diǎn)。改變接發(fā)車順序后使得接續(xù)列車C2315正點(diǎn)發(fā)車，同時(shí)不影響其接續(xù)動(dòng)車組C2333的發(fā)車，可減小總晚點(diǎn)時(shí)間，縮小晚點(diǎn)波及的影響范圍，有效控制晚點(diǎn)傳播，仿真結(jié)果與預(yù)期一致。

5 結(jié)束語(yǔ)

本文針對(duì)具有大量始發(fā)終到作業(yè)車站所在的調(diào)度區(qū)段動(dòng)車組接續(xù)的特點(diǎn)，建立考慮動(dòng)車組接續(xù)的高速鐵路列車運(yùn)行圖智能調(diào)整模型，采用基于改進(jìn)和聲搜索算法對(duì)所建立的模型進(jìn)行求解，從4種模擬干擾場(chǎng)景的調(diào)整結(jié)果看，考慮動(dòng)車組接續(xù)的高速鐵路列車運(yùn)行圖智能調(diào)整模型可根據(jù)晚點(diǎn)時(shí)間程度的不同，利用動(dòng)車組接續(xù)的冗余時(shí)分及區(qū)間運(yùn)行的冗余時(shí)分減少晚點(diǎn)時(shí)間，同時(shí)考慮晚點(diǎn)后車站接發(fā)車進(jìn)路的相互影響，適當(dāng)調(diào)整在車站的接發(fā)車順序，能夠有效縮小晚點(diǎn)的影響范圍，控制晚點(diǎn)傳播。

綜上所述，考慮動(dòng)車組接續(xù)的高速鐵路列車運(yùn)行圖智能調(diào)整模型及采用的改進(jìn)和聲搜索算法，具有可行性和有效性?？紤]動(dòng)車組接續(xù)的高速鐵路列車運(yùn)行圖智能調(diào)整研究為實(shí)現(xiàn)高速鐵路智能調(diào)度系統(tǒng)提供了理論與應(yīng)用技術(shù)支撐。