基于在途时间的快慢车停站方案优化算法

丁小兵 徐行方

(1.上海工程技术大学城市轨道交通学院，201620，上海；2.同济大学道路与交通工程教育部重点实验室,201804,上海 ∥第一作者，讲师)



基于在途时间的快慢车停站方案优化算法

丁小兵1徐行方2

(1.上海工程技术大学城市轨道交通学院，201620，上海；2.同济大学道路与交通工程教育部重点实验室,201804,上海 ∥第一作者，讲师)

地铁开行快慢车是国内近几年的新探索,而其停站方案的不同会影响地铁的服务水平高低及企业运输成本等。首先确定车站重要度评价指标体系,对指标逐一打分形成评价指标矩阵,运用层次分析法评价沿线车站的重要度,并据此确定停站权重；然后将停站权重作为停站优化方案建模的重要参数,再构建基于启发式蚁群算法的MATLAB程序,对快慢车停站方案优化模型求解,得出优化停车方案；最后,以上海轨道交通16号线为例,设计相关调查问卷获取数据对优化算法进行求解,并与目前停站方案作对比分析。通过该优化算法可以缩短乘客出行时间,提升地铁服务水平,同时为运营管理部门制定行车方案提供决策支持。

地铁；快慢车模式; 蚁群算法; 行车方案； 在途时间

First-author′s address School of Urban Rail Transportation, Shanghai University of Engineering Science,201620,Shanghai,China

随着中国城市化进程的不断推进,中心城与郊区、卫星城镇之间的客流量日益增大。轨道交通郊区线路早晚高峰潮汐客流特征明显,其客流时空分布不均衡,且主要集中在部分车站,其非高峰时段列车载客率低。故若仍然实行站站停方案,必将降低运营效率,从而对乘客出行时间和企业运输成本造成一定的浪费。研究与沿线客流出行特征相吻合的快慢车停站方案,有利于解决由于早晚高峰客流大而造成的列车运能不匹配、车厢拥堵、列车客流分布不均衡、社会对地铁的投诉率增加等问题。是轨道交通郊区线路开行快慢车模式必须解决的问题。

近几年,国内已经开展了轨道交通快慢车行车组织方面的研究,文献[1]研究了基于弹性需求的轨道交通列车开行方案,主要从乘客的广义出行费用上入手,构造乘客出行弹性需求函数,运用模拟退火算法优化列车的行车方案,而且，其开行方案中包含了零散的停站方案的研究。这为本文的研究思路指明方向,奠定了研究基础。文献[2]研究了在城市轨道交通的非高峰时期的客流特点,建立了以企业利益和出行者效益最大化的多目标决策模型。文献[3]研究了区域城际铁路开行方案,建立了站间距计算模型,为系统研究区域城际快速铁路开行方案提供了理论依据。

本文从乘客总在途时间出发研究轨道交通快慢车停站方案的优化问题,构建以乘客总在途时间最小为目标的优化模型，结合上海轨道交通16号线进行仿真验证,以实现运营企业经济效益最大化、乘客出行总时间最小化,从而提高轨道交通的服务水平。

1 乘客出行时间分析

乘客出行时间由列车所有乘客的在途时间和候车时间两部分组成[5]。开行快慢车模式,能使部分乘客的在途时间缩短,但也使部分乘客因候车时间的延长而增加总出行时间。优化停站方案可使乘客总体出行时间减少,其目的是使在优化方案的乘客总体出行时间相比于现行站站停方案下节省最多。

节省的时间为:

Δt=Δtt+Δtw

(1)

式中:

Δt——大站停模式较站站停模式(后文简称变化模式)乘客总出行时间变化量;

Δtt——变化模式下乘客在途旅行时间变化量;

Δtw——变化模式下乘客等待时间变化量[4-6]。

乘客出行时间通常主要受发车间隔与客流量影响,其指标量化计算式为

(2)

(3)

式中：

h——站站停模式下平均发车间隔;

hAB——大站停模式下相邻慢车和快车的时间间隔;

