高速鐵路網絡能力計算研究

張嘉敏，張嘉銳

（1.山東科技大學 交通學院，青島 266590；2.濟南鐵路局 青島機務段，青島 266041）

高速鐵路網絡能力計算研究

張嘉敏1，張嘉銳2

（1.山東科技大學 交通學院，青島 266590；2.濟南鐵路局 青島機務段，青島 266041）

充分考慮高速鐵路網絡作為多級遞階控制系統的復雜性和對旅客運輸服務質量的要求，構建基于時段特定場景的高速鐵路列車服務與需求意向集合（t@n-tsdis，train service-demand intention set at network），定義以完成這個集合所需基礎設施占用時間為網絡能力的衡量標準。提出了兩階段的優化計算方法，并提出多目標優化改進的Pareto（1+1）— PAES算法流程，采用交互式滾動優化策略處理整數約束條件、模糊邏輯罰函數法處理連續實數約束條件、Pareto存檔進化策略求解多目標優化問題。以某高速鐵路網絡為例進行能力計算，驗證了模型與算法的有效性。

高速鐵路；網絡能力；列車徑路規劃；多目標優化；Pareto存檔進化策略

鐵路能力具有動態性特征，其大小與運輸需求、使用方式有關。從運輸組織管理體制上看，鐵路網運輸系統是一個多級遞階控制的大系統。UIC406能力手冊將列車數、平均速度、穩定性及異質性定義為能力使用的核心元素，將能力消耗參數定義為關于能力使用的平衡；文獻[1]提出了能力的金字塔式平衡關系圖。鐵路能力影響因素眾多，大多體現在時間維度。文獻[2]構建基于時段特定場景的列車服務與需求意向集合（t@n-tsdis，train service-demand intention set at network），定義以完成列車服務與需求意向集合所需的基礎設施占用時間作為衡量高速鐵路能力的新標準，分析了網絡化條件下軌道交通系統的能力。

鐵路能力計算的方法可歸結為分析方法、優化方法、仿真方法等，基于高速鐵路網絡作為一個多級遞階控制系統的復雜性及其對運輸服務質量的要求，結合能力的動態性和不確定性特征，本文將高速鐵路網絡的能力定義為在最小化異質性、最大化可靠性的同時，最小化完成列車在高速鐵路網絡的列車服務與需求意向集合（t@n-tsdis）所需基礎設施占用時間，即運行時間，分兩個階段計算高速鐵路的網絡能力：（1）列車徑路規劃，將高速鐵路物理網的能力轉化為由運行徑路構成的有向服務網的能力；（2）多目標優化，計算綜合平衡條件下考慮一定服務質量的網絡能力，從而在服務可靠度與最大物理能力之間找到經濟優化的能力平衡點。

1 列車徑路規劃

在列車徑路規劃階段，對于給定的高速鐵路網絡，確定必開起訖點OD，應用圖論求解必開起訖點OD對間的最短路徑，再進行徑路微調，使網絡圖中的每個節點至少被一條徑路覆蓋。列車徑路規劃算法為：

（1）根據經濟總量、人口規模、地理位置、政治地位等因素劃分車站節點等級，確定必開起訖點OD，必開起訖點間應至少開行一次相應等級的旅客列車。

（2）運用圖論Dijkstra算法求解高速鐵路網絡圖中必開起訖點間的最短路徑，作為基本列車運行徑路集。

（3）以每個節點至少被一條列車徑路覆蓋為準則，判別基本列車運行徑路集是否覆蓋所有車站節點，如果是，轉（5），否則轉（4）。

（4）對基本運行徑路進行K短路調整，構建擴展運行徑路。定義列車運行徑路的模為其徑路里程長度，根據模從小到大對列車基本運行徑路排序，排序設為{a,b,c,...}。

選取模最小的基本運行徑路a，對其進行K短路調整，構建擴展運行徑路，判別當前列車運行徑路集能否覆蓋所有車站節點，如果能，轉（5），否則，對基本運行徑路b進行K短路調整，再判別當前列車運行徑路集能否覆蓋所有車站節點，如此依序循環往復調整，直至當前列車運行徑路能覆蓋所有車站節點。

（5）列車徑路規劃完畢。

2 多目標優化模型

令S為高速鐵路網絡車站的集合，Q為區間集，q代表區間，s為在列車運行方向進入區間q的車站，s∈S。tj為列車j的運行徑路，T代表列車運行徑路集合，tj∈T。ejq為列車j進入區間q的時刻，ljq為列車j離開區間q的時刻，rjq為列車j在區間q的運行時間， hjq為在區間列車j與j-1的最小間隔時間，為列車j與j-1到達車站s的間隔時間 。

aijq為進入區間q的列車i與j的最小間隔時間。xijq為0-1變量：

