考虑预警机制和开行方案的多车站客流控制问题

李妍峰 ，何金昆，彭钊

(1. 西南交通大学 经济管理学院，四川 成都 610031；2. 服务科学与创新四川省重点实验室，四川 成都 610031)

随着城市轨道交通的快速发展，出行者数量越来越多。据《城市轨道交通2019年度统计和分析报告》显示[1]，2019年内城市轨道交通客运量237.1亿人次，同比增长12.5%，高峰时段断面客流最高高达6.32万人次，这给城市轨道交通运营造成了极大的压力。很多城市(北京、上海、深圳、成都等)均采取了客流控制手段来缓解高峰时段城市轨道交通拥挤问题[2]。城市轨道交通客流控制问题可描述为：车站管理人员控制客流进站速度，避免出现列车超载、站台拥堵等现象，让部分站台外乘客有序排队等候，提高列车运输效率[3]。目前相关学者对该问题进行了研究。在模型构建方面，客流控制模型的目标函数包含最小乘客等待时间、最大服务乘客、最小乘客平均延误时间、最大企业运营成本等；模型中的决策变量有列车到发时间、发车间隔、上车乘客数量及上述几种的组合。刘晓华等[4]考虑客流需求不均衡的特点，提出以限、控、封等方式减少下游车站客流拥挤，并进行了相邻车站的客流控制特性分析。WANG等[5]以分散拥挤车站压力为目的对过饱和线路进行发车间隔及列车最大运输能力设计。LI等[6]提出了列车时刻表与发车间隔偏差的优化模型，模型中乘客进出站数量影响列车停站时间。XU等[7]考虑不同需求场景下的车站服务能力，并引入数据包络分析研究了动态客流需求下的控制问题。在此基础上，SHI等[8]提出地铁网络层面的客流控制问题，以提高车站运输效率与车站累积乘客安全。XU等[9]基于对数的随机客流分配原则，调整进站和换乘的乘客数量。MENG等[10]构建了以列车时刻表为导向的时空网络模型。HUAN等[11]等研究了乘客乘车偏好对客流控制的影响，以适应潜在的客流需求变化。ZHANG等[12]为提高不同乘客OD的乘车公平性，构建了以上车乘客数量最大化为目标的优化模型。此外，客流控制与列车开行方案的结合也是研究的热点。JIANG等[13]将列车跳停策略与客流控制相结合，构建了基于效用理论的客源站选择模型。陈维亚等[14]提出了列车大小交路与客流控制的整数规划模型，并对小交路开行频率进行特性分析。在求解算法方面，大多数研究者采用启发式算法求解，如粒子群算法、遗传算法、局部搜索算法等。皮雁南等[15]设计了混合粒子群算法求解换乘乘客客流控制问题。唐禄林等[16]为匹配乘客出行需求，设计了遗传算法求解列车停站方案。SHI等[17]基于地铁自动售检票系统(AFC)，提出了改进局部搜索算法。综上，现有城市轨道交通客流控制问题的研究中缺乏考虑站台客流安全的情形。此外，实际地铁线路中存在不同的列车大小交路及不同的列车运力情况。因此，本文在前人研究的基础上，考虑列车开行方案、车站客流控制及乘客上下车过程等约束，以进站乘客数量和车站平均限流时间为决策变量，建立最小化乘客出行时间成本的优化模型，并设计混合禁忌搜索算法进行求解。

1 问题描述及模型建立

1.1 问题描述

考虑预警机制和开行方案的多车站客流控制问题描述如下：在一条共有|V|个车站的城市轨道交通线路中，控制时段T内共计m辆列车运营，时间粒度为t0。在已知单向客流OD情形下，乘客到达车站后，根据客流预警等级决定乘客是否进入站台。以车站i为例，用Li，0，Li，1，Li，2，Li，3分别表示客流预警等级为安全(0)，不安全(1)，危险(2)，极度危险(3)的累积乘客数量上限[18]。

本文提出的客流控制问题还具有以下特点：

1) 乘客刷卡数据已知，且遵循“先到先走，先下后上”乘车原则；

2) 各次列车的始发、终到站已知，列车之间的运行顺序已知，不考虑列车越行；

3) 列车在固定交路上运行，交路之间互不影响；

4) 乘客能够快速进出站，不考虑乘客从刷卡到站台的走行时间和进出站乘客对站台的瞬时影响；

5) 当客流需求无法满足时，假定乘客不改变行程，即客流需求恒定。

图1是列车大小交路运行示例。(1,|V|)表示大交路始发站和终到站；(s,s” )表示小交路始发站和终到站。当乘客乘坐小交路列车时，车内直达乘客可直接离开车站，其余乘客在车站s” 成为小交路换乘乘客。

