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

?

基于客流均衡分析的城際鐵路列車運(yùn)行圖優(yōu)化

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

(中南大學(xué) 交通運(yùn)輸工程學(xué)院，湖南 長(zhǎng)沙 410075)

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

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

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

1 多目標(biāo)雙層規(guī)劃模型

最小化列車旅行時(shí)間是列車運(yùn)行圖優(yōu)化普遍采用的優(yōu)化目標(biāo)。然而，這僅能達(dá)到降低旅客乘車時(shí)間的目的。實(shí)際上，部分旅客出行還需花費(fèi)一定的換乘時(shí)間，且隨著旅客出行服務(wù)要求的提高，對(duì)始發(fā)、終到時(shí)間也有一定的要求。因此本文考慮以下優(yōu)化目標(biāo)。

1.1 壓縮乘車時(shí)間

當(dāng)時(shí)段OD對(duì)á,?旅客選擇路徑出行時(shí)，乘坐列車?的上車站為、下車站為′，則其乘車時(shí)間為：

1.2 減少換乘等待時(shí)間

當(dāng)時(shí)段OD對(duì)á,?旅客選擇路徑出行時(shí)，由列車換乘至列車所在的換乘站為，則其換乘等待時(shí)間為：

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

1.3 提高始發(fā)、終到時(shí)間滿意度

本文結(jié)合用戶均衡分配模擬旅客基于給定列車運(yùn)行圖的乘車選擇行為，構(gòu)建以下列車運(yùn)行圖優(yōu)化的雙層規(guī)劃模型。

(9)

其中：和為擁擠費(fèi)用參數(shù)。

以上雙層規(guī)劃模型中，式(5)表示列車區(qū)間運(yùn)行時(shí)間約束；式(6)表示列車停站時(shí)間約束；式(7)與式(8)分別表示列車滿足最小到、發(fā)達(dá)作業(yè)間隔要求；式(9)表示列車運(yùn)行時(shí)刻滿足城際鐵路運(yùn)營(yíng)時(shí)間 約束。

2 給定乘車客流列車運(yùn)行時(shí)刻計(jì)算方法

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

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

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

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

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

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

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

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

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

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

列車備選始發(fā)時(shí)段集的計(jì)算方法如下所示：

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

否則，

在按以上方法確定列車始發(fā)時(shí)段集F后，按旅客出行效益由大到小選擇列車始發(fā)時(shí)段，若列車以當(dāng)前選擇時(shí)段的中間時(shí)刻發(fā)車可完成整列列車運(yùn)行時(shí)刻推算，則輸出該列車運(yùn)行時(shí)刻；否則，繼續(xù)選擇下一個(gè)始發(fā)時(shí)段，重新計(jì)算列車運(yùn)行時(shí)刻。

3 列車運(yùn)行圖優(yōu)化算法

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

3.1 初始列車運(yùn)行圖的生成

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

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

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

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

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

根據(jù)各列車載客量q由大到小順序逐列計(jì)算列車運(yùn)行時(shí)刻。

3.2 鄰域結(jié)構(gòu)設(shè)計(jì)

鄰域結(jié)構(gòu)決定了算法從當(dāng)前列車運(yùn)行圖如何獲得一個(gè)新的列車運(yùn)行圖，進(jìn)而根據(jù)Metropolis準(zhǔn)則判斷新列車運(yùn)行圖是否被接受。具體按以下步驟產(chǎn)生新的鄰域解。

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

3.3 模擬退火計(jì)劃表設(shè)計(jì)

模擬退火計(jì)劃表控制了算法運(yùn)行過程所需要的相關(guān)參數(shù)值，設(shè)計(jì)參數(shù)參考文獻(xiàn)[3]。

至此，構(gòu)建列車運(yùn)行圖優(yōu)化算法如表1所示。

表1 城際網(wǎng)絡(luò)列車運(yùn)行圖優(yōu)化算法

4 算例分析

圖1 算例城際網(wǎng)絡(luò)

表2 列車運(yùn)行徑路

考慮路網(wǎng)上4個(gè)O-D對(duì)旅客出行，如表3所示。

表3 各OD對(duì)旅客出行需求量與出行路徑

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

4.1 算法收斂性分析

