城市轨道交通列车运行图鲁棒性优化模型

曹志超, 袁振洲 , 李得伟, 张思林, 马伶伶

(1.北京交通大学 城市交通复杂系统理论与技术教育部重点实验室，北京　100044；2.北京交通大学 轨道交通控制与安全国家重点实验室，北京　100044；3.中国民航大学 民航空管研究院，天津　300300)

随着城市轨道交通技术装备水平的提高，以及为满足乘客出行要求，客流高峰时段高密度行车已成为城市轨道交通运输的重要特征。例如，北京市城市轨道交通在移动信号闭塞系统[1]下已实现90 s的列车发车间隔。但是，在高密度行车条件下列车一旦晚点，对整个路网的运输组织会产生很大的影响。因此，如何在计划阶段通过调整列车运行图以减小此影响，从而实现城市轨道交通列车运行图抗干扰性(即鲁棒性)的优化，是高密度行车条件下列车运行计划编制和调整的重要目标。

传统的列车运行图优化模型较少考虑为满足客流需求而导致的随机干扰，缺乏鲁棒性优化的空间。国内学者对计划阶段运营管理的研究重点多集中在列车开行方案上，对城市轨道交通列车运行图研究较少。文献[2]提出以平峰时段换乘客流总等待时间最少为目标的网络周期运行图编制方法；文献[3]提出以列车总旅行时间最少和使用动车组车底数最少为目标的高速铁路周期性运行图优化模型；文献[4]研究了城市轨道交通车底运用方式、列车发车间隔和首末班车衔接方案等共线交路列车运行图铺画的关键问题；文献[5]提出以铁路企业效益最大化为目标的旅客列车开行方案和运行图综合优化的双层规划模型；文献[6]提出2种不同恢复方法的列车运行图可恢复鲁棒性的优化模型；文献[7]提出采用“时间控制点法(Time-control strategy)”提高公交开行计划鲁棒性的优化模型。以上研究为准确理解列车运行图编制问题提供了重要的研究基础。完成城市轨道交通列车运行图的编制需要以下3个基本步骤。

(1)确定列车的发车频率或发车间隔；

(2)规定列车的开行区段、折返交路和停站方案；

(3)确定列车的出发时刻、到达时刻、缓冲时间(Buffer-time)、区间运行时间。

基于以上背景，本文以步骤(3)为研究目标，考虑乘客在车站的等待行为和列车的交互关系，以城市轨道交通列车运行图扰动时间之和最小化为目标，构建满足客流需求的城市轨道交通列车运行图鲁棒性优化模型，并提出求解算法。

1　问题描述

城市轨道交通列车运行图之所以受到干扰，不能按计划时间开车，除设备技术故障外，很大程度上是由于客流高峰时段内乘客持续上车，使列车车门无法关闭而导致列车出发时刻延误，进而产生列车晚点。如果列车运行图的鲁棒性差，还将导致列车晚点传播范围增大，甚至有些列车停运。

本文的研究思路为：在计划层的列车运行时段内，调整列车缓冲时间，以优化列车运行图的鲁棒性。其中如何确定站间的缓冲时间是优化列车运行图鲁棒性的关键。因为如果缓冲时间过长，势必会延长乘客在途时间，降低列车发车频率；但缓冲时间过短，又无法提高列车运行图的抗干扰能力。

本文首先详述列车运行组织计划的约束，然后在考虑列车载客能力的情况下，基于历史客流数据并通过候车乘客与列车的交互关系确定列车的实际停站时间，最后基于列车运行图扰动时间的递推关系进行建模。

为方便建模，对列车的运行特征作如下假设。

(1)基于文献[8]的假设，以城市轨道交通单一线路为研究对象，并采用站站停的停站方案。

(2)根据国内外城市轨道交通运营实践，采用2站式的长交路运行，即始发站1为车辆段所在站，终到站n为列车折返站。

(3)所有列车编组一致，即列车具有相同的载客能力(列车内的座位数与可容纳站立人数之和)，并用C表示，人·列-1。

(4)每个车站同时仅能容纳1列列车，全线不允许有列车越行。

(5)列车站间运行包括3个阶段：起动加速阶段、匀速运行阶段和制动减速阶段。

2　模型构建

令城市轨道交通线路网络N=(J,E)，其中J={1,2,…,j-1,j,…,n}为车站集；E={e(j-1,j)|j∈J}为区间集，区间e(j-1,j)∈E为车站j-1与相邻车站j之间的区间；区间e(j-1,j)的里程长度(简称站间距)记为l(j-1,j)，m。

2.1　列车运行组织计划约束

