1. 引言

公交车辆调度是公共交通运营中的关键环节[1] [2]。每条公交线路均设有两个发车站点，司机可以在工作间隙或工作结束后在相应站点休息，并依据各站点对应的发车时间表进行调度[3]。一个车次指的是公交车从一个发车站点出发，经停沿线路线的若干站点，最终到达另一个发车站点的运行过程。发车时间表中的每个发车时间对应一个车次的开始，即公交车从当前站点发出并前往另一个发车站点。每个车次必须有且只能由一辆公交车执行。公交车辆调度问题(BVSP)涉及如何合理安排有限数量的公交车辆，以执行发车时间表中的所有车次，是公交公司在保障服务质量与降低运营成本中的核心挑战。

合理的公交车辆调度应具备以下几个特征：所需的公交车数量应最少、公交车的空驶时间应尽量减少并且所有司机的工作时间分配应尽可能公平。尽管当前已有大量关于公交车辆调度问题(BVSP)的研究，但由于该问题规模较大且复杂性较高，如何构建具有较强解释性的模型并设计出高效的解决方法，依然是研究的难点所在。本文从超级时空网络的视角对BVSP进行分析，通过梳理网络元素之间的关联关系，明确BVSP中各对象之间的相互联系，进而构建出具有高度解释性的模型。在此模型基础上，进一步分析可行解的拓扑结构，并设计出针对性的高效求解方法。

目前，针对公交车辆调度问题(BVSP)的自动调度方案生成方法已经有很多研究成果。其中，一些方法专门用于解决单车场的公[4]交车辆调度问题。Haased等人提出了一种精确算法，用于同时调度公交系统中的车辆和乘务组。Chao等人[5]通过改进非支配排序遗传算法(NSGA-II)，提出了一种多目标优化方法，专门用于解决电动公交车调度问题。针对快速公交调度，Sun等人[6]提出了一种基于遗传算法的解决方案。Kwan等人[7]为BVSP提出了一个启发式算法。Lin等人[8]构建了一个数学规划模型，用于公交车辆与乘务组的联合调度问题，将车辆和司机数量合并为一个目标函数，并采用分支定界算法进行求解。Shui等人[9]针对单车场BVSP，提出了一个基于克隆选择算法的方法，并成功应用于实际问题。

学术界还提出了许多用于解决多车场公交车辆调度问题(BVSP)的方法。Gintner等人[10]提出了一个两阶段方法，专门用于解决多车场、多车型的公交车辆调度问题。Liu等人[11]构建了一个整合时间表问题与车辆调度的同步优化模型，并为该模型设计了双层启发式算法。Forbes等人[12]针对多车场车辆调度问题提出了一个精确算法。Banihashemi等人[13]为实际的多车场公交调度问题引入了一个启发式方法，考虑了行程时间的限制。Wei等人[14]首次结合蚁群系统、最大–最小蚁群系统和最佳–最差蚁群系统，提出了改进的蚁群优化算法用于解决BVSP。Cender等人[15]基于亏损函数理论(deficit function theory)，提出了一个启发式方法来解决车辆调度问题。Kliewer等人[16]提出了一个基于时空网络流的模型，显著减少了决策变量的数量。Haghani等人[17]构建了一个带有行程时间限制的整数规划模型，并提出了一个精确算法及两个启发式算法来解决BVSP。Guo等人[18]则提出了一个结合列生成方法的遗传算法，用于解决多车场的电动公交车辆调度问题。

公交调度需要考虑多种因素，单一目标的调度难以全面满足公交公司或社会的需求。传统以运营成本最小化为单一目标的调度方式需要兼顾服务质量和社会效益等多方面的平衡。最小化运营成本是公交企业追求经济效益的核心目标[19] [20]，同时，提高服务水平，如缩短乘客等待时间[21]，以及减少环境影响[22]，也日益成为关注的重点。如何在两者之间取得最佳平衡一直是公共交通领域的研究难点。现有文献通过设计在线调度框架[19]和多目标算法[20]，在平衡成本与服务质量方面取得了一定进展。此外，充分利用运营商的现有资源[23]，确保不同车型和员工的合理配置与协作，直接关系到企业效益的提升。一些文献专注于最小化运营成本与提高服务质量的平衡。例如，Zuo等人[24]对多目标遗传算法进行了改进，从生成的候选车队中选择多个子集作为帕累托最优解。Wang等人[25]也研究了如何在不增加运营成本的前提下保证服务质量，特别是在考虑交通拥堵不确定性的情况下，实现动态公交车辆调度。在电动公交车队的调度中，实现充电成本的最小化也是降低总成本的重要途径。电力市场的环境与政策对公交企业的充电成本和调度有着重要影响。Rafique等人[26]提出了一个两阶段的多目标随机优化模型，旨在同时最小化电力成本和电池衰减惩罚成本，以减少运营商的实际成本。

