考虑车辆到达时间窗的应急公交调度优化模型

查伟雄，冯 涛，严利鑫

(华东交通大学 交通运输与物流学院，江西 南昌 330013)

0 引 言

近年来，随着我国城市轨道交通的快速发展，轨道交通在城市交通出行中越来越重要，一旦发生突发事件，将会对整个城市的公共交通系统产生严重的影响。因此高效的应急公交调度方案成了学者们研究的热点。

国内外许多学者对轨道交通中断条件下的应急公交调度问题进行了研究。Y.B.WANG等[1]考虑到有限的应急资源以及城市交通状况,设计了临时应急公交桥接网络，并基于复合泊松过程理论建立了需求模型；I.AKGUEN等[2]利用故障树分析的方法计算了需求点脆弱性，并创新地将其融入到所建立的优化模型中；J.G.JIN 等[3]考虑中断区间通勤者的出行需求，建立了动态响应需求的应急线路优化模型；J.G. SHI等[4]从脆弱性的角度分析了城市轨道交通网络的可持续性，从时空角度量化网络攻击下网络效率和结构完整性的变化，并对城市轨道交通网络脆弱性进行评估；L.J.KANG等[5]探讨了轨道交通网络环境下的最后一班列车与公交桥接服务的问题，并建立了混合整数规划桥接模型，用于解决末班列车乘客午夜滞留问题；Z.YANG 等[6]以网约车、网约车平台和滞留乘客组成的系统为研究对象，建立了以城市轨道交通为主的轨道交通与网约车平台之间的博弈模型；Y.WANG等[7]在考虑疏散优先权的前提下，建立了城轨运营中断条件下的应急公交线路规划模型；王起全等[8]提出了地铁火灾疏散路线的规划及对策， 并建立多套消防救援方案；黄家骏等[9]针对动态不确定环境下的乘客初始状态、疏散行为以及全局疏散路径不确定等问题，提出了基于Agent的疏散行为动态切换模型；张勇等[10]基于随机生灭过程理论建立了救援车辆的联合排队模型，并得到了救援状态平衡方程；赵淑芝等[11]、张思林等[12]为有效缓解固定发车间隔造成的资源浪费和过度拥挤，建立了常规公交线路多车型配置优化模型；郑玉靖等[13]建立两阶段优化模型，一阶段以管理部门角度最小化疏散时间为目标,二阶段以乘客角度降低乘客延误为目标；王佳冬等[14]以总疏散时间以及乘客平均延误最小为目标，建立了应急公交车辆调度优化模型。

上述研究主要从线路选址和疏运时间的角度，对应急公交调度模型进行研究。因此笔者在满足乘客出行需求情况下，综合考虑应急公交疏运时间以及车辆调度数量，构建了多车型下带有车辆到达时间窗的应急公交调度优化模型。

1 问题的提出

当城市轨道交通发生较严重故障时，仅通过系统内部调整列车调度计划已不能满足滞留乘客的出行需求，因此应考虑在轨道交通中断区间开设应急公交疏散滞留乘客，从而保障系统的安全、稳定运行。在满足整体客流需求的条件下，笔者主要从调度过程和时间窗两个角度对应急资源进行配置。

1.1 调度过程

应急公交车辆调度指在轨道交通中断期间从应急公交停车场调度车辆，为轨道交通中断区间上、下行滞留的乘客提供往返疏运服务。由于不同的停车场往往存在不同车型的车辆，如果不能对应急公交车辆的车型进行科学合理的选取，很可能会浪费现有的应急车辆资源。因此，在进行应急调度时需要考虑车型的因素，选取轨道交通中断站点作为应急公交临时停靠站，令中断车站为i∈I,j∈J；s为应急公交车辆的停车场，s∈S；p为应急公交线路的首末站，p∈P，p=1为应急公交线路首站，p=2为应急公交线路末站；k为车型，k=1为大型公交车，k=2为中型公交车，k∈K。应急公交调度过程示意如图1。

图1 应急公交调度示意Fig. 1 Emergency bus dispatching diagram

1.2 时间窗

