考虑线网可达性的城市轨道交通末班车时刻表优化

温芳，柏赟，李宁海，陈垚，陈绍宽，辛俊鹏

考虑线网可达性的城市轨道交通末班车时刻表优化

温芳，柏赟，李宁海，陈垚，陈绍宽，辛俊鹏

(北京交通大学 交通运输学院，北京 100044)

城市轨道交通线网的OD(出行起讫点)可达性在运营结束前时段逐渐下降，提高该时段的线网关键OD可达性可以让更多乘客在城市轨道交通系统内完成出行，有助于提升服务水平。将运营结束前时段划分为多个极小的时间间隔，在考虑运营结束延迟惩罚的基础上构建以提高时段内各间隔起始时刻的关键OD可达对数之和为目标的数学模型，优化各线路末班车的发车时刻。针对上述模型，采用最短路算法计算OD间是否可达并设计遗传算法求解末班车发车时刻。以武汉地铁为例，分析表明：在各线路发车时刻延迟总量不到15 min的前提下，可使运营结束前时段关键OD可达对数增加7.86%；在最晚发车时刻不延迟的情况下，也可使运营结束前时段关键OD可达对数增加1.37%。进行最晚发车时刻灵敏度分析，通过对比不同程度地延迟最晚发车时刻对线网关键OD可达性影响幅度的分析，可以为合理地制定末班车时刻表提供依据。

城市轨道交通；末班车；时刻表；发车时刻；OD可达性

随着城市轨道交通线网规模的扩大，大部分乘客在出行过程中需要在不同线路之间换乘。在运营结束前时段，如果部分线路之间的末班车时刻表无法有效衔接，乘客换乘失败会导致其不能通过城市轨道交通方式直接到达目的地。因此，有必要对不同线路之间的末班车时刻表进行协调优化，让更多的末班车乘客能成功抵达目的地。近年来，末班车时刻表的衔接优化是一个较为热门的研究问题。罗钦等[1]构建了轨道交通网络动态可达性的衔接模型，定义了完全可达、条件可达和不可达3个层次。康柳江等[2−7]以换乘站换乘成功方向数最大化为优化目标，构建了城市轨道交通网络末班车时刻表优化模型，并设计遗传算法求解。陈垚等[8]提出了地铁末班车最短路算法，该算法可以求解乘客从起点站出发成功到达终点站所需的最晚出发时刻及出行方案。CHEN等[9]且通过延长换乘站停站时间，建立了以换乘成功客流量最大为目标的时刻表优化模型。杜婷婷[10]采用Dijkstra算法搜索运营结束前时段可达路径。周玮腾等[11]设计并实现了城市轨道交通大规模网络条件下的时变短路径搜索算法。姚恩建等[12]提出了城市轨道交通动态可达性指标及其量化方法，对广州地铁的动态和静态可达性进行了评价。徐瑞华等[13−14]从多线换乘接续的可达性和合理性两方面构造多向列车换乘衔接模型，根据早晚间客流特点建立了首末班列车发车时间域的计算方法。胡智敏[15]对末班车客流及乘客行为进行了分析，指出在停站时间不延长的情况下不能同时实现同一换乘站所有方向的换乘衔接。对于乘客而言，能否在运营结束前成功到达目的地是至关重要的。现实中，乘客在一次出行中可能需多次换乘，只有同一出行路径的多次换乘均成功才能使乘客抵达目的地。既有研究仅对不同换乘站的换乘成功方向数或客流数进行简单相加作为优化目标，未考虑乘客的完整出行过程，不能最大化运营结束前时段的OD可达性。本文将运营结束前时段划分为多个极小的时间间隔，以时段内各间隔起始时刻的关键OD(由运营商根据客流或特殊OD的可达性需求来确定，本文视为已知条件)可达对数之和最大为目标优化各线路的末班车发车时刻。考虑到推迟末班车发车时刻会给运营公司造成损失，为此，本文模型的优化目标考虑了收车时刻延迟的惩罚，以综合优化线网可达性和收车时刻，利用遗传算法求解最优的地铁末班车时刻表。

