考慮車底接續延誤概率的普速旅客列車車底套用方案魯棒優化

朱昌鋒，李引珍

(蘭州交通大學 交通運輸學院，甘肅 蘭州　730070)

旅客列車車底是完成客運生產任務的重要移動裝備，在鐵路裝備投資中占有較大的比重。合理的車底運用方案可減少車底投入數量，降低運營成本，因此，優化車底運用對于提高鐵路運輸生產效益具有重要意義。

車底套用是提高車底運用效率的有效途徑之一，為此，相關學者就該問題開展了大量的研究，并取得了一定的研究成果。聶磊等[1]、趙鵬等[2]、史峰等[3]、張才春等[4]從不同角度研究了動車組運用計劃的優化模型，對普速旅客列車車底運用具有一定的參考價值，但由于普速旅客列車車底類型及其編組結構的多樣性，對其運用優化具有一定的挑戰。Cordeau等[5]運用Benders分解法研究了機車和車底調用；劉鋼等[6]建立了普速旅客列車車底周轉接續的雙層指派優化模型，但僅考慮了同等級列車之間車底的接續以及始發列車的車底屬于同一路局的情況；謝金貴等[7]利用多商品網絡流理論，建立了普速旅客列車車底運用優化的整數規劃模型，但由于該問題屬于NP問題，需尋找更加有效的求解算法；肖益帆等[8]通過考慮不同等級列車間的車底套用，建立了以所需車底數量最少為目標的普速旅客列車車底運用優化模型，設計了基于模擬退火算法的求解策略；Zeyi BING[9]通過引入“列車串”，建立了以車底在始發站和終到站停留時間最少為目標的普速旅客列車車底運用優化模型；朱昌鋒等[10-11]以始發和終到旅客列車的車底不必要在站停留時間最少為目標函數，建立基于既定運行詳圖的普速旅客列車車底套用優化模型，分析了車底套用對鐵路大型客運站到發線分配的影響。上述研究從不同的視角對該問題進行了研究，但僅研究了任一普速旅客列車車底最多可套跑1個區段的套用模式，且未能考慮列車晚點對車底套用的擾動影響以及車底運用的均衡性，使得所建優化模型具有一定的局限性，限制了優化模型的實際應用效果。

基于此，本文在不改變普速旅客列車車底配屬制的前提下，通過考慮列車晚點對車底套用的擾動影響以及車底運用的均衡性，提出考慮車底接續延誤概率的普速旅客列車車底套用方案魯棒優化模型，設計基于Pareto排序的多目標粒子群優化算法(Multi-objective particle swarm optimizer，MOPSO)，進一步提高普速旅客列車車底套用的效率和魯棒性。

1　問題描述及分析

根據鐵路路網布局及列車運行圖，設Z={ze|e=1,2,…,E}為鐵路列車運行圖中有普速旅客列車始發和終到的客運站集合；S={sf|f=1,2,…,F}為普速旅客列車車底集合；L={li|i=1,2,…,I}為路網上所有普速旅客列車的運行線集合，La={lai|i=1,2,…,Ia}為終到任一客運站ze的普速旅客列車運行線集合，Ld={ldj|j=1,2,…,Jd}為由任一客運站ze始發的普速旅客列車運行線集合，一般情況下，La=Ld；tai為任一普速旅客列車運行線lai的圖定終到時刻，tdj為任一普速旅客列車運行線ldj的圖定始發時刻。

“長途套跑短途”的普速旅客列車車底套用模式[8-10]如圖1所示，即通過利用任一長途普速旅客列車lai的車底在客運站ze的非生產停留時間，使該車底套跑短途列車對ldj和lai′(lai′∈La)。

圖1　“長途套跑短途”的普速旅客列車車底套用模式

由圖1可見，該類普速旅客列車車底套用模式其實就是通過優化普速旅客列車車底的周轉接續，使終到配屬站(折返站)的車底，在滿足車底整備作業時間等約束的前提下，能夠擔當另一普速旅客列車對的運行任務，并盡可能地減小車底在配屬站(折返站)的停留時間。但是該類車底套用模式受到以下兩方面硬約束的限制。