公交车辆调度问题(BVSP)的研究已经取得了许多成果，涉及单车场和多车场等多种调度场景。不同的研究主要聚焦于提高调度系统的运行效率、降低成本及优化服务质量等。这些方法包括精确算法、启发式算法和多目标优化算法等，针对不同的需求和约束条件，展现了各自的优越性。在单一目标和多目标的调度模型中，以最小化运营成本为核心的传统方法逐渐向多目标优化过渡，以适应现代公交系统对服务质量和社会效益的更高要求。部分研究探索了电动公交车队调度中的充电成本问题，表明调度决策与充电策略间的关联性在电动公交系统中至关重要。

尽管现有研究已取得较大发展，但依然存在一些不足之处：1) 目前的公交调度研究较为成熟，但大多数仍采用传统调度方式，缺乏能够挖掘调度过程中时空关系的方法来解释和建模公交调度问题；2) 现有的多目标公交调度研究主要关注于降低运营成本和减少排放，而本文则进一步考虑了车队规模、公交乘务工作时间的公平性和车辆空驶距离三者之间的平衡关系，从而在调度方案中实现更全面的优化。

2. 公交调度的超级时空网络

本章节旨在介绍公交调度系统中的一些基本元素(如车场、车次以及车次之间的连接方式等等)在超级时空网络中的表示方法，以及如何利用这些基本元素构建出公交调度系统的超级时空网络。

2.1. 基本网络元素

图1展示了一个简单的公交调度超级时空网络，由单个车场和两个具有上下行发车站点的公交线路构成。公交系统的一些信息在该网络中通过节点和弧段来表示。由于该网络为时空网络，所有元素都具有时间和空间属性。节点的坐标由一个有序数对表示，分别为节点的空间位置和时间位置。网络中的所有弧段均为有向弧，其方向为时间增加的方向。在网络中，用符号d表示车场，图中将车场在时间上分化为两个节点，分别为(d, 0)和(d, T)，其中0和T分别表示车场d的最早发车和最晚收车时刻，即[0, T]为车场的工作时间区间，因此(d, 0)和(d, T)构成了整个公交调度超级时空网络的起止节点。图中，黑色实线段表示车次弧段，其长度表示车次的时间尺度，弧段两端的黑色实心节点分别为车次的开始和结束时空节点，每个节点包含空间位置和时间位置。车次弧段在图中的位置仅与时间相关，垂直方向的位置是随机的。连接车场和车次的点划线弧段为出入场弧，该弧段代表车辆从车场出发前往执行第一个车次，或在完成最后一个车次后返回车场。此类弧段的起始节点为(d, 0)或车次的开始节点，尾节点为(d, T)或车次的结束节点。连接两个车次的虚线弧段为接续，表示车辆在完成上一个车次后执行下一个车次，并且在时间和空间上是可行的。

Figure 1. Simple super spatiotemporal network for bus vehicle scheduling

图1. 简单的公交调度超级时空网络

2.2. 公交调度超级时空网络的构建

2.2.1. 网络参量介绍

为了便于读者阅读，将网络中的参量列举成表格，如表1所示。

Table 1. Parameters in super spatiotemporal network for bus vehicle scheduling

表1. 公交调度超级时空网络中的参量

2.2.2. 网络构建

时空网络由网络节点、网络弧段和时间轴等元素构成，其中每个节点由一对有序数对(A, B)表示，A代表节点的空间位置，B代表节点的时间位置。网络中共有两类时空节点。第一类是网络的起始和结束节点$\left(d,0\right)$ 和$\left(d,T\right)$ ，即车场的工作开始和结束时间，[0, T]为车场的工作时间区间，所有的发车、运行和收车操作必须在此时间区间内完成。第二类时空节点是所有车次的起始和结束节点。例如，$\left(s_i^{start},t_i^{start}\right)$ 和$\left(s_i^{end},t_i^{end}\right)$ 分别表示车次i的发车站点及发车时间，以及结束站点及结束时间。