设在运营时段[t0,te]内计划开行的列车的集合为I={1,2,…,i-1,i,…,m}。

在E上的列车计划出发时刻需满足安全追踪间隔时间的约束，即

(1)

根据假设(4)和(5)，列车运行图中任意一班列车的计划到达和出发时刻存在如下关系。

(2)

(3)

(4)

由于有

因此将上述公式带入式(4)后可得

(5)

列车匀速运行速度vi,j-1,j应满足

(6)

(7)

2.2　乘客和列车的交互关系约束

在车站j等待乘坐列车i的客流量Wi,j为

(8)

其中，

(9)

式中：Wi,j,k为在车站j等待乘坐列车i前往车站k∈J的客流量，人；Li-1,j,k为因上一班列车i-1满员而滞留在车站j的打算前往车站k的客流量，人；λj,k为从车站j出发前往车站k的客流到达率，人·s-1。

列车i在车站j的下车客流量Ui,j为

(10)

其中，

Ui,f,j=Wi,f,j-Li,f,j

(11)

式中：Ui,f,j为列车i上在车站f上车且在车站j下车的客流量，人。

列车i在离开车站j时，车内客流量Qi,j为

Qi,j=Qi,j-1-Ui,j+Bi,j

(12)

其中，

(13)

(14)

在客流高峰时段，由于受列车载客能力的限制，列车i在车站j滞留的客流量Li,j为

(15)

Li,j还可以由下式得到，即

(16)

(17)

式中：β1，β2，β3，β4分别为拟合参数；d为每列车上下乘客的车门数量，个·列-1。

2.3　列车运行图鲁棒性约束

(18)

其中，

(19)

图1　列车运行图扰动时间

(20)

式中：δi,j-1,j为列车i在区间e(j-1,j)的可恢复因子，0≤δi,j-1,j≤1，令δi,1,2=0，即列车i在始发站正点出发。

(21)

类似式(2)和式(3)，列车i在车站j的实际出发时刻为

(22)

(23)

基于式(18)，上式可进一步写成

(24)

因为列车在始发站正点发车，那么

(25)

如果令

因为t和τ可根据历史客流量数据计算得到，δ为经验取值变量，所以将t，τ，δ作为输入变量，而缓冲时间x则为输出结果。

2.4　优化模型

(26)

γ1和γ2可通过列车实际运行数据进行标定。

以式(1)—式(26)为约束条件，列车运行图的扰动时间之和最小化为目标，构建的城市轨道交通列车运行图鲁棒性优化模型为

(27)

3　求解算法

优化模型为单目标非线性混合整数规划模型，主要通过调整缓冲时间实现列车运行图扰动时间之和最小，从而使列车的计划出发时刻与实际出发时刻尽可能一致。由于模型中需要输入的变量较多，直接求解具有很大难度，因此本文采用改进的遗传算法和计算机模拟的方法进行求解，其总体思路是首先将复杂的非线性规划问题通过递推公式转化为线性规划问题，然后通过迭代求最优解，当在限定的时间和迭代次数内目标函数值不再优化时，则认为得到的解为最优解或较优解。具体步骤如下。

步骤2基因设置。以列车i在区间e(j-1,j)的缓冲时间xi,j-1,j作为基因，因模型仅考虑单线单方向，则基因按顺序排列的集合(即染色体)为模型的解集{xi,j-1,j|i∈I,j∈J}。

步骤3求解优化模型。基于式(27)和遗传算法的求解特点，优化模型又可写为

(28)

步骤4最优解。在限定的时间或迭代次数内，最优解已收敛且不能更优，则找到最优解的解集{xi,j-1,j,i∈I,j∈J}，运算终止。

4　算　例

北京市城市轨道交通房山线共设有10个车站，列车的技术参数见表1，区间集E的运营参数见表2所示，下行客流OD的到达规律见表3，车站集J中各列车的实际停站时间见表4。选取1 h的研究时段并且针对γ1和γ2取不同值的3个算例，利用Matlab对问题进行描述，并根据本文模型和算法对该线下行列车的运行图进行鲁棒性优化，优化结果见表5。对表5中数据进行绝对值求和，得到表6。

表1　列车技术参数

表2　区间集E的运营参数

表3　下行客流OD的到达规律　人·s-1

表4　列车在各站停站时间　s

由表5和表6可得出以下结论：

(1)算例1表明模型对发车晚点和发车提前的惩罚一致，列车运行图鲁棒性可恢复时间(以下简称：可恢复时间)最短，为209 s，计划运行的总时间为2 971 s；

(2)算例2表明模型对发车晚点的惩罚小于发车提前，可恢复时间最长，为253 s，但计划运行的总时间最短，为2 951 s；