1 问题描述

随着城市轨道交通线网规模不断扩大，不少乘客需要通过换乘抵达目的地。在运营结束前时段，如果部分线路之间的末班车时刻表无法有效衔接，会导致大量乘客无法通过城市轨道交通直接抵达目的地。本文旨在对不同线路之间的末班车时刻表进行协调优化，让更多末班车乘客能成功抵达目的地。

对于只需换乘一次的乘客而言，能否抵达目的地取决于该乘客在换乘站的换乘富余时间。如图1所示，换乘富余时间为换入线路末班车的出发时刻与换出线路的末班车乘客到达换乘站台的时刻之差。若乘客步行至站台的时刻不晚于末班车发车时刻，则换乘富余时间大于0，乘客换乘成功；否则，乘客到达站台过晚，换乘富余时间小于0，则换乘失败。

图1 换乘过程示意图

对于需多次换乘的乘客而言，单次换乘成功不能保证乘客成功抵达目的地。如图2所示的OD对，只有在S1和S2站都换乘成功时，OD可达；在S1或S2换乘失败，则OD不可达。

OD可达性与各线路的列车时刻表有关。以只需换乘一次的OD为例(如图3所示)，乘客从O站出发，能否成功抵达D站，取决于S站的换乘富余时间是否大于0。换乘走行时间一般受车站设计限制难以调整，而列车到站时刻和换入线路列车的出发时刻是可变的，决定于列车运行图。在运行图编制中，列车停站时间和区间运行时间一般取固定标尺。因此，本文假设各线列车的停站时间和区间运行时间固定不变，仅对各线路列车在首站的出发时刻进行调整。图3中，推迟线在S1站的发车时刻或提前′线在S2站的发车时刻，可以增大S站换乘富余时间，使乘客成功抵达D站。

图2 2次换乘示意图

图3 2线交叉换乘示意图

在运营结束前时段，线网OD可达性随着时间的推移下降至0。从乘客角度出发，运营结束前时段内关键OD可达性下降地越慢，线网的可达性越好，乘客抵达目的地的成功率越高。因此，本文将运营结束前时段划分为多个极小的间隔，通过调整末班车时刻表使各间隔起始时刻的关键OD可达数之和最大。为了更加准确地刻画运营结束前时段关键OD可达对数，以及反映更为真实细致的线网关键OD可达性的下降过程，模型以末班车时刻表的最小单位为时间间隔。

尽管调整末班车首站发车时刻可以提高运营结束前时段的关键OD可达性，但首站发车时刻延迟会导致收车时刻延后，增加车站电费、员工工资等运营成本。为此，末班车时刻表优化应综合考虑乘客需求和运营成本。本文以运营结束前时段内各间隔起始时刻的关键OD可达对数之和与各列车收车延迟罚值的差值最大为目标，优化各线路末班车在首站的发车时刻。为了保证时刻表的可行性，本文在对时刻表进行优化时考虑车站发车间隔约束、发到间隔约束、最晚发车时刻约束等。

运营商所允许的最晚发车时刻对末班车时刻表优化有直接的影响。本文案例将进行最晚发车时刻灵敏度分析，对比不同最晚发车时刻下线网关键OD可达性和罚值，分析最晚发车时刻对目标函数的影响，可以为运营商制定末班车时刻表提供 依据。

2 模型

2.1 变量定义

2.2 模型假设

1) 列车区间运行时间和停站时间固定不变。

2) 运营结束前时段的时刻表已知，且除末班车之外，其他列车时刻表固定不变。

3) 假设不同乘客的换乘走行时间相同。在运营结束前时段，乘客异质性较小，走行时间波动较小。

4) 各线路末班车发车时刻可在一定范围内调整，但不晚于事前设定的最晚发车时刻。

5) 关键OD对由运营商根据客流需求和行政要求来决定，本文视为已知。

2.3 优化目标

模型优化目标为，运营结束前时段内各间隔起始时刻的关键OD可达对数之和与各列车收车延迟罚值的差值最大，如式(1)所示。