因为轨道交通突发事件具有随机性和紧急性，所以应急公交车辆难以准确无误地按照应急管理部门的时间要求到达站点，因此应急管理部门允许公交车辆的到达时间存在一定的波动范围，笔者称之为车辆到达时间窗。如果应急公交车辆到达应急线路首末站的时间超过了应急响应时限，则应该对该停车场予以剔除。对于晚到的公交车辆实行惩罚机制，如果公交车辆晚到，则相当于公交车辆多运行了一定的时间，以此增大目标函数值。令λ为奖惩时间，Tmin为惩罚车辆到达时间的上限(车辆到达时超过这个时间限度开始实行惩罚机制)，f(λ)为“惩罚系数函数”,χ,γ为惩罚参数：

(1)

2 应急公交调度模型

2.1 问题描述

因轨道交通系统内部结构复杂，一旦发生事故使线路运营中断，若不能快速有效地疏散滞留的乘客，往往会对轨道交通系统产生重大影响，造成城市交通网络局部拥堵甚至瘫痪等严重后果。地面公交因运量较大、响应迅速、调度灵活等优点成为疏散中断区间滞留乘客的最佳选择。因此选取地面公交车辆对滞留乘客进行疏散，从而保障公共交通网络安全高效地运营，并根据实际情况做出如下假设：①不考虑客流的动态变化，仅考虑满足客流需求的运力问题；②不同的停车场具有不同车型的车辆，且额定载客量为定值；③应急车辆沿中断区间逐站停靠，在折返站清客后直接开始下一次疏运或终止疏运；④不同车型的应急车辆具有不同的平均运营速度，且由历史平均路况确定；⑤不考虑道路上各种突发事件对应急公交车辆造成的影响。

2.2 建模分析

以往研究[15]主要集中在对“应急公交车辆的疏运时间”进行优化，从而构建了城市轨道交通运营中断下的应急公交调度模型。但是在实际公交体系中不仅存在多种车型，而且在实际调度过程中还要遵循“就近调配车辆”的原则。因此笔者综合考虑“多车型”和“车辆到达时间窗”对调度方案的影响，构建了多车型下考虑车辆到达时间窗的应急公交调度模型，因此推导出目标函数和约束条件。

2.2.1 应急公交疏运时间成本最小

应急公交车辆调度问题主要包含两个过程：一是从停车场派遣车辆到应急线路的首末站；二是应急车辆在应急线路之间进行往返疏运。建模目的是为了在满足客流出行需求的同时，减少应急公交在中断区间的疏运时间。因此选取应急公交车辆疏运时间进行优化，应急公交疏运时间成本Z1如式(2)：

(2)

2.2.2 应急车辆调度成本最少

因为城市轨道交通发生突发事件时可供调度的应急车辆是有限的，所以应急管理部门更多考虑的是在满足客流需求的前提下，尽可能地减少应急车辆的使用数量。应急车辆调度成本指参与调度的所有应急车辆所花费的成本。应急公交车辆调度成本Z2如式(3)：

(3)

2.2.3 约束条件

1)应急公交车辆的救援时间限制。令T为中断运营时间：

(4)

2)应急公交车辆的到达时间限制。尽管应急公交停车场很多，但是可供使用的停车场数量有限。因此必须通过车辆到达的时间窗，来剔除距离应急公交线路首末站距离较远(运营时间费用较大)的停车场。令Tmax为应急管理部门规定车辆到达的时间上限：

(5)

3)疏运需求的限制。令maxQi为最大断面疏运需求，Bk为k型公交车的额定载客量：

(6)

(7)

(8)

2.3 应急公交组合调度模型

minZ=αZ1+βZ2

(9)

式中：α为应急公交疏运时间成本的权重；β为车辆投入成本的权重。

应急公交车辆的救援时间限制如式(10)：

先人说过“以身作则”，做任何事先自己做好，才能要求别人那样做，教学也是一样的。想要更有效的教学方式，教师作为学生的引路人，想要学生能学好，教师首先就要树立起有效“课题学习”的教学理念。

(10)

应急公交车辆的到达时间限制如式(11)：

(11)

应急公交车辆运力的限制如式(12)：

(12)

停车场的最大派车数量限制如式(13)：

(13)

应急公交车辆的往返次数限制如式(14)：

(14)

3 改进的遗传优化算法

应急公交调度优化模型属于非线性整数规划问题中的NP-hard问题。当问题的规模比较大时，搜索解的空间难度也不断增加，通常使用传统的精确求解方法很难求解实际规模问题的解。因此，笔者根据模型的特点设计了遗传算法对优化模型进行求解。

3.1 改进的遗传算法

由于传统遗传算法存在计算量大、收敛速度慢等缺点，笔者在交叉操作上进行改进，引入线性交叉算子，来增强算法的全局搜索能力，避免程序陷入局部最优，同时与传统交叉方法进行对比分析。

