面向运营结束时段可达性的地铁末班车时刻表协调优化

2022-08-01李宁海

中国铁道科学 2022年4期

温芳，柏赟，张鑫，李宁海，陈垚

（1.北京交通大学交通运输学院综合交通运输大数据应用技术交通运输行业重点实验室，北京 100044；2.北京市交通委员会政务服务中心（北京市船舶检验所），北京 100161）

地铁时刻表协调优化是指调整线网内不同线路列车在换乘站的到发时刻，从而提高乘客换乘效率。在平常时段和高峰时段，时刻表协调优化侧重于减少乘客换乘等待时间以提升线网服务水平［1］；而在运营结束时段，各线路之间存在列车换乘衔接失效情形，导致线网服务可达性下降，乘客无法通过乘坐地铁抵达目的地［2］。因此有必要从服务可达性的角度，研究地铁末班车时刻表协调优化问题，使尽可能多的乘客通过乘坐地铁抵达目的地。

既有地铁末班车时刻表协调优化研究主要可分为2 类：第1 类侧重优化换乘站内列车换乘衔接的成功性；第2 类则优化线网OD 间乘客出行的服务可达性。在第1类换乘衔接优化研究中，文献［3—8］主要针对各线路末班车的时刻表展开研究，提高末班车乘客的换乘成功性、减少换乘等待时间；宁丽巧等［9］考虑末班车时段内的所有列车，建立了以换乘等待时间和换乘失败乘客数量最小为目标的末班车时段列车时刻表协调优化模型。然而在地铁线网内，仅优化列车换乘并不能保证到达目的地的乘客数量最多。

第2 类研究从OD 可达性角度优化末班车时刻表。Chen等［10］进一步考虑了乘客在不同线路末班车与非末班车间的换乘，以在出行起点站乘坐末班车出发的乘客（末班车出发乘客）的可达乘客数量最大为目标，优化末班车时刻表。Zhou等［11］考虑末班车出发乘客的需求，建立了基于MILP 的末班车时刻表优化模型，并采用Cplex 求解。运营结束时段内，不仅末班车出发乘客可能无法到达目的地，部分在出行起点站乘坐非末班车出发的乘客同样可能面临OD 不可达的情形。姚恩建等［12］考虑乘客在出行全过程均乘坐末班车，对线网OD 可达性进行优化。Yang等［13］考虑了部分乘坐非末班车出发乘客的需求，构建了时空网络流模型，并设计了拉格朗日松弛算法，使OD 可达的乘客数量最大；但该研究考虑运营结束时段全部客流需求，可能导致问题规模较大，难以实现高效求解。温芳等［14］建立了以运营结束时段内各时刻下可达OD对数量总和最大为目标的数学模型，但模型未考虑不同时刻的客流需求差异。这些既有研究仅选取了运营结束时段内部分客流需求（如末班车出发的客流）进行末班车时刻表优化，未详细考虑时段内所有OD 客流需求（忽略了乘坐非末班车出发的乘客），难以保证线网服务可达性最大化。

鉴于此，本文以运营结束时段所有的客流需求为导向，建立以运营结束时段内地铁网络OD 可达的乘客数量最大化为目标的末班车时刻表协调优化模型；针对时段内乘客出发时刻多、模型求解难度大的特点，设计基于预设车次的模型求解方法，求解优化的各线路末班车时刻表。

1 问题描述

1.1 参数定义

地铁网络由线路和车站组成，线路的上、下行双方向被视为2 条线路。定义参数：nl为线路数量；L为线路集合，L={li，i=1，2，…，nl}；ns为地铁网络上的车站数量；S为车站集合，S={se，e=1，2，…，ns}；nis为线路li的车站数量；Sli为线路li的车站集合，其中ei，1，ei，2，…，ei，ni

s分别对应线路各站在地铁网络车站集合S中的编号。

