高速鐵路網(wǎng)絡(luò)能力計算研究

張嘉敏，張嘉銳

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

高速鐵路網(wǎng)絡(luò)能力計算研究

張嘉敏1，張嘉銳2

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

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

高速鐵路；網(wǎng)絡(luò)能力；列車徑路規(guī)劃；多目標優(yōu)化；Pareto存檔進化策略

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

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

1 列車徑路規(guī)劃

在列車徑路規(guī)劃階段，對于給定的高速鐵路網(wǎng)絡(luò)，確定必開起訖點OD，應(yīng)用圖論求解必開起訖點OD對間的最短路徑，再進行徑路微調(diào)，使網(wǎng)絡(luò)圖中的每個節(jié)點至少被一條徑路覆蓋。列車徑路規(guī)劃算法為：

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

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

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

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

選取模最小的基本運行徑路a，對其進行K短路調(diào)整，構(gòu)建擴展運行徑路，判別當(dāng)前列車運行徑路集能否覆蓋所有車站節(jié)點，如果能，轉(zhuǎn)（5），否則，對基本運行徑路b進行K短路調(diào)整，再判別當(dāng)前列車運行徑路集能否覆蓋所有車站節(jié)點，如此依序循環(huán)往復(fù)調(diào)整，直至當(dāng)前列車運行徑路能覆蓋所有車站節(jié)點。

（5）列車徑路規(guī)劃完畢。

2 多目標優(yōu)化模型

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

aijq為進入?yún)^(qū)間q的列車i與j的最小間隔時間。xijq為0-1變量：

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

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

3 模型求解算法

3.1 模型預(yù)處理

3.1.1 目標函數(shù)標準化

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

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

3.1.2 整數(shù)0—1約束部分的處理

根據(jù)文獻[5]對運行圖結(jié)構(gòu)的分析，將車站視為緩沖庫存，將區(qū)間視為加工設(shè)備，以階段均衡模式為基礎(chǔ)，采用just-in-case策略，對整數(shù)0-1規(guī)劃約束采取交互式滾動優(yōu)化處理方法，如圖1所示。

圖1 以車站—區(qū)間為單元的 just-in-case交互式滾動優(yōu)化

3.1.3 連續(xù)實數(shù)約束條件的處理

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

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

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，根據(jù)模糊罰函數(shù)法，轉(zhuǎn)化的目標函數(shù)分別為：

F1=H'+yv

F2=P'+yv

F3=R'+yv

至此，應(yīng)用模糊—邏輯罰函數(shù)將帶約束的多目標規(guī)劃問題轉(zhuǎn)換為無約束的多目標優(yōu)化問題：

min{F1,F2,F3}

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

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

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

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

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

4 算例應(yīng)用

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

圖4 某高速鐵路網(wǎng)絡(luò)圖

根據(jù)列車徑路規(guī)劃算法流程，列車徑路規(guī)劃如表1所示。

表1 列車徑路規(guī)劃

構(gòu)造某高峰時段高速鐵路網(wǎng)絡(luò)的t@n-tsdis任務(wù)列表如表2所示。

表2 某高峰時段高速鐵路網(wǎng)絡(luò) t@n-tsdis任務(wù)列表

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

表3 高速鐵路網(wǎng)絡(luò)能力計算優(yōu)化目標結(jié)果

5 結(jié)束語

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

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

[2]張嘉敏.高速鐵路能力計算與評估之理論與方法研究[D].北京：北京交通大學(xué)，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.

責(zé)任編輯 王 浩

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

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

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