城市軌道交通列車時刻表與車底運用整合優(yōu)化模型

姚 宇，朱曉寧*，康柳江，廖正文,1b

(1.北京交通大學(xué)a.交通運輸學(xué)院，b.軌道交通控制與安全國家重點實驗室，北京100044；2.新加坡國立大學(xué)土木與環(huán)境工程系，新加坡117576，新加坡)

0 引言

隨著城市交通需求的不斷擴(kuò)大，城市軌道交通憑借其快速、準(zhǔn)點、運量大、安全性高等優(yōu)勢在城市公交系統(tǒng)中發(fā)揮著骨干作用[1].近年來，以提高服務(wù)水平、降低運輸成本為目標(biāo)的運行計劃編制成為城市軌道交通運營管理的重要研究內(nèi)容之一[2].

在理論研究方面，現(xiàn)有的研究通常將城市軌道交通的運行計劃編制問題依次劃分為4個部分：列車開行計劃、列車時刻表、車底運用計劃和乘務(wù)計劃，并將前一部分的解決方案作為后一部分的前提和基礎(chǔ)，通過迭代優(yōu)化取得一個較優(yōu)解.其中，時刻表規(guī)定各次列車在區(qū)間的運行時間、在車站的到發(fā)或通過時刻；車底運用計劃則指派各車底承擔(dān)相應(yīng)的車次任務(wù).國內(nèi)外眾多學(xué)者對以上2個問題進(jìn)行過深入研究，或利用數(shù)學(xué)、運籌學(xué)等建模方法[3]，或利用現(xiàn)代啟發(fā)式優(yōu)化算法[4]進(jìn)行求解.然而，上述大部分研究都是單獨考慮2個子問題，或僅將車底數(shù)量作為保證時刻表方案可行的約束條件[5]，而未從系統(tǒng)的角度整體優(yōu)化該問題.雖然分步求解子問題可以降低問題的復(fù)雜度，但是忽略了列車時刻表與車底運用之間的有機(jī)聯(lián)系，導(dǎo)致求解結(jié)果具有局限性.回顧文獻(xiàn)，僅有少部分研究針對這一整合問題，例如，王世峰建立了城軌列車時刻表與車底運用一體化雙層規(guī)劃模型[6]，但在求解方法上仍是采用了分步算法.Luis Cadarso等以馬德里快速軌道交通為背景，構(gòu)建了時刻表和車底改編作業(yè)的一體化模型[7]，但忽略了乘客候車時間.

基于上述既有研究成果中的不足，本文結(jié)合城市軌道交通運輸組織的特點，充分考慮列車發(fā)車時刻與車底接續(xù)的相互聯(lián)系，建立了時刻表與車底運用整合優(yōu)化模型.

1 問題描述

1.1 線路組成

對于單條城市軌道線路，可將其上下行方向視為2條獨立線路.如圖1所示，每條線路有q座車站，S為車站集合，S={s|s=1,2,3,…,2q} ；L為運行方向集合，L={l|l=1,2}，l=1為上行方向，即從1站至q站，l=2為下行方向，即從q+1站至2q站；D為停車場集合，D={d|d=1,2}；R d為停車場d保有的車底集合，r∈R d?R.

圖1 城市軌道交通線路示意圖Fig.1 Illustration of urban railway transit line

1.2 車次任務(wù)與車底運用接續(xù)關(guān)系

構(gòu)建城市軌道交通車次任務(wù)和車底運用接續(xù)關(guān)系圖，如圖2所示.節(jié)點表示列車出入車場或車次任務(wù)；實線弧表示車底r執(zhí)行的車次任務(wù)間的接續(xù)，對應(yīng)變量虛線弧表示車底r出入車場與車次任務(wù)之間的接續(xù)，分別對應(yīng)變量

圖2 車次任務(wù)與車底運用接續(xù)關(guān)系圖Fig.2 Relationship diagram between train services and rolling stocks utilization

1.3 研究問題

車底是時刻表得以執(zhí)行的保證，同時時刻表又是車底運用方案的基礎(chǔ)，考慮到兩者間的密切聯(lián)系，本文將列車發(fā)車時刻和車底接續(xù)方案均作為決策變量，建立了列車時刻表與車底運用整合優(yōu)化模型.模型已知條件、求解問題、核心決策變量及與圖2中元素的對應(yīng)關(guān)系如表1所示.

2 列車時刻表與車底運用整合優(yōu)化模型

2.1 符號定義

為方便描述，本文對模型中涉及的主要參數(shù)和變量進(jìn)行定義.

[0 ,T]——列車運營時段，τ∈[0,T]，每小時為1個時段；

J——車次任務(wù)集合分別表示l方向車次任務(wù)的集合和l方向在τ時段的車次任務(wù)集合；