所有网络弧段均为有向弧，其方向与时间增加方向一致。第一类网络弧段是所有车次的弧段，本文假设所有车次信息已知，因而此类弧段在网络中固定存在。第二类弧段连接一个车次的终点和下一个车次的起点，称为接续，其在网络中需根据以下规则生成：假设i和j分别为两个车次，当$t^l+t_{s_i^{end},s_j^{start}}\le t_j^{start}-t_i^{end}\le T_1$ 成立时，生成可行接续$\left(i,j\right)\in C$ 。其中$t_{s_i^{end},s_j^{start}}$ 表示从车次i的终点站前往车次 j的始发站的车辆行驶时间。当车次i的终点站与车次j的始发站为同一站点时，该值为0；若两站点不同，则该值为两站点之间的空驶时间。此时，接续$\left(i,j\right)$ 便包含一个第三类时空弧段，即空驶弧段。空驶弧段与空驶车次对应，本文将尽量减少空驶行程以降低运营成本。第四类与第五类弧段分别连接车场与车次，称为出场弧和入场弧。出场弧以$\left(d,0\right)$ 为起点，以$\left(s_i^{start},t_i^{start}\right)$ 为终点。当满足$t_{d,s_i^{start}}\le t_i^{start}-t_d^{start}\le T_2$ 时，可以生成出场弧$\left(d,i\right)$ 。入场弧以$\left(s_i^{end},t_i^{end}\right)$ 为起点，以$\left(d,T\right)$ 为终点。当满足$t_{s_i^{start},d}\le t_d^{end}-t_i^{end}\le T_3$ 时，可以生成入场弧$\left(i,d\right)$ 。

3. 基于超级时空网络的公交调度模型

3.1. 模型参数

网络中的元素已经在2.2.1小节说明，本节参数的罗列是为了更好的基于超级时空网络对公交调度进行建模，同样，为了便于读者阅读，以列表的形式呈现，如表2所示。

Table 2. The rest parameters in super spatiotemporal network for bus vehicle scheduling

表2. 公交调度超级时空网络中的其他参量

3.2. 目标函数

在公交调度的复杂流程中，车辆需在始发站和终点站之间往返，以满足一系列车次的运行需求。这些车辆在未载客情况下的行驶被称为空驶。不合理的车辆调度策略可能导致系统内空驶行程的增加，进而造成能源和运输资源的不必要消耗。为了有效优化公交车队的运营效率和资源利用，本文的首要目标函数旨在减少公交车队的空驶时间，从而提高系统的整体效益。使系统总空驶时间最小的目标函数如下：

$f_1=\text{Minimize}{\displaystyle \sum _{b\in B}{\displaystyle \sum _{\left(i,j\right)\in C}{y}_{\left(i,j\right)}^b{\overline{t}}_{\left(i,j\right)}}}$ (1)

在实际公交调度中，通常采用人车固定的工作模式，即将特定司机与特定车辆一一配对。在这种情境下，当为某一车次分配车辆时，该司机的工作时长会随之增加。不合理的分配可能导致司机工作负担不均衡。因此，在公交车辆的调度过程中，应重点考虑车次链中司机工作时间的公平性，以确保所有司机的工作负荷合理平衡。对于某一辆具体的公交车，其工作时间设为$t_b$ ，则可由以下公式得到：

$t_b=\frac{1}{2}\left[{\displaystyle \sum _{\left(i,j\right)\in C}{y}_{\left(i,j\right)}^b\left(t_i+t_j\right)}+{\displaystyle \sum _{\left(d,j\right)\in PO}{y}_{\left(d,j\right)}^b{t}_j}+{\displaystyle \sum _{\left(i,d\right)\in PI}{y}_{\left(i,d\right)}^b{t}_i}\right]$ (2)

因此所有公交车的工作时间之和为：

$T_{total}={\displaystyle \sum _{b\in B}{t}_b}$ (3)

所有公交车的工作时间平均值为：

$T_{average}=\frac{T_{total}}{N_b}$ (4)

