0 引言

公交车辆和乘务调度是公交运营管理的核心业务, 也是公交规划管理的研究热点之一。以人车固定搭配为主、多种值班类型共存的公交运营模式在我国许多城市被广泛采用。尽管针对公交调度的文献众多, 但是针对上述模式的公交调度研究甚少, 鲜有针对多种值班模式的深入建模分析, 这也造成实践中该类模式下公交调度的随意性和无效率。针对上述问题, 本研究尝试利用超级网络理念, 将问题转化为超级网络中的特殊网络流路径问题, 并通过分析问题可行解的网络拓扑形式, 从同一班型内部和不同班型之间2个层面对车次链进行分割重组操作, 实现调度中减少车辆空驶时间和平衡各乘务组之间工作量的目标。

下面从公交车辆调度和车辆与乘务组合调度2个方面简要介绍当前的国内外相关研究。在一般化的公交车辆调度研究方面, 针对交通拥堵等随机因素对车辆运行计划的影响, 文献[1] 提出了一种3阶段解决方法。针对给定的乘车需求的降低, 文献[2] 建立了相应的线性优化模型来在多种车辆条件下确定最小的车辆数。在假设司机开始工作时间无限制和休息时间不固定条件下, 文献[3] 建立了公交车辆和乘务调度的混合整数规划模型。在多车场条件下, 文献[4] 提出了通过微调部分车辆的发车时间进一步提升公交车辆的利用率。文献[5] 在多车场条件下比较了数种启发式车辆调度方法, 并给出了一种修复不可行解的方法。为提高计算效率, 文献[6] 提出在利用列生成算法求解多车场车辆调度问题时改用基于车次的分解方法。为了减少由于时刻表制订与车辆调度分开决策而可能增加的车辆需求, 文献[7] 建立了将二者统一决策的优化模型。文献[8] 提出利用跳站策略在减少乘客等车时间和车辆数目条件下协同决策自动驾驶班车的时刻表和车辆的调度。以班次时间接续、乘务组劳动强度、车场能力等为约束条件, 以最小化乘务组的车场驶入与驶出成本、停留等待成本和空驶成本为目标函数。文献[9] 建立了多车场公交乘务排班问题的数学模型。文献[10] 提出通过交换2条已定车辆路线来恢复和处理多车场条件下的车辆的延误和额外增加的任务。另外, 近年来研究者也分别从电动公交的数量、充电约束、半自动和自动驾驶差异、无人驾驶公交的调度策略选择等不同角度对特殊类型公交车的调度问题进行了深入研究^[11-18]。

在车辆与乘务的组合调度方面, 文献[19] 在考虑用餐时间窗约束条件下, 给出了整合公交车辆和乘务调度的优化模型。针对由于搜索二叉树的节点数呈指数级增长所导致的传统列生成方法难以有效处理较大规模乘务调度的问题, 文献[20] 提出利用线性松弛解信息, 逐次确定不被使用的换班机会集, 将问题转化为一系列规模逐次缩小的乘务调度问题。文献[21] 基于裁剪变邻域搜索算法求解乘务调度问题, 在模拟退火算法中设计了2种带概率的复合邻域结构以增加搜索的多样性, 帮助算法跳出局部最优。文献[22] 对公共交通驾驶员调度研究进行了系统的梳理和总结。

与现有研究相比, 本研究的特色主要表现为: (1) 通过超级时空网络区分公交调度的不同值班类型, 并利用网络元素间的关联关系刻画公交调度中车辆出入车场、站点停留、空驶和实际车次运行的逻辑关系, 深化对公交调度的认识, 为设计有效调度方法提供新的视角。(2) 以联接2个车次的接续为着眼点, 在相同班型车次链中搜索可替换的接续, 通过车次链的分割重组, 生成使得目标函数为局部最优的新替代车次链。(3) 针对不同值班类型规定的工作时间范围差异, 在2个给定班型的重叠时间段内, 确定可交换的部分车次链, 通过部分车次链的整体交换, 实现优化目标函数值且生成可行替代车次链的目的。(4) 双层邻域搜索在理论上可实现对解的可行域的遍历, 通过在执行2类邻域搜索过程中调整具体的搜索范围可以有效控制算法的执行时间。