(1)車底僅可在1個主跑區段(z1-ze)和1個套跑區段(ze-z2)間運行，長途普速旅客列車在主跑區段(z1-ze)間運行，短途普速旅客列車在套跑區段(ze-z2)間運行。

(2)短途普速旅客列車lai′的車底必須于長途普速旅客列車ldj′在ze站的圖定發車時刻之前返回ze站。

由于上述兩方面的硬約束，使得1個車底最多只能套跑1個區段，限制了滿足套用條件的普速旅客列車數量，難以有效提高車底套用的效率。

為了進一步提高普速旅客列車車底套用的效率，在滿足車底必要接續時間的基礎上，取消上述兩方面的限制，使任一車底連續承擔多條普速旅客列車運行線的運行任務后再返回配屬站，此時，這些普速旅客列車運行線便構成1個車底套用的大循環，可進一步節省車底數和客技站的投資規模。但由于不同旅客列車運行線之間具有一定的關聯性，任一車底接續的延誤將影響整個車底的周轉秩序和相關列車的運行秩序，也直接影響著車底套用方案的兌現，因此，魯棒性是車底套用優化中必須考慮的一個關鍵問題。

由此可見，該問題可轉化為：在滿足普速旅客列車車底必要接續時間等相關約束的基礎上，通過考慮車底接續的延誤概率，優化得到能滿足一定條件的若干個車底接續關系的集合。

2　列車晚點時間和車底接續時間對車底接續延誤概率的影響

圖2　列車終到晚點傳播

圖3　列車始發晚點傳播

設tw為旅客列車晚點時間；toper為旅客列車在客運站的技術作業時間；tr為運行圖區間容差；thc為車站預留的緩沖時間，tcon為車底接續時間。列車晚點對車底接續延誤的影響分析如圖4所示。

當列車晚點時間tw小于車站預留的緩沖時間thc或車底接續時間tcon較大時(見圖4(a))，列車晚點不影響車底接續；當列車晚點時間tw大于車站預留的緩沖時間thc或車底接續時間tcon較小時(見圖4(b))，列車晚點將影響車底接續，但由于存在車站預留的緩沖時間thc和運行圖區間容差tr，可采取“趕點”等間隔動態小幅度調整措施，因此僅會影響部分車底的接續；當列車晚點時間tw繼續增大或車底接續時間tcon較小時，如果綜合利用車站預留的緩沖時間thc和運行圖區間容差tr，列車晚點仍不能得到緩解(見圖4(c))，使得套用模式下的車底接續難以滿足要求，就需大幅度調整予以解決。由此可見，列車晚點時間越小或車底接續時間越大，車底接續延誤概率越??；反之，列車晚點時間越大或車底接續時間越小，車底接續延誤概率越大。

圖4　列車晚點對車底接續延誤的影響分析

(1)

(2)

式中：λtw為繼發晚點平均時間的倒數。

(3)

圖5　車底接續時間與車底接續延誤概率間的關系

3　優化模型

3.1　約束條件

(1)車底接續的唯一性約束。根據既定鐵路列車運行圖，在任一運行周期內，任一普速旅客列車lai的車底到達終到站后，最多只能接續1個在該客運站始發的后續車次ldj的運行任務，如果在該周期內無法接續套用，只能轉入下一運行周期。同理，在任一運行周期內，任一始發普速旅客列車ldj的車底只能由任一終到的普速旅客列車lai提供。車底終到與始發接續在同一運行周期內如圖6所示，車底終到與始發接續不在同一運行周期內如圖7所示。

圖6　車底終到與始發接續在同一運行周期內

圖7　車底終到與始發接續不在同一運行周期

定義Xij為0-1變量，表示若普速旅客列車lai的車底接續ldj的運行任務，則Xij=1，否則Xij=0。由此得到車底接續的唯一性約束可表示為

(4)

(5)

(2)車底接續地點約束。只有當任一普速旅客列車ldj的始發站zdj與任一普速旅客列車lai的終到站zai為同一客運站時，普速旅客列車lai的車底才有可能承擔普速旅客列車ldj的運行任務，即

zai=zdj

(6)