其中$N_b$ 为使用的公交车的实际数量。故要使司机的工作时间公平性最大，则使其工作时间偏差最小即可，得到以下目标函数：

$f_2=\text{Minimize}\frac{{\displaystyle {\sum }_{b\in B}{\left(t_b-T_{average}\right)}^2}}{N_b}$ (5)

此外，为了进一步提高公交公司的运营效率和经济效益，通常的目标是以最小车队规模满足所有车次的运行需求。因此，最小化车队规模也成为本文的研究目标之一，旨在探索如何在满足所有运输需求的前提下，通过合理的调度策略来减少车队规模，从而有效控制和优化运营成本。使公交车队规模最小化的目标函数如下：

$f_3=\text{Minimize}\frac{{\displaystyle {\sum }_{b\in B}{\left(t_b-T_{average}\right)}^2}}{N_b}$ (6)

3.3. 约束条件

${\displaystyle \sum _{\left(i,j\right)\in L}{y}_{\left(i,j\right)}^b}+{\displaystyle \sum _{\left(d,j\right)\in PO}{y}_{\left(d,j\right)}^b}={\displaystyle \sum _{\left(j,k\right)\in L}{y}_{\left(j,k\right)}^b}+{\displaystyle \sum _{\left(j,d\right)\in PI}{y}_{\left(j,d\right)}^b},\forall j\in I$ (7)

${\displaystyle \sum _{\left(d,j\right)\in PO}{y}_{\left(d,j\right)}^b}\le 1,\forall b\in B$ (8)

${\displaystyle \sum _{b\in B}{\displaystyle \sum _{\left(d,j\right)\in PO}{y}_{\left(d,j\right)}^b}}=N_b$ (9)

${\displaystyle \sum _{h\in H}{\displaystyle \sum _{\left(d,j\right)\in PO}{y}_{\left(d,j\right)}^b}}={\displaystyle \sum _{d\in D}{\displaystyle \sum _{\left(j,d\right)\in PI}{y}_{\left(d,j\right)}^b}},\forall b\in B$ (10)

${\displaystyle \sum _{\left(i,j\right)\in C}{\displaystyle \sum _{b\in B}{y}_{\left(i,j\right)}^b}}=1,\forall i\in I$ (11)

模型中的变量y可以被视为网络中的流量。约束(3.7)表示所有车次的第b类流量守恒，即出入流量相等。这意味着对于任何车次，当车辆b执行结束后，需要继续执行后续车次或返回车场，而不会在此车次上滞留。约束()用于限制从车场出发的第b类流量之和不大于1，即所有车辆只能从车场最多发车一次。约束(3.9)表示所有从车场出发的车辆构成实际的使用车辆。约束(3.10)表示流出车场的第b类流量与流入车场的第b类流量相等，从而保证车场的车辆数量守恒。约束(3.11)表示流经任意车次的所有类别流量之和为1，意味着每个车次都需要被执行，并且只被执行一次。

4. 多目标3M算法

4.1. 3M算法

4.1.1. 生成初始解

生成初始解的过程是将每个车次分配给一辆公交车执行，从而形成每辆车的车次链，并最终构成一个完整的初始解。

在生成初始解的过程中，首先将所有车次按照发车时间进行升序排列。接着，逐一遍历这些车次，为每个车次选择一辆当前空闲的公交车来执行，并立即更新该车辆的状态，使其在当前车次结束前不再接受新的车次任务。一旦所有车次都被分配完毕，每辆公交车将按顺序执行其分配的任务，形成一条车次链。在车次链中，相邻车次之间的连接关系由变量$y_{\left(i,j\right)}^b$ 表示。

每一辆公交车对应一条车次链。当车队中包含$N_b$ 辆公交车时，一个可行解即由$N_b$ 条车次链组成。

4.1.2. 混声操作

在此步骤中，将基于前一阶段生成的初始解，构造出一系列新的可行解。这些新解在保留部分原始解特征的同时，加入新的元素，从而丰富了解的多样性。这一过程实际上是向优秀个体学习的过程。首先从初始解中挑选出所有非支配解并进行标记，标记内容包括这些非支配解中的出入场弧和接续的车次与车辆的对应关系。随后，按照生成初始可行解的方式构建新解，但在为车次选择车辆时，会以一定的概率优先选择那些已标记的车次与车辆的对应关系。最后，需检查新生成的解是否与原初始解相同。如果新解与初始解重复，则需重新执行该过程，直至生成一个与初始解不同的新解为止。