1 超级时空网络构建 1.1 基本参变量介绍

d∈ D为所研究线路的关联车场, D为所有车场的集合。

s∈ S为车次的起终点, 一般为线路的起终站点。

v∈ V为1辆公交车, V为所有车辆的集合。

i∈ I为人车固定搭配模式下车辆或乘务组的第i类班型, I为所有班型的集合。

v_i∈ V_i为属于第i类班型的1辆公交车, V_i为第i类班型所有公交车的集合。

n_vi为第i类班型所有公交车的总数。

[0, T] 为1 d内公交线路运行的跨越时间段, 0和T分别为起止时刻。

[t_{i, start}, t_{i, end}] 为第i类班型的公交车的允许运行时段。

p, q∈ P为2个典型的公交车次, P为所有公交车次的集合。

(p, q)∈ C为联接车次p和q的接续, C为所有可行接续的集合。

(d, p) ∈ PO为联接车场d和车次p的出场弧, PO为所有出场弧的集合。

(p, d)∈ PI为联接车次p和车场d的入场弧, PI为所有入场弧的集合。

[t_{p, start}, t_{p, end}] 为车次p的跨越时间段, t_{p, start}和t_{p, end}分别为其起、止时间点。

[t_{q, start}, t_{q, end}] 为车次q的跨越时间段, t_{q, start}和t_{q, end}分别为其起、止时间点。

s_{p, start}和s_{p, end}分别为车次p的起、止站点。

s_{q, start}和s_{q, end}分别为车次q的起、止站点。

t_p为车次p的跨越时长, 其值等于t_{p, end}-t_{p, start}。

t_{(p, q)}为接续(p, q) 的跨越时长, 其值等于t_{q, start}-t_{p, end}。

t_{(p, q)}为接续(p, q) 包含的车辆空驶时间, 如车次p的终点与车次q的起点相同, 该值为0。

P_v为车辆v所执行的所有车次构成的车次有序集合。

t_v为车辆v所执行的所有车次的跨越时长之和, 称为对应车辆的车次链的工作时长。

x_{v, (p, q)}为车辆连续执行车次的决策变量, 其值为1时表示车辆v将依次执行车次p和q, 及利用接续(p, q); 其他情况, 其值为0。

x_{v, (d, q)}为车辆是否利用给定出场弧的决策变量, 其值为1时表示车辆v将利用出场弧(d, q); 其他情况, 其值为0。

x_{v, (p, d)}为车辆是否利用给定入场弧的决策变量, 其值为1时表示车辆v将利用入场弧(p, d); 其他情况, 其值为0。

t_layover为最小的车辆停站时间, 其间需要对车辆进行必要的检查和维护。

Ṫ为给定时间长度, 用于控制在同一站点生成接续的最大跨越时长。

为给定时间长度, 用于控制在两个不同站点之间生成接续的最大跨越时长。

为给定的时长, 用于限定最晚的出场弧结束时间。

为给定的时长, 用于限定最早的入场弧开始时间。

1.2 多班型调度的超级时空网络构建

多班型车辆调度问题需要解决在已知车次的起止站点、车次的起止时间和不同班型乘务组的数量条件下, 如何利用给定的乘务组集合完成对所有车次的执行。每个乘务组所执行的车次按时间顺序形成1个车次链, 这些车次链需要满足车次之间的时间衔接和空间位置衔接约束, 且彼此独立。超级时空网络通过添加一些虚拟的网络元素, 如虚拟的时空节点和时空弧段, 将现实问题中抽象的时空逻辑关系形象化为时空网络中点线之间的关联关系, 并通过网络流概念解释问题的各种约束与目标。利用超级时空网络可将多班型车辆调度中复杂的车次之间的时间衔接、位置衔接关系加以有效刻画, 并可利用网络流的概念刻画乘务组与车次之间的执行关系。通过构建车辆调度的超级时空网络, 不仅可进一步梳理问题所涉及的各种对象, 同时也可为设计求解问题的具体优化操作提供新的视角。

