混合量子粒子群算法求解车辆路径问题

黄震

惠州学院计算机科学系，广东惠州 516007

混合量子粒子群算法求解车辆路径问题

黄震

惠州学院计算机科学系，广东惠州 516007

1 引言

车辆路径问题广泛地应用于交通和物流领域，已经引起了国内外学者对该问题进行深入的研究，产生了许多种经典、智能的求解方法，其中粒子群算法在求解车辆路径问题上也成为了研究热点。针对粒子群算法容易陷入局部最优的缺点，很多学者利用改进的粒子群算法对车辆路径问题进行求解，马慧民等[1]提出一种引入模拟退火机制的并行粒子群算法对车辆路径问题进行求解，该算法可以提高进化后期的收敛精度，具有良好的性能。陈严等[2]在基本粒子群算法的基础上引入了杂交PSO模型和变异算子，并且运用罚函数法将约束优化问题转化为无约束优化问题，同时采用实数编码方案，将离散的车辆路径问题转化成准连续优化问题。张思亮等[3]提出一种粒子群算法和蛙跳算法的混合算法求解车辆路径问题，采用粒子群算法产生阶段最优解，利用蛙跳算法对阶段最优解进一步优化，取得比较理想的效果。李娅等[4]提出一种改进的混沌粒子群优化算法求解车辆路径问题，在基本混沌粒子群优化算法基础上，引入逻辑斯特函数对惯性权重因子w进行非线性调整，提高了算法的寻优能力，有效避免了算法陷入局部最优并防止过早收敛。李德富等[5]提出了扫描粒子群算法，运用扫描算法对矿点进行扫描，生成初始可行解链，将其作为粒子的初始位置代入到粒子群中搜索，得到粒子种群历史最优位置，将种群粒子最优位置逆转录生成对应的可行解链。

本文首先使用量子粒子群算法[6-7]求解车辆路径问题，实验结果表明该算法存在容易陷入局部最优的缺点，于是参考了文献[8]提出的将粒子群算法和遗传算法相结合的思想，在基于量子粒子群算法更新了粒子位置之后再进行交叉和变异操作，实验结果表明改进后的算法不仅可以提高局部搜索能力，而且具有良好的全局寻优能力和较快的收敛速度。

2 车辆路径问题的数学模型

车辆路径问题（Vehicle Routing Problem，VRP）是由Dantzig和Ramser于1959年首先提出的[9]，基本车辆路径问题的描述为某配送中心（编号为0）有K辆车，每辆车最大载重量为w，对N个客户（编号为1，2，…，n）进行货物配送，每辆车从配送中心出发给若干客户送货，最后回到配送中心，设客户i对货物的需求量为qi(i=1,2,…,n)，cij表示客户之间的距离。

根据基本车辆路径问题的描述，配送系统的变量和数学模型定义如下：

其中，式（1）、式（2）为变量的定义，式（3）是保证每辆车的运载能力约束，式（4）是保证每个用户被服务，式（5）、式（6）保证每个用户有且仅被一辆车访问，式（7）是本配送系统的目标函数。

3 改进的量子粒子群算法求解车辆路径问题

3.1 量子粒子群算法

量子粒子群算法（QPSO）是指具有量子行为的粒子群算法，根据文献[10]的描述，算法中粒子的状态由波函数ψ(x,t)决定，通过Monte Carlo方法模拟得出粒子位置更新方程如下：

式（8）中p由式（9）给出，式（9）中α1和α2为[0，1]上的均匀分布的随机数，best_l为粒子在第t次迭代的局部最优值，best_g为粒子在第t次迭代的全局最优值；式（8）中β表示惯性权值，其值随着迭代动态变化，一般按照式（10）求值，其中t表示当前迭代次数，tmax表示最大迭代次数；式（8）中mbest由式（11）给出，表示第t次迭代时每个粒子在局部搜索到的最优位置的平均值；式（8）中u指的是[0，1]上的均匀分布的随机数，在迭代过程中当u＞0.5时β前的符号取负号，否则取正号。