hA/B——大站停模式下相邻两列快车或相邻两列慢车时间间隔,hA/B≥hAB;

tl——因停站而引起的时间损失;

Vmax——列车最高运行速度;

α——列车起动时的加速度;

β——列车制动时的减速度;

ts——停站时间。

(4)

(5)

构建线性规划模型为

Δtmax=Δtt+Δtw

(6)

其约束条件为

(7)

(8)

主要从轨道交通服务水平角度考虑。

(9)

i,j∈(1,2,3,…,n)

我们将2010～2016年这7年间不同饲料企业采购的不同鱼粉产品进行感官分析、化学质量分析的数据进行归纳整理，得到一些有意义的结果，旨在分享这些结果的同时，对鱼粉产品的质量评价和质量控制进行有益的探讨，供同行者参考。

在求解运算中设定每位乘客都能搭乘第1趟车,即不考虑超过车厢满载率而滞留车站的情况[8]。

2 轨道交通车站重要度

2.1 车站重要度

从客流量、旅客出行时间、企业运营成本三个指标出发建立加权的AHP(层次分析法)模型,来综合评价轨道交通线路沿途车站的重要度。其评价指标体系如图1所示。

图1 轨道交通车站重要度评价指标

2.2 节点重要度的确定

根据图1建立轨道交通车站评价指标矩阵。矩阵的构建方法采用传统的方法:①aij>0,②aji=1/aij。并用1-9及其倒数作为标度来确定aij的值。指标体系中的指标,拟通过调查问卷的方式(抽样调查对象为经验丰富的基层员工和行业专家)获取。并通过评分确定其权重,最终确定车站重要度的一级判断矩阵A。

将轨道交通路网中的车站视为复杂网络中的节点,则节点i(i=1,2,…,n)的重要度计算式为:

式中:

n——节点数量；

m——选取的评价指标值；

wj——通过层次分析法评价得到的车站的停站权重；

pij——节点i的评价指标得分值,i,j=1,2,…,m。

3 快慢车停站方案优化建模实例分析

3.1 上海轨道交通16号线运营数据

上海轨道交通16号线从龙阳路站—滴水湖站在龙阳路站与上海轨道交通2号线、7号线及磁浮列车换乘,以满足连接远郊临港新城到中心城区的要求。其线路长度达58.96 km。其主要运营条件为:

(1)终端站和部分大站设站前折返双岛四线,接发车间隔时间应至少满足60 s要求。

(2)列车采用A型车,定员216人/辆(站立标准4人/m2)，最高运行速度为120 km/h。

(3)近期快车采用3节编组,慢车6节编组,短期可用列车数不设上限。

(4)现行停站方案快慢车全程运行时间和旅行速度如表1所示。

表1 快车、普快、慢车运行信息

3.2 客流数据

上海轨道交通16号线开通后,通过AFC(自动售检票)系统数据可得出开通后初期的早晚高峰时段沿线60 min进站客流量。其具有明显的地域影响,与车站所在的位置、周边的商场、社区，以及与其他交通方式的衔接等紧密相关。高峰客流分布如表2所示。

表2 上海轨道交通16号沿线车站早晚高峰进站客流量

3.3 车站重要度计算

相应的权重分别为W1=(0.50,0.13,0.37),W2=(0.11,0.64,0.25),W3=(0.22,0.61,0.17)。通过对判断矩阵和指标权重的计算,得出判断矩阵的偏离一致性CI。如CI值小于标准参数0.12,则表明判断矩阵具有满意的一致性,各级指标计算可靠。

将轨道交通线路中的车站视为复杂网络中的节点,则节点i(i=1,2,…,n)的重要度为

分别计算出上海轨道交通16号线各车站节点重要度结果如表3所示。

表3 上海轨道交通16号线各车站节点重要度

3.4 行车方案优化模型构建

3.4.1 数据获取

通过问卷实地调查和网上调查,获取轨道交通沿线车站乘客的出行情况,获得乘客出行的OD出行情况、出行的时段、周出行次数及出行总时长等参数,如表4所示。

