基于客流均衡分析的城際鐵路列車運行圖優化

周文梁，張先波，屈林影，李鵬

?

基于客流均衡分析的城際鐵路列車運行圖優化

周文梁，張先波，屈林影，李鵬

(中南大學 交通運輸工程學院，湖南 長沙 410075)

將城際客流均衡分配與列車運行圖優化相結合，構建城際列車運行圖優化的雙層規劃模型，其中，上層模型以滿足行車組織要求、運營時間等為約束，以降低旅客乘車時間、換乘等待時間以及提高始發、終到時間滿意度為目標優化列車運行圖；而下層模型為基于列車運行圖的客流均衡分配模型。模型采用模擬退火算法與GP算法組合求解，在生成初始列車運行圖的基礎上不斷通過均衡分配乘車客流、構造鄰域解迭代優化。算例分析表明模型與算法具有較好的收斂性與有效性。

城際鐵路；列車運行圖；客流均衡分配；模擬退火算法；GP算法

近年來城際鐵路在我國多個城市群內得到了快速發展。作為旅客乘車選擇依據的城際列車運行圖，其編制質量決定了城際列車服務水平與運行效率，其優化對提高城際鐵路在城市群區域客運市場競爭力具有重要意義。目前，較多研究基于列車運行組織與旅客乘車選擇之間的主從博弈關系，借助于交通流理論均衡分配乘車客流，由此為依據優化組織列車運行。史峰等[1]將列車開行方案與旅客乘車選擇結合起來，構建了旅客列車開行方案優化的雙層規劃模型與算法；彭其淵等[2]基于隨機穩定性客流分配方法構建了旅客列車開行方案的多目標隨機期望值規劃方法；史峰等[3]結合彈性需求條件下的旅客乘車選擇均衡分配，建立了基于彈性需求的旅客列車開行方案的雙層規劃方法。但以上研究僅是將乘車客流均衡分配結合到列車開行方案優化過程中，由于缺乏列車運行時刻信息，難以準確描述旅客乘車選擇行為。列車運行圖優化至今已取得了較多的研究成果。ZHOU等[4?5]以最小化列車旅行時間為優化目標，采用分枝定界法、定序優化方法等優化旅客列車運行圖；Ghoseiri等[6]在最小化列車旅行時間外，還兼顧機車能源消耗、運行圖均衡性等目標；汪波等[7?8]借助網絡約束圖及周期勢差模型優化周期性列車運行圖。黃鑒等[9]以時段需求為差別，提出基于分步循環的模擬退火算法實現運行圖全局優化。但目前并沒有考慮列車運行圖編制與旅客乘車選擇之間的相互影響，由于缺乏列車乘車客流與列車間換乘客流信息，優化過程中難以針對性地安排列車運行時刻。本文將城際列車運行圖優化與旅客乘車選擇結合起來，在列車運行圖優化過程中通過均衡分配乘車客流而獲得各列車乘車客流與換乘客流等信息，以此為依據對列車運行圖進行迭代優化。

1 多目標雙層規劃模型

最小化列車旅行時間是列車運行圖優化普遍采用的優化目標。然而，這僅能達到降低旅客乘車時間的目的。實際上，部分旅客出行還需花費一定的換乘時間，且隨著旅客出行服務要求的提高，對始發、終到時間也有一定的要求。因此本文考慮以下優化目標。

1.1 壓縮乘車時間

當時段OD對á,?旅客選擇路徑出行時，乘坐列車?的上車站為、下車站為′，則其乘車時間為：

1.2 減少換乘等待時間

當時段OD對á,?旅客選擇路徑出行時，由列車換乘至列車所在的換乘站為，則其換乘等待時間為：

其中：h為旅客在換乘站換乘所需要的必備時間。

1.3 提高始發、終到時間滿意度

本文結合用戶均衡分配模擬旅客基于給定列車運行圖的乘車選擇行為，構建以下列車運行圖優化的雙層規劃模型。

(9)

其中：和為擁擠費用參數。

以上雙層規劃模型中，式(5)表示列車區間運行時間約束；式(6)表示列車停站時間約束；式(7)與式(8)分別表示列車滿足最小到、發達作業間隔要求；式(9)表示列車運行時刻滿足城際鐵路運營時間 約束。

2 給定乘車客流列車運行時刻計算方法

每列列車運行時刻的安排既要使得乘坐該列車旅客具有較高服務水平，同時又不影響已安排列車服務水平。對于列車，其乘車客流可分為以下 4類：

2.1 列車i為出行首列與末列列車

計算此類乘客的出行效益(即始發、終到時間滿意度)如下：

2.2 列車i為出行首列而非末列列車

若該類乘客由列車換出后所乘坐的后續列車運行時刻均未計算，則假設乘客能夠以零等待時間換乘至目的地，按式(16)計算始發時間，并按如下方法計算其終到時間：

至此便可計算此類乘客的出行效益為：

2.3 列車i為出行末列而非首列列車

