基于并行变异微分进化算法的公交车调度优化

丁贤勇，李玉贞

上海电科智能系统股份有限公司，上海 200063

【摘要】随着城市化进程的加快，越来越多的市民选择公交出行。作为城市的重要交通工具，合理的公交调度既能降低公交公司的运营费用，又能满足市民出行需求。本文从平衡公交公司和乘客的利益角度出发，构建基于运营成本和乘客等待损失最小的公交车调度模型。为高效求解该模型，提出一种并行变异微分进化算法（PMDE）。该算法将当前种群划分两个大小相同的子种群，并分配两种不同的变异策略。两个子群在运行期间以并行方式实施个体进化，较优子群中最好的个体参与较差子群的进化以加强两个子群的协同。利用8个标准函数对PMDE的有效性进行验证，试验结果表明，提出的PMDE能够显著提高算法的收敛性能和稳定性。最后，结合文献中的公交数据，利用PMDE算法对建立的公交调度模型进行求解，结果表明该算法能够以较快的收敛速度获得满意的调度方案。

【关键词】公交调度；微分进化；并行变异；变异策略

Optimization on Bus Scheduling Based on Parallel Mutation Differential Evolution

Ding Xianyong, Li Yuzhen

Shanghai SEARI Intelligent System Co.，Ltd.，Shanghai 200063

Abstract: With the acceleration of urbanization, more and more citizens select to travel by bus. As an important means of transportation in the city, reasonable bus scheduling can not only reduce the operating cost of bus company, but also meet the travel needs of citizens. From the perspective of balancing the interests of bus company and passengers, this paper constructs a bus scheduling model based on the minimum operating cost and waiting loss of passengers. A parallel mutation differential evolution algorithm （PMDE）is proposed to solve the model. The PMDE divides the current population into two subpopulations with the same size, and allocates two different mutation strategies for them. The two subgroups implement individual evolution in parallel manner during the run of the algorithm, and the best individuals in the better subgroup participate in the evolution of the worse subgroup to strengthen the cooperation between the two subgroups. Eight standard functions are used to verify the effectiveness of PMDE, and the experimental results demonstrate that the proposed PMDE can significantly improve the convergence performance and stabil-ity. Finally, PMDE is used to solve the established bus scheduling model based on bus data in the literature, and the results show that it can obtain a satisfactory scheduling scheme with faster convergence speed.

Key words：bus scheduling;differential evolution;parallel mutation;mutation strategies

1 引言

随着城市车辆和人口的逐步扩大，交通拥堵和环境污染也成为城市发展过程中面临的重要问题，公共交通出行成为新的流行方式，可以节约出行成本、降低运营成本、缓解道路拥堵、降低环境污染等。地面运行的公交车如何设定运行线路和运行时刻，对于企业运营成本和人们出行便捷性有重要的意义。公交智能调度属于智能交通领域研究的范畴，也是研究的重点。如何更科学地制定公交调度机制，对于公交管理部门来说至关重要，也是影响民生的重要方面。

鉴于此，国内外学者做了很多公交车辆调度研究。Palma[1]等人研究在固定一条线路和固定数量的公交车辆情况下，对乘客出行时间与公交实际运营时间不匹配时进行优化，构造了在连续时间内最小化乘客的总时间延误模型。Wang和Shen[2]等把路线和燃料的因素考虑在内，运用启发式算法进行公交车调度。Ceder[3]等人对不同车辆类型的公共车辆调度问题进行研究，并用启发式算法对模型进行求解。丁勇[4]等通过研究泰州市公交智能化方面的现状和问题，将遗传算法应用于该市的公交调度问题。邓芳玥[5]等对遗传算法进行改进，将其作用于公交线路调度问题研究。武斌[6]利用模糊多目标规划模型进行智能交通研究，并且用遗传算法验证模型是合理的。彭蝶飞[7]等根据景区现有的公共交通资源和旅客的出行规律，构建了以旅游公交营运成本、游客等待成本和游客流失成本三方面优化目标的模型，并通过遗传算法进行了验证研究。徐晨畅[8]等对于突发交通状况应对，提出相应的公交智能调度算法。

本文从平衡公交公司和乘客的利益角度出发，构建基于运营成本和乘客等待损失最小的公交车调度模型，并提出一种并行变异微分进化算法（PMDE）对模型进化优化。PMDE算法在标准函数上的优化结果表明其具有较高的收敛性能。此外，进一步利用文献中的公交数据对PMDE算法以及调度模型的有效性进行研究，仿真结果表明提出的算法能够以较快的收敛速度获得满意的调度方案。

2 公交调度模型

为同时保障公交公司和乘客的利益，建立的公交调度模型通常应当包含两个方面[10]：一是最小化公交公司的营运成本，二是最小化乘客因等车而造成的损失。前者与营运里程、发车次数以及每公里的营运成本有关；后者与等车时长和单位时间的损失费用有关。