4.1.3. 变异操作

为了保证种群的多样性并扩大解的搜索空间，需要对可行解进行一定程度的扰动。为了确保扰动后的解仍然可行，扰动过程必须基于公交调度的超级时空网络进行。对于解集合中的每一个解，每一条车次链的每一个接续均进行是否变异的判断，当都符合变异的条件时，对相应的接续进行变异操作。在具体操作之前，对一些关键术语进行解释。车次i的“后续车次”指的是发车时间在车次i之后且在超网中与车次i有接续连接的车次，而车次i的“前向车次”指的是发车时间在车次i之前且在超网中与车次𝑖有接续连接的车次。

以图2演示接续的改变，图中每个圆圈代表一个车次，带有箭头的实线为当前解中实际采用的接续，带有箭头的虚线表示网络中存在但在当前解中并未采用的接续，不同的车次链以颜色区分。以接续(1, 2)为例具体说明变异的过程。首先，找出超网中车次1的所有后续车次，比如节点3和4；然后，在后续车次中随机选择一个，例如车次2为车次5的后续车次，则用接续(1, 4)和(5, 2)代替接续(1, 2)和(5, 4)。在上述操作中，如果车次4的前向车次与车次1的后续车次之间没有接续，则选择车次1的其他后续车次进行分析。当所有后续车次均无法实现此变异过程时，保持原有的接续(1, 4)。

Figure 2. Illustration of mutation

图2. 变异操作示意图

4.1.4. 成长操作

在表现较好的个体中，通过自我成长操作可以进一步提升解的质量。该成长过程类似于邻域搜索，但更具方向性，即确保解集向更优的方向变化。成长操作分为两部分：成长指派网络的构建和新的非支配解的生成。以图3为例，具体步骤如下：1) 找到车次1的所有后续车次；2) 在当前可行解的车次链集合中，找到所有车次1的后续车次的前向车次；3) 为当前找到的所有车次添加可行接续。

Figure 3. Illustration of mature

图3. 成长操作示意图

成长指派网络构建完成后，需要计算网络中每一个接续的成本值，成本值包括两个目标函数：系统总空驶时间和工作时间公平性。由于一个解的车队规模恒定，接续操作只需计算剩余目标函数的成本变化。通过增加值来表示接续所导致的成本变化，构建网络对应的空驶时间增加矩阵和工作时间方差增加值矩阵，再采用加权法得到最终的网络成本矩阵。最后，应用匈牙利算法求解该成本矩阵，并保留新生成的非支配解。

4.2. 多目标3M算法

上述3M算法的描述涉及可行解在算法执行过程中的具体变化。在此部分，将详细介绍如何使用基于3M算法的方法来求解多目标公交车辆调度问题的具体步骤。

步骤0：初始化。在算法开始之前，需要设置初始种群规模M，需要生成的混合解的数量N，可行解的变异系数$\epsilon$ 和成长系数$\theta$ ，以及最大迭代次数K。令初始迭代次数$\tau =0$ 。

步骤1：生成规模为M的初始种群，并提取出其中的非支配解集ND。

步骤2：基于非支配解集ND执行混合操作，生成N个新个体。

步骤3：将步骤2中生成的N个新个体与初始种群合并，并从合并的解集中去除N个被支配个体，以保持种群规模不变。若此时被支配个体数量少于N，则在去除所有被支配个体后，随机保留M个个体。

步骤4：对种群执行变异操作。对于种群中的每个接续，以概率$\epsilon$ 进行变异。

步骤5：从变异后的种群中提取出非支配解集ND，并对其执行成长操作。对于ND中的每个解，依次遍历其中的所有车次链，每条车次链均以概率$\theta$ 成长。需要成长时，随机选择车次链中的一个接续执行成长操作。该过程将生成一个新的解集NND。

步骤6：若NND为空，执行步骤7。若非空，则提取出NND中的非支配解集ND。若ND的规模大于M，则从中随机选择M个个体作为最终解集。否则，将ND视为最终解集。