U——擁擠度等級集合，U={u|u=1,2,3}；

表1 獨立模型與整合模型對比Table 1 Comparison of independent models and integrated model

hmin,hmax——最小發(fā)車間隔和最大發(fā)車間隔；

ts——列車從s站行駛至s+1站的運行時間；

ttr——列車最短折返時間；

Al(t)——l方向時間t的乘客到達(dá)速率；

θu——擁擠度等級u對應(yīng)的感知時間偏差系數(shù)；

Cu——擁擠等級u對應(yīng)的列車能力；

Cf——車底固定保有費用；

Cr——車底執(zhí)行1次車次任務(wù)的運行成本；

Vd——車場d的車底保有量；

Tj——車次j的發(fā)車時刻；

2.2 目標(biāo)函數(shù)

(1)公司運營費用.

公司運營費用Zc包括2部分：車底固定保有費用和車底運行費用.前者為單位車底固定保有費Cf與上線運營車底總數(shù)的乘積，后者為單次車次任務(wù)的運行成本Cr與總車次數(shù)的乘積.

(2)乘客出行費用.

乘客出行費用包括購票費用、換乘時間費用、候車時間費用和乘車時間費用等，本模型考慮受時刻表影響的候車時間費用Zp，乘車時間費用Zt和滯留乘客的時間費用Zd.

假設(shè)在同一時段內(nèi)到達(dá)的乘客服從均勻分布，則乘客的候車時間可以表示為候車人數(shù)乘以發(fā)車間隔的1/2.乘客總候車時間為

實際乘車時間是指乘客從進(jìn)入車廂至到站后離開車廂所經(jīng)歷的時間，但車廂內(nèi)的擁擠環(huán)境會造成乘客對乘車時間的感知偏差[8].本文將車廂內(nèi)的乘客擁擠度分為3個等級，用u表示.當(dāng)u=1時，乘客有較大站立的空間，可自由走動；u=2時，車廂處于中度擁擠狀態(tài)；u=3時，車廂處于擁擠狀態(tài)且無法容納更多乘客.乘客在擁擠度等級為u時感知的乘車時間為實際時間的(1+θu)倍.因此，乘車時間Zt由乘客實際乘車時間和擁擠環(huán)境造成的偏差感知時間2部分組成.

擁擠環(huán)境不僅會造成對時間的感知偏差，當(dāng)車廂內(nèi)乘客數(shù)達(dá)到飽和時，未上車的乘客只能在站臺等候下次列車，滯留乘客的懲罰系數(shù)用ξ表示，總時間費用Zd為

通過乘客平均時間價值μ將乘客費用的時間單位轉(zhuǎn)換為經(jīng)濟(jì)單位，模型的總目標(biāo)函數(shù)為公司運營和乘客出行的總費用Z最少.

2.3 約束條件

約束條件式(6)～式(11)是時刻表相關(guān)約束：式(6)和式(7)為發(fā)車間隔上下限約束；式(8)和式(9)分別為相鄰列車處于同一時段和不同時段下的“車流耦合”約束，即列車車次和客流需求之間的匹配關(guān)系，表示斷面客流需求減去滯留乘客數(shù)應(yīng)小于等于列車在對應(yīng)擁擠度等級下的運力；式(10)表示列車在每個區(qū)間的擁擠度等級唯一；式(11)表示只有在車廂內(nèi)乘客達(dá)到飽和時才會產(chǎn)生滯留乘客，M為一個足夠大的正數(shù).

式(12)是聯(lián)系時刻表與車底運用問題的關(guān)鍵約束，表示同一車底依次執(zhí)行2次車次任務(wù)時，必須滿足相應(yīng)的時間約束.

約束條件式(13)～式(15)表示車底運用與車次任務(wù)之間的匹配關(guān)系：式(13)表示每一車次都有1個前驅(qū)點與之相連，前驅(qū)點可以是車次任務(wù)，也可指車底從車場發(fā)車；同理，式(14)保證每一車次節(jié)點都有1個后繼節(jié)點相連；式(15)為同一車底約束，即每個車次節(jié)點的前驅(qū)和后繼節(jié)點都由同一車底連接；式(16)表示所有的車底只能從車場發(fā)出1次；式(17)表示從d車場發(fā)出的車輛數(shù)應(yīng)小于該車場的列車保有量.

2.4 模型的線性化處理

