基于GA-ACO的带时间窗车辆路径问题研究

（武汉理工大学，湖北 武汉 430063）

1 引言

在物流理论体系中，车辆路径问题（Vehicle Routing Problem,VRP）是一类经典的组合优化问题。有能力约束的车辆路径问题[1](Capacitated Vehicle Routing Problem，CVRP)是最基础的VRP模型，随着理论发展与实际环境的不断结合，越来越多的VRP问题模型得以在此基础上发展，而带时间窗车辆路径问题（Vehicle Routing Problem with Time Windows,VRPTW）[2]是其中的经典问题。更多的研究者倾向运用智能优化算法来求解VRPTW，比较普遍的智能优化算法主要包括遗传算法[3]、蝙蝠算法[4]、蚁群算法[5]以及粒子群算法[6]等。

在解决VRPTW时，针对传统启发式算法在求解时容易出现无法收敛和陷入局部最优等不足，越来越多的学者通过改进优化单一启发式算法或融合多种启发式算法来提高算法的寻优能力。

在改进优化单一算法方面，学者们主要通过改进算法的某些规则或者引入某因子实现改进的目的。朱杰、张培斯等[7]运用改进蚁群算法来求解MVRPTW，通过改进转移概率公式，采用邻域搜索策略提高解的质量，借鉴模拟退火算法的思想对信息素更新，加快收敛速度。孙小军、介科伟[8]也是运用改进蚁群算法来求解DVRPTW，通过引入交通拥堵因子，并改进挥发因子的选择策略，以此有效地提高了蚁群算法的寻优能力。陈成[9]则是提出一种改进的遗传算法来求解VRPTW，通过改变算法的编码结构和交叉变异策略来提升算法的收敛效果和解的质量。Sivaramkumar V，Thansekhar M R等[10]针对带时间窗的多目标车辆路径问题，设计了一种聚合适应度函数的改进遗传算法（FAGA）。针对同样的问题，Dong、Zhou等人[11]设计了一种基于MOEA的多细胞组织算法（PDVA），在新的算法中充分利用离散萤火虫演化机制（DGEM）和可变邻域演化机制（VNEM）两种机制，在加快算法求解速度的同时提高算法寻优的能力。

在融合多种启发式算法方面，学者们主要通过算法之间的相互混合，充分发挥各算法的优点。黄震、罗中良等[12]提出一种混合蚁群优化算法用于解决VRPTW，混合算法结合了蚁群算法与遗传算法。宋强[13]提出了一种基于局部搜索的混合遗传算法来求解VRPTW。Keskin，M、Catay,B[14]针对带时间窗的电动汽车车辆路径问题（EVRPTW），设计了一种融合大领域搜索（ALNS）与精确式算法的智能算法，有效提高了算法的寻优能力。Baños、Julio等[15]在求解带时间窗的多目标车辆路径问题时，充分考虑总运输路程，车辆运力与里程的不平衡，设计了一种基于Pareto最优的进化计算和模拟退火的混合算法。

上述学者的研究工作体现了传统算法的可塑性，通过传统算法间的碰撞延伸出多种效率更佳、寻优能力更强的智能算法。算法改进是算法研究过程中一个亘古不变的研究方向，为了更好地解决和改善传统算法在求解VRPTW时收敛速度慢、解的质量不高等问题，本文借鉴上述学者的研究思想，提出一种以改进蚁群算法为主体，插入遗传算法作为局部优化方法的混合算法，在蚁群算法转移概率的改进中借鉴文献[12-16]引入时间窗因素，除此之外还引入节约距离因子，设置随机变量来优化算法的迭代过程，在信息素更新机制中，定义信息素为标量，构造信息素挥发因子的阶段函数，然后使用遗传算法中的交叉变异算子对蚁群算法得到的较优解进行下一步优化，达到加快算法收敛速度、提高解的质量的目的。算法的仿真实验与结果对比验证了混合算法的有效性与优越性。

2 问题描述

一般带时间窗的车辆路径问题可以描述如下：一个具有若干额定载重和行驶速度已知的配送车辆的配送中心，需要向区域内的多个客户进行货物配送，各客户点的坐标位置、需求和可以接受服务的时间窗已知。在这样的前提下，考虑如何合理安排车辆配送路线，既能在满足各项约束的条件下，将货物安全送到客户的手中，又能实现配送车辆行驶总路径最短。