3.4.2 模型的构建

计算出沿线车站节点重要度后,需构建多目标优化模型,才能得出最优的行车方案。设上海轨道交通16号线模型为N=(S,E),具有n个车站、m个区段。其中，S为车站的集合,S={S(1),S(2)…S(n)};E为运行区段集合,E={e(1),e(2)…e(3)};Sr为列车r的停站集合。建立基于行车方案的多目标优化模型,其多目标函数主要包括以下4个方面。

表4 上海16号线轨道交通客流时段分布

(1) 快慢车停站次数目标函数为:

(10)

式中:

yr,a,b——车站a到车站b乘坐列车r的客流量；

nr,a,b——列车r通过车站a到车站b的停站次数；

wk——车站的重要度系数,其值由上述模型计算而得。

(2) 乘客乘坐快慢车在途节省时间Δt值最优按式(6)为:

Δtmax=tt+Δtw

(11)

计算时间所需的客流量数据由轨道交通AFC闸机获得。

(3) 上海轨道交通16号线运营费用最小化目标函数为:

(12)

式中:

xr——列车r的开行对数;

de——区段e的里程。

(4) 上海轨道交通16号线开行对数目标函数为

(13)

根据上海轨道交通16号线采用的快慢车实际情况建立如下4个约束条件:

(3)xr≥m(r);xr≤n(r),m(r)为列车最小开行对数,n(r)为最大的开行对数,xr为整数。

(4) 式(11)的约束条件由式(7)～(9)确定。

3.5 模型求解

根据车站重要度分析,建立上海轨道交通16号线基于客流、旅行时间、企业运营成本的多目标模型。其中，列车采用3节A型列车编组,定员216个座位,其满载率上限为250人(超员15.7%)。超载时按7～9人/m2计算，最小发车间隔为4 min。运用蚁群算法多次迭代搜寻最优解时，首先初始化信息,设集合C为所有的线路车站集合;CG(min)为每次蚁群寻优的最优值;CA(min)为目标最优值。则蚁群算法求解步骤为:

(1) 蚁群和路径初始化。将M只蚂蚁放置于上海轨道交通16号线的沿线车站，并将蚂蚁视为计算中心; 设初始时间t= 0,且所有配送路径上的初始信息和信息素之和都为零。

(2) 设蚁群的禁忌表索引号为1，将所有蚂蚁出发后访问的第一个停站编号放入其相对应的禁忌列表中。

(3) 循环次数增加1。

(4) 蚁群个体根据状态转移概率来选择下一步该到达的停站编号。

(5) 修改禁忌表的索引号,将选择好之后的蚂蚁移到新的编号上,并将该编号插入到禁忌表中。

(6) 如集合C中所有的编号没有遍历完,则跳到步骤(4)继续,否则停止运算。

(7) 如果一个蚂蚁找到了终点站点,则计算该只蚂蚁的总路径费用(出行时间),同时更新当前得到的最小费用路径,记录此时最小费用线路所对应值,并更新路径上的信息素的浓度。

(8) 计算每一条路径上的信息量。

(9) 若没有达到最大循环次数,则清空所有禁忌表,并跳转至步骤(1)；否则跳转至步骤(7)。

(10) 对已找到的最小费用(出行时间)停站方案更新,并记下最小费用值,如果CG(min)与CA(min)之间的差小于预先设定的值,则得到最小费用线路，并终止整个程序的执行;否则转至步骤(3),继续执行。

运用MATLAB对上述蚁群算法求解,其主要计算代码如附录1所示,迭代过程示意图如图2所示。通过MATLAB算法对构建的最优化模型进行计算,最终得出开行方案的停站方案如图3所示,相应的停站时间如表5所示。

图2 迭代次数与时间变化量示意图

表5 上海轨道交通16号线不同停站方案的停站时间

图3 上海轨道交通16号线停站优化方案示意图

3.6 优化结果分析