(3)車底接續時刻約束。在任一運行周期內，普速旅客列車ldj的始發時刻必須晚于普速旅客列車lai的終到時刻，同時，還應保證必要的列車到發、車底整備等作業時間。

(7)

其中，

式中：ζij為0-1變量，當普速旅客列車lai的車底在接續普速旅客列車ldj前需進整備所整備時，則ζij=1，否則ζij=0；?ij為0-1變量，當普速旅客列車lai的車底需轉股道接續普速旅客列車ldj時，則?ij=1，否則?ij=0。

因此普速旅客列車lai的車底接續普速旅客列車ldj的時刻應滿足

(8)

此時，車底在始發站(終到站)的非生產停留時間tij為

(9)

其中，

(4)車底的匹配度約束。被套用車底與套用列車之間在到發接續時間間隔、車底要求(設計速度、編組結構等)方面應有盡可能高的匹配度。

設wij為普速旅客列車lai的車底接續ldj的時間匹配度，其值越小則接續套跑的可能性越大，反之則越小。則不考慮車底接續延誤概率的接續時間匹配度為

(10)

而考慮車底接續延誤概率的接續時間匹配度為

(11)

設φij為普速旅客列車lai和ldj的車底在設計速度、編組結構等方面的匹配度，其值越小則接續套跑的可能性越大，反之則越小，即

(12)

(13)

(14)

(5)車底日常檢修約束。任一普速旅客列車車底sf在接續套跑的過程中，應滿足檢修的時間間隔、走行公里的約束，二者只要有1個條件滿足，即應安排該車底進行檢修。

(15)

(6)車底運用的唯一性約束。在任一運行周期內，鐵路列車運行圖規定的任一普速旅客列車運行線li有且僅有1個車底來承擔其運行任務，即

(16)

(17)

(8)車底接續時間的控制約束。在提高車底套用方案魯棒性(抗干擾能力)的過程中，不能以無限延長車底接續的非生產停留時間為代價，需將車底接續的非生產停留時間控制在一定的范圍之內，即

(18)

式中：r為魯棒性因子，0≤r≤1；Copt為不考慮車底接續延誤概率時，所有車底接續的非生產停留時間總和的最小值。

3.2　目標函數

為了提高車底套用方案的魯棒性(抗干擾能力)，以車底接續延誤概率最小為目標函數1，即

(19)

為了盡可能達到普速旅客列車車底運用的均衡性，以車底運用效率的標準差最小為目標函數2，即

(20)

其中，

4　算法設計

普速旅客列車車底套用方案魯棒性優化模型的約束條件眾多，且同時存在等式和不等式約束，2個目標函數間還存在很強的相關性，因此，必須采用高效的多目標算法進行求解。粒子群算法(Particle Swarm Optimization algorithm，PSO)是一種隨機搜索、并行的優化算法，可將非劣最優解集Pareto 排序機制和傳統的PSO算法結合，求解多目標優化問題。

傳統的PSO算法中，粒子在搜索過程中按如下公式進行更新[16]

(21)

(22)

但傳統的PSO算法在求解多目標問題時，存在慣性權重θ的取值缺乏依據以及非劣最優解集Pareto的多樣性、分布性較差等問題。為此，本文基于非劣最優解集Pareto排序的多目標粒子群算法(Multi-objective particle swarm optimizer，MOPSO)，對慣性權重θ的取值和非劣解集Pareto更新策略進行如下改進。

1)自適應慣性權重的取值依據

本文根據粒子與種群最優粒子的差距程度，非線性地調整慣性權重的大小，即[17]

(23)

(24)

自適應慣性權重曲線如圖8所示。

圖8　自適應慣性權重曲線

2)基于動態密集距離的非劣解集更新策略

任一粒子與其周圍粒子間的動態密集距離表述為

(25)

為保證 Pareto 解集中解的多樣性和均勻性，從動態密集距離Y(xn)較大的前20%個Pareto解中隨機選出種群全局最優解[18]，用于指導種群的更新。算法流程如圖9所示。

5　實例分析

以旅客列車到發較為密集的北京西、鄭州、西安、蘭州4個鐵路大型客運站為例，隨機選取不同等級的20個車次，并對其信息進行格式化，結果見表1。