若此類乘車客流換入列車前所乘坐列車的運行時刻均未計算，則同樣假設乘客能夠以零等待時間從始發站換乘至列車，按式(17)計算其終到時間，并按如下方法計算其始發時間：

至此便可計算此類乘車客流出行效益為：

2.4 列車i既非出行首列也非末列列車

列車備選始發時段集的計算方法如下所示：

若路徑乘客屬于1和2類旅客，則

否則，

在按以上方法確定列車始發時段集F后，按旅客出行效益由大到小選擇列車始發時段，若列車以當前選擇時段的中間時刻發車可完成整列列車運行時刻推算，則輸出該列車運行時刻；否則，繼續選擇下一個始發時段，重新計算列車運行時刻。

3 列車運行圖優化算法

列車運行圖優化屬于NP-難問題。鑒于求解的復雜性，最優化算法難以在可接受時間范圍內完成優化，為此本文設計模擬退火算法進行求解，同時將乘客客流均衡分配的GP算法嵌套其中。

3.1 初始列車運行圖的生成

根據假定的理想出行條件的乘車客流均衡分配結果生成，具體如下：

1)旅客僅在給定的備選列車集中選擇列車；

2) 旅客在任意換乘站以零等待時間完成換乘；

3)旅客乘坐任意列車均可獲得最大的始發、終到時間滿意度值；

4)任意列車在車站的停站時間均為所規定的最小值。

根據各列車載客量q由大到小順序逐列計算列車運行時刻。

3.2 鄰域結構設計

鄰域結構決定了算法從當前列車運行圖如何獲得一個新的列車運行圖，進而根據Metropolis準則判斷新列車運行圖是否被接受。具體按以下步驟產生新的鄰域解。

其次，分別以f(),d(),c()和h()為概率選擇f，d，c和h列列車對其運行時刻進行重新計算，計算方法如下：

3.3 模擬退火計劃表設計

模擬退火計劃表控制了算法運行過程所需要的相關參數值，設計參數參考文獻[3]。

至此，構建列車運行圖優化算法如表1所示。

表1 城際網絡列車運行圖優化算法

4 算例分析

圖1 算例城際網絡

表2 列車運行徑路

考慮路網上4個O-D對旅客出行，如表3所示。

表3 各OD對旅客出行需求量與出行路徑

(a) α=0.80；β=1.20；(b) α=0.80；β=2.00；(c) α=1.20；β=1.20；(d) α=1.20；β=2.00

4.1 算法收斂性分析

為了分析算法的收斂效果與優化效率，取4組(,)值，如表4所示，其它參數取值保持不變，目標函數關于計算時間的變化如圖2所示。由圖2可知：隨著算法不斷迭代優化，所花費的計算時間不斷增加，但同時目標函數值亦逐漸降低直至算法收斂。各情形下算法達到收斂時計算時間均大約為14 min，但實際上在運行10 min左右便已達到收斂解。由此表明該算法具有較好的收斂性，但相比而言，該算法收斂計算時間相對較長，其收斂速度有待改進，原因為乘車客流均衡分配消耗過多計算時間，尤其本算例將客流均衡分配算法收斂終止條件設置的較苛刻。

4.2 算法有效性分析

4組參數取值條件下旅客出行服務指標值如表4所示。旅客人均出行時間滿意度均約為88，達到最大出行時間滿意度的88%；人均乘車速度約為183 km/h，為列車最高運行速度200 km/h的91.50%；而人均單次換乘等待時間約為1.40 min。由此可見，由本文算法優化得到的列車運行圖能夠較好地滿足旅客出行時間、乘車時間與換乘3方面的要求。

表4 4組參數取值條件下旅客出行服務指標值

各出行時間滿意度值對應的旅客量占總客流量的百分比如圖3(a)所示，各換乘等待時間值對應的旅客量占總換乘客流量的百分比如圖3(b)所示。由圖3可知，出行時間滿意度為最高值100的旅客百分比達到60%以上，而以零等待時間換乘的旅客數量占換乘總人數的百分比達到65%左右，隨著換乘等待時間的增加，相應的換乘旅客數量越小，旅客所花費的最大換乘等待時間為5 min。由此表明大部分旅客均能選擇其最滿意的出行時間出行，而且O-D 3換乘旅客所花費的換乘等待時間都較少。

(a) 出行時間滿意度；(b) 換乘時間

此外，由表4可知，和取值的變化對3組服務指標值并無較大影響；但由圖2可知，不同和取值下目標函數的收斂值并不相同，隨著和取值的增大，目標函數值收斂值也隨之增加。經分析其主要原因為構成目標函數的3部分內容之間并不互相對立，其中任意一部分的改善，并不會制約另外兩部分的改善，三者可以同時進行改善，但顯然其權重值和增加將導致整個目標函數值增加。

5 結論

1) 結合不同出行目的城際客流乘車均衡分配，構建了城際列車運行圖優化的雙層規劃模型，其優化目標由降低旅客乘車時間、換乘等待時間以及提高旅客始發、終到時間滿意度3部分構成。