為了分析算法的收斂效果與優(yōu)化效率，取4組(,)值，如表4所示，其它參數(shù)取值保持不變，目標(biāo)函數(shù)關(guān)于計(jì)算時(shí)間的變化如圖2所示。由圖2可知：隨著算法不斷迭代優(yōu)化，所花費(fèi)的計(jì)算時(shí)間不斷增加，但同時(shí)目標(biāo)函數(shù)值亦逐漸降低直至算法收斂。各情形下算法達(dá)到收斂時(shí)計(jì)算時(shí)間均大約為14 min，但實(shí)際上在運(yùn)行10 min左右便已達(dá)到收斂解。由此表明該算法具有較好的收斂性，但相比而言，該算法收斂計(jì)算時(shí)間相對(duì)較長(zhǎng)，其收斂速度有待改進(jìn)，原因?yàn)槌塑嚳土骶夥峙湎倪^多計(jì)算時(shí)間，尤其本算例將客流均衡分配算法收斂終止條件設(shè)置的較苛刻。

4.2 算法有效性分析

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

表4 4組參數(shù)取值條件下旅客出行服務(wù)指標(biāo)值

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

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

此外，由表4可知，和取值的變化對(duì)3組服務(wù)指標(biāo)值并無較大影響；但由圖2可知，不同和取值下目標(biāo)函數(shù)的收斂值并不相同，隨著和取值的增大，目標(biāo)函數(shù)值收斂值也隨之增加。經(jīng)分析其主要原因?yàn)闃?gòu)成目標(biāo)函數(shù)的3部分內(nèi)容之間并不互相對(duì)立，其中任意一部分的改善，并不會(huì)制約另外兩部分的改善，三者可以同時(shí)進(jìn)行改善，但顯然其權(quán)重值和增加將導(dǎo)致整個(gè)目標(biāo)函數(shù)值增加。

5 結(jié)論

1) 結(jié)合不同出行目的城際客流乘車均衡分配，構(gòu)建了城際列車運(yùn)行圖優(yōu)化的雙層規(guī)劃模型，其優(yōu)化目標(biāo)由降低旅客乘車時(shí)間、換乘等待時(shí)間以及提高旅客始發(fā)、終到時(shí)間滿意度3部分構(gòu)成。

2) 設(shè)計(jì)模擬退火算法與GP算法來求解模型。

3) 通過算例分析表明本文該算法具有較好的收斂性與優(yōu)化效果，但由于客流分配計(jì)算量較大導(dǎo)致算法收斂速度較低而有待改進(jìn)?？紤]城際鐵路客流需求量與其列車服務(wù)水平的彈性變化關(guān)系來優(yōu)化城際列車運(yùn)行圖將更符合實(shí)際。

[1] 史峰, 鄧連波, 霍亮. 旅客列車開行方案的雙層規(guī)劃模型和算法[J]. 中國(guó)鐵道科學(xué), 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] 彭其淵, 賈曉秋, 關(guān)曉宇. 隨機(jī)穩(wěn)定性配流規(guī)劃的客運(yùn)專線列車開行方案模型[J]. 西南交通大學(xué)學(xué)報(bào), 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] 史峰, 周文梁, 陳彥, 等. 基于彈性需求的旅客列車開行方案優(yōu)化研究[J]. 鐵道學(xué)報(bào), 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] 汪波, 韓寶明. 城市軌道交通網(wǎng)絡(luò)周期運(yùn)行圖編制研究[J]. 鐵道學(xué)報(bào), 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] 謝美全, 聶磊. 周期性列車運(yùn)行圖編制模型研究[J]. 鐵道學(xué)報(bào), 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] 黃鑒, 彭其淵. 基于分時(shí)客運(yùn)需求的客運(yùn)專線列車運(yùn)行圖優(yōu)化[J]. 鐵道科學(xué)與工程學(xué)報(bào), 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] 周文梁, 史峰, 陳彥, 等. 客運(yùn)專線網(wǎng)絡(luò)列車開行方案與運(yùn)行圖綜合優(yōu)化方法[J]. 鐵道學(xué)報(bào), 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

國(guó)家自然科學(xué)基金資助項(xiàng)目(71401182, U1334207)

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

(編輯 蔣學(xué)東)