(3)算例3表明模型对发车晚点的惩罚大于发车提前，可恢复时间为231 s，但计划运行的总时间最长，为3 053 s。

表5中的计算结果可直接转化为该线的列车运行图或列车时刻表形式。例如，假设列车在始发站(郭公庄站)的出发时刻为15:30:00，则列车时刻表见表7。

表5　优化结果　s

表6　列车运行图鲁棒性恢复时间　s

表7　列车时刻表

5　模型的扩展

在城市轨道交通列车运行时段内，可能出现无法保证在每个车站都能准点发车的情况。当运营部门只要求大型枢纽站等重要车站准点发车即可时，本文在既有模型的基础上，提出“时间控制点法”来实现指定车站发车准点的目标，以提高规定区段内的列车运行图鲁棒性。

时间控制点法的思想是在计划层同时间轴条件下引入虚拟层，如图2所示。虚拟层每个时间控制点对应准点率要求高的车站，时间控制点对应的车站集合R⊂J，旨在形成时间控制点区段内包含多个区间的形式，即列车在时间控制点间的运行时间等于列车在多个区间运行的时间之和。

图2　时间控制点示意图

表8　时间控制法的求解结果 s

6　结束语

本文以城市轨道交通列车运行图扰动时间之和最小化为目标，构建了城市轨道交通列车运行图鲁棒性优化模型，通过改进的遗传算法对问题进行求解。通过模型分析发现，不同惩罚参数的取值对列车运行图鲁棒性的影响较大，需根据实际问题对参数进行标定。以北京市城市轨道交通房山线为例，优化后的列车运行图有效缩短了总扰动时间，证明了本文方法能够有效提高列车运行图的鲁棒性。

本文还扩展了城市轨道交通列车运行图鲁棒性优化模型的应用场景，引入时间控制点变量，可实现约束不变的情况下，提高指定车站发车准点率的目标，优化规定区段内的列车运行图鲁棒性。

[1]TAKEUCHI H, GOODMAN C, SONE S.Moving Block Signaling Dynamics: Performance Measures and Re-Starting Queued Electric Trains[J]. IEE Proceedings on Electric Power Applications, 2003, 150(4)：483-492.

[2]汪波, 韩宝明, 战明辉, 等. 城市轨道交通网络周期运行图编制研究[J]. 铁道学报, 2013, 35(4): 9-15.

(WANG Bo, HAN Baoming, ZHAN Minghui，et al. Study on Formulation of Periodic Train Diagram of Urban Rail Transit Network[J]. Journal of the China Railway Society, 2013, 35(4): 9-15. in Chinese)

[3]聂磊, 张渊, 武鑫. 计算机编制周期性列车运行图关键技术[J]. 中国铁道科学, 2014, 35(1): 114-121.

(NIE Lei, ZHANG Yuan, WU Xin. Key Technologies for Computer Generation of Cyclic Train Timetable[J]. China Railway Science, 2014, 35(1): 114-121. in Chinese)

[4]江志彬, 徐瑞华, 吴强, 等. 计算机编制城市轨道交通共线交路列车运行图[J]. 同济大学学报:自然科学版, 2010, 38(5): 692-696.

(JIANG Zhibin, XU Ruihua, WU Qiang, et al. Shared-Path Routing Timetable Computer Designing in Rail Transit System[J]. Journal of Tongji University:Natural Science, 2010, 38(5): 692-696. in Chinese)

[5]周文梁,史峰, 陈彦,等. 客运专线网络列车开行方案与运行图综合优化方法[J]. 铁道学报, 2011, 33(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, 33(2):1-7. in Chinese)

[6]刘敏, 韩宝明. 列车运行图可恢复鲁棒性优化模型[J]. 铁道学报, 2013, 35(10):1-8.

(LIU Ming, HAN Maobing. Recoverable Robust Timetabling Models for Railways[J]. Journal of the China Railway Society, 2013, 35(10):1-8. in Chinese)

[7]YAN Y, MENG Q, WANG S, et al. Robust Optimization Model of Schedule Design for a Fixed Bus Route[J]. Transportation Research Part C: Emerging Technologies, 2012, 25: 113-121.

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

(DENG Lianbo, ZENG Qiang, GAO Wei, et al. Research on Train Plan of Urban Rail Transit with Elastic Demand[J]. Journal of the China Railway Society, 2012, 34(12):16-25. in Chinese)

[9]WANG Y, DE S B, VAN D B T J J, et al. Efficient Bilevel Approach for Urban Rail Transit Operation with Stop-Skipping[J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(6):2658-2670.