非套用模式下，車底在配屬站或折返站停留時間大于10 h的有16個，大于20 h的有3個，最大停留時間為1 417 min，需要22個車底。

取旅客乘降的期望時間為5 min；清掃檢查的期望時間為15 min；進出整備所及在整備所非整備維修的期望時間為20 min；轉股道所需的期望時間為10 min；車底檢修作業時間標準、維修時間間隔、走行公里依據《鐵路客車運用維修規程》取值。

結合文獻[12,14]的研究，以30 min為1個時間段，列車晚點時間在[0,30]，(30,60]，(60,90]，(90,120]，(120,150]各時間段內的概率分別取0.25，0.15，0.10，0.05，0.05，晚點150 min以上的概率取0.05。采用本文提出的模型和優化算法，計算得到的考慮車底接續延誤概率的普速旅客列車車底套用方案見表2。

圖9　算法流程

列車編號車次始發站終到站發時到時11303北京西鄭州　22：459：2621487北京西鄭州　10：1820：393K179北京西鄭州　22：307：064T231北京西西安　21：1510：025T41北京西西安　14：335：026T43北京西西安　19：508：347T75北京西蘭州　14：258：458Z19北京西西安　20：437：589Z55北京西蘭州　16：209：5710Z56蘭州　北京西21：3314：3511K120蘭州　西安　21：407：0212T76蘭州　北京西17：0612：4613K119西安　蘭州　22：266：3914T232西安　北京西17：446：0515T42西安　北京西18：189：0816T44西安　北京西19：008：2917Z20西安　北京西19：557：10181304鄭州　北京西7：1521：38191488鄭州　北京西20：169：1820K180鄭州　北京西22：006：36

由表2可見：考慮車底接續延誤概率的4個套用方案中，每個套用方案均只用5個車底接續循環就覆蓋了所有車次；車底在配屬站和折返站的最小、最大總停留時間分別為8 917和9 293 min，每個套用方案所需的車底數均為19個；與現行非套用模式下的車底運用相比較，考慮車底接續延誤概率的套用方案可節省的最小、最大停留時間分別為3 964和4 340 min，每個套用方案均可節省3個車底。

為了進一步分析本文所建模型的合理性，對考慮車底接續延誤概率和不考慮車底接續延誤概率兩種情況下的套用方案進行對比分析。參照不考慮車底接續延誤概率條件下的套用模型[10]，計算得到不考慮車底接續延誤概率的套用方案見表3。

表2　考慮車底接續延誤概率的套用方案

注：*為列車編號；**為該接續循環內車底在配屬站和折返站的總停留時間， min。

表3　不考慮車底接續延誤概率的套用方案

對比表2和表3可見：考慮車底接續延誤概率和不考慮車底接續延誤概率2種情況下，套用方案所需的車底數均為19個，但不考慮車底接續延誤概率條件下，車底在配屬站和折返站的最小總停時為8 307 min，而考慮車底接續延誤概率條件下的最小總停時為8 917 min。這2種情況下車底總停時最小的套用方案分別如圖10、圖11所示。

圖10不考慮車底接續延誤概率條件下總停時最小的套用方案1′

由圖10可見：在不考慮車底接續延誤概率條件下總停時最小的套用方案1′中，最小車底接續時間僅為42 min(編號19的列車車底接續編號3的列車)，極易產生車底接續延誤，方案的魯棒性較差。

圖11考慮車底接續延誤概率條件下總停時最小的套用方案1

由圖11可見：在考慮車底接續延誤概率條件下總停時最小的套用方案1中，最小車底接續時間為67 min(編號19的列車車底接續編號1的列車)，方案的魯棒性較好。

6　模型討論與分析

(1)在處理列車晚點時間概率時，本文對時間段的劃分及其晚點時間概率的取值相對粗略。在實際鐵路運輸組織中，可根據不同時期列車晚點的差異性，采取更合理的動態劃分方法及其取值標準。

(2)鐵路客運樞紐是旅客列車密集始發、終到的場所，也是解決普速旅客列車車底套用的關鍵環節。對于有多個客運站的鐵路客運樞紐，可采取以下策略進一步提高套用效率。