3.2 遗传算法的步骤

Step 2种群初始化。随机产生初始种群。

Step 3选择操作。使用轮盘赌法，选择适应度较高的优秀个体遗传给下一代。适应度用来评估个体的优劣程度，从而决定其遗传机会的大小。

Step 4交叉操作。采用线性交叉算子。交叉操作指把两个父代个体的部分结构加以替换重组而生成新的个体的运算。交叉的目的是为了在下一代产生新的个体。交叉操作在遗传算法中起核心作用。

Step 5变异操作。使新个体的基因以一定的概率出错，增强算法的局部随机搜索能力和维持种群多样性防止早熟现象。

Step 6收敛判定。当个体的适应度达到给定阈值时或最优群体适应度不再上升时，则迭代过程收敛，算法结束；否则重复Step 3，直至最终得到符合条件的染色体为止。

4 算例分析

4.1 算例背景

南昌地铁2号线，全长31.51 km，共建设28座车站，西起南路站，途经新建区、东湖区、西湖区和青山湖区，东止辛家庵站，且经过南昌站、南昌西站两个铁路枢纽站，线路横跨赣江两岸，地理位置较独特，局部线路如图2。如果翠苑路站—学府大道站区段发生供电故障，中断运营时间为1.5 h，导致雅苑路站、地铁大厦站、翠苑路站、学府大道站、前湖大道站、岭北站共6个车站运营中断。同时在中断区间附近选取下正街、省体育馆、文教路、红都大市场、老福山立交桥、辛家庵6个公交停车场进行车辆调配。停车场配车信息如表1，车辆运营参数如表2。

图2 南昌市轨道交通2号线局部线路Fig. 2 Partial route map of Nanchang Rail Transit Line 2

表1 停车场配车信息Table 1 Parking dispatching information

表2 车辆运营参数Table 2 Vehicle operation parameters

4.2 优化结果分析

利用改进的遗传算法对模型求解，同时根据文献[16]固定其它参数不变，权值取[0,1]区间进行灵敏度分析，以0.1为步长，均分为11组进行计算。结果发现，当应急公交疏运时间成本权重为0.5、车辆投入成本权重为0.5时，优化效果较佳。因此选取该组数据作为优化结果进行分析。利用MATLAB2018a 软件，通过大量的参数计算，最终选取种群规模为100、最大迭代次数为1 000 次、交叉概率为0.8、变异概率为0.05对优化模型进行求解。表3为改进遗传算法的优化结果。

表3 优化结果Table 3 Optimized results

表3表明：派往应急公交首站大型车13辆、中型车3辆，派往应急公交末站大型车17辆、中型车2辆；通过对车辆到达时间窗的限制，可以有效剔除停车场1和停车场3对线路末站派车、停车场5和停车场6对线路首站派车，因为这些停车场到发车点的时间费用较大。

4.3 算法对比分析

笔者将改进的遗传算法与普通的遗传算法的优化结果进行对比分析，来证明改进的遗传算法具有较高的收敛精度和搜索能力。将两种算法重复运行10次对算法效果进行对比，如图3。图3中，适应度指的是每代适应度函数值的自然对数的平均值。表4为相关优化指标。

图3 算法效果对比Fig. 3 Contrast map of algorithm effect

表4 相关优化指标Table 4 Related optimization indicators

图3、表4表明：改进的遗传算法相比普通遗传算法，总目标降低了16.87%，车辆满载率提高了18.49%，验证了改进的遗传算法具有较高的收敛精度和搜索能力。

5 结 论

1)在轨道交通运营中断条件下，考虑到车辆到达情况和车型对调度方案的影响，笔者构建了考虑车辆到达时间窗的应急公交调度优化模型，并利用改进的遗传算法对优化模型进行求解。

2)以南昌轨道交通1号线为例进行分析，研究结果表明：通过时间窗的奖惩机制可以使距离首末站较近的停车场优先服务，同时剔除不满足时间窗约束的停车场；改进的遗传算法相比普通遗传算法，总目标降低了16.87%，车辆满载率提高了18.49%。

3)笔者仅研究了固定疏运需求和固定疏运线路下的应急公交调度方案，而目前随着互联网技术和车联网技术的迅速发展，实时动态客流响应和动态网络调度方案将是未来研究的重点，对推动 “互联网+交通”具有积极意义。