列车收车延迟量t为优化时刻表和初始时刻表中线路发车时刻的差值。当优化时刻表发车时刻提前时，列车收车延迟量t为0，如式(2)所示。

一个OD出行路径中可能需要多次换乘，只有同一出行路径的多次换乘均成功才能使OD可达。换乘过程能否成功取决于换乘站的换乘富余时间。换乘富余时间为换入线路列车的出发时刻与换出线路列车到站时刻、乘客换乘走行时间之差，如式(4)所示。

列车在中间站的到发时刻可以由首站发车时刻、区间运行时间和停站时间确定，如式(5)和(6)所示。

由于站间运行时间、停站时间固定，因此末班车在首站发车时刻延迟量等于收车时刻延迟量。

2.4 约束条件

为保证区间行车安全，末班车与次末班车的发车间隔应大于等于最小发车间隔；为保证车站作业安全，在同一车站，末班车到站时刻与次末班车的发车时刻的间隔应大于等于最小发到间隔。

考虑到列车在车辆段的夜间作业要求，应避免线路过晚结束运营。由于列车运行过程中停站时间、运行时间固定，末班车在线路终点站的到站时刻取决于末班车的发车时刻。因此，当末班车发车时刻早于最晚发车时刻时，末班车可在最晚运营时刻前到达终点站。

由于推迟末班车的发车时刻会使运营公司收车时刻变晚，增加运营公司的成本。因此，为避免优化时刻表给运营公司带来较大损失，优化时刻表各线路收车总延迟时间应小于运营公司设定的最大值。

3 求解算法

末班车时刻表优化问题为NP难问题[2]，上述模型决策变量个数为，具有决策变量多、解的空间范围大的特点(为线网中线路数)。

3.1 遗传算法

3.2 最短路算法

模型中的式(3)需要计算指定时刻下，线网中指定的O和D之间是否可达。CHEN等[9]提出了地铁运营结束前时段最短路算法，能够得到乘客从起点站成功到达终点站可行的最晚出发方案。通过比较最晚出发时刻和指定时刻，即可确定某一时刻指定O和D之间是否可达。算法的具体内容如下。

算法具体步骤如下。其中，表示起点站，表示终点站，(,,)表示(,)方向倒数第辆车在站的出发时刻，(,)表示节点指向的弧，(,)表示(,)的标记值，(,)表示(,)的父代路径，是所有从重要节点出发的弧的集合。

图4 遗传算法流程图

步骤1 初始化：将与在相同线路且指向的弧标记，标记值为该线路末班车在对应站点上的出发时刻。其余弧的标记值为0。

步骤3 更新永久标记点：将集合HP中(,)最大的弧(*,)删去，起始节点*永久标号；

4 案例分析

本文以武汉地铁为对象进行案例分析。武汉地铁网络由5条线路组成，共有12个换乘站，134个车站。由于运营结束前时段主客流方向为出城方向，为简化问题，案例结合实际客流数据，选择线网中心的6个换乘站为关键起点站，线网外围的29个站点为关键终点站，考虑174个关键OD对的可达性。线网如图5所示，红点表示起点站，绿点表示终点站。

图5 武汉地铁网络示意图

4.1 现行时刻表

现行时刻表末班车首站发车时刻如表1所示，大多数线路的发车时刻统一设置为22:30。

表1 现行时刻表末班车首站发车时刻

现行时刻表中，运营结束前时段关键OD可达对数之和为8 739，其关键OD可达对数随时间变化如图6所示。可以看出，现行时刻表下，22:20开始出现不可达的关键OD对，22:52开始可达性小于50%，所有关键OD均不可达时刻为23:14。

4.2 优化结果

优化时刻表末班车发车时刻如表2所示。优化时刻表中，运营结束前时段关键OD可达对数之和为9 426，线路发车延迟时间之和为14 min。其关键OD可达对数随时间变化如图6和表3所示。优化时刻表下，22:20开始出现不可达的关键OD对，22:57开始可达性小于50%，所有关键OD均不可达时刻为23:16。优化时刻表的目标函数值为9 202，目标函数优化效果为5.80%。运营结束前时段关键OD可达对数之和为9 426，增加了7.86%。