目標(biāo)函數(shù)中的乘客總候車時間Zp為非線性表達(dá)式.候車時間取決于列車發(fā)車間隔，當(dāng)發(fā)車數(shù)確定時，乘客總候車時間隨發(fā)車間隔之間的偏差增大而增大.本文引入0-1變量，通過分段化處理使Zp線性化；定義為l方向τ時段的理想發(fā)車間隔，即該時段內(nèi)總偏差為0的發(fā)車間隔；定義與理想發(fā)車間隔之間偏差等級的集合N={n|-5≤n≤5}，且n為整數(shù)，當(dāng)列車j與前車的實際發(fā)車間隔和理想發(fā)車間隔之間的偏差等級為n時否則為0.對應(yīng)增加約束條件式(18)～式(20).

實際發(fā)車間隔與理想發(fā)車間隔的差值對乘客候車時間的影響可由式(21)算出，其中是l方向在τ時段平均每分鐘的到達(dá)人數(shù).則乘客總候車Zp的近似線性化表示為第1部分表示理想發(fā)車間隔下乘客的總候車時間，第2部分為變化部分.

總目標(biāo)函數(shù)變?yōu)?/p>

綜上，本文最終構(gòu)建的混合整數(shù)線性模型為目標(biāo)函數(shù)，即式(23)；約束條件為式(6)～式(20).經(jīng)測試，該模型可用CPLEX軟件在一定時間內(nèi)求得全局最優(yōu)解.

3 實例分析

3.1 基本信息及參數(shù)取值

以2015年7月北京市地鐵亦莊線的實際運營情況為基礎(chǔ)進(jìn)行案例分析，該線路運營長度23 km，共有13座車站.研究運營時段為6:00-8:00，研究時段站間斷面客流量如表2所示.

表2 研究時段斷面客流Table 2 Transect volume during study hours

其他參數(shù)取值如下：當(dāng)車廂內(nèi)乘客密度小于6.0人/m2時，u=1，C1=1 468人/車；乘客密度為6.0～7.5人/m2時，u=2，C2=1 752人/車；乘客密度為7.5～9.0人/m2時，u=3，C3=2 037人/車.車底保有成本利用城市軌道交通車輛全壽命周期成本計算模型[9]進(jìn)行計算，車底日均保有成本=(車輛購置費用+維修費用+處置成本-殘值)/全壽命周期，可估算出Cf=5 000元/列，單次車次任務(wù)的運行成本為單位里程成本[10]與線路里程的乘積，計算得Cr=60×23=1 380 元.θ1=0，θ2=1.5，θ3=2，ξ=15，hmin=2min，hmax=12 min，列車最短折返時間ttr=4 min.2015年北京市職工年平均工資為85 083元，計算得乘客平均時間價值

3.2 結(jié)果分析

模型運行的硬件環(huán)境為Intel(R)Core(TM)i5-4210U CPU@2.40GHz，內(nèi)存為4GB；軟件環(huán)境為Windows10系統(tǒng)，使用PYTHON調(diào)用ILOG CPLEX12.7.1對模型進(jìn)行求解.

根據(jù)實例中上下行客流需求相差較大的特點，本文考慮了城市軌道交通運輸組織中通常使用的成對發(fā)車和非成對發(fā)車2種模式，利用上述時刻表與車底運用整合優(yōu)化模型進(jìn)行求解，并與分步優(yōu)化模型的求解結(jié)果進(jìn)行對比，分步優(yōu)化模型的解是先求解列車時刻表子模型，再將其結(jié)果作為輸入求解車底運用子模型計算得到，求解結(jié)果對比如表3所示.

表3 模型求解結(jié)果比較Table 3 Comparison of results by different models

其中，成對開行方案中，上下行方向列車開行對數(shù)一致，6:00-7:00和7:00-8:00分別開行列車6列和9列；非成對開行方案中，上行方向列車在2個時段分別開行6列和9列列車，下行方向均開行6列列車.

比較整合優(yōu)化模型與分步優(yōu)化模型，在2種運行模式下整合模型均有明顯的優(yōu)化效果，在乘客成本變化可接受的前提下，有效地縮減了所需車底數(shù)量，降低了企業(yè)運營成本.以成對開行方案為例，總費用下降了3.37%，其中，上線車底數(shù)量減少了2列，公司運營費用下降了8.71%；同時，乘客平均出行時間僅增加1.16 s，擁擠度等級未改變，總乘客出行費用僅增加0.10%.

比較成對開行與非成對開行2種運行模型，在分步模型的計算結(jié)果中，非成對開行方案的乘客出行費用和公司運用費用均高于成對開行方案，這是由于非成對開行的運輸組織方案較為復(fù)雜，如果不對發(fā)車時刻和車底運用方案綜合考慮，會造成車底的不充分利用和成本的增加.而在整合優(yōu)化模型計算結(jié)果中，非成對開行方案的總費用小于成對開行方案.因此，對于方向不均衡明顯的線路或時段，采用適應(yīng)客流的非成對開行方案，利用整合優(yōu)化模型求解，可以提高列車滿載率，節(jié)約運營成本.

