基于排队论的地铁列车运行自动调整优化模型

宁正，牛宏侠，张肇鑫

基于排队论的地铁列车运行自动调整优化模型

宁正1, 2，牛宏侠1, 2，张肇鑫1, 2

(1. 兰州交通大学 自动控制研究所，甘肃 兰州 730070；2. 甘肃省高原交通信息工程及控制重点实验室，甘肃 兰州 730070)

针对乘客到达时间分布不均衡对列车晚点调整的影响，既有研究中的列车自动调整模型未涉及在动态变化的客流输入下，对行车间隔和停站时间进行优化的问题，通过引入排队理论研究客流变化和行车间隔与停站时间的关系。基于休假排队模型获得调整过程中候车乘客平均排队长，并以此为基础建立以减少列车晚点时间和提高列车运输量为目标函数的优化模型。根据候车排队长优化停站时间，运用线性递减权重粒子群算法进行求解。研究结果表明：与仅减小晚点时间的模型相比，本文提出的方法可以能在吸收晚点的过程中提高交通系统的运行效率。

运行自动调整；运行效率；排队理论；地铁列车；客流不均衡；列车晚点

城市轨道列车在运输组织中，易受客流波动和设备失效等随机因素的干扰造成列车晚点。作为一种短途出行的公共交通工具，地铁列车不仅具有干线铁路列车按图运行的规律性特点，还具有公共交通工具服务机制应与客流变化规律相协调的特点。但随着客流的高速增长和网络负荷能力的日趋紧张，客流的状态与变化趋势已经成为列车运行调整需要考虑的关键因素。因此，从新的角度下考虑列车运行自动调整问题，是实现列车全自动化驾驶与智能化运行的重要研究方向之一。列车运行调整的模式一般主要有4种，包括自动调整模式、人工调整模式、人工调度模式和全人工模式。其中，自动调整模式是调度自动控制的最高级别。当列车出现较小范围内的运行偏离情况时，列车自动调整子系统(ATR)可以通过不断地对比计划时刻表和实际运行时刻，调整列车到站和出站时间，通过对列车自动驾驶系统(ATO)设置列车运行等级而调整晚点时间[1]。现有文献对于列车晚点调整的研究主要有2个方面，一方面从人工调整的角度出发，优化列车运行图缓冲时间和列车开行方案或列车行车均衡性，或者通过建立分布式调整方案，解决地铁网络下的换乘问题[2−6]。但此类研究需要在铺画运行图之前完成，无法满足当列车在运行过程中发生小范围晚点，系统自动调整的实时性要求；另一方面从列车运行的角度出发，多以列车晚点时间最短，列车晚点数目最少等为目标函数，建立列车自动调整优化模型[7−10]，但此类方法不能在吸收晚点过程中同时优化地铁系统的运营效率。目前的运行调整模型，无论在人工调整还是自动调整方面，均未研究在动态变化的客流输入与行车间隔调整及列车停站时间改变的影响下，站台候车乘客排队队长的变化规律。可见考虑客流变化的地铁列车运行调整尚在初步探究阶段。本文针对地铁列车运行晚点问题，引入排队理论研究客流变化和行车间隔与停站时间的相互影响。分析客流在系统中的输入，基于纯限量服务休假模型获得调整过程中候车乘客平均排队长，并以此为基础建立了减少列车晚点时间和提高列车运输量的多目标优化模型，并优化停站时间，最后运用线性递减权重粒子群算法进行求解。

1 地铁列车候车排队系统设计

排队论是在研究各种排队系统概率规律性的基础上，解决相应排队系统最优设计和最优控制的问题。一般排队系统都有输入过程、服务规则和服务台3个组成部分[11]。由于地铁列车双线单方向的运行特点，列车到达一次提供一次服务，为单服务台等待制服务。

1.1 候车系统排队过程

将列车停车时间抽象为服务时间，列车行车间隔抽象为休假时间的平均值()。则地铁列车服务过程是一个纯限量服务休假排队模型，即每提供一次服务就进入休假状态的单重休假系统。利用该模型可以描述调整时间内顾客到达的平均排队长()与列车行车间隔()以及停站时间的关系，可以在停站时间内最大吸收排队顾客的目标下，优化列车行车间隔时间。根据文献[12]不加推导地给出等待顾客的平均队长()与列车行车间隔以及停站时间的关系为：