①可通過調整旅客列車在客運樞紐內的始發站、終到站，進一步提高普速旅客列車車底套用的效率。但該策略需調整列車運行圖，應在調圖前予以研究。

②可將有多個客運站的鐵路大型客運樞紐看作為1個點(1個客運站)，終到該樞紐內所有客運站的車底可統一重新分配利用。該策略無需調整列車運行圖，但需將部分車底進行樞紐內站間調整。此時，本文所建模型中的zai(zdj)可能是某客運站，也可能是有多個客運站的客運樞紐?？瓦\樞紐內站間車底調整如圖12所示。

7　結　語

普速旅客列車車底運用方式的優化對提高鐵路客運生產效益和效率具有重要的意義。本文在不改變車底配屬制的前提下，提出1個車底可套跑多個區段的普速旅客列車車底運用模式；分析了車底接續時間與車底接續延誤概率間的關系，提出了考慮車底接續延誤概率的普速旅客列車車底套用方案魯棒優化模型及其優化算法。通過實例，對非套用模式、不考慮車底接續延誤概率的套用模式和考慮車底接續延誤概率的套用模式3種情況下的普速旅客列車車底套用方案進行了比較分析。研究結果表明：考慮車底接續延誤概率的普速旅客列車車底套用方案魯棒優化模型，不但可提高車底的運用效率，也具有一定的魯棒性。但為了進一步挖掘普速旅客列車車底運用的潛能，應研究編圖前的普速旅客列車車底經濟合理運用問題，以及套用條件下的乘務組合理調配問題，以期為鐵路普速旅客列車車底運用優化提供決策依據，這將是后續研究的重點問題。

圖12　客運樞紐內站間車底調整

[1]聶磊，趙鵬，楊浩，等.高速鐵路動車組運用的研究[J].鐵道學報，2001，23(3)：1-7.

(NIE Lei，ZHAO Peng，YANG Hao，et al. Study on Motor Trainset Operation in High Speed Railway[J]. Journal of the China Railway Society，2001，23(3)：1-7.in Chinese)

[2]趙鵬，富井規雄. 基于概率局域搜索的動車組平日運用計劃編制算法[J].系統工程理論與實踐，2004(2)：123-129，144.

(ZHAO Peng，NORIO Tomii. An Algorithm for Train-Set Scheduling on Weekday Based on Probabilistic Local Search[J]. Systems Engineering—Theory & Practice，2004(2)：123-129，144. in Chinese)

[3]史峰，周文梁，郁宇衛，等.客運專線動車組運用計劃優化模型與算法[J].鐵道學報，2011，33(1)：1-13.

(SHI Feng，ZHOU Wenliang，YU Yuwei，et al.Optimized Model and Algorithm of Motor Train-Sets Scheduling for Dedicated Passenger Lines[J]. Journal of the China Railway Society，2011，33(1)：1-13. in Chinese)

[4]張才春，花偉，陳建華. 雙修制下的動車組運用計劃編制研究[J].鐵道學報，2010，32(3)：16-19.

(ZHANG Caichun，HUA Wei，CHEN Jianhua. Research on EMU Scheduling under Constraint of Kilometrage and Time for Scheduled Inspection and Maintenance[J]. Journal of the China Railway Society，2010，32(3)：16-19. in Chinese)

[5]CORDEAU J F，SOUMIS F，DESROSIERS J. Simultaneous Assignment of Locomotives and Cars to Passenger Trains[J].Operations Research, 2001，49 (4)：531-548.

[6]劉鋼，孫晚華，韓學雷.旅客列車車底運用優化模型及算法[J].鐵道運輸與經濟，2004，26(2)：62-64.

(LIU Gang，SUN Wanhua，HAN Xuelei. An Optimized Model and Algorithm for the Utilization of Passenger Carriage [J].Railway Transport and Economy，2004，26(2)：62-64. in Chinese)

[7]謝金貴，曾亮，徐昕愷.鐵路旅客列車車底套用優化模型的研究[J].鐵道運輸與經濟，2006，28(12)：75-77.

(XIE Jingui，ZENG Liang，XU Xinkai. Study on Optimization Model of Railway Passenger Train Set Assignment [J]. Railway Transport and Economy，2006，28(12)：75-77. in Chinese)