车辆调度对应的超级时空网络主要包括4种时空节点和5种时空弧段。1个时空节点由1对有序数字表示, 其中第1个数字指代节点的物理位置, 而第2个数字指代节点所处的时间点。如(d, 0) 表示位置在车场d, 在时空网络中的时间点为0。4种时空节点包括由车场形成的特定班型的车辆时空起点、由车场形成的特定班型的车辆终点、车次的时空起点和车次的时空终点。5种时空弧段包括车次弧段、出场弧、入场弧、接续和空驶车次弧。其中, 空驶车次弧包含于对应的接续之中; 由于接续的时间一般会大于所包含的最小车辆停站时间和空驶车次时间, 因此空驶车次的起止时间具有一定的灵活性。基于上述分析, 构建时空网络时仅将空驶车次弧的时间跨度和包含于相关接续的关系加以明确, 而不具体绘出。每个时空弧段由联接2个时空节点的弧段形成。除了车次弧给定外, 其他的时空弧段需按照一定的规则生成。

公交车辆调度的超级时空网络的具体构建步骤如下。

步骤1: 生成车辆的时空起点与终点。由车场d位置和班型i的工作时间范围[t_{i, start}, t_{i, end}] 生成对应第i种班型的时空起点(d, t_{i, start}) 和终点(d, t_{i, end})。对所有班型执行上述操作。

步骤2: 将所有的车次按照起始时间升序排列, 得到车次有序集合P。

步骤3: 生成可行接续。从车次集合P依次取出车次p, 与该车次所有后续的车次(如后续车次q) 逐一进行如下判断操作。如果条件t_layover≤ t_{q, start} -t_{p, end} ≤ Ṫ和s_{p, end} =s_{q, start}成立, 那么生成1个可行接续(p, q)∈ C。t_{sp, end, sq, start}为车辆从站点s_{p, end}行驶到站点s_{q, start}的所需的时间。如果条件t_layover +t_{sp, end, sq, start} ≤ t_{q, start} -t_{p, end} ≤ 和s_{p, end} ≠ s_{q, start}成立, 那么生成一个可行接续(p, q)∈ C, 同时生成包含于该接续的空驶车次。

步骤4: 生成可行出场弧。设i∈ I和q∈ P为任一班型和任意的1个实际车次。t_{d, sq, start}为从车场d行驶到站点s_{q, start}所需的行驶时间。如果条件t_{d, sq, start} ≤ t_{q, start}- t_{i, start} ≤ 成立, 则可生成可行的出场弧段(d_{i, start}, q)∈ PO。这里d_{i, start}为与班型i对应的时空节点(d, t_{i, start})。

步骤5: 生成可行入场弧。如果条件t_{q, end}-t_{i, start}≥ 成立, 则可生成可行的入场弧段(q, d_{i, end}) ∈ PI。这里d_{i, end}为与班型i对应的时空节点(d, t_{i, end})。

图 1给出了一个具有2个不同班型的调度时空网络。图 1中d_{1, start}和d_{1, end}标示了第1类班型对应的时空网络车辆的起终点; 而d_{2, start}和d_{2, end}标示了第2类班型对应的时空网络起终点。图 1下方是时间轴, 2类班型的起止时间标示在时间轴上。图中共有9个车次, 9条出场弧, 8条入场弧和16条接续。为了使图形更加清晰, 图中车次起终点位置和车场的位置并没有与这些对象的实际地理位置在图形的纵向存在关联关系。

2 调度模型