高速鐵路列車的服務質量可從異質性、可靠性及運行時間幾方面考量。文獻［3］提出用最小間隔時間倒數的和表示不同種類列車區間組合的異質性，用到達間隔時間倒數的和表示不同類型列車組合在車站的異質性；異質性會增加列車運行過程中延誤傳播的可能性，降低運行圖的穩定性。鐵路網系統運輸能力可靠性與鐵路網系統有效使用能力直接相關，可以通過列車間隔時間的合理設置提高運行的可靠性。文獻 [4]提出并證明了在混合交通流條件下列車運行時間的定理。根據高速鐵路網絡能力的定義，考慮一定服務質量的綜合平衡條件下，高速鐵路網絡能力計算的多目標優化模型為：

模型中，式（1）～式（3）為目標函數，其中，式（1）為最小化異質性，式（2）為最大化可靠性，式（3）為最小化運行時間。式（4）～式（11）為約束條件，其中，式（4）表示列車離開區間的時刻與其進入區間的時刻之差不小于其在區間運行時間；式（5）表示列車進入區間的時刻與其離開前一個區間的時刻不小于其在車站的作業時間；式（6）表示兩個相鄰的列車進入同一個區間的時間之差不小于列車控制系統所規定的最小安全間隔時間；式（7）表示除第一列列車外，每列列車有且只有唯一一個直接前驅；式（8）表示除最后一列列車外，每一列列車有且只有唯一一個直接后繼；式（9）表示列車在區間的最小間隔時間不小于列車控制系統所規定的最小安全間隔時間；式（10）表示列車在車站的到達間隔時間不小于列車控制系統所規定的最小安全間隔時間；式（11）表示兩個相鄰的列車離開同一個區間的時間之差不小于列車控制系統所規定的最小安全間隔時間。

3 模型求解算法

3.1 模型預處理

3.1.1 目標函數標準化

對模型的目標函數標準化（最小化）處理：

則標準化后的目標向量為：

3.1.2 整數0—1約束部分的處理

根據文獻[5]對運行圖結構的分析，將車站視為緩沖庫存，將區間視為加工設備，以階段均衡模式為基礎，采用just-in-case策略，對整數0-1規劃約束采取交互式滾動優化處理方法，如圖1所示。

圖1 以車站—區間為單元的 just-in-case交互式滾動優化

3.1.3 連續實數約束條件的處理

對實數型約束條件依據gi(v)≥0（i=1,…,6）形式標準化處理，應用模糊邏輯罰函數法處理轉化后的實數約束條件。令tvi表示解v對于約束i的沖突程度，且有：

令Zi表示第i個不可行域的容忍閾值（置各區域的容忍閾值Zi分別為0.001， 0.01， 0.02， 0.5， 1.0，5.0， 10.0， 15.0， 25.0， 35)，yv為解v的模糊罰函數（代表在非可行域中解違反約束的程度），將整個搜索空間劃分為10個區域。

Zone 1 為可行域，懲罰項yv=0，此時有：

max(tv1,…,tvL)≤Zi；

Zone i，i=2～9， 為懲罰空間，懲罰項yv=i，此時有：

Zi–1＜max(tv1,…,tvL)≤Zi；

Zone 10為拒絕空間，懲罰項yv=100，此時有：

Z10＜max(tv1,…,tvL)。

對于任意解v，根據模糊罰函數法，轉化的目標函數分別為：

F1=H'+yv

F2=P'+yv

F3=R'+yv

至此，應用模糊—邏輯罰函數將帶約束的多目標規劃問題轉換為無約束的多目標優化問題：

min{F1,F2,F3}

3.2 Pareto存檔進化策略與交互法求解多目標優化問題

以車站—區間為單元滾動優化，在每一單元采用改進的Pareto（1+1）—PAES［6］存檔進化策略與交互法，求解轉換后的無約束多目標優化問題，基本流程如圖2所示。

圖2 多目標優化改進的Pareto（1+1）—PAES算法流程

將t@n-tsdis中的列車視為列車群，采用justin-case策略生成初始解。在改進的Pareto（1+1）—PAES存檔策略中維持當前的Pareto最優解，在每一次迭代中依據各約束條件違反情況與當前目標值優化程度進行對當前解的取舍，并從更新后存檔列表中選擇一個產生變異解。PAES評估函數基于支配關系進行個體評價，改進的Pareto（1+1）—PAES亦采取基于優勝關系的適應度賦值（即統計群體中優于個體的數目，設某個體i被群體占優的個數為di，取di的倒數作為個體i的適應度），改進的Pareto（1+1）—PAES存檔更新與當前解接受邏輯如圖3所示。

圖3 改進的(1+1)-PAES存檔列表更新策略與當前解接受邏輯

4 算例應用

