離所時間限制下動車組交路計劃優化研究

郭倩倩，王振宇，林柏梁

(1.石家莊鐵道大學 河北省交通安全與控制重點實驗室，河北 石家莊 050043；2.石家莊鐵道大學 交通運輸學院， 河北 石家莊 050043；3.北京交通大學 交通運輸學院，北京 100044)

動車組交路計劃是編制動車運用計劃與檢修計劃的基礎,是列車運行圖車次合理接續的依據。在運輸實踐中,一般先根據列車運行圖勾畫出動車組交路,然后以動車組交路為基礎編制運用與檢修計劃。故優化動車組交路,可以有效地減少動車組運用數量,科學地配置動車組資源。此外,對于提高動車組的運用與檢修管理水平亦具有重要的意義?？茖W地安排動車組交路是完成圖定運輸任務的前提,也是保障動車組列車安全運行和提高動車組運用效率的關鍵。截至2021年底,我國高速鐵路(以下簡稱“高鐵”)營業里程超過4萬km,動車組保有量達4 153標準組。為保證動車組安全高效運行,其交路與檢修計劃優化問題得到業內研究人員的廣泛重視。

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

以上對動車組交路優化方面的研究,大多數僅從檢修約束,如動車所檢修能力、動車組檢修時間、檢修里程以及檢修成本等方面考慮,幾乎沒有在離所時間約束下動車組交路計劃編制的文獻。但在實際運營中動車組如果離所時間過晚,則會造成動車組運行時間較短,無法承擔長距離交路任務。舉個比較極端的例子,動車組22:00離所,24:00回所理論上也是交路方案的備選之一,但是從動車所管理人員角度考慮,他們認為這是顯然不合理方案,不予考慮。

本文基于列車接續網絡圖,建立離所時間約束下動車組交路優化模型,以滿足動車組日常運用需求為基礎,以縮短動車組接續總時間與降低動車組交路總損失里程為雙重目標,提高動車組的運用效率。

1 離所時間限制下動車組交路問題的背景

動車組交路計劃[16]是基于給定列車運行圖,規定列車任務間動車組接續關系及一級檢修地點,將列車運行圖中列車任務組合成若干運用交路的計劃,是編制日常動車組運用計劃的基礎性計劃。動車組的交路計劃主要與動車組的一級檢修關聯,根據動車組交路的定義可以將其理解為動車組在兩次一級檢修之間所擔當的列車車次有序接續集合。而動車組的二級修則與動車組的上線計劃相關聯,動車組上線運用計劃就是安排動車組去擔當列車車次或交路的問題,同時,要考慮動車組二級修各個檢修項目的檢修周期。相對于一級檢修和二級檢修,動車組的高級檢修的檢修周期和扣修周期都比較長,對動車組的交路計劃和運用計劃影響相對較小,其往往與春、暑運相關聯。因此,本文在研究動車組交路計劃時,僅考慮動車組的一級檢修。

根據動車組管理的實際情況,動車組擔當完一條交路后,需要進行一級檢修。以包含4個車站,1個動車所,12個列車的實例來說明,研究離所時間約束下動車組交路計劃優化問題的必要性。A站列車車次的相關信息見表1,其中A站為動車所相連接的車站,B、C、D站為折返站。

表1 A站列車車次相關信息

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

圖1 不考慮離所時間限制的動車組交路

圖2 最晚離所時刻為14:00的動車組交路

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

2 數學模型構建

2.1 列車接續網絡圖

通過引入網絡理論,以列車車次為網絡的節點,以列車車次接續關系和一級檢修作為網絡的弧,構建動車組列車接續網絡[16]。因為交路的起點和終點都是動車所,每一條交路實際上是由列車車次節點、列車車次接續弧和一級檢修弧構成的閉合回路。動車組列車接續網絡示意圖見圖3,根據圖2中的動車組交路,可以構建兩條列車車次接續回路,見圖3(a)。為了便于后續數學模型的建立,將列車接續網絡中的各條閉合回路通過一級檢修弧連接起來,形成一條由所有列車車次節點、列車車次接續弧和一級檢修弧構成的閉合回路,見圖3(b)。

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

2.2 構建模型的假設

為進一步把問題抽象和簡化,建模前作如下假設:

1)不考慮動車所對一級檢修能力的限制,對于動車組集中到達動車所的情況,通過人工干預進行調整。

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

3)只考慮動車組的單車種、單基地問題,對于多車種、多基地問題,可以采用本文研究的思路將其轉化為多個子問題求解。

2.3 符號定義

模型涉及的相關符號,包括集合、參數、變量的定義見表2。

2.4 數學模型