[8]肖益帆，朱昌鋒.基于模擬退火算法的鐵路旅客列車車底套用優化研究[J]. 鐵道科學與工程學報，2012，9(5)：108-113.

(XIAO Yifan，ZHU Changfeng.Railway Train Set Assignment Based on Simulated Annealing Algorithm[J].Journal of Railway Science and Engineering，2012，9(5)：108-113. in Chinese)

[9]BING Zeyi， LI Wentian， ZHU Changfeng，et al. Research on Assignment Optimization of Railway Train Stock Based on Simulated Annealing Algorithm [J]. Journal of Information and Computational Science，2014，11(14)：4911-4919.

[10]朱昌鋒，李引珍.基于既定列車運行圖的鐵路旅客列車車底套用協同優化研究[J]. 中國鐵道科學，2014，35(3)：120-128.

(ZHU Changfeng，LI Yinzhen. Collaborative Optimization on Assignment of Passenger Train Stock Based on Given Train Diagram [J]. China Railway Science，2014，35(3)：120-128.in Chinese)

[11]朱昌鋒. 鐵路大型客運站到發線分配耦合優化及時域調整研究[D].蘭州：蘭州交通大學，2014.

(ZHU Changfeng. Research on Coupling Optimization of Arrival and Departure Track Scheduling for Railway Large-Scale Passenger Station and Its Receding Horizon Adjustment[D].Lanzhou：Lanzhou Jiaotong University，2014.in Chinese)

[12]宗俊雅，李宗平. 列車運行圖緩沖時間合理取值究[J]. 交通運輸工程與信息學報，2010，8(3)：56-61.

(ZONG Junya，LI Zongping. Study on Reasonable Value of the Buffer Time in Train Diagram [J]. Journal of Transportation Engineering and Information，2010，8(3)：56-61.in Chinese)

[13]胡思繼，孫全欣，胡錦云，等. 區段內列車晚點傳播理論的研究[J]. 中國鐵道科學，1994，15(2)：41-53.

(HU Siji，SUN Quanxin，HU Jinyun，et al. Research on Theories of Train Delay Propagation in a Railway District [J]. China Railway Science，1994，15(2)：41-53. in Chinese)

[14]孫焰，劉胤宏，李致中，等.列車運行圖的晚點概率分析[J].長沙鐵道學院學報，1998，16(4)：83-89.

(SUN Yan，LIU Yinhong，LI Zhizhong，et al.The Analysis of Delaying Time Probability for the Travelling Graph of Trains[J]. Journal of Changsha Railway University，1998，16(4)：83-89. in Chinese)

[15]彭其淵，朱松年，閻海峰. 列車運行圖可調整度評價系統研究[J].西南交通大學學報，1998，33(4)：367-371.

(PENG Qiyuan，ZHU Songnian，YAN Haifeng.A System for Evaluation of Train Diagram Elasticity [J].Journal of Southwest Jiaotong University，1998，33(4)：367-371.in Chinese)

[16]賈兆紅，陳華平，唐俊，等. 面向多目標的自適應動態概率粒子群優化算法[J]. 系統仿真學報，2008，20(18)：4959-4963.

(JIA Zhaohong，CHEN Huaping，TANG Jun，et al. Self-Adaptive Dynamic Probabilistic Particle Swarm Optimization Algorithm for Multiple Objectives[J].Journal of System Simulation，2008，20(18)：4959-4963.in Chinese)

[17]HO S L，YANG Shiyou，NI Guangzheng，et al. A Particle Swarm Optimization-Based Method for Multi-Objective Design Optimizations[J]. IEEE Transactions on Magnetics, 2005, 41(5): 1756-1759.

[18]吳小剛，劉宗歧，田立亭，等. 基于改進多目標粒子群算法的配電網儲能選址定容[J]. 電網技術, 2014, 38(12): 3405-3411.

(WU Xiaogang，LIU Zongqi，TIAN Liting，et al. Energy Storage Device Locating and Sizing for Distribution Network Based on Improved Multi-Objective Particle Swarm Optimizer[J]. Power System Technology, 2014, 38(12): 3405-3411. in Chinese)