某小型高速鐵路網絡如圖4所示。圖4中，數字代表相鄰站間距離，字母代表車站節點，其中 ，A、B、C、D為必開起訖點，B、C為一級節點，A、D、F、G為二級節點，E、H為三級節點。

圖4 某高速鐵路網絡圖

根據列車徑路規劃算法流程，列車徑路規劃如表1所示。

表1 列車徑路規劃

構造某高峰時段高速鐵路網絡的t@n-tsdis任務列表如表2所示。

表2 某高峰時段高速鐵路網絡 t@n-tsdis任務列表

根據提出的模型求解算法，運用.net平臺環境下的C#語言編程，對高速鐵路網絡能力計算模型優化求解的結果如表3 所示。根據模型優化結果，完成高速鐵路列車在網絡的服務—需求意向集合（t@ n-tsdis）需占用基礎設施的總時間為569.96 min ，實現這個目標的異質性全網合計為2.039 180 505，全網平均為0.254 897 563，可靠性全網合計為0.872 543 069，全網平均為0.096 949 23。在所有車站—區間單元中，異質性最高值為0.419 718 593 140 599，出現在G—D單元，其對應的可靠性為0.015 151 515 151 515 2，G—D單元是整個網絡系統的能力薄弱部分，在實際運營中需要加強對G—D單元的列車運行組織，以實現網絡系統的能力加強。

表3 高速鐵路網絡能力計算優化目標結果

5 結束語

高速鐵路的運輸組織模式從傳統的以運能管理為中心轉變為以旅客服務為中心，基于高速鐵路網絡作為多級遞階控制系統的復雜性和對旅客運輸服務質量的要求，本文定義了高速鐵路網絡能力的衡量標準，以完成高速鐵路列車在網絡的列車服務與需求意向集合（t@n-tsdis）所需要占用的基礎設施時間為網絡能力的衡量標準，提出高速鐵路網絡能力計算的兩階段方法，以某高速鐵路網絡為例進行了算例應用。能力計算的一個主要意義在于指導實際列車運營服務，本文提出的高速鐵路網絡能力兩階段計算方法，可以在路徑規劃的基礎上，通過多目標優化，計算得到考慮一定服務質量的綜合平衡條件下的路網能力，能夠更充分地把握鐵路能力的動態性特征，更接近高速鐵路網絡列車運行組織的實際。

[1]Landex,A.Methods to estimate railway capacity and passenger delay[D].Denmark:Technical University of Denmark,2008.

[2]張嘉敏.高速鐵路能力計算與評估之理論與方法研究[D].北京：北京交通大學，2012.

[3]Michiel J.C.M.Vromans.Reliability and heterogeneity of railway services[J].European Journal of Operational Research,2006:647–665.

[4]Tijs Huisman,Richard J.Boucherie.Running times on railway sections with heterogeneous train traffic[J].Transportation Research Part B ,2001 (35):271-292.

[5]Jiamin Zhang,Jun Liu.Analysis on Comprehensive Balance of Train Operation Plan for High Speed Railway under Mixed Traffic Condition[C].International Conference on Intelligent Rail Transportation，2011:397 – 401.

[6]Joshua D.Knowles,David W.Corne.Approximating the Nondominated Front Using the Pareto Archived Evolution Strategy[J].Evolutionary Computation， 1999，7(1):1-24.

責任編輯 王 浩

Calculation of network capacity for high-speed railway

ZHANG Jiamin1,ZHANG Jiarui2
( 1.College of Transportation,Shandong University of Science and Technology, Qingdao 266590,China;2.Qingdao Locomotive Depot,Jinan Railway Administration,Qingdao 266041,China)

Taking full account of the high speed railway network as the complexity of the multilevel hierarchical control system and requirements for the quality of passenger transport service,this article set up the high-speed train service-demand intention set at railway network according to the specifc scenario of the period ( train service-demand intention set at network,abbreviated as t@n-tsdis),and then took the occupation time of the infrastructures needed to fulfll the set as the criteria to measure the network capacity,proposed the two stage optimization calculation method.On solving the model,the article proposed improved (1+1)-PAES Algorithm fow for multi-objective optimization,and took the interactive-rolling strategy to tackle the integer constraints,the fuzzy-logic penalty function to tackle the real constraints,and the Pareto archived evolution strategy to solving multi-objective optimization problems.The model and the Algorithm were applied to a high speed railway network for case study,the validity of the model and the Algorithm was verifed.

high-speed railway;network capacity;train path planning;multi-objective optimization;Pareto archived evolution strategy

U238：U293：TP39

A

1005-8451（2016）08-0016-05

2016-02-17

山東科技大學人才引進科研啟動基金項目（2014RCJJ025）。

張嘉敏，講師；張嘉銳，工程師。