公交车辆调度的基本目的是利用给定数量的车辆实现对所有车次的完全覆盖, 同时使车辆的空驶时间最短。当车辆和乘务组为固定搭配时, 车辆的调度需要符合一定的工作条件约束, 其中比较重要的是各乘务组之间工作时间的平衡。平衡的工作时间可以避免由于工作时长的较大差异引发乘务人员对工作任务分配的不满。本研究将实现对所有车次的完全覆盖作为优化模型的约束条件, 而分别将最小化车辆的空驶时间和实现乘务组间工作时间的公平性作为优化的目标, 从而建立相应的调度优化模型。

如何权衡“最小化车辆的空驶时间”和“实现乘务组间工作时间的公平性” 2个目标是一个在资源有限条件下如何平衡效益最大化与任务分配公平性的问题。尽管本研究将分别针对上述2个目标构建具体的目标函数, 并通过实例分析比较不同目标的计算结果, 但是在实际应用时仍需要根据具体情况在二者之间进行平衡。例如, 当分别以二者为优化目标求得的结果显示增加的车辆空驶时间比较接近时, 可以在实际中采用以实现乘务组间工作时间的公平性为目标得到的结果; 而当二者对应的结果差异较大时, 就要分析公平性要求诱发的空驶时间代价是否可以接受。为了权衡2个目标带来的结果差异, 实践中管理者有必要采取其他措施, 如超时工作补贴, 来使工作任务的安排获得乘务人员的认可。

设向量x为由所有x_{v, (p, q)}, x_{v, (d, q)}, x_{v, (p, d)}, ∀ p∈ P, q∈ P构成的向量。在给定x的条件下, 所有被采用的空驶车次的总运行时间的计算公式为:

(1)

车辆v对应的车次链所包含的所有车次的跨越时长计算公式为:

(2)

在所有车次信息给定条件下, 可以方便地得到运行所有车次总的工作时间。在给定车辆总数n_V条件下, 即可顺利得到所有车辆的平均工作时间t_average。而所有车辆的工作时间的偏差可以表示为:

(3)

以f₁(x) 或f₂(x) 作为优化目标的公交车辆调度模型如下:

(4)

(5)

(6)

(7)

(8)

(9)

(10)

(11)

调度模型(4) ~ (11) 的目标函数项(4) 的含义已经在前面作过解释。为了方便理解模型含义, 可以结合超级时空网络, 将x视为一类特殊的网络流量。该流量可依据对应的车辆不同细分为不同的类别。约束(9) ~ (11) 限定该流量为不可分割的单元化流量。约束(5) 中集合I_q表示与车次q之间存在前向可行接续的所有车次的集合, O_p表示与车次p之间存在后向可行接续的所有车次的集合。约束(5) 的含义为对于给定流量类别, 即v∈ V给定, 对于任意给定的一个车次而言, 流入该车次对应的时空弧段的流量等于流出该弧段的流量。约束(5) 为对应车次弧段的流量守恒约束。约束(6) 为所有流入任意给定车次q∈ P的流量必须等于1。结合约束(5) 可知, 满足约束(6) 的流量x将覆盖所有车次, 且任意车次仅能被一类网络流所覆盖。约束(6) 被称为车次的唯一覆盖约束。约束(6) 也可被下面的约束替代:

(12)

约束(12) 表示所有流出任意给定车次p∈ P的流量必须等于1。约束(7) 和(8) 分别为流出和流入对应给定班型的时空车场节点的流量守恒约束。结合前面的约束(5) 和(6) 可知, 约束(7) 和(8) 限定不同班型的车辆不能相互替换与混合, 即给定班型的车辆必须满足给定班型的工作时间范围限制。

上述公交车辆调度模型也可转化为等价的集合覆盖问题模型, 不过转化后的模型一般会将车次间的可行接续关系等隐含起来。等价的集合覆盖模型尽管形式简单, 但是由于隐含了研究对象之间大量的逻辑关系, 因此不利于后续实现对问题的具体求解。集合覆盖问题具有NP-hard特征, 因此可以推出上述模型(4) ~ (11) 也具有NP-hard特征。考虑到车辆调度问题本身的规模较大, 因此有必要设计有效的启发式算法对其加以求解。