步骤7：终止条件判断。当达到最大迭代次数或NND为空时，算法终止。否则，令迭代次数$\tau =\tau +1$ ，并返回步骤2。

5. 多目标公交车辆调度案例

为了验证本文提出的模型和算法的有效性，本节将其应用在中国青岛市的某个实际公交线路上。

5.1. 案例数据

案例选取线路的相关数据如表3、表4和表5所示。受到不同时间段交通状况的影响，不同时间段发车的车次运行时间不一样。具体发车区间及其对应的班次运行时间如表3所示。因为是单线双向发车，故有两个发车站点，分别为主站s1和副站s2，两个站点拥有独立的发车计划，表4给出了两个发车站点在各发车区间的发车最优间隔和发车数量。表5给出了主、副站点以及车场之间的空驶时间。

Table 3. Travel time of different time intervals

表3. 不同发车区间的车辆运行时间

Table 4. Scheduling plan

表4. 发车计划

Table 5. Deadheading time of vehicles between depot and bus stations

表5. 发车场及发车站点之间的车辆空驶时间

5.2. 案例结果

本节讨论上述案例的研究结果，以此评估本文提出的模型和算法是否在优化多目标公交调度方面具有代表性和有效性。基于以上数据，本文进行了三组实验：

1) 最小化系统空驶时间(Deadheading time, DHT)并计算在此条件下的最小车次链时长方差。

2) 最小化车次链时长方差(Trip chain time variance, TCTV)，该指标体现了所有车辆的工作时间公平性。

3) 多目标优化。对上述两个目标同时进行优化，找到使得调度系统可行的非支配解集。

在对每个目标进行优化的过程中，车队规模始终是一个重要的影响因素，为了让不同的目标取得最优的结果，需要配合不同的车队规模，因此在对每一个目标或者双目标进行优化时，会首先确定这一情境下的最佳车队规模。由于本文研究静态调度，在生成初始解时车辆严格遵守车次的运行时间，在当前车次运行时间内无法被安排新的车次，并且每一个车次都必须被执行，这些对于生成可行解是较为苛刻的条件，因此也限制了最小的车队规模，针对本文案例，利用3M算法可以生成可行解的最小车队规模为30。

5.2.1. 空驶时间

较大的空驶时间也就意味着较大的成本，为了尽量减少系统运行过程中产生的空驶，在基于超级时空网络产生初始可行解时做出一定的改变，其具体操作是：在给特定的车次分配车辆执行时，对当前空闲车辆分成两类，第一类是对于当前车次来说，无需空驶便可以执行它的车辆，也就是车辆的上一个车次的终点站和当前车次的始发站相同；第二类是上一车次的终点站与当前车次的始发站不同的车辆。在给具体车次匹配车辆时，优先将车次匹配到第一类车中，这一改变将极大提高算法最小化DHT的效率。

当采用最小车队规模(30)时，系统的最小空驶时间为30分钟，即在调度过程中出现了一个空驶车次。当车队规模为31时，调度系统中将不会出现DHT，即系统中的车辆可以在没有空驶的情况下完成所有车次的运行。图4和图5分别是车队规模为31时算法迭代过程中解和两个目标函数(DHT和TCTV)的变化情况。

Figure 4. The changes in solutions when DHT is minimized

图4. DHT最小时解的变化情况

由图5可以看出，算法在进行初始解生成的过程中便会出现DHT为0的解，但是这些解内部车辆的工作时间方差(TCTV)较大(平均值大于65分钟)。利用算法可以在保证DHT最小的情况下(DHT = 0)尽量减小TCTV，最终系统的TCTV为29.26分钟，车次链的时间长度在525分钟到665分钟不等。

5.2.2. 司机工作时间公平性

由于现实中多采用人车固定的工作模式，司机的工作时间由其驾驶的车辆的车次链时间长度所决定。为了使得所有司机的工作时间更加平衡，需要使得所有车辆的车次链时长接近，本文用车次链时长方差(TCTV)来反映这一指标。