VRPTW的时间窗可以分为硬时间窗、软时间窗和混合时间窗三种类型，这里主要构建硬时间窗车辆路径问题的数学模型。

为方便构建数学模型，需说明以下符号：将配送中心与客户节点构成的有向网络图集合设为G(N,A) ，其中：N=N0⋃NC，N0表示配送中心，NC={1,2,...,n}为客户节点的集合；A={(i,j)| i,j∈N,且i≠j}表示节点i与j的有向线段集合。dij表示节点i与节点j之间的距离，节点i可以接受服务的时间窗为[ETi,LTi]，qi表示节点i的需求量，完成节点i的服务需要的时间为STi，K={1,2,...,m} 表示车辆集合，配送车辆的额定载重量为Q，车辆k到达节点i的时刻为Tik，配送车辆从节点i到节点j所需时间为Tij，同时还需定义以下两个0-1变量：

建立带硬时间窗的车辆路径问题的数学模型，需满足以下条件：（1）各客户的需求只能由一辆车一次服务完成，并且各客户只在自己规定的时间窗范围内才接受服务；（2）所有车辆均从配送中心出发开始服务，服务完毕后返回配送中心；（3）不考虑配送中心的取货时间窗，即配送中心在任意时间都可以取货；（4）除货物数量外，不考虑货物的其余属性，同时各配送车辆的行驶速度固定且不考虑交通状况。

根据上述符号说明，建立带硬时间窗的车辆路径问题数学模型如下：

式（1）为车辆总行驶路径最小目标函数；式（2）为配送车辆的载重约束；式（3）表示每个客户只能由一辆车进行服务；式（4）表示车辆服务某节点后必须从此节点出发去下一节点约束；式（5）和（6）表示每个客户节点只允许被服务一次；式（7）为消去子回路约束；式（8）和（9）为时间窗约束。

3 GA-ACO混合算法

3.1 GA-ACO混合算法策略提出

遗传算法能够在大范围内进行快速全局搜索，但是不能充分利用系统反馈的信息，所以在求解进行到一定范围后，会有大量的重复迭代，这大大降低了算法的优化效率；而蚁群算法是采用分布式、并行的方式进行搜索，并且还具有正反馈的特点，正反馈使得它能够很好地运用系统反馈的信息，但是由于前期信息素匮乏，求解速度很慢。遗传算法和蚁群算法的优势正好可以互补，混合在一起形成的混合算法可以提高单一算法的优化性能。

目前，蚁群算法和遗传算法进行混合的研究很多，总结下来，其混合形式主要有以下四种：

（1）蚁群算法为主体，前期使用遗传算法求解问题的可行解，利用这些可行解进行蚁群算法路径上的信息素初始化，后期使用蚁群算法求解。

（2）遗传算法为主体，前期使用蚁群算法求解问题较优解，作为遗传算法初始种群，再使用遗传算法进行求解。

（3）融合方式，即在遗传算法交叉变异操作后，再使用蚁群算法进行优化。

（4）插入的方式，即在蚁群算法优化得到问题可行解后，选取若干可行解作为初始种群进行遗传优化。

为了能够充分利用遗传算法的快速全局搜索特性以及蚁群算法的分布式计算、正反馈的特点，本文采用第四种插入的方式，即在蚁群算法的每一迭代过程中引入遗传算法的交叉变异操作，将蚁群算法与遗传算法融为一体，它们之间通过更新每次迭代过程中的最优解来相互指导。首先是蚁群算法在每次迭代后得到问题的若干可行解，从这些可行解中选出相对较优的几个组合成遗传算法的父代，父代通过复制、交叉以及变异过程产生子代，使用子代中的较优解来更新蚁群迭代可行解中的较差解，作为当次迭代的路径来更新蚁群算法中各路径上的信息素。使用遗传算法中的交叉变异算子对蚁群算法得到的较优解进行进一步优化，可以有效的避免蚁群算法陷入局部最优。

3.2 GA-ACO混合算法的基本规则设计