3 双层邻域搜索算法

邻域搜索是通过定义可行解邻域, 并在给定可行解邻域内改变可行解, 以期优化目标函数或扩大问题可行解的搜索范围。如果以求得给定邻域内最佳的可行解为目标, 相应的邻域搜索称为贪婪式邻域搜索。如果以改变解的选择范围、防止算法过早陷入局部收敛为目的, 相应的邻域搜索称为随机邻域搜索。邻域搜索是许多算法的重要组成部分, 也可独立成为问题求解的方法。本研究将针对多班型车辆调度的特征, 设计双层邻域搜索算法。其中, 在单一班型的车次链之间采用贪婪式局部邻域搜索。而在不同班型的车次链之间采取随机优化的邻域搜索。下面首先介绍2类邻域搜索的具体操作, 然后给出搜索算法的具体实施步骤。

3.1 两类邻域搜索

如果2辆车属于同一班型, 则其对应的车次链在超级时空网络中具有相同时空起点和终点。因此可在同一班型的车次链之间实施比较自由的分割和重组, 得到新的可行车次链。1个车次链可以在其包含的1个接续处分割得到前后2个部分车次链。多个同班型的车次链经分割后, 如果可以重新组合, 即可得到同等数量的新车次链。下面以图 2为例, 说明如何利用上述思想实现单班型内的邻域搜索优化。

图 2中小圆圈表示1个车次, 车次序号为圈中标示的数字。车次间的带箭头的线段为联接车次的接续。实线表示被当前车次链采用的接续, 短划虚线为可行的但未被采用接续, 而点划虚线为不可行的接续。不可行接续仅为分析问题方便而添加。假设当前考虑的接续为(1, 2)。首先从当前接续的尾车次出发, 得到与之后向相接的所有车次, 这里包括车次2, 3, 4; 然后从这些车次出发找到被当前班型的车次链采用的接续, 并得到相应的接续的尾车次, 这里包括1, 5, 6。接着, 在上述尾车次集合{1, 5, 6} 和头车次集合{2, 3, 4} 之间添加可行的接续和不可行的接续, 构成1个指派问题的二部图。随后, 根据优化的目标函数计算二部图前后车次之间如果实际发生接续时对应的指派费用。最后, 利用匈牙利算法求得指派问题的最优解, 并根据计算结果重新组合构建新的车次链。上述搜索优化属于邻域搜索中的贪婪式邻域搜索。

与同一班型的车次链分割重组不同, 不同班型的车次链之间不能进行上述较为自由的分割重组, 因为任意2个班型的车次链的起止时间不同, 上述的分割重组往往会生成不可行的车次链。因此, 针对不同班型的车次链设计了班型层面的邻域搜索优化。下面以图 3为例, 对不同班型车次链的邻域搜索进行解释。

图 3 (a)为2条不同班型的车次链在搜索优化前的状态。车次链1属于班型i。该车次链从其对应时空车场节点d_{i, start}出发, 首先经出场弧(d_{i, start}, p₁) 到达车次p₁, 然后经过一系列的接续和车次到达车次p₂, 从车次p₂出发经接续达到车次p₃, 最后从车次p₃出发, 经一系列的接续和车次到达其时空车场终点d_{i, end}。车次链2属于班型j。该车次链从其对应时空车场节点d_{j, start}出发, 首先经一系列的接续和车次到达车次p₄, 从车次p₄出发经接续达到车次p₅, 从车次p₅出发, 经一系列的接续和车次到达车次p₆, 最后从车次p₆出发, 经入场弧(p₆, d_{j, end}) 到达其对应时空车场节点d_{j, end}。要对上述2条车次链进行分割重组操作从而形成2条新的车次链, 首先需要确定二者的重叠时间段[t_{i, j, start}, t_{i, j, end}]。重叠时间段的起止时间在图 3中用2条竖直线标示。然后, 分别确定2条车次链被重叠时间段包含的可交换部分, 如图 3中车次链1的车次p₁与车次p₂之间的部分。接着, 判断2车次链重叠时间段内部分是否可以交换, 即如图 3 (b) 中的出场弧(d_{i, start}, p₅)、接续(p₄, p₁)、入场弧(p₂, d_{j, end}) 和接续(p₆, p₃) 是否可行。随后, 如果上述交换可行, 判断交换后目标函数是否改进。最后, 如果判断交换后得到改进的目标函数, 则对2条车次链进行实际的分割和重新组合。图 3仅给出了1种2条车次链的时间重叠形式, 也存在1条车次链的跨越时间包含另一车次链跨越时间的情况。不同时间重叠形式下的车次链交换操作基本相似。上述不同班型车次链之间的邻域搜索属于随机优化邻域搜索。