同样，为了加快解的TCTV收敛情况，在生成初始解时做出了相应的调整：在给车次分配车辆时，会对车次链的长度作出排序，车次会优先分配到车次链最短的三辆车的其中一辆上。图6显示了TCTV随着车队规模的变化，该变化并没有呈现出明显的趋势，TCTV不会随着车队规模的增加而减少。原因是单个车次时间的离散性，车次时间无法均匀地分布在每一辆车上。在车队规模为30~40这一区间内，TCTV取最小值时，车队规模为36。因此在最小化TCTV的过程中，取车队规模为36。图7是车队规模为36时，TCTV随着迭代次数的变化情况。可以看出，利用3M算法可以在生成初始解的阶段便可以获得较小的TCTV值，在迭代过程中经历了两次优化达到了最小值。值得一提的是，此时系统为了尽量减小车次链时间长度的方差，增加了较多的空驶车次，此时的系统空驶时间为2370分钟。可以看出DHT和TCTV之间存在一定的对立关系，是一对此消彼长的矛盾，因此需要在二者之间折衷，这也是后文多目标优化的目的。

Figure 5. The changes in TCTV when DHT is minimized

图5. DHT最小时TCTV的变化情况

Figure 6. The impact of fleet size on minimizing TCTV

图6. 车队规模对最小化TCTV的影响

Figure 7. The convergence of TCTV with a fleet size of 36

图7. 车队规模为36时TCTV的收敛情况

5.2.3. 多目标优化

在这一组实验中，对DHT和TCTV两个目标同时优化，应用多目标3M算法来寻找帕累托解。这里为了表示DHT和TCTV在优化过程中的重要程度相同，在成长步骤中进行成本计算时，取DHT和TCTV的权重${\omega }_1={\omega }_2=0.5$ 。

图8为车队规模增加过程中双目标优化的帕累托解的变化过程，与TCTV的优化过程相似，双目标优化过程中的车队规模增加并没有使得帕累托解的性能得到相应的优化，而是呈现出不稳定的波动。所以在此情境下，选择最好的折衷解所对应的车队规模，也就是31作为最佳车队规模进行研究。

Figure 8. The change of DHT and WTV with increasing fleet size

图8. DHT与WTV随着车队规模增加的变化

图9为车队规模为31时，非支配解的变化情况。所有帕累托解的颜色随着迭代次数均匀的从蓝色变成红色，图中颜色在变成淡蓝色之后便出现了最终的红色，这说明算法在迭代50次左右便已经收敛到最优解，此时的DHT为270分钟，TCTV为14.35分钟。相对于相同车队规模时的单目标优化，折衷方案在两个目标函数上的最优值均有所增加，表6是车队规模为31时，分别进行单目标优化和多目标优化的目标函数值。可以看出，司机工作时间公平性的小幅度增加会导致系统产生较多的空驶时间，导致总成本快速上升。

6. 结论

本研究提出了一种基于超级时空网络的多目标公交车辆调度模型，应用多目标3M算法优化了车队规模、系统空驶时间以及司机工作时间的公平性，成功构建了高效、解释性强的公交调度系统。通过在青岛公交系统上的实证验证，研究表明，该模型能够有效减少空驶时间，同时实现司机工作时间的均衡分配。本研究发现应用超级时空网络的理念对公交调度进行描述时，对于可行调度的生成具有很高的效率，利用本文基于超级时空网络提出的算法甚至在生成初始解的阶段便可以使得系统的空驶时间达到最小。空驶时间与司机工作时间公平性之间存在一定的矛盾关系，小幅度的公平性变化会导致车队的空驶时间产生较大的变化，同时车队规模增加并不会导致车队的总空驶时间和工作时间的公平性得到明显提升，这些发现可以为公交公司和政策制定者在提高效率、节省成本和提高工作公平性方面提供参考。

Figure 9. The change of non-dominated solutions with a fleet size of 31

图9. 车队规模为31时非支配解的变化情况

Table 6. Comparison of single-objective optimization and multi-objective optimization with a fleet size of 31

表6. 车队规模为31时单目标优化与多目标优化的对比

尽管本研究在公交调度优化上取得了突破，但在模型的适用性方面仍存在局限。例如，由于当前模型基于静态需求假设，未能考虑实际调度中可能的动态变化(如突发客流和实时交通情况)，因此模型的广泛适用性仍有待检验。未来研究可以在动态调度情境下对模型进行扩展，融入实时数据和更复杂的调度需求。此外，模型当前主要针对单线路和有限车场的调度场景，在多线路、多车场以及电动公交车队的调度优化方面仍有提升空间。

参考文献