根据上海轨道交通16号线现行列车运行图(如图4所示),大站车停靠惠南站和新场站。在该运行方案开通运营后一个月里,多次乘客反映大站停站设置不合理,在临港大道站和书院站上班的市民很不方便。这也与网络调查结果吻合。在大站停模式下,列车仅停靠两站,旅客出行时间约37 min 34 s;而站站停方案全程耗时约48 min,其中,慢车在越行站等待时间约3 min,乘客普遍反映不能接受。运营管理方也一直在寻找解决方案。

图4 上海轨道交通16号线列车运行图

在优化模型计算出的停站方案下,大站车停靠新场站、惠南站及书院站等3站,全程运行时间为32 min 51 s,停站时间也作了相应改进和调整。与现采用的停站方案相比,列车虽多停靠1个车站,全程仍节省了4 min 43 s,不仅缩短了乘客在途时间,而且增加了书院站的客流吸引力,提升了轨道交通对外服务水平。若再优化大站车与慢车的开行比例和越行站的位置,则该方案优势更明显。

4 结语

轨道交通快慢车共线组合运行在国内探索尚不多,其行车方案参多照高铁的开行方案。如何有针对性的摸索出适合轨道交通的快慢车的方案还需作深入探究。本文从轨道交通停站方案的影响因素出发,建立基于多目标优化模型,运用启发式蚁群算法构建MATLAB程序,搜索最优解,在保证乘客目的地可达性的基础上(即合适的停站方案),缩短乘客总出行时间,提升地铁服务水平。最后结合上海轨道交通16号线进行实例分析,得出的优化方案具有实践指导意义。启发式蚁群算法的计算效率和精确度是今后的研究重点,结合考虑快慢车停站方案的更多影响因素,可使得优化方案更好地服务于乘客。

[1] 邓连波,曾强.基于弹性需求的城市轨道交通列车开行方案研究[J].铁道学报,2012,34 (12):16.

[2] 孙鹏,丁宏飞.城市轨道交通非高峰期开行方案建模与求解[J].计算机工程与应用,2012(28):26.

[3] 高麟.我国发展区域城际快速铁路的相关研究[D].成都:西南交通大学,2003.

[4] 徐瑞华,潘寒川.市域轨道交通快慢车组合运营的通行能力研究[J].城市轨道交通研究,2009(10):48.

[5] MUNDER S,GAVRILA D.An experimental study on pedestrian classification[J].IEEE Trans,2006,28(11):1863.

[6] 聂磊,郭富娥.计算机编制高速铁路列车运行图的研究[J].中国铁道科学,1997,18(1):101.

[7] 徐行方,忻铁朕.城际列车的概念及其开行条件[J].同济大学学报(自然科学版),2003,31 (4):432.

[8] CHEN H,YAO X.Multi-objective neural network ensembles based on regularized negative correlation learning[J].IEEE Trans,2010,22(12):1738.

[9] DAM H, ABBASS H.Neural-based learning classifier systems[J].IEEE Trans,2008,20(1):26.

[10] 陈晓峰.上海轨道交通16号线快慢车运行方案研究[J].城市轨道交通研究，2014(5):68.

Optimization Algorithm of Fast/Slow Train Stop Scheme Based on Passenger Travel Time

DING Xiaobing, XU Xingfang

Since the quality of urban rail stop schemes will influence the business cost and service level, the operation of fast/slow stop scheme becomes a new research topic in China. An evaluation index system of importance degree is firstly established, and AHP is used to evaluate the importance degree of stations along the line from the influencing factors over traffic organization plan; then based on MATLAB in ant colony algorithm, the best stopping solution and interval from both the operators and passengers are studied to maximize the economic benefits of enterprises. Finally, taking Shanghai rail transit Line 16 as an example, a questionnaire is designed to collect data for modeling and solution of the optimization algorithm. Through optimization Algorithm, the cost could be saved, the service level be improved with a certain value to support the decision-making for urban rail transit operation.

metro; fast/slow operation model; ant colony algorithm; operation scheme; travel time

U 292

10.16037/j.1007-869x.2016.06.011

2014-12-02)