量子粒子群算法对比粒子群算法具有参数少、收敛速度快的优点，但是由于只有一个参数β来控制粒子的更新，β是随着迭代次数的增加而线性减少的，而解决实际问题时搜索过程往往是比较复杂的、非线性的，所以在实际的优化搜索过程中容易陷入局部最优，出现早熟收敛现象。

3.2 改进算法求解车辆路径问题

针对QPSO可能出现早熟收敛现象，本文对QPSO进行了改进，借鉴了遗传算法的交叉和变异操作。改进的算法流程如图1所示。

图1 改进算法流程图

3.2.1 初始化粒子群

利用粒子群算法求解实际问题时，首先需要解决的是粒子的编码问题，本文参考了文献[11]，采用整数编码，具体方式如下：

（1）采用整数i表示配送中心和客户，其中0表示配送中心（有K辆车），1，2，…，n表示客户。

（2）每个粒子由一个n维整型向量[a1,a2,…,an]表示，ai∈[1,n]，每个ai对应一个客户号。

（3）每个粒子的解路径由一个n+K+1维的整型向量[b1,b2,…,b(n+K+1)]表示，bj∈[0,n]，每个bj代表配送中心或客户，粒子的解路径按照如下方法求解：

①定义变量W，初始值为0，解路径的第一维b1赋值为0（表示配送中心）。

②先将粒子向量的第一维a1对应客户的需求量与变量W相加，如果W没超过车辆限重则将a1加入到解向量中，即将a1赋值给解路径向量的第二维b2，按同样的方法继续计算后面的每一维，若W不超重则将粒子的当前维ai加入到解路径向量中，若W超重则结束，并且不把粒子的当前维加入到解路径向量，这样之前加入到解路径向量中的客户就构成了子路径1。

③在解路径向量中子路径1的后面一维分量赋值为0（表示配送中心），然后按照步骤②的方法遍历粒子向量剩下的维分量，可以求出所有子路径。

例如某配送中心有2辆车，每辆车限重8吨，为8个客户送货，客户的需求量分别是：1，2，1，2，1，4，2，2，设向量[4 2 8 5 3 1 6 7]为一个粒子，按照上述方法可以求出其解路径为[0 4 2 8 5 0 3 1 6 7 0]，对应的子路径为：0-4-2-8-5-0和0-3-1-6-7-0，每个子路径对应一辆车。

按照上述的粒子编码方式，本文的初始化粒子群的步骤如下：

（1）随机产生1个粒子，计算其解路径，如果解路径非法则通过3.2.5节的方法进行调整，如果调整不成功则重新产生一个粒子，按照这种方法产生40个粒子。

（2）计算40个粒子的适应值，适应值是指解路径中各点之间的距离之和。

3.2.2 更新粒子位置

本文采用Matlab编写代码，根据公式（8）对粒子位置更新，实现步骤如下：（1）计算每次迭代所有粒子局部最优的平均值mbest。（2）使用unifrnd（0，1）产生2个随机数α1和α2，根据公式（9）计算p。

（3）根据公式（10）计算惯性权值β，β的值随着迭代次数t增加由1.0减至0.5。

（4）使用unifrnd（0，1）产生随机数u，根据u的值来确定公式（8）的正负号。

（5）计算的结果会出现小数，本算法采用的是整数编码，所以要对结果进行规格化，才能得到合法的粒子，规格化方法如下：

①将更新后的粒子向量的每一维排序。

②将每一维分量的排名赋值给粒子向量。

例如粒子[8 2 7 4 3 6 5 1]按照上述步骤更新后得到向量[36.66 38.40 38.47 34.93 35.63 37.97 37.96 38.46]，规格化后的粒子向量为[3 6 8 1 2 5 4 7]。

3.2.3 交叉操作

本文加入了遗传算法中的交叉操作，交叉是指将两个父代个体的部分基因加以替换重组而生成新个体的操作，是产生新个体的主要方法，决定了遗传算法的全局搜索能力，在遗传算法中起关键作用[12]，本文采用了算术交叉算子，具体操作步骤如下：