定义t0为运营结束时段的开始时刻，并将运营结束时段划分为间隔为δ的若干时间点，则运营结束时段可表示为集合T={t0+δ，t0+2δ，…，t0+nδδ}，nδ为时段内间隔数量。由于同一OD 间相同时刻出发的乘客可达性相同，可视为1组客流，将起点站sp∈S和终点站sq∈S组成的OD 对记为gpq；bγ为该OD间出发时刻为t的乘客组，bγ=(sp，sq，t)；运营结束时段内所有乘客组需求则可表示为集合B={bγ，γ=1，2，…，nb}，nb为乘客组数量；uγ为乘客组bγ的乘客数。

对乘客组bγ=(sp，sq，t)，其OD 对gpq间的有效路径集可表示为Rγ={rγ，k，k=1，2，…，nγr}，nγr为乘客组bγ的有效路径数量；有效路径集Rγ中，每1个有效路径rγ，k又均由若干个乘车段v组成，即乘车段vγ，k，m=(li，se，)表示乘客组在线路li的车站se乘车至车站下车，nγ，kv为路径rγ，k中的乘车段数量；和分别为乘客组bγ到达乘车段vγ，k，m起点站和终点站的时刻。某OD 对gpq间的有效路径示意图如图1所示。由图1可知，乘客组bγ=(sp，sq，t)的有效路径集Rγ包含rγ，1与rγ，2共2 条路径，分别为rγ，1={(l1，sp，s2)，(l4，s2，sq)}和rγ，2={(l1，sp，s1)，(l2，s1，s3)，(l3，s3，sq)}。

图1 OD对gpq间的有效路径示意图

运营结束时段内，线路li上的车次可表示为集合Hi={hi，j，j=1，2，…，nih}，nih为线路li上的车次数量（列车车次按出发时刻逆序排序）；和分别为线路li上的车次hi，j在沿线车站se的出发时刻和到达时刻；当se为换乘站时，为乘客组从线路li换乘至线路的换乘走行时间。

1.2 可达性分析

可达性随出发时刻不同而变化，其与OD 间有效路径的连通性直接相关。在某一时刻，若OD 间存在至少1条连通路径，则认为OD可达［15-16］。以图1中乘客组bγ=(sp，sq，t)为例，若路径rγ，1={(l1，sp，s2)，(l4，s2，sq)}或rγ，2={(l1，sp，s1)，(l2，s1，s3)，(l3，s3，sq)}连通，则OD 对gpq可达，乘客组bγ=(sp，sq，t)可以抵达目的地。路径连通的充分必要条件为：乘客组在路径中每个乘车段均能乘坐上列车。这取决于乘客在乘车段起点站的乘车富余时间，而该时间等于乘车段线路列车的出发时刻与乘客组到达站台的时刻之差。

以路径rγ，1={(l1，sp，s2)，(l4，s2，sq)}为例，其在s2站换乘的出行路径如图2所示。图2中：对于乘车段vγ，1，1=(l1，sp，s2)，乘客组bγ=(sp，sq，t)到达sp站站台的时刻早于线路l1上车次h1，1和车次h1，2在sp站的出发时刻，则该乘客组bγ在车次h1，1、车次h1，2的乘车富余时间大于0，乘客组将乘坐先到站的车次h1，2，其到达s2站的时刻为；对于乘车段vγ，1，2=(l4，s2，sq)，乘客组bγ抵达乘车段起点站s2站台的时刻等于与两线间换乘走行时间之和，再结合线路l4上各车次的发车时刻，即可判断出乘客组在乘车段vγ，1，2=(l4，s2，sq)能否顺利上车及所乘坐的车次；由此，可依次计算乘客组在所有乘车段的乘车行为，从而判断路径是否连通。

图2 出行路径示意图

2 末班车时刻表协调优化模型

2.1 模型假设

（1）假设运营结束时段的乘客异质性较低、换乘走行时间波动较小，即换乘站同一换乘方向的乘客换乘走行时间相同。