为便于表示公交调度模型，定义如下变量：Cost是待优化的目标函数；α₁和α₂分别是公交公司的营运成本和乘客因等待所产生的损失的权重；OM是公交线路的总里程数；Δt_i和T_i分别是第i个时间段的发车间隔和时间长度；N是一天中所有的运行时间段；C₁是每辆车每公里的营运成本；C₂是每位乘客每等待1min所产生的等待损失费用；S是公交车所走路线包含的总站点数；P_i，j是在第i个时间段第j个站点的乘客数量。具体的公交调度模型为[10]

约束条件

式（2）是权重约束，确保公交公司营运成本的权重与乘客等待损失的权重之和为1。式（3）是最小最大发车间隔约束，发车间隔越大，发车次数越少，乘客等待的时间越长；发车间隔越小，发车次数越多，乘客等待的时间越短。

3 微分进化算法及其改进

3.1 微分进化算法

在DE中，每代种群Pop_T由NP个个体组成，其中D为优化问题的维度。DE的变异、交叉以及选择操作如下所示：

（1）变异DE利用变异操作为种群中的每个个体X_i，T生成一个变异个体V_i，T+1=。常见的变异策略如下所示：

1）DE/rand/1

2）DE/rand/2

3）DE/best/1

4）DE/best/2

5）DE/current-to-rand/1

式中，F是缩放因子；r1、r2、r3、r4和r5是索引，随机来自[1，NP]，且互不相同；X_best，T是第T代种群中最优个体。

（2）交叉DE利用下述等式生成目标个体X_i，T对应的试验个体U_i，T+1=。

式中，j_r是[1，D]之间的随机整数；r_j是[0,1]区间内的随机数；CR是交叉概率，CR∈[0，1]。

（3）选择 目标个体X_i，G和试验个体U_i，G+1中更好的个体将进入下代种群（以最小化问题为例，则选择目标函数值更小的个体）。

3.2 并行变异微分进化算法

变异策略直接影响DE的收敛性能和可靠性，不同的优化问题往往需要不同的变异策略[9]。常用的变异策略已在上节给出，其中DE/rand/1变异策略已经在多个文献中使用，有着较强的多样性保持能力和收敛速度。DE/rand/2变异策略的收敛速度明显要慢于DE/rand/1。DE/best/1和DE/best/2两种策略具有更快的寻优速度，但是容易陷入局部最优，难以实现全局优化。DE/current-to-rand/1变异策略并不参与后续的交叉操作，虽然寻优速度差于其他几种策略，但是具有更好的可靠性。

一般来讲，如果算法在整个运行过程中，仅仅只采用单一变异策略，受优化问题的特征所限，常常很难取得令人满意的优化结果。比如，对于单峰函数，适合采用收敛速度快的DE/best/1和DE/best/2策略；而对于多峰函数，则适合采用全局探索能力强的DE/rand/1变异策略；如果不清楚优化问题的特征，则适合采用多种变异策略共同参与个体变异，从而避免单一策略带来的不足。

基于上述分析，本文提出一种并行变异微分进化算法（PMDE）。该算法根据个体的目标函数值将当前种群划分成2个相同的子种群S1和S2，即两者的种群规模均为NP/2。S1存放种群中最好的个体，而S2存放种群中最差的个体。在执行变异操作时，对于S1，采用传统的DE/rand/1变异策略；对于S2，则采用DE/current-to-rand/1变异策略。此外，为了加强2个子群的协同交流，共同促进进化，利用S1中最优的5个个体代替DE/current-to-rand/1中的X_r1，T，见式（11）。由于S2中的个体较差，S1中较优个体的引入可以为S2的进化提供有价值的引导，加快寻优速度。

较优种群S1为整个种群的进化提供明确的前进方向，而且DE/rand/1变异策略的使用能够有效维持搜索多样性，避免早熟收敛；较差种群S2则有利于适时调节种群多样性，为种群的进化注入活力，DE/current-to-rand/1策略的使用能够提高算法的稳定性。同时，S1中5个最优个体的引入能够显著提高种群S2的变异速度和求解精度。S1和S2在算法运行期间，执行并行进化，因此并未增加原始DE算法的时间复杂度。

PMDE的算法流程如下所示：

1）步骤1：设置控制参数NP、F和CR;随机初始化T=0代初始种群Pop₀。

2）步骤2：根据每个个体的目标函数值，对当前种群Pop_T进行排序，并划分成2个大小相同的子群S1和S2。从S1中选取5个最优个体。

3）步骤3：对于S1中的每个个体，分别利用式（4）、式（9）和式（10）执行变异、交叉和选择操作。

4）步骤4：对于S2中的每个个体，利用式（11）和式（10）执行变异、选择操作。

5）步骤5：S1和S2中的个体组成下一代种群Pop_T+1。

6）步骤6：判断当前代T是否到达最大进化代数T_max。如果T≥T_max，则终止进化，输出结果；否则，令T=T+1，并转到步骤2继续执行。

4 试验研究

4.1 PMDE有效性验证