（1）首先选择进行交叉的两个父代个体，本文选择当前局部最优的个体作为父代1，另外再选择一个父代2即可，选择的主要原则[13]是要有一定差异的两个个体，这样利于后代性状进化，可以在选择前先设定某个阈值Y，尝试在当前所有粒子中随机选择一个作为父代2，将两个父代的适应值S1和S2代入公式（12）计算出d，当d大于给定阈值时进行交叉，否则重新选择父代2，公式（12）中的Smax和Smin分别是当前迭代次数的最大适应值和最小适应值：

（2）在父代1中随机产生2个不同的交叉位作为交叉区域。

（3）将父代2中与父代1交叉区域中相同的客户点逐一删除，每删除一个客户点的同时将后续客户点全部前移。

（4）将父代1交叉区域中的客户点插入到父代2的末尾，构成子代粒子。

（5）计算交叉后粒子的适应值，如果更优则保留子代粒子。

例如，父代1为粒子[8 7 4 2 6 5 3 1]，父代2为粒子[7 8 1 3 6 2 4 5]，随机产生2个交叉位分别为2和5，取出父代1的第2至第5位[7 4 2 6]作为交叉区域，将父代2中与交叉区域相同的客户点删除并将交叉区域插入到末尾，得到子代粒子为[8 1 3 5 7 4 2 6]。

3.2.4 变异操作

变异操作是指将个体编码中的某个基因值用其他等位基因来替换，从而形成一个新的个体，它是产生新个体的辅助方法，可以改善遗传算法的局部搜索能力[12]。本文采用的是不同子路径间单点变异，具体方法是在粒子解路径的2个子路径上分别产生1个变异位，尝试将两者位置交换，如果交换后适应值更优则保留变异后的粒子，否则不交换。

例如粒子[4 6 2 1 3 5 8 7]对应的解路径为[0 4 6 2 0 1 3 5 8 7 0]，对应有2个子路径：0-4-6-2-0和0-1-3-5-8-7-0，如图2所示。

图2 变异前的路径图

假设在子路径1中产生变异位为7号客户，在子路径2产生变异位为2号客户，将两者位置交换完成变异操作，变异后的粒子为[4 6 7 1 3 5 8 2]，变异后的路径如图3所示。

图3 变异后的路径图

3.2.5 非法解的调整

初始化粒子群或者在算法进行过程中产生的粒子可能会出现非法的解路径，例如存在一个粒子[2 8 5 3 6 7 1 4]，按照3.2.1节的方法可以求出其解路径为[0 2 8 5 3 0 6 7 1 0 4]，对应的子路径为：0-2-8-5-3-0、0-6-7-1-0和0-4-0，需要3辆车才能完成配送任务，而配送中心只有2辆车，明显这是个非法的解路径。本文参考了文献[14]的方法对非法解进行调整，具体步骤如下：

（1）将最后两条子路径合并，合并后上述粒子的子路径为：0-2-8-5-3-0、0-6-7-1-4-0，这样就转化为解决最后一条子路径超重的问题。

（2）针对最后一条子路径，先取出第一个客户号，尝试放入之前的子路径中是否超重，如果不超重则将第一个客户加入到之前的子路径中，然后再判断最后一条子路径是否超重，如果不超重则调整结束，得到合法解，否则取后续客户号重复之前的操作。

（3）如果最后一条子路径的每一个客户号按照步骤（2）操作都不能得到合法解，则取第一个客户号尝试与之前子路径的每一个客户号交换位置，如果交换后之前的子路径不超重且最后一条子路径也不超重则进行交换，此时调整结束得到合法解，否则取后续客户号重复之前的操作。

（4）如果上述步骤都不能得到合法解，则舍弃该非法粒子。

按照上述方法调整非法解路径[0 2 8 5 3 0 6 7 1 0 4]可以得到合法解路径[0 7 2 8 5 3 0 6 1 4 0]。

4 实验仿真结果与分析