（2）OD间有效路径采取无环前K短物理路径。

（3）假设列车运力充足，不存在乘客滞留，乘客总选择乘坐最先到站的车次。

2.2 模型构建

2.2.1 决策变量

本文为提高运营结束时段内线网的OD 可达性，模型中以各线路末班车在各个车站的到达和发车时刻（，∀li∈L，se∈Sli）为决策变量。

2.2.2 约束条件

1）末班车区间运行时间和停站时间调整范围约束

设tΔ1和tΔ2为区间运行时间调整的最大值和最小值，tΔ3和tΔ4为停站时间调整的最大值和最小值，时间调整应符合实际运营要求，因此末班车在各站的到发时刻应该在调整范围之内，即

2）最大发车间隔时间约束

为保障乘客服务水平，末班车与次末班车在首站的发车间隔时间不大于最大发车间隔时间，即

3）最小发车间隔时间约束

为确保区间行车安全，末班车与次末班车的发车间隔时间不小于最小发车间隔时间，即

为保证车站作业安全，在同一车站，末班车到站时刻与次末班车发车时刻的间隔时间不小于最小发到间隔时间Iida，即

4）最晚收车时刻约束

为避免干扰夜间检修，各线路终点站的收车时刻不应晚于最晚收车时刻timax，即

2.2.3 目标函数

定义xγ为0-1 变量，表示乘客组bγ的OD 可达性，当乘客组bγ可达时取1，否则取0。模型目标函数为运营结束时段内乘客组集合B={bγ，γ=1，2，…，nb}的可达乘客总量最大化，即

2.2.4 可达性计算

1）计算可达性

定义yγ，k为0-1 变量，表示乘客组bγ的路径rγ，k是否连通，当路径rγ，k连通时取1，否则取0。若OD间存在连通的有效路径，则OD 可达，那么OD 可达的约束条件可表示为

2）计算路径连通性

定义zγ，k，m为0-1 变量，表示乘客组bγ在路径rγ，k中的乘车段vγ，k，m能否成功乘上列车，当乘客组成功乘上列车时取1，否则取0；M1为足够大的正整数。若乘客组在路径中所有乘车段均能乘坐上列车，则路径rγ，k连通，那么路径连通的约束条件为

3）计算乘车段能否乘车

定义αγ，k，m，j为0-1 变量，表示乘客组bγ在路径rγ，k的乘车段vγ，k，m（位于线路li）是否乘坐车次hi，j，若乘坐线路li上任一车次hi，j，则αγ，k，m，j=1，zγ，k，m=1；若乘客组无法乘上任一车次，则zγ，k，m=0。当有多列列车可供选择时，乘客组只可选择其中某一列车。为最大化乘客可达性，最先到站车次的αγ，k，m，j值应为1，那么乘车段能否乘车的约束条件为

4）计算乘车段乘坐车次

变量αγ，k，m，j的取值与乘客组乘坐车次hi，j的富余时间有关。对于乘车段vγ，k，m=(li，se，se′)，乘客组bγ对车次hi，j的乘车富余时间等于车次hi，j在se站出发时刻与乘客组bγ到达该乘车段起点站se的时刻之差。若乘车富余时间小于0，则αγ，k，m，j=0；否则αγ，k，m，j＞0，表示乘客组可选择乘坐车次hi，j，那么乘客组在乘车段能否乘坐某辆列车的约束条件为

5）计算乘客组在乘车段起点站到达时刻

式（12）中，若vγ，k，m为路径第1个乘车段（m=1），则乘客组bγ到达乘车段起点站站台时刻等于乘客组bγ=(spsqt)的出发时刻t；若vγ，k，m=(li，se，se″)为后续乘车段（m＞1），则乘客组到达乘车段vγ，k，m起点站se站台时刻为乘客组在上一乘车段vγ，k，m-1=(li′，se′，se)终点站se到达时刻与换乘走行时间之和。因此，乘客组在乘车段起点站到达时刻的计算式为