綜上所述，結(jié)合客流需求特征選擇相應(yīng)的運行模式，利用本文提出的整合優(yōu)化模型進(jìn)行求解，可以達(dá)到乘客和公司利益的綜合最優(yōu).列車發(fā)車時刻及車底運用方案最優(yōu)解如表4所示.

繪制相應(yīng)的列車運行圖，如圖3所示，斜線表示列車運行線.

表4 列車發(fā)車時刻及車底運用計劃Table 4 Train departure times and rolling stock schedules

圖3 列車運行圖Fig.3 Optimal train timetables

4 結(jié)論

本文綜合考慮了列車時刻表和車底運用之間的有機(jī)聯(lián)系，結(jié)合客流需求，構(gòu)建了基于單條線路的城市軌道交通列車時刻表與車底運用整合優(yōu)化模型，并提出了模型線性化處理方法，利用CPLEX在可接受時間內(nèi)求得最優(yōu)解，生成了列車時刻表和車底運用計劃，優(yōu)化效果明顯.最后以北京地鐵亦莊線為例進(jìn)行了實例分析，并得出以下結(jié)論：

(1)對時刻表和車底運用方案進(jìn)行綜合考慮，可以在保證服務(wù)水平的前提下減少上線運營的車底數(shù)量；

(2)選擇和客流特征相匹配的運行模式，可以有效地避免運能浪費，節(jié)約運營成本.

此外，在實際運營中，多線路的協(xié)調(diào)調(diào)度和統(tǒng)一指揮可以減少旅客換乘時間，同時促進(jìn)車底和車場等資源的合理運用.因此，進(jìn)一步考慮網(wǎng)絡(luò)化運營下的列車時刻表和車底運用整合優(yōu)化將是下一步研究的主攻方向；其次，停站方案、乘務(wù)組排班計劃等問題也與時刻表及車底運用方案間存在必然聯(lián)系，如何將這些問題與本文研究結(jié)合也將是今后研究的主要內(nèi)容.

[1]KANG L,ZHU X,SUN H,et al.Modeling the first train timetabling problem with minimal missed trains and synchronization time differences in subway networks[J].Transportation Research Part B Methodological,2016(93):17-36.

[2]KANG L,WU J,SUN H,et al.A case study on the coordination of last trains for the Beijing subway network[J].Transportation Research Part B,2015,72(72):112-127.

[3]寧麗巧,趙鵬,徐文愷,等.城市軌道交通末班車時段時刻表協(xié)同優(yōu)化研究[J].交通運輸系統(tǒng)工程與信息,2016,16(6):108-114.[NING L Q,ZHAO P,XU W K,et al.Timetable synchronization optimization for urban rail transit in the last trains’hour[J].Journal of Transportation Systems Engineering and Information Technology,2016,16(6):108-114.]

[4]鄭鋰,宋瑞,肖赟,等.網(wǎng)絡(luò)化運營下城市軌道交通列車車底運用計劃編制的優(yōu)化方法[J].中國鐵道科學(xué),2014,35(2):104-110.[ZHENG L,SONG R,XIAO Y,et al.Optimization method for working out vehicle scheduling plan of urban rail transit under network operation[J].China Railway Science,2014,35(2):104-110.]

[5]?；菝?陳明明,張明輝.城市軌道交通列車開行方案的優(yōu)化理論及方法[J].中國鐵道科學(xué),2011,32(4):128-133.[NIU H M,CHEN M M,ZHANG M H.Optimization theory and method of train operation scheme for urban rail transit[J].China Railway Science,2011,32(4):128-133.]

[6]王世峰.基于動態(tài)客流的城市軌道交通列車時刻表與車底運用一體化優(yōu)化模型和算法研究[D].北京:北京交通大學(xué),2016.[WANG S F.Study on integrated train timetabling and rolling stock scheduling model and algorithm based on time-dependent demand for urban rail transit[D].Beijing:Beijing Jiaotong University,2016.]

[7]CADARSO L,áNGEL MARíN.Integration of timetable planning and rolling stock in rapid transit networks[J].Annals of Operations Research,2012,199(1):113-135.

[8]NIU H,ZHOU X.Optimizingurban rail timetable under time-dependent demand and oversaturated conditions[J].Transportation Research Part C,2013,36(11):212-230.

[9]JUN H K,KIM J H.Life cycle cost modeling for railway vehicle[C].International Conference on Electrical Machines and Systems,IEEE,2007:1989-1994.

[10]中國交通運輸協(xié)會.城市軌道交通運營績效評估體系成果報告2015[R].北京:中國交通運輸協(xié)會,2015.[China Communications and Transportation Association.Report of metro operation performance evaluation system for 2015[R].Beijing:China Communications and Transportation Association,2015.]