4.1 实验1

实验1的数据采用文献[4]中的数据，即有1个配送中心配有2辆车，每辆车限载重8吨，需要服务8个客户，具体数据如表1所示，表1中第1行和第1列中的0表示配送中心，1～8表示各客户号，最后一行表示各客户的需求量（单位为t），表1中的其余数据表示配送中心与各客户之间的距离（单位为km）。

本文使用Matlab7.0进行编程，分别利用QPSO和本文算法对实验1的数据进行仿真，两种算法的粒子数设置为40，迭代次数设置为50，本文算法的交叉概率为0.55，变异概率为0.02，对两种算法的仿真程序分别运行20次，得到运送货物的总运输距离，结果如表2所示。为了说明本文算法的有效性，表2中加入了文献[4]的实验结果。

表1 各客户间的距离及各客户的需求量

表2 实验1结果对比1）

已知实验1的理想解为67.5，由表2的结果可知，QPSO仅获得5次理想解，平均解为69.3；文献[4]的算法获得14次理想解，平均解为68.37；本文算法20次的运行结果都获得了理想解67.5，明显优于QPSO，也优于文献[4]的算法，实验结果说明本文算法可以很好地解决小规模的车辆路径问题。

4.2 实验2

实验2使用的数据是中等规模实例VRPNC1，VRPNC1是通用的VRP测试数据[15]，VRPNC1中有1个配送中心，配5辆车，每辆车限量160，为50个客户运送货物，已知VRPNC1实例的理想解为524.61。分别用QPSO、遗传算法（GA）和本文算法进行仿真实验，设置粒子数为40，迭代次数为400，本文算法的交叉概率为0.55，变异概率为0.02，阈值为0.2。三种算法各运行20次，计算出运送货物的总运输距离，运行结果如表3所示。

表3 实验2结果对比

由表3可知，QPSO和GA算法在20次运行中得到的解与VRPNC1实例的理想解的误差率都比较大。本文算法在运行过程中获得了VRPNC1实例的理想解524.61，最差解的误差率为4.1%，平均解的误差率仅为2.5%，取得了比较好的运行结果。

图4 三种算法的迭代过程

三种算法得到的最好解的迭代过程如图4所示。

由图4可知，本文算法的最终结果明显优于QPSO和GA算法，收敛性也更好，QPSO的收敛性较好，但是容易陷入局部最优，本文算法很好地解决了这个问题。

由于本文算法加入了交叉和变异操作以及每次产生新的粒子都需要检测是否为非法解，需要对非法解进行调整，所以运行时间较长。在迭代次数同为400次，运行20次的情况下，QPSO的平均运行时间是8.8 s，GA的平均运行时间是8.3 s，本文算法的平均时间为23.2 s，这是本文算法需要改进的地方。

5 结束语

本文将量子粒子群算法和遗传算法相结合对车辆路径问题进行求解，给出了具体的粒子位置更新方法、交叉和变异的方法以及对非法粒子的调整方法。分别对8个客户的小规模实例和50个客户的中等规模实例进行仿真，实验结果表明小规模实例可以迅速得到理想解，中等规模实例可以得到理想解，而且平均解与理想解的误差率也比较小，说明本文算法可以有效求解车辆路径问题，但是本文算法的运行时间较长，需要在这方面进行改进。

[1]马慧民，吴勇，叶春明.车辆路径问题的并行粒子群算法研究[J].上海理工大学学报，2007，29（5）：435-439.

[2]陈严，刘利民.改进型PSO算法在VRP中的应用[J].计算机工程，2011，37（1）：170-172.

[3]张思亮，葛洪伟.粒子群和蛙跳的混合算法求解车辆路径问题[J].计算机工程与应用，2011，47（21）：246-248.

[4]李娅，李丹，王东，等.改进的混沌粒子群算法求解车辆路径问题[J].计算机应用研究，2011，28（11）：4107-4110.

[5]李德富，郭海湘，刘龙辉，等.改进型粒子群优化算法求解车辆径优化问题[J].计算机工程与应用，2012，48（20）：216-223.