6）计算乘客组在乘车段终点站到达时刻

式（13）中，乘客组在乘车段vγ，k，m-1=(li′，se′，se)终点站se的到达时刻由乘坐的车次决定［10］。若乘客组在乘车段vγ，k，m-1=(li′，se′，se)乘坐的车次为hi′，j，即αγ，k，m-1，j=1，则有若乘客组无法乘上线路li′任一列车，即则将其到站时间设为1个大的正整数M2（M2≪M1）。因此，乘客组在乘车段终点站到达时刻计算式为

3 求解方法

建立的末班车时刻表协调优化模型为混合整数非线性规划模型，其决策变量和约束条件数量主要受乘客组数量和各线路车次集合Hli规模的影响。为判断乘客组的乘车车次，对于乘客组bγ的任意有效路径rγ，k，其每一乘车段vγ，k，m均需考虑|Hli|个变量αγ，k，m，j，这导致模型包含大量0-1 变量，采用商业求解器求解的时间过长。

为缩减变量数量，提出1 种基于预设车次的求解方法。预设车次指的是根据乘客组出发时间、非末班车时刻表信息以及末班车时刻表调整范围，估计乘客组在出行路径中可以选择的最早车次。若出行路径中乘客组无需乘坐末班车，则末班车时刻表的调整后乘客组仍可抵达目的地，算法将这部分乘客组筛除；若乘客组可选车次为末班车，则通过判断乘客组是否能够乘坐上该末班车确定其OD 可达性，使模型线性化，从而利用商业求解器对时刻表优化模型快速求解。

3.1 乘车段车次的预设方法

乘车段的预设车次与乘车段对应线路时刻表和乘客组到达乘车段起点站的时刻有关。针对乘客组bγ=(sp，sq，t)，以非末班车时刻表、末班车时刻表约束和路径rγ，k为输入，依次估算该乘客组在路径rγ，k中各乘车段vγ，k，m的预设车次jγ，k，m。

1）步骤1

给定路径rγ，k中乘车段vγ，k，m=(li，se，se′)和乘客组到达线路li上se站的时刻，判断该乘车段的预设车次jγ，k，m：若乘客组到达时刻早于线路li非末班车在se站发车时刻，即存在列车hi，j=则乘客组乘坐最早到站的非末班车，预设车次为否则，乘客组在该乘车段只能选择末班车，预设车次为末班车jγ，k，m=1。对rγ，k的第1 个乘车段vγ，k，1，等于乘客组的出发时刻t；对后续乘车段，等于乘客组在上一乘车段终点站的到达时刻与换乘走行时间之和。

2）步骤2

基于乘车段vγ，k，m=(li，se，se′)的预设车次jγ，k，m，估算乘客组到达乘车段终点站se′的时刻：若乘客组乘坐非末班车（jγ，k，m≥2），则乘客组到达se′时刻为该列车到站时刻，即若乘坐末班车（jγ，k，m=1），由于末班车在各站到发时刻为决策变量，是1个非固定值，因此以该末班车在该站的可行最晚到达时刻作为乘客组的预计到达时刻。

3）步骤3

判断vγ，k，m是否为rγ，k中最后1 个乘车段，即是否有m=nγ，kv，若是，则输出rγ，k中各乘车段的预设车次jγ，k，m，当前路径rγ，k的预设车次计算结束；否则计算下一乘车段vγ，k，m+1的预设车次，转步骤1。

3.2 基于预设车次的重构模型

在给定乘车段预设车次之后，假设乘客组在出行路径中只选择预设车次，建立末班车时刻表协调优化模型（后简称为原始模型）的重构模型。

由于重构模型仅考虑乘客组bγ能否乘上乘车段的预设车次jγ，k，m，因此可在无须考虑约束条件式（11）的情况下，将约束条件式（10）重构为

