响应动态需求的灵活型公交路径优化调度模型

孙继洋， 黄建玲， 陈艳艳， 魏攀一， 贾建林， 宋程程

(1.北京工业大学北京市交通工程重点实验室， 北京 100124； 2.交通运输部公路科学研究院， 北京 100088;3.北京市交通信息中心， 北京 100161)

城市公交线路优化调度是提高公交运行效率、降低乘客出行和公交运营成本的主要手段. 一个好的公交调度系统能够根据乘客的出行需求，快速优化调整线路运营方案，提高线路服务率，减少运行时间，降低乘客出行时间成本[1-3]. 传统公交路径优化方法主要是通过长期的经验观察或IC卡数据统计分析，对部分线路进行延长、缩短、增删、调整走向等优化，优先满足大客流站点的乘客需求，这类方法主要适用于固定线路的公交路径优化，线路调整周期较长[4-7]. 灵活型公交的出现，为线路的动态优化调整提供了可能[7-10]，目前国内外学者均开展了相关研究. 其中，Quadrifoglio等[11-12]通过对灵活公交系统关键参数的分析，建立了公交系统运行效率参数优化调整模型，并针对其前期建立的系统线路设计和调度问题，进行了仿真验证分析，对模型进行了参数修正. 付晓等[13]利用超级网络同时模拟用户的活动与出行行为，并根据用户出行行为特征建立了公交路径选择模型. Koffman[14]提出了基于多目标需求的城市公交智能调度算法；Tsubouchi[15]提出了利用最小生成树寻优公交路径最优算法；熊杰[16]通过对区域内潜在公交用户需求的分析，建立了接驳轨道交通的公交线路优化模型；Li等[17]、Chen等[18]通过对乘客预期等待时间和线路上客概率的推导，建立了超路径的公交运输路径调整模型；潘述亮[19]重点考虑了长时预约对灵活公交线路调整的影响，并提出了优化调度方法；郭晓俊[20]重点考虑了短时预约对灵活公交线路调整的影响，并提出了优化调度方法. 这些研究虽然都是根据乘客的预约需求建立的灵活型公交路径优化算法，但其前提条件均是乘客需提前发出预约或假设乘客需求已知，相对即时预约来说均属于“静态需求”. 然而，在乘客出行过程中，往往会根据出行需要发出短时预约或即时预约，灵活型公交需要根据乘客的“动态需求”，计算因动态需求变化导致的车辆接驳行程时间变化，即时调整线路实现路径的动态优化.

鉴于此，考虑到乘客需求的动态变化以及由于需求变化导致的车辆接驳行程时间变化，本文提出了一种基于乘客动态需求的灵活公交路径优化调度方法. 在已知车辆载客容量、车队规模等条件下，根据乘客需求动态变化特征对接驳行程时间实时迭代更新，将车辆运营成本和乘客出行成本最小化作为主要目标，建立了考虑乘客动态需求的灵活型公交路径优化调度模型.

1 问题描述与建模

1.1 问题描述

在传统的固定型接驳公交运营中，公交线路规划设计与车辆运营调度是2个独立的过程，一般在线路规划设计完成之后制定车辆运营调度方案，调度方案在相当长一段时间内不发生变化. 这就造成了线路设计和车辆调度之间脱节，两者不能有效衔接的问题，且线路设计和车辆调度无法根据乘客需求进行及时调整. 但高效的接驳公交系统，应能够根据乘客的实际需求及时调整运营线路，并根据线路和乘客需求实时动态调整车辆调度方案.

灵活型公交是一种以需求为基础的交通系统，它能根据乘客发出的需求，以最短路线服务最多乘客为目标，动态调整运营线路，并在线路调整同时，融合分析沿线乘客需求数量、车辆载客容量等因素，实时调整车辆调度方案，最大程度地满足更多乘客需求，解决传统固定型接驳公交的乘客需求与线路规划、车辆调度脱节的问题.

本文提出的响应动态需求的灵活公交路径优化调度模型，将乘客即时需求作为公交路径动态优化调整的依据之一，根据乘客出行需求点位、需求量和需求时间，对公交路径和行车方案进行实时优化和调度. 为使得本文所建立的模型更合理、得当，本文综合考虑乘客需求、运营成本等各方面的因素，进行如下灵活型公交路径优化模型假设、参数选取和建模.

1.2 模型假设

对灵活型公交路径优化模型的建立提出如下假设，其中1)、2)为动态假设，3)～6)为静态假设.

1) 每个站点的乘客预约需求量动态变化.