為表述動車組交路計劃中列車車次接續關系、一級檢修作業安排及修程標準約束,需要給出以下變量的表達式。

若車次i的到達車站等于車次j的始發車站,并且車次j的始發時刻與i的到達時刻相差時間間隔大于列車之間接續的最小時間標準,則tij等于車次j的始發時刻減去車次i的到達時刻;同理,若車次i的到達車站等于車次j的始發車站,但是車次j的始發時刻與i的到達時刻相差時間間隔小于列車之間接續的最小時間標準,那么可以考慮接續第二天的相同列車車次,此時接續時間增加1 440 min;若兩個列車車次不滿足接續地點的要求,規定車次的接續時間為無窮大。tij為

( 1 )

( 2 )

( 3 )

動車組交路優化問題的目標函數一般為動車組使用數量最少、接續時間最少、檢修次數最少和動車組交路損失里程最少等。在列車運行圖確定的情況下,所有列車的運行時間和運行里程是不變的,動車組接續時間最少和動車組使用數量最少是等價的,動車組交路損失里程最少和檢修次數最少是等價的,可任選其一作為目標函數[17]。本文選擇動車組交路中列車車次接續時間Z1與動車組交路總損失里程Z2作為優化目標函數,即

( 4 )

( 5 )

為將兩個目標的量綱統一,將目標式( 4 )和式( 5 )進行加權(權重系數為w1和w2),取最小值作為目標函數,即

minZ=w1Z1+w2Z2

( 6 )

1)列車車次接續唯一性約束

對于每一個列車車次,只能有一個緊前車次和一個緊后車次,這種關系在邏輯上表現為唯一性約束,即

( 7 )

( 8 )

2)動車組一級檢修邏輯約束

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

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

( 9 )

3)動車組一級檢修里程周期和時間周期約束

在實際運營組織中,動車組的運行里程一般允許存在超期檢修,但是不同級別的檢修作業有著不同的超期檢修比例,一級檢修作業的超期檢修比例λ一般為10%,即

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

(10)

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

tj≤Tcyclej=1,2,…,n

(11)

4)動車組最晚離所時間約束

動車組的離所時刻要早于要求的最晚離所時刻,即交路的開始時刻要早于要求的最晚開始時刻,即

(12)

5)避免子回路邏輯約束

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

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

(13)

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

(14)

式中:ui和uj分別為車次i和j在回路中的位置編號。

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

6)0-1變量約束

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

(15)

綜上所述,考慮離所時間約束下的動車組交路計劃優化模型為

minZ=w1Z1+w2Z2

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

3 模擬退火算法

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

3.1 能量函數

為了降低模型的求解復雜程度,需要將模型中的復雜約束條件作為懲罰項加入到目標函數中。這里的復雜約束主要是約束式(10)～式(12),將其乘以懲罰系數作為懲罰項添加到目標函數中。3個約束對應的3個懲罰項分別為

(16)

(17)

(18)

式中:β1、β2、β3分別為相應的懲罰系數;H1、H2、H3分別為3個復雜約束對應的懲罰項。

原模型的目標函數為

(19)

將其與上述懲罰項結合,所得能量函數為

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

(20)

3.2 初始溫度的確定

在確定初始溫度T0時,利用Aarts等[18]提出的方法,先隨機地產生m個解,則有

(21)

(22)

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

3.3 初始解的生成

首先定義兩個集合Ω1、Ω2,其中Ω1用來存放始發站為檢修站(運用所連接站)的車次,Ω2用來存放終到站為檢修站的車次,然后為每個車次生成一個集合,該集合內存放可以與該車次相接續的其他車次,最后額外定義一個集合Ω3用來存放已經得到的可行解。

從Ω1集合中隨機選取一個車次作為整體回路的首位,然后根據約束式( 7 )～式( 9 )在首位車次確定的基礎上,依照上述邏輯約束隨機確定一條回路。即在首位車次確定的基礎上,從該車次對應的集合中隨機選取一個車次進行接續,同時確保該車次在該回路中沒有出現過,按照該種思路,依次選取車次接續,若選中車次已經存在于當前回路中,則重新隨機選取直至所有車次均被包含在回路中。在確定回路中的最后一個車次時,要確保該車次的終到站為檢修站,即確保最后一個車次來源于Ω2。最后把該回路存放到Ω3中,記為一個可行解。

3.4 鄰域解的生成

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

3.5 溫度的更新策略

降溫方法為

(23)

式中:參數δ一般取0.4;α一般取0.95;kd為高低溫迭代次數的分界點,一般為70;φ(Tk)為Tk溫度下能量函數期望值的標準差。