1.2 客流输入分析

2 自动调整模型建立

列车运行自动调整就是列车运行发生晚点时，在一定约束下，利用运行图的冗余时间调整列车在各车站的实际到站和出站时间的多目标优化问题。

2.1 优化目标

图1 与列车行车间隔E(V)以及客流到达率λ的关系图

用实际到发时间表示服务时间为：

用实际到发时间表示行车间隔即休假时间为：

将式(3)，(4)和(5)式代入式(1)，候车系统的顾客平均排队长表示为：

考虑变化客流的影响，以最小停站时间顾客吸收数最多为依据的目标函数为：

用各列车在各车站实际到站晚点时间与实际出站晚点时间的总和表示，列车总晚点时间最短的目标函数为：

将双目标线性加权，则列车运行调整的总目标函数为：

其中：1和2是分目标在总目标中所占的权重系数。运行调整时，列车晚点最少和交通运行效率均需权衡考虑，所以本文以2个目标等权重同时优化，取2=0.4，1=0.5。

2.2 停站时间优化下的约束条件

2.2.1 系统平衡条件约束

2.2.2 区间运行时间约束

2.2.3 列车追踪时间约束

2.2.4 附加停站时间约束

在运行调整过程中，在缩短列车晚点的基础上要考虑最大程度的吸收客流，当最小停站时间内不能完全吸纳客流时，要增加附加停站时间。假设客流是匀速上车，每个人所需的服务时间为，s/人，则附加停站时间为：

2.3 评价指标

3 仿真实验

3.1 模型求解算法

在粒子群算法可调参数中，惯性权重较大时有利于全局搜索，较小时利于进行精确的局部搜索，因此针对PSO算法后期易在全局最优附近产生振荡的现象，采用线性变化的权重[15]，随算法迭代次数的变化公式为：

其中：max和min分别表示的最大值和最小值；为当前迭代次数，max为最大迭代步数。本模型中取max=0.9，min=0.4。

为了提高算法的求解速度，初始化时需要限制微粒矩阵满足停站时间、行车间隔以及停站时间的约束，选取无量纲处理后的总目标函数为适应度函数。由于求解问题的复杂性，取种群个数为200，学习因子1=2=2。算法基本流程如图2所示。

3.2 算例

案例采用某地铁线路的运行数据和MATLAB仿真平台，对获取得到晚点信息的列车进行调整，然后对调整后所输出的数据进行验证。该线路车站数目14个，开行列车数10个，选取客流影响程度较高的早高峰8:00~9:00为研究时段，该时段内的列车追踪冗余时间是30 s，计划停站时间是35 s，最小停站时间是30 s，最大停站时间为35 s，高峰小时内顾客在站台的平均到达率是0.05人/s，调整时间内的客流到达率在平均到达率邻域内取值。顾客乘车所需的平均时间为0.7 s/人，其余一些基本运行参数，如表1所示。

假设列车运行过程中由于随机因素的干扰，自动调整模块识别到10104次列车到达A站时晚点了100 s，采用本文提出的列车运行调整模型计算，可以在14 s内输出调整后的结果，受影响的车次调整后的列车时刻表和计划时刻表对比如表2所示。

图2 粒子群算法求解流程图

表1 运行调整模型基本参数

表2 调整后时刻表与原始时刻表对比

注：斜体表示调整后的时间。

表2中斜体表示调整后的时间，由于10104次列车在A站晚点，到达D站才充分吸收晚点，并连带影响了后续车辆，使10107次列车在C站吸收晚点。初始晚点时由于2车次到站时间过长候车人数过多，模型主要缩短了晚点时间。而在调整晚点的连带晚点影响的车辆时，同时考虑乘客到达率变化的影响，调整了行车间隔时间，避免晚点初期车辆吸收过多顾客造成车内拥挤。

为比较本文模型优化效果，本文建立了仅考虑吸收晚点的自动调整模型。晚点调整中的停站时间为最小停站时间，其对比结果如表3所示。