2) 车辆站点之间的行程时间动态变化.

3) 每个站点的位置均已知.

4) 预约后，每个乘客拟到达目标站点的时间已知.

5) 乘客到站上车的服务时间为常数.

6) 接驳车辆的载客容量已知.

1.3 模型参数

按照上述模型假设，对各模型变量进行定义，如表1所示.

表1 模型参数Table 1 Medol parameter

1.4 模型表述

按照上述模型假设和变量设置情况，采用非线性规划形式对灵活型公交路径优化模型进行表述，即

(1)

式(1)为灵活型公交路径优化模型表述的目标方程，由3个部分之和组成，取其最小化值：1)所有车辆的行驶时间，以降低运营成本； 2) 每个乘客在需求点等候车辆抵达的时间之和，以减少乘客的总出行时间； 3) 每个乘客等待车辆的实际到达时间与期望到达时间的差值之和，以减少乘客的总出行时间.

(2)

(3)

约束式(2)(3)表示在任意一个乘客需求点，保证车辆进行服务，且车辆数在1与V之间.

(4)

约束式(4)表示参与服务的车辆总数不超过V辆.

(5)

约束式(5)表示对任意一个需求点，任一参与服务的车辆均有到达和离开的过程.

Uik-Ujk+|H|×Yijk≤|H|-1,∀i,j∈H∪D,k∈K

(6)

约束式(6)保证了系统规划路径的单向性，即不能产生往返回路.

(7)

(8)

约束式(7)(8)表示参与服务的任意一辆车必须将乘客运送至目标站点.

(9)

约束式(9)保证车辆不能超载运输.

(10)

约束式(10)表示乘客发出需求后，只能被一辆车服务，不能同时被多辆车服务.

(11)

约束式(11)表示一辆接驳车辆在单程接驳运送中，只能服务于一个目标站点的一个发车时刻.

(12)

约束式(12)表示所有接驳车辆实际服务的需求数量与预约的需求量相等.

ar+cprps-as+YprpskM≤M,∀r,s∈R,∀k∈K

(13)

as-ar-cprps+YprpskM≤M,∀r,s∈R,∀k∈K

(14)

约束式(13)(14)表示当同一接驳车辆为相邻2个站点提供接驳服务时，后一个站点接受服务的时间应等于前一个站点接受服务的时间与两站点间行程时间之和.

ar+cprj-as+YprpskM≤M,∀r∈R,∀k∈K,∀j∈D

(15)

as-ar-cprj+YprpskM≤M,∀r∈R,∀k∈K,∀j∈D

(16)

约束式(15)(16)表示接驳车辆到达目标站点的时间等于为最后一个需求点提供服务的时间与需求点与目标站点之间的行程时间之和.

(17)

约束式(17)表示接驳车辆应在目标站点车辆发车之前抵达目标站点.

2 模型求解

本文提出的面向多目标站的灵活性公交路径优化调度问题，是一类典型的非确定性多项式问题都能在多项式时间复杂度内归约到的问题(non-deterministic polynomial hard，NP-hard). 在问题规模较大时计算量和复杂程度会急速增加. 因此，为了应对复杂问题的快速高效计算问题，通常采用可同时保证计算速度和计算精度的启发式算法进行求解. 当在一定区域范围内，多个点位同时发出出行需求时，可看作同时存在的多个引力点. 受点位间距离影响，不同点位之间引力大小各有不同，可对应理解为车辆在2个需求点间接驳运送的时间成本各不相同. 因此，为使车辆能够快速在需求最多、距离最小的点位间进行接驳服务，受四阶段出行分布预测的引力模型启发，本文提出一种基于引力模型的启发式算法. 总体思路是：首先基于引力模型生成较优的初始解，再利用路线间和路线内的优化算法分别改进路线，从而得到最终路线. 详细步骤介绍如下.

2.1 乘客出行预约与需求分配

首先，将乘客发出出行预约和进行需求服务分配分为以下4个步骤：

步骤1乘客按其出行需求，进行预约出行. 每个乘客将其出发站、目标站、期望到达目标站的时间等信息传输到出行预约平台. 考虑到乘客需求和接驳车辆站点之间的行程时间的动态变化特征，预约平台的乘客需求和接驳车辆站点之间的行程时间每5 min进行一次更新.

步骤2出行预约平台根据每个乘客的目标站和期望到达目标站的时间，按照实际到达时间不晚于乘客期望值的原则，对所有乘客进行聚类.

步骤3根据2.2、2.3节中路径生成结果，结合接驳车辆到达时间、平均行驶速度、乘客需求点的位置、各需求点乘客数量等因素，初步估算车辆到达的时间.