从图6可以看出，优化时刻表下的线网可达性明显高于现行时刻表。即优化后的时刻表，网络可达性下降速度相比原时刻表更慢，乘客在同一时刻下可到达的站点相比原时刻表的更多，表明模型的优化效果好。

表2 优化时刻表末班车首站发车时刻

表3 现行、优化时刻表的关键OD可达性对比

图6 现行、优化时刻表可达性对比

4.3 最晚发车时刻灵敏度分析

末班车最晚发车时刻约束的上限T会直接影响时刻表的优化效果。分析该参数对时刻表优化效果的影响，可以为运营公司选择各线路的收车时刻提供依据。

仍以武汉地铁网络为对象，且关键OD的选择、运营结束前时段的范围、现行时刻表以及目标函数的计算方法与前文案例相同，通过调整运营商所允许的最晚发车时刻T，分析不同T取值下目标函数的优化效果，结果如表4所示。其中，∆ T的含义为，与现行时刻表的最晚发车时刻22:32相比，优化时刻表最晚发车时刻变化量。

表4 最晚发车时刻灵敏度分析

可以看出，随着地铁网络末班车最晚发车时刻的推迟，目标函数优化效果逐渐增强。但二者并不是严格正相关的，当最晚发车时刻推迟到22:34，目标函数优化效果不再增加。这是因为过度推迟末班车发车时刻会给运营公司带来较大的损失，抵消了推迟发车时刻所增加的关键OD可达对数。因此，末班车最晚发车时刻存在最优值，可以通过参数灵敏度分析进行确定。

5 结论

1) 模型通过对各线路末班车发车时刻的调整，可以降低运营结束前时段线网可达性的下降速度，有效提高时段内线网关键OD的可达性。

2) 推迟末班车的收车时刻可以提高运营结束前时段的线网关键OD可达性，但二者并不是严格正相关的。在实际应用中，运营公司可以进行灵敏度分析，来合理选择各线路末班车收车时刻。

[1] 罗钦, 徐瑞华, 江志彬, 等. 基于运行图的轨道交通网络动态可达性研究[J]. 同济大学学报(自然科学版), 2010, 38(1): 72−75. LUO Qin, XU Ruihua, JIANG Zhibin, et al. Dynamic accessibility of urban mass transit network based on train diagram[J]. Journal of Tongji University(Natural Science), 2010, 38(1): 72−75

[2] 康柳江. 城市轨道交通末班列车运行计划协同组织优化[D]. 北京: 北京交通大学, 2016. KANG Liujiang. Optimizing last train timetable synchronization for urban railway transits[D]. Beijing: Beijing Jiaotong University, 2016.

[3] KANG L, ZHU X, WU J, et al. Departure time optimization of last trains in subway networks: Mean-variance model and GSA algorithm[J]. Journal of Computing in Civil Engineering, 2014, 29(6): 04014081.

[4] 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: Methodological, 2015(72): 112−127.

[5] KANG Liujiang, WU Jianjun, SUN Huijun, et al. A practical model for last train rescheduling with train delay in urban railway transit networks[J]. Omega, 2015: 50.

[6] KANG Liujiang, ZHU Xiaoning. A simulated annealing algorithm for first train transfer problem in urban railway networks[J]. Applied Mathematical Modelling, 2016, 40(1): 419−435.

[7] KANG Liujiang, MENG Qiang. Two-phase decomposition method for the last train departure time choice in subway networks[J]. Transportation Research Part B, 2017(104): 568−582.

[8] 陈垚, 柏赟, 冯旭杰, 等. 基于换乘站停站时间延长的城市轨道交通末班车时刻表优化[J]. 交通运输系统工程与信息, 2017, 17(6): 228−234. CHEN Yao, BAI Yun, FENG Xujie, et al. Last train timetable synchronization optimization on urban rail networks with dwell time extension[J]. Journal of Transportation Systems Engineering and Information Technology, 2017, 17(6): 228−234.