3.2 双层邻域搜索算法的求解步骤

基于前文给出的2类不同层面的邻域搜索, 可以构建对应的双层邻域搜索优化算法。算法的具体执行步骤如下。

步骤1: 超级时空网络构建。按照1. 2节给出的方法, 建立调度的超级时空网络。

步骤2: 初始解生成。首先, 在时空网络上为每个车场时空起点添加给定的车辆; 然后按照时间的升序, 逐一考虑每个车次的执行; 按照当前空闲车辆的空闲时间长短和距离当前车次的空驶时间长短, 随机选择1辆可用公交车执行当前车次; 更新所有车辆的状态, 包括空闲和运行状态、位置的更新, 转下一车次继续上述操作, 直到所有车次被执行。

步骤3: 同一班型内的邻域搜索。逐一考虑不同班型包含的车次链, 按照3. 1节的同班型内部车次链邻域搜索对相关车次链所包含的接续进行操作。考虑到每次如果对所有接续进行邻域搜索的计算时间较长, 因此可按一定的概率只选择部分接续加以邻域搜索。

步骤4: 多班型之间的车次链邻域搜索。任意选择2个不同班型执行如下操作。首先确定2个班型的重叠时间段; 根据重叠时段分别确定单个班型的车次链包含于该时段内的可交换部分, 形成对应班型的部分车次链集合; 在2个部分车次链集合中, 各取出1个部分车次链, 按照3. 1节给出的方法进行车次链的交换操作。可以根据需要重复上述步骤多次, 从而达到优化目标函数和扩展解的搜索范围的目的。

步骤5: 终止判断。如果已达到规定的最大迭代次数, 则终止算法, 输出目前得到的最佳调度结果; 否则, 更新迭代次数, 转步骤3, 进行新的迭代操作。

设置最大迭代次数作为启发式算法的终止准则是一种常见做法, 但是具体的最大迭代次数需要通过试算来确定。例如本研究处理的公交车辆调度问题, 由于算法在迭代10余次后即收敛, 因此最大的迭代次数设置为20次即可。在算法中为同一班型内的邻域搜索设置执行概率是为了避免对所有接续进行相关邻域搜索, 从而减少计算耗时。在算法运行的初期, 考虑到不同班型之间邻域搜索的影响, 大量的同班型邻域搜索可能效果并不理想。同一班型内邻域搜索执行概率的值大致决定了进行同班型邻域搜索的接续比例。上述执行概率的大小也需通过试算, 在平衡计算效率和计算资源条件下决定。

4 实例分析

通过一个实例验证本研究模型与算法的有效性。选取的公交线路具有1个车场d, 2个发车点, 分别记为s₁和s₂。线路运行分为3个值班类型, 3个班型的允许工作时间范围分别为5:00—17:00, 10:00— 22:00, 11:40—23:30。3个班型对应的车辆或乘务组数目分别为22, 10, 20。在生成调度超级时空网络时, 用于控制在同一站点生成接续的最大跨越时长Ṫ设为300 min, 用于控制在2个不同站点之间生成接续的最大跨越时长设为400 min, 用于限定最晚的出场弧结束时间设为700 min, 用于限定最早的入场弧开始时间设为600 min。