步骤4将初步估计的接驳车辆到达各需求点的时间，发送给对应需求点的乘客，乘客根据接驳车辆到达时间的合理性，选择是否确定乘车.

2.2 基于引力模型的生成初始车辆路径解

基于引力模型的计算方法，以起始需求点为已知站点，根据引力模型的原理遍历所有剩余需求点，查找与已知点之间引力最大的点，并将最新搜索到的站点作为新的已知点，继续遍历剩余需求点确定下一个与已知点之间引力最大的点，按此步骤逐步迭代，直到所有需求点均被查找到，从而可以生成可行的初始车辆路径解. 定义两站点间的引力

(18)

式中：Ni为站点i的上车人数；cij为站点i和站点j之间的车辆行驶时间.Fij的值越大，说明这2个站点的乘客数越多且旅行花费越小，需要优先服务，应该将站点j设为站点i的下一个站点.

在已知车辆载客限定辆Q时，按如下步骤生成初始路径的解：

步骤1确定车辆出发站点. 初始k=1，从有乘客上车需求的站点中，随机抽取一个作为车辆k的出发点.

步骤2判断是否还有同类乘客未服务. 若有，则跳至步骤3；否则，跳至步骤5.

步骤3搜索下一站点. 在包含同类乘客的上车站点中，找出与当前站点之间吸引力最大的站点X，尝试将站点X加入路径选择链，计算车辆在加入该需求点后车上总人数，以及加入该需求点X后直接行驶至目标站点所需的时长.

步骤4判断加入站点X后，车辆路线是否合理. 若当前车辆服务的乘客数量未超过车载容量Qk，且到达目标站点的时间未超过乘客需求的时间，则以站点X为新的起点，跳至步骤3；否则，跳至步骤5.

步骤5判断是否所有类别的乘客均被安排服务. 若还有乘客未被安排服务，则调度下一辆车，k=k+1，跳至步骤1；否则，输出当前全部初始解，结束基于引力模型的初始解计算步骤.

2.3 基于站点均衡与交换的车辆路径优化

介绍路线间和路线内的路径优化算法，使得路径质量和乘客服务水平进一步提升. 需要注意的是，算法的步骤1和步骤2均属于车辆路径间的优化，在步骤1和步骤2的路径优化算法执行过程中，可能会搜索出多组可行的路线解. 若在搜索时仅保存当前最优的一组解，再执行步骤3，可能搜索到的最终路线结果并不是最优. 所以，本算法会保存步骤1和步骤2寻找到的所有可行解组，并对每一组可行解执行步骤3，综合评价所有的路线解组的目标函数，以找到最终的最优解.

步骤1首先对服务于目标站点和到达目标站点时间需求相同的车辆之间进行站点数量均衡. 检查各接驳车辆是否存在服务需求点过多或过少的现象. 如果有，则在确保车辆不超载的条件下，将需经过站点数量较多的车辆路线中的部分站点，转移给经过站点数量较少的车辆路线，并安排合理的站点顺序.

步骤2尝试对服务于目标站点和到达目标站点时间需求相同的车辆之间进行路径优化. 主要应用两路线间，交换两站点的方式，搜索更优的路线. 在交换优化的过程中，保证车辆不超载和按时到达目标站点的需求.

步骤3对每一辆车的路线进行内部优化. 主要在同一车辆路线内，尝试交换两站点的顺序，评估目标函数值是否减少. 若减少，则交换站点顺序；否则舍弃本次交换. 在尝试一定次数之后，结束计算流程，生成最终路线结果.

步骤4考虑到乘客需求的动态变化特征和站点之间旅行时间的变化特征，每5 min进行一次各站点需求的采集和重新计算，重复以上步骤1至步骤3.

经过如上4个步骤，可在保证乘客按照预期时间到达目标站点的前提下，使得路径调度模型的目标函数最优，全部服务时间缩短，每一辆车的路线更加合理，车辆的运行成本降低，乘客的等待时间减少，提升服务质量和效率.

3 案例分析

3.1 案例假设

北京市回龙观地区是通勤人群居住密集区，高峰时段出行需求量大，不同工作性质和通勤距离的出行者出行时间差异较大，因此适合作为需求响应型灵活公交模型验算的案例. 为了便于模型分析，本文对回龙观区域公交网络进行了抽象化提取，保留网络拓扑结构.