利用表1的8个标准测试函数对PMDE算法进行评估。其中F1～F4为单峰函数，F5～F8为多峰函数。每个函数的搜索空间、维数以及全局最优均已在表1中给出。为了显示PMDE的优越性，将其与四种基本DE算法（DE/rand/1/bin、DE/rand/2/bin、DE/best/1/bin、DE/best/2/bin）进行对比。所有算法的种群规模均设置为80。对于DE/rand/1/bin、DE/rand/2/bin和PMDE，控制参数设置为F=0.5和CR=0.9。对于DE/best/1/bin和DE/best/2/bin，参数设置为F=0.7和CR=0.5。算法在每个函数上均运行20次。5种算法所得的最优解、最差解以及所得解的平均值和标准差见表2。此外，绘制了算法在部分函数上的进化曲线，如图1所示。

根据表2所示的优化结果，可以看出本文提出的PMDE算法在测试函数上的整体表现明显优于其他4种算法。对于单峰函数F1～F4、多峰函数F5和F8，PMDE所得的最优解、最差解、平均值和标准差均好于DE/rand/1/bin、DE/rand/2/bin、DE/best/1/bin和DE/best/2/bin，这表明PMDE具有更高的求解精度和良好的稳定性。对于多峰函数F6和F7，PMDE所得的结果与DE/best/1/bin一样，但明显优于其他3种算法。对于采用相同参数的DE/rand/1/bin和DE/rand/2/bin，以及DE/best/1/bin和DE/best/2/bin，所得的结果也有明显的差异，这也验证了变异策略对算法的性能有重要影响。此外，图1的进化曲线表明提出的PMDE具有更快的收敛速度。简而言之，PMDE算法能够有效增强DE算法的收敛性能和可靠性。

4.2 PMDE在公交调度中的应用

利用参考文献[10]的公交数据检验PMDE的应用性能，结果见表3。公交车的运营时间为6:00—20:30，以小时为单位，划分为15个时间段。利用PMDE对公交调度模型进行优化的目标就是找出每个时间段内的发车间隔。最小和最大发车间隔分别设置为3min和20min。设置问题的维数为15，种群规模为40，最大进化代数为150。同时应用基本DE算法和PMDE算法对公交调度模型进行求解，调度结果见表4。

从表4的调度结果可以看出，基本DE和PMDE算法均得到了一种可行的公交调度方案，但PMDE所得的目标函数值明显比DE算法的更小，这表明PMDE算法具有更高的求解精度。此外，图2所示为两种算法的寻优曲线，从中可以发现PMDE算法具有更快的寻优速度，在40多代时已经开始收敛。

5 结语

针对公交车调度问题，本文综合考虑公交公司和乘客的利益，建立基于公交营运成本和乘客等待损失最小的公交调度模型，并提出一种并行变异微分进化算法（PMDE）对其进行优化。PMDE根据个体的适应值将种群划分成2个大小相同的较优种群和较差种群，并为其分别分配DE/rand/1和DE/current-to-rand/1变异策略。在算法运行过程中，两种策略并行执行，同时较优种群中的优秀个体参与较差种群的个体变异，从而加快收敛。

利用标准函数对提出的PMDE算法进行试验分析，并与DE/rand/1/bin、DE/rand/2/bin、DE/best/1/bin和DE/best/2/bin 4种算法进行对比。试验结果表明，PMDE能够获得更高的求解精度和收敛速度，整体性能明显优于对比算法。同时，利用文献中的公交站点数据对PMDE的实用性进行验证，仿真结果表明PMDE能够获得合理、有效的公交调度方案，求解质量和寻优速度明显比基本DE算法更高。

参考文献

[1]PALMA A D, LINDSEY R. Optimal timetables for public transportation [J]. Transportation Research Part B: Methodological，2001，35（8）：789-813.

[2]WANG H, SHEN J. Heuristic approaches for solving transit vehicle scheduling problem with route and fueling time constraints [J]. Applied Mathematics and Computation，2007，190（2）：1237-1249.

[3]CEDER A A. Public transport vehicle scheduling with multi vehicle type [J]. Transportation Research Part C: Emerging Technologies，2011，19（3）：485-497.

[4]丁勇，姜枫，武玉艳．遗传算法在公交调度中的应用 [J]. 计算机科学，2016，43（11A）：601-603.

[5]邓芳玥，王欢．基于改进遗传算法的公交线路调度模型 [J]. 交通世界，2017，77（33）：158-159.

[6]武斌．基于遗传算法的公交调度模糊最优解 [J]. 计算机科学，2019，33（12）：50-53.

[7]彭蝶飞，彭懿，郭啸．基于遗传算法的公交智能调度与优化 [J]. 运筹与管理，2019，28（11）：34-38.

[8]徐晨畅，钱松荣．基于遗传算法的突发公交智能调度算法 [J]. 微型电脑应用，2020，36（7）：78-80.

[9]MA Y, BAI Y. A multi-population differential evolution with best-random mutation strategy for large-scale global optimization [J]. Applied Intelligence，2020，50:1510-1526.

[10]刘芹．差分进化细菌觅食算法求解公交车调度问题 [J]. 交通运输系统工程与信息，2012，12（2）：156-161.