（1）转移规则设计。在求解VRPTW的蚁群遗传混合算法中，蚁群算法部分的蚂蚁转移规则采用确定性选择和随机选择相结合的过程，首先对蚂蚁选择下一个节点的转移概率公式进行改进。定义如下参数：节点数量为n，人工蚁群的蚂蚁数目为m，节点i与节点j之间的距离为dij，节点i与节点j之间路上的信息素浓度为τij；节点i与节点j之间的可见度（或者亲密浓度）为ηij，ηij=1/dij；wij表示时间窗系数，wij=1waitij；蚂蚁k可访问节点的集合为allowedk。

则蚂蚁k在t时刻从节点i转移至节点j的概率pkij为：

其中，α为信息启发式因子，β为期望启发式因子，θ为时间窗启发式因子，γ为节约距离值启发式因子，Uij为节约距离，其计算公式见式（11），考虑当蚂蚁从配送中心出发时，节约距离设定为定值1：

时间窗系数wij中的waitij是一个与车辆行驶时间和各客户点服务时间窗相关的变量，其表达式为：

为了解决算法过早收敛这一问题，在蚂蚁选择下一个节点过程中引入变量q0，蚂蚁按式（13）的规则选择下一个节点。

其中q为随机变量，q∈(0,1)，即在随机变量q小于变量q0时，蚂蚁选择计算的转移概率最大的节点进行访问，否则，就随机选择一个可访问的节点进行访问。变量q0的值会随着迭代次数的增加而发生改变，其变化公式为：

其中，NC代表当前的迭代次数，根据q0的变化可知，随着迭代的进行，q0的值先变大再变小。这就意味着，在前期各蚂蚁以较大的概率采用随机选择机制选择下一个访问节点，有助于各蚂蚁在全局范围内搜索最优解；中期则以较大的概率采用确定性选择机制选择下一个访问节点，使得各蚂蚁向着遍历过的最优路径上靠拢，使得算法收敛；而后期各蚂蚁则以较大的概率采用随机选择机制选择下一节点，进行全局搜索，有助于跳出局部最优。

（2）信息素更新规则设计。基本蚁群算法中蚂蚁线路上的信息素更新规则如下：

其中：ρ为信息素挥发因子，ρ∈(0,1) ，即：τij(t)表示t时刻节点i到节点j之间的路径上的信息素含量，它随时间的推移而不断的减少；Δτij(t)表示在当次循环中节点i到节点j之间路径上的信息素增量，其表达式为：

其中：Q表示每只蚂蚁携带的信息素总量，Lk为蚂蚁当次迭代走过的总路径。

本文对蚁群算法的信息素更新规则中的全局信息素更新规则和信息素残留因子ρ进行如下改进，而局部信息素更新按照式（15）进行。

①全局信息素更新机制的改进。算法在每一次迭代结束时，对当次迭代下的最优路径按照式（17）进行信息素的更新，式（17）中的Lk为当次迭代下最优路径的长度。根据式（16）可以计算出每一次迭代运算后各路径上的信息素增量。

与基本蚁群算法不同，定义信息素为标量，即信息素不具方向性，同时认为节点i至j与j至i增加的信息素在数值上具有一致性。所以改进的信息素更新规则如下：

②信息素挥发因子ρ的改进。在基本蚁群算法中，信息素挥发因子ρ是一个常量，各路径上信息素的积累速度与ρ值的大小息息相关。研究发现，在算法前期，为避免陷入局部最优，需要设置较大的ρ值，可以扩大搜索范围，使蚂蚁能够在更大的范围内访问各线路；而在算法后期，需要加快算法的收敛，设置较小的ρ值，放大各路径上的信息素含量差异，使蚂蚁逐步向优势路径集聚。为此，ρ值随着迭代的进行，应该是一个由大到小的变化过程，本文提出使用下列阶段函数模拟ρ值的变化：

（3）局部优化规则。为了避免算法陷入局部最优，在每次迭代结束后，使用遗传算法对当次迭代的较优解进行局部优化，以增加解的多样性。

3.3 染色体编码与解码

遗传算法处理的直接对象是染色体，所以在使用遗传算法对VRPTW等实际问题进行优化时，需要通过编码建立实际问题与遗传算法的染色体之间的联系。在遗传算法中可以使用的编码方式有二进制编码、实数编码、符号编码、自然数编码等多种形式，其中二进制编码和自然数编码是最常用的。

本文选用自然数编码方式对染色体进行编码，由所有的客户点的编号组成染色体的基因，所有基因的一个排列就是一个染色体结构。比如VRPTW共有14个客户点，需要有3辆车进行配送，由蚁群算法求解的一个可行解（解中的1代表配送中心）为：