对于约束条件式（12），可将乘客组bγ对预设车次jγ，k，m的乘车富余时间约束重构为

与原始模型相似，对于路径rγ，k中第1 个乘车段，等于乘客组的出发时刻t；对于后续乘车段vγ，k，m=(li，se，se″)，等于乘客组在上一乘车段vγ，k，m-1=(li′，se′，se)到达se站的时刻与换乘走行时间之和，为线路li′的预设车次j(vγ，k，m-1)在se站到达时刻。乘客组在乘车段起点站和终点站的到达时刻的计算式可表示为线性公约束（17）和式（18），即原模型约束条件式（13）和式（14）分别重构为

其余约束条件不变，得到重构模型为

式（1）—式（6），式（8）—式（9），式（15）—式（18）

与原始模型相比，重构模型中关于车次的决策变量及约束规模大幅度减小，且重构模型为线性模型，可采用Cplex软件快速求解。

需要说明的是，由于模型仅调整各线路末班车时刻表，出行过程中乘坐非末班车即可抵达终点站的乘客组在时刻表调整后仍然可达，其可达性不受末班车时刻表调整的影响。对于出行过程中需乘坐末班车的乘客组，其可达性则受末班车时刻表影响。为提高求解效率，首先利用预设方法判断运营结束时段内所有乘客组各路径乘车段的预设车次；根据预设车次，从运营结束时段所有客流需求B中筛选出行过程中必需乘坐末班车的乘客组，其集合用B′表示，即存在bγ∈B′，且其路径rγ，k∈Rγ均存在jγ，k，m=1的乘车段。重构模型仅以客流集合B′作为输入，既可确保考虑运营结束时段所有需乘坐末班车乘客组的需求，又可减小问题的求解规模。

4 案例分析

以武汉地铁为背景，将地铁线网中上、下行视为2 条线路，并设置关键车站48 个，包括换乘站、线路首末站以及两相邻换乘站间客流量最大的车站，得到简化后的线网图如图3所示。图中：绿色和蓝色箭头分别表示线路的上行方向和下行方向；圆点表示线网中的关键车站。2 个关键车站组成关键OD（共2 256对），OD间考虑3条有效路径。参数设置：运营结束时段为21：30 至24：00；初始时刻表中各车站的停站时间在30～60 s；区间运行时间在1～4 min；车站最小发车间隔、最小发到间隔均为2 min；线路首站末班车与次末班车最大发车间隔为10 min；线路收车时刻可延后10 min。

图3 线网及关键车站示意图

4.1 重构模型与原始模型的求解效率对比

分别以10，5 和1 min 为间隔时间δ划分运营结束时段，以出行过程中必需乘坐末班车的乘客组集合B′为输入，采用Cplex 软件测试在不同间隔时间的客流数据下原始模型与重构模型的求解效果，结果见表1。表中：“预设可达人数”指在求解的时刻表下乘坐预设车次出行的可达乘客数量，即重构模型的目标函数值（原始模型则无这一结果）；“准确可达人数”包含了实际未选择预设车次而抵达目的地的乘客（以解得的时刻表作为输入，通过原始模型中式（7）—式（14）计算得到）；“上限”指Cplex求解的上界值；“相对差”指准确可达人数与上限的差值占上限的百分比。

表1 不同间隔时间的客流数据下原始模型与重构模型求解结果

由表1可知：重构模型的预设可达人数与准确可达人数的差值仅为44 人，这是由于预设车次的方法偏保守，其假设乘客在出行路径中只选择预设车次，但实际中乘客选择的车次可能与预设车次存在偏差，这也说明预设方法对乘客在乘车段乘坐车次的估计准确度较高，模型计算误差较小；随着间隔时间的减小，问题规模和求解难度增大，2 种模型的相对差增大，求解时间也变长；在客流数据的间隔时间越小时，重构模型求解速度快的优势更加明显。因此，与原始模型相比，重构模型能够在相对更短的时间内求解到趋近最优的优质解。