[6]Sun Jun，Feng Bin，Xu Wenbo.Particle swarm optimization with particles having quantum behavior[C]//Proceedings of the 2004 Congress on Evolutionary Computation.Portland，OR：IEEE Press，2004：325-331.

[7]dos Santos Coelho L.A quantum particle swarm optimizer with chaotic mutation operator[J].Chaos，Soliton and Fractals，2008，37：1409-1418.

[8]黄为勇.一种采用完全Logistic混沌的PSO-GA优化方法[J].计算机应用研究，2012，29（9）：3236-3239.

[9]Dantzig G B，Ramser J H.The truck dispatching problem[J]. Management Science，1959，6（1）：80-91.

[10]靳雁霞，韩燮，周汉昌.具有量子行为的粒子群优化算法的改进[J].计算机工程与应用，2009，45（35）：41-43.

[11]杨虎林.改进粒子群优化算法求解车辆路径问题的研究[D].南宁：广西师范学院，2012.

[12]葛继科，邱玉辉，吴春明，等.遗传算法研究综述[J].计算机应用研究，2008，25（10）：2911-2916.

[13]周艳聪，孙晓晨，余伟翔.基于改进遗传算法的物流配送路径优化研究[J].计算机工程与科学，2012，34（10）：118-122.

[14]熊宁.基于粒子群优化算法求解车辆调度问题[D].广州：华南理工大学，2012.

[15]戴树贵，姜昌华，潘荫荣，等.求解车辆路径安排问题的混合遗传算法[J].计算机工程与应用，2007，43（21）：225-228.

HUANG Zhen

Department of Computer Science,Huizhou University,Huizhou,Guangdong 516007,China

Quantum Particles Swarm Optimization（QPSO）algorithm partly solves the shortcoming such that Particle Swarm Optimization algorithm rate of convergence is not fast enough,while in solving the Vehicle Routing Problem（VRP）.But there is still disadvantage.QPSO falls into local optimum easily.This paper proposes a hybrid Quantum Particle Swarm Optimization algorithm to solve the vehicle routing problem.It uses the QPSO to update particles of initial particle swarm;the crossover operating to particles can improve the global search ability;the mutation operating to particles can improve the local search ability. Applying Matlab as tool for simulation experiment,the experimental result shows that the improved algorithm had good performance to deal with VRP.It can avoid falling into local optimum,and it is better than QPSO and genetic algorithm.

Particles Swarm Optimization（PSO）algorithm;Quantum Particles Swarm Optimization（QPSO）algorithm;crossover;mutation;vehicle routing problem

量子粒子群算法在求解车辆路径问题时一定程度上解决了基本粒子群算法收敛速度不够快的缺点，但是量子粒子群算法仍然存在容易陷入局部最优的缺点。利用混合量子粒子群算法对车辆路径问题进行求解，运用量子粒子群算法对初始粒子群的粒子进行更新，对粒子进行交叉操作，可以提高算法的全局搜索能力，进行变异操作，可以改善算法的局部搜索能力。以Matlab为工具进行仿真实验，实验结果表明改进后的算法在求解车辆路径问题时具有良好的性能，可以避免陷入局部最优，对比量子粒子群算法和遗传算法具有一定的优势。

粒子群算法；量子粒子群算法；交叉；变异；车辆路径问题

A

TP301.6

10.3778/j.issn.1002-8331.1306-0353

HUANG Zhen.Hybrid quantum Particle Swarm Optimization algorithm for vehicle routing problem.Computer Engineering and Applications,2013,49（24）：219-223.

广东省惠州市科技计划项目（No.2012-10）；广东省惠州学院自然科学研究项目（No.2012QN11）。

黄震（1980—），男，讲师，主要研究方向：智能算法。E-mail：195146501@qq.com

2013-07-01

2013-08-19

1002-8331（2013）24-0219-05

CNKI出版日期：2013-10-11http://www.cnki.net/kcms/detail/11.2127.TP.20131011.1653.008.html