去掉可行解中的配送中心编号，只保留客户节点编号，并且客户节点编号的序列保持不变即为可行解对应的染色体结构。则该可行解转换而来的染色体结构为：在同一限定条件下，编码能够保证所有染色体的长度都是一样的，方便后续的交叉变异。

父代染色体经过复制、交叉、变异处理后，得到子代的染色体结构，进一步对子代染色体进行解码，转换成问题的可行解。解码时按照VRPTW模型里面的约束条件，依次将同时符合车辆载重约束和客户点时间窗约束的客户分配给配送车辆。以下面的染色体结构为例：结合VRPTW模型中的约束，对其进行染色体解码：首先将客户5分配给车辆1，更新车辆1的时间和载重，再将其后的节点10分配给车辆1，检验载重约束和时间窗约束，如果载重和时间窗约束中有一个及以上不满足，则形成子路径（1,5,1），即车辆1只为客户点5配送货物；若都符合要求，则将客户10也由车辆1配送，再依次检验后面的客户，只要车辆超载或是不满足时间窗约束，则启动下一辆车，依次检验下去，直到染色体结构中所有的客户点都被分配完。上述子代染色体解码出来的可行解可能为：

即共需要三辆车完成配送，其路径分别为（1,5,10,6,9,3,1），（1,8,7,14,2,4,1）和（1,12,13,11,1）。

3.4 遗传算子

遗传算法中的核心遗传算子主要有选择算子、交叉算子和变异算子三个，它们与遗传算法的性能息息相关。

（1）选择算子。选择也称之为复制，就是按照一定的原则或方法，选择种群中优秀的个体作为父代来繁衍子代的过程。在基本遗传算法中，使用的选择策略有精华选择和比例选择两种形式。精华选择就是每次从种群中选取适应度最好的个体作为父代中的一个，直到选出组成种群需要的个体数目；而比例选择就是每次随机从种群中选取一个，不一定每次都是最好的那个，直到选出构建种群需要的个体数。

本文设计的蚁群遗传混合算法，是以蚁群算法为主体，将遗传算法融入到蚁群算法的每一次迭代计算中，使用遗传算法对蚁群算法求得的解进行局部优化。所以本文采用的是精华选择策略，即从每次迭代得到的路线中，选取总路径相对较小的若干只蚂蚁的行驶路径作为遗传算法中的种群。

（2）交叉算子。交叉也叫重组，是自然进化过程中新个体或物种产生的主要方式。在遗传算法中常用的交叉算子有一点交叉、两点交叉、异位交叉、基于次序的交叉等多种形式。前两种交叉方式主要用于使用二进制编码的遗传算法中，后面的几种形式常用于使用自然数编码的遗传算法中。

本文选用的是异位交叉的形式。其主要步骤为：①随机生成两个交叉点x和y，假设x≤y；②父代1中的交叉区域基因为第x到y位，父代2中的交叉区域基因为第1到y-x+1位，并交换父代中交叉区域的基因；③对于交换区域外的重复基因，根据交叉区域中的基因对应关系进行替换，替换完成后得到子代。

（3）变异算子。在遗传算法中通过增加变异算子来模拟自然界中基因突变这一环节，变异算子的作用虽然小于交叉算子，但也是遗传算法所必须的，它能够有效地增强遗传算法的局部搜索能力，避免算法优化得到的解陷入局部最优，发生过早收敛现象。遗传算法中常用的变异算子有反转变异、2-opt变异等多种形式。

本文选用的变异算子是反转变异方式。首先随机确定两个基因位，然后把这两个基因位之间的染色体基因进行反序排列，即得到子代个体的染色体结构。

4 GA-ACO混合算法的实现

4.1 算法步骤

带硬时间窗的VRPTW混合算法的具体流程描述如下：

Step1：初始化各参数。设初始迭代次数NC=1，设置算法最大迭代次数NCmax，初始化蚁群算法部分的相关系数α、β、γ、θ，蚂蚁数量m，信息素Q，初始化Tabu表以及Tau表；设置遗传算法部分的交叉概率Pc和变异概率Pm。计算ηij，初始化各路径上的信息素为1。

Step2：将m只蚂蚁初始化到各节点上，并将各蚂蚁的初始化城市编号放入Tabu表中。