[9] CHEN Y, MAO B H, BAI Y, et al. Timetable synchronization of last trains for urban rail networks with maximum accessibility[J]. Transportation Research Part C: Emerging Technologies, 2019(99): 110−129.

[10] 杜婷婷. 城市轨道交通末班车条件下可达路径问题研究[D]. 北京: 北京交通大学, 2012. DU Tingting. The reachable paths finding problem with constrain of last trains in urban mass transit network[D]. Beijing: Beijing Jiaotong University, 2012.

[11] 周玮腾, 韩宝明. 城市轨道交通网络时变路径搜索算法[J]. 北京交通大学学报, 2017, 41(4): 115−122. ZHOU Weiteng, HAN Baoming. Temporal path searching algorithm of urban rail transit network[J]. Journal of Beijing Jiaotong University, 2017, 41(4): 115−112.

[12] 姚恩建, 刘文婷, 刘莎莎, 等. 基于动态可达性的城轨末班车时刻表优化[J]. 华南理工大学学报(自然科学版), 2018, 46(1): 58−65. YAO Enjian, LIU Wenting, LIU Shasha, et al. Optimizing last train timetable for urban rail transit based on dynamic accessibility[J]. Journal of South China University of Technology (Natural Science Edition), 2018, 46(1): 58− 65.

[13] 徐瑞华, 李璇. 城市轨道交通网络末班车衔接方案的综合优化[J]. 同济大学学报(自然科学版), 2012, 40(10): 1510−1516. XU Ruihua, LI Xuan. Comprehensive optimization for connection scheme of last trains in urban mass transit network[J]. Journal of Tongji University (Natural Science), 2012, 40(10): 1510−1516

[14] 徐瑞华, 张铭, 江志彬. 基于线网运营协调的城市轨道交通首末班列车发车时间域研究[J]. 铁道学报, 2008(2): 7−11. XU Ruihua, ZHANG Ming, JIANG Zhibin, et al. Study on departure time domain of the first and last trains of urban mass transit network based on operation coordination[J]. Journal of the China Railway Society, 2008(2): 7−11.

[15] 胡智敏. 城市轨道交通末班车时刻表协调优化方法研究[D]. 北京: 北京交通大学, 2015. HU Zhiming. Research on last-train timetables coordination and optimization method in urban rail transit[D]. Beijing: Beijing Jiaotong University, 2015.

Timetable synchronization of last trains in urban rail systems to maximize network accessibility

WEN Fang, BAI Yun, LI Ninghai, CHEN Yao, CHEN Shaokuan, XIN Junpeng

(School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China)

In urban rail transit, the accessibility of the key ODs gradually decreases during the period before the service closure. Promoting the accessibility of the key ODs (origin and destination) in metro network before the service closure benefits to improving the service level. A programming model was proposed to optimize the departure time of the last trains on different metro lines. The objective was to maximize the number of accessible key ODs in metro network, while the timetable adjustment kept minimal. To solve the proposed model, the shortest path algorithm was applied to compute the accessibility of each OD, and the genetic algorithm was employed to find the optimal departure time of the last train for each line. The case studies on Wuhan metro network indicates that, under the premise that the total delay time of each line was less than 15 minutes, the number of accessible key ODs before the service closure increased by 7.86% with the optimized timetable, in comparison with the practical timetable, and without any delay on service closure time, the number of accessible key ODs before the service closure still grew by 1.37%. Finally, the sensitivity analysis was carried out to investigate the influence of different service closure time on the accessibility of the key ODs in the network, which provided a basis for the rational selection on the service closure time of different metro lines.

urban railway transit; last train; timetable; departure time; OD accessibility

U239.5

A

1672 − 7029(2019)06− 1569 − 08

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

2018−08−24

国家自然科学基金资助项目(71621001, 71571016)；中央高校基本科研业务费专项资金资助项目(2018JBM025)

柏赟(1985−)，男，湖南祁阳人，副教授，博士，从事城市轨道交通运输组织研究；E−mail：yunbai@bjtu.edu.cn

(编辑 蒋学东)