根据实际情况下乘客的出行需求，假设一个乘客出行案例，采用上述模型对案例进行求解，验证本文所提模型的可用性. 小型网络常变量的输入参数如表2所示，初始时刻每个站点的乘客需求如表3所示，初始时刻站与站之间的旅行耗时矩阵如表4所示，其中H为需求点，D为目标站.

表2 案例中的常变量Table 2 Constant variables in the case

表3 初始时刻各站点乘客需求(初始5 min)Table 3 Quantity demanded at the demand point (the first 5 minutes)

表4 初始时的乘客行程时间矩阵(初始5 min)Table 4 Case network travel time matrix (the first 5 minutes)

3.2 案例计算

根据本文提出的计算模型和方法，对上述假设案例进行计算，获取各接驳车辆的行驶路线、接驳乘客的数量、每条路线对应的目标函数如表5所示.

表5 初始时刻车辆的服务路径结果(初始5 min)Table 5 Service path results of vehicles at initial time (the first 5 minutes)

之后，随着乘客需求和站点之间旅行时间的动态变化，上述路径规划结果无法满足当前乘客需求和真实状况，需进行新的路径规划. 此时，预约平台将汇总的第一个5 min后新的乘客需求和接驳车辆站点之间的行程时间并进行更新，如表6所示，再次利用2.2节中所述的方法进行求解.

表6 5 min后各站点乘客需求Table 6 Passenger demand of each station in 5 minutes

之后，根据乘客需求和站点之间旅行时间的动态变化信息，预约平台汇总第2个5 min后新的乘客需求，并更新接驳车辆站点之间的行程时间，如表7所示，再次利用2.2节中所述的方法进行求解. 以此类推，预约平台继续汇总之后每个5 min的乘客需求和更新接驳车辆站点之间的行程时间，并利用2.2节中所述的方法进行求解，直至能满足所有需求站点的所有乘客需求，如表8所示. 当前假设下，车辆行驶最终路径结果如图1所示，此时，15个需求站点发出的102个预约需求全部得以满足(为便于识别，分别以D1、D2、D3作为目标站点，给出了5-2-3-12-4-D1、5-13-6-3-12-7-D2、8-10-2-D3三条路径作为示意，并未列举所有路径).

图1 车辆行驶路径计算结果示意图Fig.1 Schematic diagram of vehicle routing results

表7 5 min后案例网络的旅行时间矩阵Table 7 Travel time matrix of case network after 5 minutes

表8 5 min后车辆的服务路径结果Table 8 Service path results of vehicles after 5 minutes

3.3 结果验证

为确保计算模型的准确性，保持现有常变量不变，保持假设案例中任意接驳车辆的行程时间不变，对100组由系统随机给出的15个需求点发出的102个预约需求进行算法验算，测试结果如下：

1) 在当前假定情况下，满足15个需求点的102个出行预约，需要的接驳车辆为17～21辆，84%的接驳车辆行程时长为6.67～8.33 h，如图2所示. 每辆接驳车辆的行驶时长约为24.59 min，这说明所建立的模型随机波动性较小，计算结果相对稳定可靠.

图2 接驳车辆行驶时间分布Fig.2 Time distribution of connecting vehicles

2) 模型计算结果显示：100组随机案例数据情况下，模型总目标函数值均在43.33～48.33 h，如图3所示. 也就是说在乘客预约需求变化较为频繁的情况下，目标函数受需求变化的影响较小，所建立的模型具有较高的鲁棒性.

图3 总的目标函数结果分布Fig.3 Total objective function result distribution

3) 计算结果表明：100组随机案例的模型计算时长均小于25.00 s，如图4所示，案例平均计算耗时约为12.04 s，因此可以证明本文所提出的模型能够满足大批量运算的要求，可为出行者和车辆运营企业节约等待时间，提升用户体验效果.

图4 模型求解计算耗时结果分布Fig.4 Time distribution of the model being calculated

4 结论

1) 以最大化乘客服务量、最小化所有乘客出行时间、最小化所有车辆运营时间为优化目标的灵活公交路径优化调度模型，能够更大程度满足乘客动态需求，有效减小规划路径的误差，缩短行车距离和乘客出行时间.

2) 乘客预约需求变化较为频繁的情况下，规划路径的总时间成本波动较小，说明所建立的模型具有较高的鲁棒性.

3) 基于引力模型的启发式算法能够较为精确且快速求得线路规划的模型的最优解. 随机产生的15个需求点的102个出行需求，全部服务完成所需车辆为17～21辆，平均每辆车的旅行时间为24.59 min，100组数据的求解时间均在25.00 s以内，计算耗时平均为12.04 s.