图1 列车大小交路Fig. 1 train short turning strategy

1.2 符号说明

为构建模型，引入以下符号。

1) 集合

K：列车集合。

V：车站集合。

T：统计时段集合。

Z：预警等级集合。

2) 参数

t0：时间粒度。

Ni：车站i客流总需求。

Xij(t)：时段t到达车站i目的地为j站的乘客数量。

Aij(t)：时段t内到达车站i目的地为j站的累积乘客数量

3)Ci站台i的容纳能力

Li，z：车站i等级z的累积乘客数量上限。

d：闸机最大通过能力。

Or/Dr：列车运营始发站和终点站。

a：相邻时段进站乘客数量相差限度。

，：列车k到达/离开车站i的时刻。

hk：列车k的载客量。

Δ：允许的客流预警等级。

M：足够大的正数。

w：站最大平均限流时间权值。

4) 中间变量：

(t)：时段t进入站台i目的地为j站的累积乘客数量。

(t)：时段t在车站i目的地为j的限流乘客数量。

Wk，ij：站台i等候列车k目的地为j站的乘客数量。

Rk，ij：站台i未乘坐列车k目的地为j站的滞留乘客数量。

Gk，ij：站台i乘坐列车k目的地为j的上车乘客数量。

ηk，i，i+1：列车k在区间(i,i+1)的车内乘客数量。

Ek，j：乘坐列车k目的地为j站的乘客数量。

Uk，Dk，j：乘坐列车k目的地为j小交路换乘乘客数量。

tdelayi：车站i的延误时间。

φ：平均延误时间。

ρmax：车站最大平均限流时间。

：0-1变量，列车k在车站i的客流预警等级。

5) 决策变量：

Yij(t)：t时段进入站台i目的地为j的乘客数量。

1.3 模型建立

目标函数(1)表示最小化乘客出行时间成本，包括平均延误时间和车站最大平均限流时间；约束(2)表示进站累积乘客数量，由时刻1至时刻t进站乘客数量累加；约束(3)和(4)表示客流控制过程，限流乘客数量为t时段到站累积乘客与t时段进站累积乘客之差；约束(5)表示单位时间进站乘客数量不超过车站闸机刷卡限制；约束(6)表示相邻时段进站乘客数量限制，避免单位时间进站客流过大对站台造成的瞬时影响；约束(7)表示进站客流平衡，即所有到站乘客进入站台候车；约束(8)表示站台等候列车的乘客数量，由进站乘客、小交路换乘乘客、滞留乘客组成；约束(9)表示因列车剩余容量导致的站台滞留乘客数量；约束(10)表示客流预警等级线性化；约束(11)表示上车乘客数量为车内剩余容量与站台候车乘客数量的最小值；约束(12)表示列车载客量。当列车在运营起点时，列车载客量即为首站上车人数。在其他站点，列车载客量由上车乘客数量、下车乘客数量及前一站列车载客量组成；约束(13)和约束(14)分别表示小交路换乘乘客数量与离站乘客数量与上车乘客数量的关系；约束(15)表示离站客流平衡，即站台候车客流全部乘车到达目的地；约束(16)表示车站i的乘客延误时间，包括站外客流控制时间与站台乘客滞留时间；约束(17)和(18)分别表示平均延误时间和平均限流时间计算；约束(19)表示车站最大平均限流时间不小于各车站的平均限流时间；约束(20)表示站台客流预警等级不超过允许客流预警等级；约束(21)表示0-1变量。

2 算法设计

在城市轨道交通运营过程中，客流控制问题是一类NP-hard问题[10]，本文结合列车大小交路、列车编组及站台客流预警，因此也是NP-hard问题，且更难求解。在已有文献中，禁忌搜索算法的性能较为依赖初始解的质量。因此，本文设计了一种混合禁忌搜索算法。结合本问题特性，按列车发车间隔随机生成乘客进站方案。由于上一时刻未进站客流会直接影响下一时刻进站客流，因此在产生进站客流方案时，每时刻的进站乘客数量需依赖上一时刻的客流需求；然后根据模型特征，本文设计了7种领域算子；最后通过解的相似度保证解的多样性，进一步提高解的质量。算法框架如下所示：

?

2.1 解的表示

2.2 初始解

由于各车站客流需求相互独立，该问题的解由各时段进站客流决定，采用整数编码的方式，依照先后时刻顺序排列。以车站i，控制时段|T|=10为例，解的编码方式如图2所示。

图2 解的表示Fig. 2 Description of solution

