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

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

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

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

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

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

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

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

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

2.1 建模約定

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

2.2 參數(shù)定義

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

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

2.3 約束條件

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

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

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

(4)某動車組車底同一時刻只能擔當唯一一趟列車的運輸任務(wù)。

(5)區(qū)間運行時分不得小于最小區(qū)間運行時分。

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

ε取值為3 min。

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

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

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

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

2.4 目標函數(shù)

(1)總晚點時間最小，提高正點率。

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

3 求解算法

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

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

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

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

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

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

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

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

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

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

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

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

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

改進后的和聲搜索算法流程如圖1所示。

4 算例驗證與分析

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

圖1 改進和聲搜索算法流程圖

圖2 天津城際場示意圖

圖3 于家堡站示意圖

圖4 京津城際二臺8:00—12:00基本圖

車次站 名天津城際場機場西線路所軍糧城北城際場濱海西線路所塘沽城際場于家堡到達出發(fā)股道到達出發(fā)到達出發(fā)到達出發(fā)到達出發(fā)到達出發(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到達于家堡站進入6G縱向切割下行咽喉；C2317由天津城際場Ⅰ6G出發(fā)縱向切割上行咽喉，C2317到達于家堡站進入5G縱向切割下行咽喉；C2303由天津城際場Ⅰ6G出發(fā)縱向切割上行咽喉；C2332由于家堡站1G出發(fā)縱向切割下行咽喉;C2332到達天津城際場進入Ⅰ5G縱向切割上行咽喉；C2854由于家堡站2G出發(fā)縱向切割下行咽喉；C2314到達天津城際場進入Ⅰ7G縱向切割上行咽喉。

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

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

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

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

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

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

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

5 結(jié)束語

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

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