仅缩短列车晚点时间模型中，列车在晚点初期为了减小晚点时间会以最短时间运行，到调整后期逐渐增大行车间隔。横向对比相邻车次在不同车站的到站间隔时间，初始晚点的车辆在2个模型均以最小间隔时间进行调整，后期本文提出优化模型根据不同客流到达调整了行车间隔。纵向对比在同一站相邻的车次到站的时间间隔，该优化模型在顾客到达率较小时延长了行车间隔，顾客到达率增大时缩短了行车间隔。

考虑客流吸收的列车调整模型在优化行车间隔的同时还根据站台等待顾客数延长了停站时间，与仅缩短晚点时间调整模型的停站时间对比如表4所示。

表3 不同顾客到达率下的行车间隔时间对比

优化模型均以最小停站时间内吸收的顾客数调整了10106和10107次列车的行车间隔，并计算的停站时间。实际调整过程中当10107次列车到达B和C 2站时小于计划运行时刻时，列车运行自动调整模块终止了调整，实际列车停站时间为35 s，所以出现了偏差。与普通模型相比，虽然优化模型总晚点时间增加了26%，但是行车空闲率降低了20.6%。尽管总晚点时间越长，列车实际行驶时分与计划运行图的偏离程度越高，但是由于地铁系统在优化过程中需首先考虑满足客流需求，优化模型平衡了列车调整中吸收晚点与吸纳客流之间的关系，提高了交通系统效率。

表4 不同模型下的停站时间及停站时间空闲率对比

4 结论

1) 考虑乘客到达的变化与行车间隔时间对平均排队长的相互影响，设计了基于纯限量服务休假模型的地铁列车候车排队系统，研究行车间隔与站台候车顾客数的数学关系。

2) 建立列车晚点调整的多目标优化模型，并增加了附加停站时间。该模型能在顾客到达较多时，缩短行车间隔来减少等候服务的顾客数，并能通过延长停站时间增加吸收的等待顾客数。当休假时间内顾客到达数较少时，能延长行车间隔，在吸收晚点时间的同时，分散吸收客流，避免较多客流在同一列车内拥挤。

3) 通过粒子群算法验证了该模型的可行性，其能在14 s内求解得出调整后的运行时刻表，符合自动调整对于时间效率性的要求。仿真结果表明优化模型能根据客流变化调整行车间隔，与仅调整列车晚点时间的自动调整模型相比，本文提出的模型在减少列车晚点的同时，使停站时间行车空闲率降低了20.6%，提高了交通系统的运行效率。

[1] 徐金祥. 城市轨道交通列车运行自动控制技术[M]. 北京: 中国铁道出版社, 2013. XU Jinxiang. Urban rail transit train operation automatic control technology[M]. Beijing: China Railway Press, 2013.

[2] 柏赟, 陈垚, 陈玥, 等. 考虑列车总晚点和到发均衡性的地铁列车运行调整方法研究[J]. 交通运输系统工程与信息, 2014, 14(3): 104−110. BAI Yun, CHEN Yao, CHEN Yue, et al. Rescheduling of metro train timetable for delay reductionand equilibrium of trains’ arrival and departure[J]. Journal of Transportation Systems Engineering and Information Technology, 2014, 14(3): 104−110.

[3] 赵宇刚, 毛保华, 蒋玉琨. 基于列车运行时间偏离的地铁列车运行图缓冲时间研究[J]. 中国铁道科学, 2011, 32(1): 118−121. ZHAO Yugang, MAO Baohua, JIANG Yukun. Study on the buffer time of metro train diagram based on train running time deviation[J]. China Railway Science, 2011, 32(1): 118−121.

[4] 王媛媛, 倪少权. 城市轨道交通大小交路模式列车开行方案的优化[J]. 铁道学报, 2013, 35(7): 1−8. WANG Yuanyuan, NI Shaoquan. Optimization of train schedules of full-length and short turn operation modes in urban rail transit[J]. Journal of the China Railway Society, 2013, 35(7): 1−8

[5] LING X, WANG D C, LI K P, et al. A green train scheduling model and fuzzy multi-objective optimization algorithm[J]. Applied Mathematical Modeling, 2013, 37(4): 2063−2073.

[6] LI Shukai, ZHOU Xuesong, YANG Lixing, et al. Automatic train regulation of complex metro networks with transfer coordination constraints: A distributed optimal control framework[J]. Transportation Research (Part B), 2018(117): 228−253.