本节采用“随机”策略获得初始解。首先各车站根据列车发车间隔生成|K|集合，集合中到站乘客顺序随机打乱，其次随机生成进站客流方案，具体算法框架如下：

Input 客流需求、列车及车站设施信息Step 1 所有乘客按列车发车间隔随机打乱，设列车集合为K，k∈K；Step 2 初始化，令k=1；Step 3 随机生成进站客流方案，若满足约束(12)，转入Step 4；否则重新生成进站客流方案，直至满足约束(12)。k=k+1;Step 4 若k＜|K| 时，转入Step 3；否则转入Step 5；Step 5 若不满足约束(15)，转入Step 2；否则，结束得到初始解。

2.3 邻域算子

为了获得更好的搜索解空间，本文设定了7种邻域算子，分别是单点插入算子、单点移除算子、子序列插入算子、子序列移除算子、两点交换算子、子序列交换算子、两子序列交换算子，如图3所示。

图3 领域算子Fig. 3 Field operator

1) 单点插入算子：随机选择一点，并随机插入限流乘客数量；

2) 单点移除算子：随机选择一点，并随机移除站台乘客数量；

3) 子序列插入算子：随机选择一条子序列，并随机插入限流乘客数量；

4) 子序列移除算子：随机选择一条子序列，并随机移除站台乘客数量；

5) 两点交换算子：随机选择两点，重新分配乘客数量；

6) 子序列交换算子：随机选择一条子序列，重新分配乘客数量；

7) 两子序列交换算子：随机选择两条子序列，重新分配乘客数量。

2.4 解的评价

本节提出的混合禁忌搜索算法为扩大搜索范围，允许违背约束(7)。当违反客流进站平衡限制时，将|T|时段的限流乘客时间作为惩罚值进行度量。

2.5 禁忌表和藐视准则

在迭代过程中，若某次移动改进了当前最优解，则该移动被禁忌θ代，本文选取基于评价函数的藐视准则对优良解实施解禁。当某个候选解的评价函数能改进当前最优解时，则该移动被特赦并继续迭代。

2.6 多样化策略

为避免算法陷入局部最优，本文的多样化策略基于精英解集合[19]。精英解集合是算法在运行过程中不断加入新的高质量解所构成的，其多样性是通过不断删除集合中的解来实现的。被删除解的选择基于解之间的相似度[20]，考虑以下2种情况：1) 当精英解集合未达到规模上限，删除集合中所有相似度ΔY(Ybest，Y)≥(|V|-2)*|T|的解；2) 当精英解集合达到规模上限，以当前最好解替换集合中相似度最高的解。

3 数值实验

为验证模型及算法的有效性，4.1节首先通过小规模算例对权值及客流预警等级进行灵敏度分析。4.2节将混合禁忌搜索算法与CPLEX运行结果相比较，测试算法性能。4.3节应用实际案例对优化结果进行分析。本文算法使用C#进行编码，考虑到目前没有针对本问题的标准算例，参考SHI等[18]提出的算例生成方法，客流需求通过正态分布产生。取时间粒度t0=30 s，控制时刻|T|=120。为简化研究，站台容纳量统一取400人，闸机最大通过能力150人，相邻时段进站乘客数量最大相差为30人。列车相邻区间运行时间为4t0，停留时间为t0，每节列车编组定员为310人，精英集合规模设置为10，程序运行100代终止。

3.1 小规模算例

以5个车站为例，记为V={A, B, C, D, E}。在实际乘车过程中，前方车站客流需求往往高于后方车站，所以假设车站A和B的客流需求为1 500人，车站C和车站D为1 000人，如表1所示。

表1 小算例客流需求Table 1 Small example passenger flow demand

为探讨权重系数w的不同取值对平均限流时间的影响，固定站台客流预警等级为2，其余信息与上文相同。表2为CPLEX求解得结果，依次列出目标值、平均延误时间、最大平均限流时间、车站平均限流时间。同时给出w=1时车站B(车站最大平均限流时间)的乘客进站动态过程，如图4所示。

表2 不同权重系数的目标值Table 2 Target values of different weight coefficients

图4 车站B的乘客进站动态Fig. 4 Passenger boards at station B

