作者简介:李 伟(1989—),男,深圳大学博士后研究人员.研究方向:交通运输规划与管理.E-mail:aliweib1@126.com
中文责编:方 圆; 英文责编:淡 紫
1)深圳大学光电工程学院,光电子器件与系统教育部/广东省重点实验室, 广东深圳 518060; 2)深圳技术大学城市交通与物流学院,广东深圳 518118
1)College of Optoelectronic Engineering, Key Laboratory of Optoelectronic Devices and Systems of Ministry of Education and Guangdong Province, Shenzhen University, Shenzhen 518060, Guangdong Province, P.R.China2)College of Urban Traffic and Logistics, Shenzhen Technology University, Shenzhen 518118, Guangdong Province, P.R.China
traffic engineering; urban rail transit; train schedule; transfer coordination; active coordination; stepwise optimization
DOI: 10.3724/SP.J.1249.2018.06629
为适应城市轨道交通网络化运营需求,编制列车行车计划应当尽可能缩短乘客的换乘等待时间,方便乘客出行.从实用性和可操作性出发,提出网络换乘的主动衔接和被动衔接概念,在此基础上利用逐步优化的思路对列车行车计划进行优化,优先针对换乘客流大的换乘方向进行衔接,然后按换乘客流大小依次衔接网络上剩余换乘方向,得到优化后的列车行车计划.以上海市轨道交通网络为例验证算法的计算流程和优化结果.结果表明,在网络衔接中不同线路的列车开行间隔呈现相同或者倍数的关系,网络的整体衔接程度较优.
In order to meet the demand for urban rail transit network operation, train operation planning should shorten the waiting time of passengers as much as possible to facilitate passengers to travel. From the aspect of practicability and operability, this paper puts forward the concepts of active and reactive coordination, on the basis of which, train schedules are optimized step by step. The plan is optimized, and priority is given to the transfer direction with large passenger flow, and then the remaining transfer direction on the network is connected in turn according to the size of the transfer flow. Finally, Shanghai rail transit network is taken as an example to show the validity of the proposed algorithm, as well as the calculation process and optimization results. The case study shows that the overall coordination of metro network is better when the train intervals of different lines are the same or multiple in the network connection.
随着城市轨道交通的不断发展,城市轨道交通运营管理逐步进入网络化运营阶段,直接体现在网络中不同线路间的换乘衔接.良好的换乘衔接会缩短乘客的换乘等待时间,提升乘客的轨道交通出行良好感受,相反糟糕的换乘衔接则会大大延长乘客的换乘时间,降低轨道交通的服务水平.因此,在研究制定城市轨道交通列车行车计划时应尽可能缩短乘客在路径上的换乘等待时间.行车计划的主要内容包括该时段的列车开行间隔以及换乘站换乘衔接方案.
传统意义上的行车计划优化是指在满足众多运营和安全约束(如到达或出发间隔要求)的条件下,生成一个使目标函数可行或使给定目标函数较优的列车运行图.列车运行计划优化问题是一个典型的NP难(non-deterministic polynomial-time hard)问题[1-3],不少学者利用如启发式算法[4]、分支定界法[5-6]、仿真方法[7]及衔接分层优化算法[8]等求解该优化问题.然而,随着客流在制订轨道交通列车行车计划、合理配置运能方面的指导作用日趋重要,如今优化模型的目标函数不仅局限于轨道交通运营层面.文献[9-11]通过引入动态客流需求研究行车计划衔接与优化问题,以时变客流需求为背景,以乘客在车站的候车时间最小化为目标函数,利用启发式算法求解列车运行计划优化问题.
以上增加时变客流因素的研究大大增加了列车运行计划编制的科学性和先进性.然而,当前中国许多大城市的轨道交通网络规模十分庞大,线路及换乘站数量多,换乘方向繁多复杂,各线路间、各换乘站内部的关系具有关联和不确定性,若将网络上所有换乘站均考虑在内,求解起来十分困难,使用常规的建模及优化方法分析该问题已无法得到满意结果,较难用于实际.因此,研究一个贴近实际并且易于实现的行车计划衔接优化模型显得尤为重要.
面对一个具有复杂关系和众多参变量的大系统,需从系统内部相互关联子系统的分解出发,逐步、逐级地研究.基于以上考虑,本研究探讨在时变客流需求下的网络行车计划衔接优化问题,采用逐步优化思想,优先考虑换乘客流大的车站和衔接方向,并依次考虑换乘客流小的衔接方向,逐步形成优化的列车运行计划.该问题可以被阐述为:以具体客流需求数据为基础,以列车开行间隔与列车到达时刻为变量,以整体换乘衔接为目标函数的优化模型,旨在减少乘客总候车时间及提升轨道交通运营服务频率与运营服务水平,提升轨道交通整体网络动态可达性.
轨道交通换乘衔接优化模型的主要思路为:参考最小生成树思想,先对换乘站换乘衔接方向按客流量大小排序,优先考虑换乘站换乘客流大的衔接方向,并综合考虑同一换乘站内相关换乘衔接方向,以平均换乘等待时间为目标函数进行局部优化求解,逐步求解得到全网络所有换乘站的优化列车行车计划.
在此之前,先提出主动衔接与被动衔接概念,由于同一换乘站内,换乘衔接方向A-B的产生就必然会有换乘衔接方向B-A,调整线路A和B任意的列车开行间隔和到达时刻均会导致这两个换乘衔接方向乘客的换乘等待时间发生改变,因此,线路A和线路B之间换乘衔接就存在主动衔接和被动衔接概念,由线路A去主要衔接线路B称之为主动衔接,相应线路B衔接线路A称为被动衔接.定义符号*」表示不大于*的最大整数,「*表示不小于*的最小整数.
假设主动衔接方向为由线路换向线路,换乘路径的示意图如图1.
令Hi,l为线路l上列车在车站的开行间隔(发车间隔),则在时间段T内共有T/(Hi,l)」趟列车到达车站i, 其中,第s列(s≤T/(Hi,l)」)列车到达车站i的时间为t(0)i,l+sHi,l.那么乘客经由线路l换乘到达线路r的时间为t(P, A)i,r=t(0)i,l+sHi,l+t(T)i,l→r(1)
其中, t(0)i,l为在时间段T内,线路l上第1列列车到达车站的时间; t(T)i,l→r为乘客在车站i由线路l换向线路r所花费的步行时间.
同时,可得线路r上列车在车站的发车时间为
t(D)i,r=t(0)i,r+uHi,r+t(S)i,r(2)
其中, t(0)i,r为在时间段T内,线路r上第1列列车到达车站i的时间; Hi,r为线路r上列车在车站i的开行间隔(发车间隔); t(S)i,r为线路r上列车在车站i的停站时间; u表示到达后的第几列列车, u≤T/(Hi,r)」.
乘客若要乘坐线路r上的衔接列车,则线路r上列车在车站i的发车时间需至少大于乘客经由线路l换乘到达线路r的时间, t(P,A)i,r≥t(D)i,r,即
t(0)i,r+uHi,r+t(S)i,r≥t(0)i,l+sHi,l+t(T)i,l→r(3)
整理可得
u≥(t(0)i,l+sHi,l+t(T)i,l→r-t(0)i,r-t(S)i,r)/(Hi,r)(4)
考虑到理性乘客首选候车后第1趟到达的列车,则
u=「(t(0)i,l+sHi,l+t(T)i,l→r-t(0)i,r-t(S)i,r)/(Hi,r)(5)
因此,第s列列车上乘客的换乘等待时间Wl→r(S)为
Wl→r(S)=t(0)i,r+t(S)i,r+u(Hi,r)-
(t(0)i,l+sHi,l+t(T)i,l→r)(6)
综上,乘客在时间段T内由线路l换向线路r的平均换乘等待时间W^-l→r为
W^-l→r=1/(T/(Hi,l)」)∑T/(Hi,l)」s=1Wl→r(s)(7)
主动衔接方向为由线路l换向线路r, 相应被动衔接方向为线路r换向线路l, 对应的换乘示意图如图2.其平均换乘等待时间的计算方法与主动衔接平均等待时间的计算方法相类似.
在时间段T内共有T/(Hi,r)」趟列车到达车站i, 其中, 第s'列(s'≤T/(Hi,r)」)列车到达车站i的时间为t(0)i,r+s'Hi,r, 则乘客经由线路l换乘到达线路r的时间t(P,A)i,l为t(P,A)i,l=t(0)i,r+s'Hi,r+t(T)i,r→l(8)
同时,可得线路l上列车在车站i的发车时间t(D)i,l为
t(D)i,l=t(0)i,l+u'Hi,l+t(S)i,l(9)
其中, u'表示到达后的第几列列车, u'≤T/(Hi,l)」.
乘客若要乘坐衔接列车,则线路l上列车在车站i的发车时间需至少大于乘客经由线路r换乘到达线路l的时间, t(P,A)i,l≥t(D)i,l, 即
t(0)i,l+u'Hi,l+t(S)i,l≥t(0)i,r+s'Hi,r+t(T)i,r→l(10)
整理可得
u'≥(t(0)i,r+s'Hi,r+t(T)i,r→l-t(0)i,l-t(S)i,l)/(Hi,l)(11)
考虑到理性乘客第一选择始终是候车后第一趟到达的列车,因此
u'=「(t(0)i,r+s'Hi,r+t(T)i,r→l-t(0)i,l-t(S)i,l)/(Hi,l)(12)
则第s'列列车上乘客的换乘等待时间Wr→l(s')可以表示为
Wr→l(s')=t(0)i,l+t(S)i,l+u'Hi,l-
(t(0)i,r+s'Hi,r+t(T)i,r→l)(13)
乘客在时间段T内由线路r换向线路l的平均换乘等待时间W^-r→l为
W^-r→l=1/(T/(Hi,r)」)∑T/(Hi,r)」s'=1Wr→l(s')(14)
综合主动衔接和被动衔接两个平均换乘等待时间,在车站i的总换乘等待时间F为
F=fi,l→r(T)W^-l→r+fi,r→l(T)W^-r→l(15)
其中, fi,l→r(T)为在时间段T内,在车站i中从线路l换向线路r的总客流量; fi,r→l(T)为在时间段T内,在车站i中从线路r换向线路l的总客流量.
要求换乘车站i的主动衔接方向和被动衔接方向的衔接程度最优,即使得总平均换乘等待时间最小,需满足
minFi=min{(fi,l→r(T)W^-l→r+fi,r→l(T)W^-r→l)/(fi,l→r(T)+fi,r→l(T))}(16)
s.t. Hmin,l≤Hi,l≤Hmax,l
Hmin,r≤Hi,r≤Hmax,r
0≤t(0)i,l≤Hi,l
0≤t(0)i,r≤Hi,r
其中, Hmin,l和Hmin,r表示列车开行间隔能取的最小值,其与线路折返能力、追踪能力有关; Hmax,l和Hmax,r表示列车开行间隔能取的最大值.
模型求解思路主要基于逐步优化思想,① 将换乘站换乘衔接方向按换乘客流大小排序; ② 对换乘客流大的衔接方向优先构建连接边,确定该方向列车开行间隔和列车到达时刻,并进行标记,逐步按换乘客流大小依次将网络上所有换乘方向覆盖,形成一个完整列车运营计划.具体求解思路的流程框架如图3.
模型求解首先要得到按换乘客流量排序的全网络换乘衔接方向.得益于近来兴起的轨道交通自动售检票系统(automatic fare collection, AFC),我们可以获得大量乘客出行数据,进而获得在微观层面上量化的客流时空分布结果.具体使用方法为利用给出的路径清分比例表,分析计算指定日期和指定时间段的进出站AFC刷卡数据,可得每个时间点和每个车站上的客流量,随即获得该时段内各换乘站各换乘方向的客流量.将排序后的换乘站和换乘方向集合存储供后续步骤调用.
逐步优化目标可描述为:① 制定一个列车行车计划,使所有换乘站的所有换乘方向均能被接上,且网络所有换乘站的总换乘等待时间最小.根据排序好的换乘衔接方向,对换乘客流大的换乘衔接方向优先构建衔接计划,确定该方向列车开行间隔和首列列车到达时刻,并将该换乘方向进行标记; ② 按换乘客流大小依次将网络上所有换乘方向连接上.若该方向列车开行间隔和列车到达时刻已被标记,则无需改变它们; 若该方向列车开行间隔或列车到达时刻有其中一个未标记确定,则求解之.最终形成一个完整的列车行车计划.
换乘衔接求解中存在两种情况,一是主动衔接与被动衔接中4个变量(分别为列车开行间隔与列车到达间隔)均未知,或3个变量未知1个变量已知; 另一种是主动衔接与被动衔接中2个变量未知2个变量已知,或1个变量未知3个变量已知.从建立模型的公式可以看出,模型为弱约束最优化问题,当变量数量过多时(如情况一),将很难求出优化结果,此时通常采取启发式算法,本研究选取模拟退火算法求解; 而当变量数量少时(如情况二),为得到较优结果,可采用最优化理论求解,本研究选取一维线性搜索算法求解.
模拟退火算法源于固体退火原理[12],将固体加温至足够高的温度,加温时固体内部分子随升温变为无序状呈现随机排列状态,而逐步降温时粒子渐趋有序.最后在常温时达到基态,内部分子以低能状态排列,固体达到某种稳定状态.
具体模拟退火算法步骤如下:
步骤1 设定初始温度值T0, 初始状态解x, 计算其目标函数值E.
步骤2 内部循环.
1)产生一个随机干扰,得到新解x', 并计算其目标函数值E'.
2)计算内能增量ΔE, 若ΔE<0, 则接受新解x', 设新解为当前解x←x', 跳转步骤4),否则跳转步骤3).
3)若ΔE>0, 计算概率p=e-ΔE/kTi, 并随机生成一个0~1的均匀分布变量,用以判断是否接受新解,若接受则设新解为当前解x←x'; 否则保持原解x, 转步骤4).
4)若满足内循环终止条件,跳出内循环; 一般内循环终止条件取为连续若干个新解都没有被接受,即当前解保持不变若干次循环.
步骤3 外部循环.
1)判断当前温度Ti是否满足终止条件,即Ti→Tmin, 其中, Tmin为目标温度,若达到终止条件,则终止算法,输出当前解为最优解;
2)设置当前温度为Ti→Ti×ε, 其中, ε为温度衰减参数,一般设置为0.99或0.98,跳转步骤2开始内部循环.
本研究采用的一维线性搜索中“改进0.618法”来计算模型求解中未知变量少的情况二.0.618法(又称黄金分割法)是美国数学家KIEFER[13]于1953年提出,属于分割法函数求极值方法,分割类方法仅需计算函数值,因此使用范围较广,尤其适用于非光滑及导数表达式复杂或写不出等情形.改进0.618法是针对目标函数是单峰函数,也就是目标函数为凸的情形的分割类方法,因其不要求函数可微,且每次迭代只需计算1个函数值,程序简单容易实现而被广泛采用.由于黄金分割法是以等比例0.618分割缩小区间的,因此,针对在实际问题中遇到的目标函数往往不是单峰函数的情况,它是一种近似最优方法.
以上海轨道交通网络为例,对本研究提出的城市轨道交通行车计划衔接优化算法进行分析验算,以平峰时期(如13:00—15:00)的列车衔接进行说明.实例分析中所需的数据如下:
1)AFC刷卡数据.选用2014-12- 09的客流刷卡数据,其中选用时间段13:00—15:00的客流,共有1 386 402条配对好的进出站AFC刷卡数据.
2)清分比例表.共有119 918个起终点(origin destination, OD)对,总共有288 200条路径.
3)换乘走行时间.各换乘站各换乘方向的步行时间,可从上海轨道交通运营公司票务部门获取.
按照换乘站换乘客流大小进行排序,可得如表1的换乘衔接方向.
利用C#.Net程序语言对本节提出的模型与算法进行编程求解,按排序后的换乘衔接方向对换乘站换乘方向进行衔接优化,优化后进行标号,并依次处理余下换乘衔接方向,直至所有换乘衔接方向均已优化.优化过程如图4,其表示随程序求解步骤的推进,当前状态下网络平均换乘等待时间的改变程度.图中x轴表示程序求解步骤,即当前计算到排序后换乘衔接方向的顺序; y轴表示当前网络中已确定的模型决策变量数,包括列车开行间隔和首列到达时刻.图中数据散点圆的半径大小表示当前状态下网络平均换乘等待时间.数据点的大小随求解步骤的推移先增后减,说明随着换乘衔接方向的不断优化,乘客的平均换乘等待时间越来越优.
需指出,在图4程序求解步骤的后期,出现较长时间空白,原因在于该迭代时间点,换乘衔接的变量均在前面的求解步骤中被标定过,此步骤中无决策变量可求解,因此出现该数据点上的空白.
最终获得所有换乘站换乘方向的衔接方案结果如表2.可见,平峰时段上海轨道交通1、2、4、5及11号线,由于存在换乘客流大的换乘站,其列车开行间隔优先得到衔接满足,而3、12、13及16号线,由于其中的换乘站客流较小,其列车开行计划主要用于衔接其他线路.此外,表2还显示,平峰时段线路上下行的列车开行间隔均保持相同,并且多条线路的开行间隔由于换乘衔接关系的密切,列车开行间隔呈相同或倍数的关系.同理,几个重要的换乘站首列到达时刻如表3.
本文研究时段为平峰时间段13:00—15:00,共计2 h,经计算共有换乘客流226 726人次,在未衔接优化之前,各线独立运营,未考虑相互之间的衔接关系,乘客的平均换乘等待时间为128.9 s.经优化衔接后,乘客的平均换乘等待时间为93.9 s,较之前平均减少换乘等待时间约27.1%,优化后的网络整体衔接效果较之前有一定提升.由此可见,通过调整线路间的换乘衔接关系,优化城市轨道交通网络整体衔接程度,可使乘客的平均换乘等待时间缩短,提升乘客出行效率,为网络上的出行乘客提供优质的客运服务.
本研究探讨常规时间下的城市轨道交通网络行车计划衔接优化问题,模型通过优化列车的开行间隔与列车的首列到达时刻,使乘客换乘站的总平均等待时间最短.建模中提出主动衔接和被动衔接概念,并利用它们计算换乘方向的总平均等待时间,并设计基于逐步优化的算法来解该模型.通过案例分析说明,本算法求解过程思路清晰,易于实现,能够优先匹配换乘客流量大的换乘衔接方向.且得出换乘衔接中,不同线路的列车开行间隔呈现相同或者倍数的关系,网络的整体衔接程度较优.
深圳大学学报理工版
JOURNAL OF SHENZHEN UNIVERSITY SCIENCE AND ENGINEERING
(1984年创刊 双月刊)
主 管 深圳大学
主 办 深圳大学
编辑出版 深圳大学学报理工版编辑部
主 编 李清泉
国内发行 深圳市邮电局
国外发行 中国国际图书贸易集团有限公司(北京399信箱)
地 址 北京东黄城根北街16号
邮 编 100717
电 话 0755-26732266
0755-26538306
Email journal@szu.edu.cn
标准刊号 ISSN 1000-2618
CN 44-1401/N