[7] CHANG S C, CHUNG Y C. From timetabling to train regulation-a new train operation model[J]. Butterworth- Heinemann, 2005, 47(9): 575−585.

[8] 吴洋, 罗霞. 一种晚点地铁列车实时调整策略及其动态速控模式[J]. 中国铁道科学, 2005, 26(6): 113−118. WU Yang, LUO Xia. Tactic for real-time operation adjustment and correspo-nding dynamic velocity control mode for delayed metro trains[J]. China Railway Science, 2005, 26(6): 113−118.

[9] 卢稳, 朱爱红, 宋丽梅. 城市轨道交通列车运行过程的多目标优化研究[J]. 铁道标准设计, 2017, 61(2): 131− 135. LU Wen, ZHU Aihong, SONG Limei. Multi-objective optimization of train operation process of urban rail trainsit[J]. Railway Standard Design, 2017, 61(2): 131− 135.

[10] Seles P, Dewilde T, Cattrese D, et al. Reducing the passenger travel time in practice by the automated construction of a robust railway timetable[J]. Transport (Part B) Methodol, 2016(81): 124−156.

[11] 何选森. 随机过程与排队论[M]. 长沙: 湖南大学出版社, 2010. HE Xuansen. Random process and queuing theory[M]. Changsha: Hunan University Press, 2010.

[12] 田乃硕. 休假随机服务系统[M]. 北京: 北京大学出版社, 2001. TIAN Naishuo. Vacation random service system[M]. Beijing: Beijing University Press, 2010.

[13] 蔡昌俊, 姚恩建, 张永生, 等. 基于AFC数据的城轨站间客流量分布预测[J]. 中国铁道科学, 2015, 36(1): 126−132. CAI Changjun, YAO Enjian, ZHANG Yongsheng, et al. Forecasting of passenger flow’s distribution among urban rail transit station based on AFC data[J]. China Railway Science, 2015, 36(1): 126−132.

[14] 胡路. 考虑稳定性的城市轨道交通车站交通服务设施系统优化配置理论与方法[D]. 成都: 西南交通大学, 2014: 135−137. HU Lu. The optimization theory and method for configuration of transportation facilities in urban rail trainsit station with consideration of stability analysis[D]. Chengdu: Southwest Jiaotong University, 2014: 135−137.

[15] DONG C, WANG G, CHEN Z, et al. A method of self-adaptive inertia weight for PSO[C]// International Conference on Computer Science and Software Engineering. IEEE, 2008: 1195−1198.

Automatic operation regulation optimization model of metro train based on queuing theory

NING Zheng1, 2, NIU Hongxia1, 2, ZHANG Zhaoxin1, 2

(1. Automatic Control Institute, Lanzhou Jiaotong University, Lanzhou 730070, China; 2. Gansu Provincial Key Laboratory of Traffic Information Engineering and Control, Lanzhou 730070, China)

Considering the impact of uneven arrival time distribution of passengers on train delay adjustment, the automatic train adjustment model in existing studies are little involve the optimization of train interval and stop time under the dynamic change of passenger flow input. The queuing theory was introduced to study the relationship among passenger flow changes and train running intervals and dwell times. Based on pure limited service action model, the train operation adjustment model with the objectives of the shortest train delay and the maximum number of passengers accommodated during the minimum dwell time was established and then optimized the dwell time. The simulation suggests that the presented method not only can reduce the delay time of the train, but also can improve the operational efficiency of transportation systems compared with the model that only reduced the time delay.

automatic train operation regulation; operation efficiency; queuing theory; metro train; unbalanced arriving passengers; train delay

U231.92

A

1672 − 7029(2019)07− 1826 − 07

10.19713/j.cnki.43−1423/u.2019.07.029

2018−10−15

甘肃省自然科学基金资助项目(1606RJZA002，1610RJYA034，17JR5RA089)；甘肃省高等学校科研资助项目(2017A-026)；甘肃省重点研发能力提升计划资助项目(2060404)

牛宏侠(1978−)，女，辽宁黑山人，副教授，从事交通信息工程与智能控制理论研究；E−mail：nhx56055@mail.lzjtu.cn

(编辑 蒋学东)