4.2 优化结果

以时间间隔为1 min 的客流数据为输入，以出行过程中必需乘坐末班车的乘客组集合B′为输入，通过重构模型，对末班车时刻表进行优化。优化前、后的线网可达OD 比例随时间变化过程如图4所示，运营结束时段所有客流需求B的可达乘客数量变化过程如图5所示，乘客平均旅行时间变化见表2。由于部分OD 乘客不能到达终点站，不可达乘客的旅行时间惩罚值设为100 min。

图4 优化前后线网可达OD比例变化过程

图5 线网可达乘客数量变化过程

表2 优化前后可达乘客比例和平均旅行时间

由图4和图5可知：运营结束时段内优化后的可达OD 比例和可达乘客数量较优化前均有一定的提高；可达OD 比例在时段22：31—22：56 内增幅较大，在22：32时增大了15.6%。

由表2可知：可达乘客比例在运营结束时段需乘坐末班车客流B′的由32.3%增加至42.3%，提高了10%；可达乘客的平均旅行时间增加了5.2 min，原因主要是部分线路末班车的发车时刻有所推迟，这意味着末班车时刻表优化使得部分优化前不可达的乘客到达目的地，但同时部分乘客的旅行时间也有小幅增加；综合考虑B′中的所有乘客，优化后平均总旅行时间由原始的79.2 min 下降至76.7 min，这意味着乘客总体服务水平有所提升。

综上所述，优化后的时刻表虽然小幅增长了部分优化前可达乘客的旅行时间，但有效提高了运营结束时段的线网可达OD 比例和可达乘客数量，提升了线网整体服务水平。

4.3 考虑时段整体客流需求的必要性验证

既有研究仅考虑了乘坐末班车出发的乘客组集合B″，进行末班车时刻表优化。为验证本文模型考虑运营结束时段内整体客流需求的必要性，设置以乘坐末班车出发的乘客组集合B″为输入客流的对比案例，和以需乘坐末班车出行的乘客组集合B′为输入客流的本文案例，对两者求解结果进行对比分析。

设两者客流数据的时间间隔均为1 min，通过构建重构模型并采用Cplex 求解后的结果见表3。由表3可知：在对比案例和本文案例中，客流B″可达乘客比例的增幅分别为24.9%和24.1%，客流B′可达乘客比例的增幅分别为28.0%和31.0%；相比于对比案例，本文案例对客流B″可达乘客数量的提升效果略低，但对客流B′可达乘客数量的增幅高出3.0%，能够使更多的乘客乘坐末班车抵达目的地。因此，末班车时刻优化研究中有必要考虑运营结束时段内所有的客流需求。

表3 优化后可达乘客数量和增幅对比

4.4 最晚收车时刻灵敏度分析

各线路最晚收车时刻约束了末班车在各车站到发时刻的调整范围，从而对线网服务可达性有较大影响。本文将各线路最晚收车时刻tmaxi分别设置为相对原始收车时刻延迟0，5，10 和15 min，客流数据的时间间隔取1 min，优化客流B′的可达乘客比例，分析最晚收车时刻tmaxi对可达性优化效果的影响，结果如图6所示。

图6 最晚收车时刻延迟对可达乘客比例的影响

由图6可知：在不延迟各线路收车时刻时，仅通过模型协调优化各线路末班车时刻表，使可达乘客比例增大了6.5%；随着最晚收车时刻的延迟，需乘坐末班车的客流B′的可达乘客比例逐渐增大，当延迟5 min 时增大了3.4%；当收车时刻可延迟10 和15 min 时，可达乘客比例几乎没有进一步提高。这说明：适当地延迟线路收车时刻可增大线网可达乘客比例；由于客流需求减小，收车时刻延迟对可达比例的提升存在瓶颈。因此，运营公司可通过灵敏度分析确定合理的收车时刻，实现服务可达性最大化并避免收车时刻过晚。