2) 設計模擬退火算法與GP算法來求解模型。

3) 通過算例分析表明本文該算法具有較好的收斂性與優化效果，但由于客流分配計算量較大導致算法收斂速度較低而有待改進。考慮城際鐵路客流需求量與其列車服務水平的彈性變化關系來優化城際列車運行圖將更符合實際。

[1] 史峰, 鄧連波, 霍亮. 旅客列車開行方案的雙層規劃模型和算法[J]. 中國鐵道科學, 2007, 28(3): 110?116. SHI Feng, DENG Lianbo, HUO Liang. Bi-level programming model and algorithm of passenger train operation plan[J]. China Railway Science, 2007, 28(3): 110?116.

[2] 彭其淵, 賈曉秋, 關曉宇. 隨機穩定性配流規劃的客運專線列車開行方案模型[J]. 西南交通大學學報, 2011, 46(1): 143?147. PENG Qiyuan, JIA Xiaoqiu, GUAN Xiaoyu. Train line planning model with stochastic stability in passenger flow assignment scheme for passenger-dedicated line[J]. Journal of Southwest Jiaotong University, 2011, 46(1): 143?147.

[3] 史峰, 周文梁, 陳彥, 等. 基于彈性需求的旅客列車開行方案優化研究[J]. 鐵道學報, 2008, 30(3): 1?6. SHI Feng, ZHOU Wenliang, CHEN Yan, et al. Optimization study on passenger train plans with elastic demands[J]. Journal of the China Railway Society, 2008, 30(3): 1?6.

[4] ZHOU Xuesong, ZHONG Ming. Single-track train timetabling with guaranteed optimality: Branch-and- bound algorithms with enhanced lower bounds[J]. Transportation Research Part B, 2007, 41(3): 320?341.

[5] LI Feng, GAO Ziyou, LI Keping, et al. Efficient scheduling of railway traffic based on global information of train[J]. Transportation Research Part B, 2008, 42(10): 1008?1030.

[6] Ghoseiri K, Szidarovszky F, Asgharpour M J. A multi-objective train scheduling model and solution[J]. Transportation Research Part B, 2004, 38(10): 927?952.

[7] 汪波, 韓寶明. 城市軌道交通網絡周期運行圖編制研究[J]. 鐵道學報, 2013, 35(4): 9?15. WANG Bo, HAN Baoming. Study on formulation of periodic train diagram of urban rail transit network[J]. Journal of the China Railway Society, 2013, 35(4): 9?15.

[8] 謝美全, 聶磊. 周期性列車運行圖編制模型研究[J]. 鐵道學報, 2009, 31(4): 7?13．XIE Meiquan, NIE Lei. Model of cyclic train timetable[J]. Journal of the China Railway Society, 2009, 31(4): 7?13．

[9] 黃鑒, 彭其淵. 基于分時客運需求的客運專線列車運行圖優化[J]. 鐵道科學與工程學報, 2012, 9(6): 66?71. HUANG Jian, PENG Qiyuan. Train diagram optimization of passenger dedicated line based on passenger transport demand in different time[J]. Journal of Railway Science and Engineering, 2012, 9(6): 66?71.

[10] 周文梁, 史峰, 陳彥, 等. 客運專線網絡列車開行方案與運行圖綜合優化方法[J]. 鐵道學報, 2011, 3(2): 1?7. ZHOU Wenliang, SHI Feng, CHEN Yan, et al. Method of integrated optimization of train operation plan and diagram for network of dedicated passenger lines[J]. Journal of the China Railway Society, 2011, 3(2): 1?7.

Optimization of intercity railway train schedule based on passengers equilibrium analysis

ZHOU Wenliang, ZHANG Xianbo, QU Linying, LI Peng

(School of Traffic and Transportation Engineering, Central South University, Changsha 410075, China)

This paper combined passengers’ equilibrium assignment to trains into intercity trains optimizing, and designed a bi-level programming model. The upper model was to optimize each train’s arrival and departure time at stations for reducing passenger in-train travel time and transfer time as well as improving their satisfaction to departure and arrival time under the requirements of trains departing interval time, minimum station dwell time, operating time, etc. And the lower model was the passenger equilibrium assignment model. This model was solved with the simulated annealing algorithm combined with GP algorithm, which continuously evaluates and adjusts the current train schedule for getting a better solution according to the result of passenger equilibrium assignment begin with an initial train schedule. Numerical example analysis shows that the proposed model and algorithm has good convergence and effectiveness.

intercity railway; train schedule; passengers equilibrium assignment; simulated anneal algorithm; GP algorithm

10.19713/j.cnki.43?1423/u.2019.01.031

U292.41

A

1672 ? 7029(2019)01 ? 0231 ? 08

2018?01?12

國家自然科學基金資助項目(71401182, U1334207)

周文梁(1982?)，男，江西永新人，副教授，博士，從事軌道交通運營組織優化研究；E?mail：zwl_0631@csu.edu.cn

(編輯 蔣學東)