由表2可知，随着权重系数的逐渐增大，目标值与平均延误时间也逐渐增加，增大的幅度对各站平均限流时间产生不同程度的影响。当仅考虑平均延误时间(w=0)时，各车站平均限流时间呈现极大的不均衡性，其中车站A最小为37.6 s，车站B最大为117.3 s；当w在一定的范围内变化时(0

为清楚体现站台客流预警等级的设置对乘客出行时间成本的影响，固定权重系数w=1，其计算结果如图5所示。随着客流预警等级的增大，平均延误时间由141.5 s缩减至77.4 s，车站最大平均限流时间由132.2 s缩减至72.6 s，分别减少45.3%和45.1%。这是因为站台可容纳乘客数量增多，拥挤程度变高。因此，地铁运营商可设置合理的预警等级来满足乘客出行的舒适体验，提高运营服务质量。

图5 不同客流预警等级的目标值Fig. 5 Target values of different passenger flow warning levels

3.2 算法性能分析

为测试本文所提禁忌搜索算法的求解效率，本节将使用精确算法求解器CPLEX对模型进行精确求解，并将所得结果与混合禁忌搜索算法求解结果最比较，验证模型及算法的正确性。随着数据规模的增加，CPLEX不能求解大规模数据，实验过程中设置CPLEX的最长运行时间为7 200 s。本文算例生成方式与上文相同，为不失一般性，相同车站数量设置不同的客流需求，求解结果如表3所示。表3依次列出了CPLEX求解时间time(s)，求解下界(LB)，求解上界(LB)及求解Gap%，混合禁忌搜索算法计算20的平均目标值(Avg.obj)，平均gap(Avg.gap%)，最好解(Best.obj)，最好解gap(Best.gap%)，平均求解时间Avg.time(s)，混合禁忌搜索算法与CPLEX的相对偏差(Related.gap%)。

表3 CPLEX与混合禁忌搜索算法比较Table 3 Comparison of CPLEX and hybrid tabu search algorithms

由表3可以看出，CPLEX在问题规模较小时(|V|=7)可求得模型的最优解，这表明本文所提模型的正确性。随着问题规模的扩大(|V|=9,11)，CPLEX在规定时间(7 200 s)内无法求解最优解，且解得质量也随之下降(最大gap为26.5%)。当问题规模继续变大时(|V|=13)，CPLEX已无法求得可行解，这表明CPLEX可求得本问题小规模算例的最优解，对于大规模算例求解存在一定程度的局限性。

由表3还可以看出，混合禁忌搜索算法可获得所有算例的可行解。实验发现在问题规模较小时(|V|=7, 9)可快速求得最好解，平均计算时间Avg.time<30 s，且Related.gap<3%；当问题规模继续扩大到车站数|V|=11时，Related.gap均为负值，充分表明本文算法良好的求解效果；直至车站数|V|=13时，混合禁忌搜索算法仍能在较短时间(120 s)内求得可行解。这表明本文所设计的混合禁忌搜索算法在大规模问题中有更优的求解质量和求解效率。

3.3 实际案例

本节以重庆地铁6号线某日早高峰(8:00～9:00)为例，车站集合V={V1，V2，…，V28}，小交路运营区间为(V1，V23)，各车站客流需求如表4所示，其余信息与上文相同。为清楚体现列车大小交路与小交路列车编组设置对求解结果的影响，假设列车编组与发车频率如表5所示，其求解结果如表6所示。

表4 地铁6号线客流需求Table 4 Passenger flow demand of Metro Line 6

表5 列车编组、发车频率Table 5 Train size and departure frequency

由表6可知，在相同编组(8A)情形下考虑列车大小交路比不考虑列车大小交路，平均延误时间节约15.2%，车站最大平均限流时间节约12.7%，且列车大交路平均满载率相应增加13.9%。这是因为小交路乘客提前乘坐列车离开，进而影响列车平均满载率与出行时间成本。所以从地铁运营的角度来讲，采取大小交路模式可以解决客流需求的时空不均衡性，达到缓解车站拥挤的目的。

表6 不同开行方案、列车编组指标对比Table 6 Comparison of different operating schemes and train grouping indexes

当地铁运营商采用大小交路模式时，小交路列车编组6A比8A出行时间成本更低，乘客能更快完成行程，其平均满载率增高15.8%，乘客平均延误时间与车站最大平均限流时间分别节约7.3%和6.1%，这说明在列车大小交路模式中采用“大交路大编组、小交路小编组”可以提高列车平均满载率，以减少运力浪费。

4 结论

1) 考虑车站平均限流时间可有效提高线路乘车公平性，避免局部客流积压严重。

2) 合理的站台客流预警等级能有效缓解车站拥塞，减少乘客安全风险。

3) 列车大小交路模式及小交路小编组可有效提高运营服务质量，节约企业成本。

4) 本文所设计的混合禁忌搜索算法表现出了良好的求解性能和质量。后续研究可考虑列车跳停策略及列车时刻表优化等问题，也可进一步优化混合禁忌搜索算法，设置更加有效的初始解获得方案。