表 1给出了在不同时段内发车时1个车次的运行时间。表 2给出了不同时间段内从主副2个发车点发出的车次的时间间隔和发车数。利用表 1和2的数据可方便生成具体的车次信息。后面表 4中出现的车次序号是按照先主站, 后副站, 依时间顺序从表 1和2数据得到的。表 3给出了车场与发车站点间的车辆空驶行驶时间。

以最小化各车次链之间的实际工作时间偏差为优化目标, 表 4给出了部分计算结果。表中缩写“TCT”、“PT”、“DT”和“RT”分别表示车次链实际开行车次的时间(Trip Chain Time)、出入车场的开行时间(Pulling Time)、车次链包含的空驶车次开行时间(Deadheading Time) 和停驶休息时间(Rest Time)。表中数据显示为了平衡工作时间出现了大量的空驶时间, 而如果以最小化空驶时间为目标, 算法可以得到一个无空驶车次出现的结果, 但是各车次链工作时间会表现出显著的不平衡性。在以最小化空驶时间为目标时, 计算得到的工作时间变化范围为从最短的170 min到最长的435 min, 而休息时间变化范围为从最短的245 min与最长的525 min。计算同时表明要覆盖所有车次, 线路至少需要52 veh公交车。

利用Java 1. 8. 0程序实现双层邻域搜索算法, 在NetBeans IDE 8. 0. 2开发环境下运行, 采用的计算机处理器为Intel ® Core i3 - 3120M CPU。以表示所有车次链运行时间的标准偏差。算法的最大迭代次数设为20, 在进行单邻域内部搜索时, 对考虑相关接续是否执行邻域搜索的概率设为0. 3。图 4给出了随迭代次数增加, 利用不同邻域搜索策略得到的目标函数值ω的变化趋势。图 4中系列1对应双层邻域搜索, 系列2对应仅进行同一班型内部的邻域搜索, 系列3对应算法仅进行不同班型之间的邻域搜索。图 4表明, 2种邻域搜索策略配合的计算效果最佳, 仅进行同一班型内部的邻域搜索有一定效果, 而仅进行不同班型之间的邻域搜索基本没有效果。上述结果基本反映了2种策略的效率。针对其他线路的计算也表现出类似的结果。图 4数据也说明算法具有较强的收敛性, 一般迭代10次左右即可得到最佳效果。对应系列1的计算时间为1 min 48 s; 对应系列2的计算时间为1 min 42 s; 而对应系列3的计算时间为3 s。

5 结论

通过建模分析和实例验证, 可得到如下主要结论: (1) 利用超级时空网络中添加的虚拟时空节点和弧段可以刻画公交调度中涉及的各种对象及对象间复杂的时空关联关系, 而网络流概念的引入可方便地描述多班型公交车辆与车次之间的具体执行关系。(2) 如果仅以平衡车次链之间的工作时间为优化目标, 各乘务组间的任务分配将较为公平, 但会增加总的车辆空驶时间; 而仅以最小化车辆的空驶时间为优化目标, 则可能导致乘务组间较大的任务分配量差异。基于上述原因, 在实际调度中必须根据需要对2个目标加以合理权衡。(3) 双层邻域搜索算法在理论上可以遍历解的可行空间, 且算法仅需设定最大迭代次数和同一班型内邻域搜索的执行概率2个参数。算法的收敛性较强, 求解实例时仅需迭代10余次即收敛。可以将2类邻域搜索单独使用, 也可组合使用。而组合使用的计算效果最佳, 而仅进行同一班型内的邻域搜索计算效果次之。

在本研究基础上, 可进一步深入的研究方向包括: 多线路多车场情景下的公交车辆调度、可变时刻表情景下的公交调度、考虑随机因素影响下车次运行时间变动的公交车辆调度, 以及针对特殊类型公交车辆的多班型调度等。