Step3：对于从节点i出发的蚂蚁，按照转移概率式（10）计算并得到蚂蚁k将要转移的下一个节点j。

Step4：判断蚂蚁k是否遍历完成所有节点或是满足载重和时间窗约束，若不满足约束，则回到配送中心，转到Step3；若遍历完成所有客户节点，则转到Step5；否则，蚂蚁k成功转至节点j，将节点j加入Tabu表中并转到Step3。

Step5：判断蚂蚁k是否回到配送中心，若没有回到配送中心，则将节点1加入到Tabu表，并转至Step6；否则直接转至Step6。

Step6：判断k是否大于蚂蚁数m，若k＞m，转到Step7；否则k=k+1，转至Step3。

Step7：计算各蚂蚁所走路径的长度，按路径长短选取路径短的若干只蚂蚁的行驶路径，初始化为蚁群算法的初始种群，并转至Step8；

Step8：依次随机从种群中选取两个个体作为父代，使用遗传算法进行优化，直到种群中所有的可能都被选择完毕，得到子代并转至Step9。

Step9：对子代染色体进行解码，并计算各子代个体染色体解码后的路径长度，用路径短的线路更新掉原来蚂蚁走过的路径较长的线路，更新Tabu表和相应的路径长度，以及每次迭代的最佳路径。

Step10：进行信息素更新，更新Tau表，得到当前迭代次数中的最优解，并初始化相关数据表。

Step11：判断迭代次数NC是否超过设置的最大迭代次数NCmax，若超过最大迭代次数NCmax，则算法终止，输出问题的最优路径和最优路径长度。否则NC=NC+1，跳到Step2。

4.2 算法流程

根据上面所述的步骤，使用GA-ACO混合算法求解VRPTW问题的流程图如图1所示。

4.3 算例分析

选取文献[12]和文献[16]中的共同算例作为本文计算算例，在MATLAB软件中编写上述GA-ACO混合算法的程序对上述算例进行仿真运算。

该仿真算例有一个配送中心节点，20个客户节点，共21个节点，配送车辆的额定载重为8t，车辆的行驶速度为60km/h，各节点的坐标位置、需求、允许服务时间窗等数据见表1（节点编号1指配送中心，其余的为各客户节点的编号）。

图1 GA-ACO混合算法的流程图

编写算法程序，在MATLAB软件中多次仿真运算，对仿真结果和参数进行统计，结果表明，本文设计的混合蚁群算法在下列参数设置下，算法具有较好的性能。

按照上述参数对改进蚁群算法进行初始化设置，在MATLAB软件中运行本文改进的蚁群算法100次，取其中较好的10次数据作为展示，见表2。

由上述结果可知，使用本文改进的蚁群算法计算文献中算例得到的最优路径长度为1 170.68km，最优路径车辆行驶线路如图2所示，最优路径出现时的混合算法收敛曲线图如图3所示。

将使用本文设计的混合算法求解20个客户节点算例得到的最优结果与文献中的算法求解同样算例的结果进行比较，见表3。

表1 算例中各节点的位置坐标与需求量

表2 算例运行结果

表3 最优值比较

由表3中的对比结果可以看出，运用本文设计的蚁群遗传混合算法求解20个客户节点的带硬时间窗的VRPTW算例，得到的最优结果比文献[12]中的结果优化了6.29%，比文献[16]中的结果优化了7.53%，可见本文设计的混合算法是有效的，并且具有一定的优越性。

图2 最优结果路线图

图3 最优路径时算法收敛图

5 结语

本文针对车辆路径问题中的经典变型—带时间窗的车辆路径问题，设计了一种以改进蚁群算法为主体、插入遗传算法作为局部优化手段的改进混合算法。充分考虑问题的实际情境，结合时间窗等相关约束条件建立VRPTW问题的数学模型，设计改进混合算法，通过对文献中的算例进行仿真运算，仿真结果证明改进混合算法可有效提高收敛速度并提高解的质量。通过与其它文献中的最优结果进行对比分析，验证了本文设计的GA-ACO改进混合算法在求解带时间窗的车辆路径问题上的有效性和优越性。同时需要说明的是，随着约束条件的变化，算法的构造就更为复杂，同时算法求解时的群体属性也是可以变化的，这些都可以作为以后的研究方向。