3.6 算法步驟

Step1確定初始溫度T0。記當前的降溫次數k=0,轉Step2。

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

Step3當經過k次降溫后,在溫度Tk下,記第n-1次迭代后的解為Xn-1,按照3.4節中的方法生成鄰域解,計算出對應的函數值能量G(Xn),轉Step4。

Step4利用Metroplis抽樣準則對當前解進行檢驗,若G(Xn)-G(Xn-1)<0,則無條件接受Xn代替Xn-1;若G(Xn)-G(Xn-1)>0,則以概率γn(Tk)接受鄰域解。γn(Tk)為

(24)

轉Step5。

Step6算法收斂終止判定。本文設置了兩個終止準則:一種是接受率小于給定的閾值時,另一種是能量函數在多次迭代過程中保持不變,兩個準則滿足一個即結束該算法。否則,轉Step7。

Step7按3.5節中的內容進行降溫,記降溫次數k=k+1,置迭代步數n=0,返回Step3。

4 算例分析

4.1 數據

本文以太原南動車所配屬的CRH2A動車組車型為例,選取2021年10月該車型擔當的部分車次作為基本數據,進行算例驗證分析。太原南站部分列車車次見表3,所研究車次的開行區段覆蓋車站11個。動車所與太原南站相連,采用單點檢修方式,可為本動車所的動車組提供一級檢修。

表3 太原南站部分列車車次

根據TG/CL 127—2017《鐵路動車組運用維修規則》[22],CRH2A型動車組的一級檢修時間周期Tcycle為48 h,里程周期Lcycle為4 000 km,動車組超期檢修的百分比λ為10%,列車接續時間標準tconnect為15 min。

4.2 優化計算

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

根據本文設計的求解步驟,采用VC++程序設計實現,在Core 2.4 GHz的個人計算機上運行。這里ρ0取值為0.9,β1、β2均取值為50(通過多次試驗計算確定),w1、w2取值為0.5。結合實際情況,要求動車組離開動車運用所的最晚時刻為14:00,即Tlatest取值為14:00,晚點懲罰系數β3取值為99(通過多次試驗計算取值)。兩種場景下的動車組交路優化方案見表4。

表4 兩種場景下的動車組交路優化方案

由表4可知,兩種場景下得到的交路數量一樣,均為7個交路,但具體的交路方案存在差異。對比表4中結果可以發現,場景二與場景一相比,僅有交路2、3、6有所變化,其余交路方案則相同。此外,場景一的交路方案中,交路2的離所時刻為15:12,即過晚發車,這正是由于沒有考慮離所時刻約束所導致的情況。相反,場景二的交路方案中均滿足最晚離所時刻限制,即離所時刻均早于14:00。

同時,由于列車車次是已知的,并且得到的交路數量也一樣,則說明兩種場景下交路方案的檢修里程利用率相等,但是總運行時間則有所不同。從表4可以看到,場景一中交路運行時間最短為1 226 min,最長為2 308 min;場景二中交路運行時間最短為1 528 min,最長為2 288 min。從運行時間指標來看,雖然場景一得到的交路方案較好,但是存在過晚發車的情況。此外,還統計分析了兩種場景下交路方案的總接續時間。列車車次數量一定,各個車次的圖定運行時間一定,則總運行時間的不同體現在總接續時間上。經計算,場景一中動車組的總接續時間為5 153 min,而場景二中動車組的總接續時間為5 205 min。場景二的總接續時間僅比場景一多52 min,但是場景二中得到的交路方案可以很好地避免動車組過晚離所。

綜上分析,在考慮動車組離所時間約束下,本文所建模型可以很好地避免動車組的過晚離所發車,使動車組的運營更加符合實際運輸生產需求。

5 結論

本文研究離所時間限制下的動車組交路優化計劃,在建立數學模型時將動車組最晚離開動車所時刻作為約束條件,以動車組接續總時間最少和動車組交路總損失里程最少為優化目標,構建離所時刻約束下的動車組交路優化模型。所建立模型為非線性0-1整數規劃模型,為提高求解效率,設計模擬退火啟發式算法。最終通過算例分析驗證本文提出模型和算法的有效性。結果表明:與不考慮離所時刻約束相比,離所時刻約束下的動車組交路優化方案,可以很好地避免動車組的過晚離所發車,更加符合運輸生產實際需求。

本文所建模型是非線性規劃模型,求解有一定的難度,因此,在建模前做了簡化,如僅考慮單車種、單基地的動車組以及列車運行圖是已知的情況等,今后可在考慮多車種、多基地動車組情況下,研究動車組交路和列車運行圖的協調優化問題。