车辆路径问题的混沌粒子群算法研究

李 毅，陆百川，刘春旭

(重庆交通大学交通运输学院，重庆 40007)

车辆路径问题的混沌粒子群算法研究

李 毅，陆百川，刘春旭

(重庆交通大学交通运输学院，重庆 40007)

针对车辆路径问题中单仓库非满载这一基本类型的具体特性，设计了一种混沌粒子群算法;利用混沌系统的随机性、规律性和遍历性初始化粒子，大范围覆盖车辆路径问题的解空间，加强算法最优路径的搜索能力;通过在求解过程中的次优路径处施加混沌扰动，使算法放弃当前求解的路径，避免结果为次优解。并通过试验验证了该算法在车辆路径问题中具有很强的寻优能力。

车辆路径问题;粒子群算法;混沌系统

车辆路径问题(Vehicle Routing Problem，VRP)自Dantzing［1］于1959年首次提出后，迅速成为运筹学、应用数学、网络分析、计算机应用及交通工程等学科交叉领域研究的热点，受到众多专家、学者的极大重视。时至今日，人们对VRP进行了大量的研究，设计了针对各种约束条件的算法。这些算法种类丰富，但大致可归纳为精确型算法和启发式算法两大类。数搜索法、动态规划、分支定界法、网络流算法等属于精确型算法。精确型算法的计算量一般随问题规模的增大而呈指数增长。而启发式算法则是一种在可接受的计算时间或占用空间下得出待解决问题的满意解，是一种基于直观或经验构造的算法，它包含构造性算法、两阶段法、不完全优化法等。在问题的规模上，启发式算法相对于精确型算法已有些许进步。在近20年内发展起来了一批智能优化算法，如:禁忌搜索算法、遗传算法、蚁群算法以及粒子群算法等一类亚启发式算法，在大规模的VRP问题的求解中，得到了很好的研究与应用。

粒子群算法(Particle Swarm Optimization，PSO)是Kennedy和Eberhart受鸟群觅食启发，于1995年提出的一种群智能优化算法，这种算法具有计算简单、调控参数少、鲁棒性好等优点，已在各类多维连续空间优化问题上取得了非常好的效果。迄今为止，不少研究者设计了基于粒子群的算法，尝试解决车辆路径问题，这些算法包括有基于基本粒子群算法，基于改进粒子群算法，基于混合粒子群算法等［2-5］。改进或是混合粒子群算法都试图改善单纯的基本粒子群算法容易早熟和后期粒子开掘能力差的缺点。笔者针对这缺点，设计了混沌粒子群算法。该算法是在基本粒子群算法中引入混沌的思想，利用混沌系统的规律性、随机性和遍历性来初始化粒子群，改善粒子在搜索全局上的分布，加强粒子的全局搜索能力，并且在粒子的局部极值点施加混沌扰动，帮助惰性粒子逃离局部极值点，改善基本粒子群算法早熟的缺点。

1 车辆路径问题描述及数学模型

一般可以将基本的车辆路径问题描述为:存在一个中心仓库，拥有容量分别为qk(k=1，2，…，K)的K辆车，有L个发货点运输任务需要完成，以1，2，…，L表示，那么定义第 i个发货点的货运量为gi(i=1，2，…，L)，且有 maxgi≤ maxqk，目的是求满足货运需要的所有车辆行驶的最短总路径。

笔者采用文献［6］给出的数学模型:将中心仓库编号为0，发货点编号为1，2，…，L，任务及中心仓库均以点i(i=0，1，…，L)来表示。定义变量如下:

定义Cij为从点i到j的运输成本。这里的运输成本可以是费用、时间、距离，亦或是它们的某种组合等。笔者研究的运输成本代表的是距离。则车辆优化调度数学模型如式(1):

从式(1)可以看出，此模型的每个发货点都有车辆配送，并且每一发货点只由一辆车来完成。问题的寻优就是在保证每条路径上各发货点的总需求量不超过此配送路径上车辆容量的前提下，完成对所有车辆的总路径最短的搜寻。

2 混沌粒子群算法

2.1 基本粒子群算法

在PSO中的粒子代表着一个可能的解，多个粒子同时在解空间中飞行，搜寻最优解。

PSO的数学模型如下:假设针对VRP问题构造的解空间有D维，参与解空间搜索的粒子总数为n。第i个粒子的位置向量可以表示为 Xi=(xi1，xi2，…，xiD);第i个粒子自身的历史最优位置向量记为Pi=(pi1，pi2，…，piD);群体的历史最优位置向量Pg=(pg1，pg2，…，pgD)定义为所有的 Pi(i=1，2，…，n)中的最优;第i个粒子的速度向量可以表示为Vi=(vi1，vi2，…，viD)。则每个粒子的位置向量应按式(2)、式(3)进行更新:

通过近些年的科学研究和工程实践可以发现，PSO算法在高维空间多极值问题以及动态目标的寻优方面有着搜索速度快，解质量高，算法鲁棒性好等诸多优点。

2.2 引入混沌优化的粒子群算法

混沌状态广泛存在于自然现象和社会现象中，其看似混沌，却有着精致的内在结构，具有规律性、随机性和遍历性等独特的性质，它介于确定性和随机性之间。混沌运动能在一定范围内按其自身“规律”不重复遍历所有状态，利用这种性质来初始化粒子，可以优化粒子群算法的粒子初始分布，加强算法的全局搜索能力。

一个典型的混沌系统是由Logistic方程产生:

高鹰，等［7］将混沌优化思想引入到了PSO中，提出了混沌粒子群优化算法(Chaos Particle Swarm Optimization，CPSO)。CPSO的思想主要表现在下面两点:

1)利用混沌方程产生大量差异较大的点来初始化PSO粒子的位置和速度，以此提高PSO群体的遍历性。在产生大量初始群体的基础上，择优出粒子群算法的初始群体，加强算法的全局搜索能力。

2)在Pg处利用混沌方程产生大量混沌序列，根据适应度函数的计算，将最优点随机替换原PSO中的粒子。此举旨在次优解处产生一个混沌扰动，借以帮助惰性粒子离开次优解而继续搜索。

CPSO计算过程可以用图1来示意。

图1 CPSO计算流程Fig.1 Flow chart of the CPSO

3 车辆路径问题的混沌粒子群算法

借鉴文献［8］的思路，构造一个2L维的空间来对应有L个发货点任务的VRP问题。将每个粒子的2L维位置向量X分成两个L维向量:表示各任务对应车辆的Xv和表示各任务在对应的车辆路径中的执行次序Xr。

例如，若一个VRP问题中有9个发货点需要满足发货任务，车辆数为3，此时某一粒子的位置向量X若为:

粒子速度向量V则相应表示为Vv和Vr。

该表示方法以增加粒子的维数为代价换取发货点与单一配送车辆的对应，使解空间的范围大大缩小。后面的实验结果表明维数的并没有增加太大的计算复杂度。

3.1 车辆路径问题的CPSO算法步骤

在实现CPSO算法求解VRP问题时，需要考虑将实数化的解空间转换为整数解空间。因此，求解VRP问题的具体CPSO算法步骤如下:

步骤1:设置精度要求和最大迭代次数，以及惯性权重、学习因子。

步骤2:混沌初始化粒子的位置和速度。

1)随机产生一个2L维的向量X1=(X1v，X1r)，其分量大小均在0～1之间的，L为发货点数量，根据式(4)，得到 N 个向量 X1，X2，…，XN。

2)向量Xiv乘以K取整(意为取1～K之间的整数)，向量Xir乘以L(意为取1～L之间的实数)。

3)用适应度函数Eval(后述)评价所有粒子，择优选出M个作为初始粒子的位置。

4)随机产生M个粒子的初始速度V=(Vv，Vr)，Vv取值为 -(K-1)～(K-1)之间的整数，Vr取值为-(L-1)～(L-1)之间的实数。

步骤3:将初始适应度值作为个体历史最优解Pi，并比较找出种群的最优解Pg。

步骤4:重复执行以下步骤，直到满足精度要求或达到最大迭代次数。

1)根据式(2)、式(3)更新粒子的位置和速度，其中Xv向上取整;当X、V超过其范围时按边界取值。

2)用适应度函数Eval评价所有粒子。

3)更新单个粒子的历史最优值Pi，然后更新种群的全局最优值Pg。

4)对全局最优值Pg施加混沌扰动，用扰动产生

的最优值随机替代一个粒子。

3.2 CPSO算法中适应度函数Eval定义与作用

CPSO算法具体步骤中的适应度函数Eval有两个作用:将实数化的解转换为整数解和计算车辆的总路径Z。

1)首先要将计算过程中得到的Xr按升幂排列，并进行整数化处理，方便行驶距离的计算和后续的迭代。例如，某一粒子的位置向量为:

则表示第 2、3、4、5、6 号任务由车 2 完成，这些任务点所对应的 Xr值为(3.2，6.2，1.2，2.5，0.5)，将其值按升幂重新排列Xr。任务点6所对应的值是0.5，最小，将其更新为1;任务点4对应的值1.2次小，将其更新为2，以此类推。经过整数化处理后得到的Xr为:1 4 5 2 3 1 3 1 2。

2)根据模型计算该粒子所代表方案的距离之和。对于计算过程中出现的不可行解，则此适应度值设为一个可行解不可达到的最大值Tmax。

4 试验结果及分析

笔者用MATLAB7编写了求解VPR问题的CPSO算法、PSO算法和GA算法的程序，并在同一Pentium(R)Dual E2180，1.00GB RAM，Win XP 操作系统的PC机上运行，以此来比较3者之间的性能。

4.1 算法参数设定

GA算法参数:种群规模n=20;参数ε=20，λ =0.95，X=5，Y=50;交叉概率Pc=0.5;变异概率Pm=0.1;轮盘赌法选择子代，最大迭代数100。

PSO算法及CPSO算法参数:粒子群m=20;w=0.729;c1=c2=1.494 45;最大迭代数 100。

4.2 仿真算例的描述

为了方便进行比较，采用文献［6］中的例子:有一个7个发货点任务的VRP问题。各任务的序号和对应坐标如图2。

图2 各任务的序号以及对应坐标Fig.2 Sequences and coordinates of freight-delivery points

各发货点及其对应货运量如表1。

表1 各发货点及货运量Table 1 Freight-delivery points and their volumes

4.3 仿真试验结果及分析

将GA、PSO以及CPSO等3种算法各运行50次，比较结果如表2。

表2 GA、CPSO、PSO算法结果对比Table 2 Result comparison of algorithm for GA，PSO，CPSO

在各自50次的运行中，3种算法成功寻优时的迭代次数有显著的差异，其差异表现如图3。

图3 GA，PSO，CPSO成功寻优迭代次数比较Fig.3 Comparison of steps for GA，PSO，CPSO successful searching

CPSO方法每次达到最优路径的车辆路径均为:

车1:0 2 3 4 5 0

车2:010

车3:0 7 6 0

试验结果表明，从准确度的角度看，CPSO算法对该问题的搜索成功率为100%，高于PSO算法的92%，远高于GA算法的64%;从运算时间的角度看，CPSO算法达到最优路径的速度略快于PSO算法，要比GA算法快10倍左右;从算法结果稳定的角度看，CPSO算法的标准差最小，最稳定，PSO算法对粒子的初始化依赖较高，稳定性最差，GA算法本身成功寻优时的迭代次数较高，没有另外两种算法快捷，稳定性略高于PSO算法。综上可知，在该问题上使用CPSO算法的效果要优于PSO速度，远远优于GA算法。

5 结语

物流配送中，合理安排车辆和路线可以有效减少人力、物力的浪费以及对环境的污染、提高经济效益。然而因为VRP本身属于NP难问题，大规模VRP问题的精确求解难以实现，可以预见亚启发式算法优化求解VRP问题是一种行之有效的方法。笔者将CPSO算法应用到VRP问题中，并通过具体的实验与其他求解算法进行比较，试验结果表明，本文CPSO算法性能稳定，可以很快地找到问题的精确解，是求解车辆路径问题的一种有效方法。

［1］Dantzing G，Ramser J.The truck dispatching problem［J］.Management Science，1959，10(6):10-80.

［2］李宁，邹彤，孙德宝.车辆路径问题的粒子群算法研究［J］.系统工程学报，2004，19(6):596-600.

Li Ning，Zou Tong，Sun Debao.Particle swarm optimization for vehicle problem［J］.Journal of Systems Engineering，2004，19(6):596-600.

［3］吴斌.车辆路径问题的粒子群算法研究与应用［D］.浙江:浙江工业大学，2008.

［4］李相勇.车辆路径问题模型及算法研究［D］.上海:上海交通大学，2007.

［5］王正初.车辆路径问题的改进混合粒子群算法研究［J］.计算机仿真，2008，25(4):267-270.

Wang Zhengchu.Research on improved hybrid particle swarm optimization for vehicle routing problem［J］.Computer Simulation，2008，25(4):267-270.

［6］李军，郭耀煌.物流配送车辆优化调度理论与方法［M］.北京:中国地质出版社，2001.

［7］高鹰，谢胜利.混沌粒子群算法［J］.计算机科学，2004，31(8):13-15.

Gao Ying，Xie Shengli.Chaos particle swarm optimization algorithm［J］.Computer Science，2004，31(8):13-15.

［8］Salmen A，Ahmad I，AI-Madani B.Particle swarm optimization for task assignment problem［J］.Microprocessors and Microsystems，2002，26:363-371.

［9］Maurice C，Kennedy J.The particle swarm-explosion，stability，and convergence in a multidimensional complex space［J］.IEEE Transactions on Evolutionary Computation，2002，6(1):58-73.

［10］黄美灵，陆百川.考虑交叉口延误的城市道路最短路径［J］.重庆交通大学学报:自然科学版，2009，28(6):1060-1063.

Huang Meiling，Lu Baichuan.Determination of the shortest path considering delays at intersections［J］.Journal of Chongqing Jiaotong University:Natural Science，2009，28(6):1060-1063.

Research on Chaos Particle Swarm Optimization Algorithm for Vehicle Routing Problem

Li Yi，Lu Baichuan，Liu Chunxu
(School of Traffic＆ Transportation，Chongqing Jiaotong University，Chongqing 400074，China)

According to characters of the vehicle routing problem，a novel chaos particle swarm optimization(CPSO)algorithm was proposed to solve the basic type of single depot and non-full load.After the chaos was introduced to the particle swarm optimization(PSO)，the random，regularity and ergodicity were used to initialize particles in order to cover the solution space of the vehicle routing problem in large range，enhance the ability for optimal route searching，and prevent the suboptimal solution of the PSO in the way of exerting chaos disturbance at the place of suboptimal solution to help algorithm to abandon the current searching route.Illustration results showed the CPSO had the strong ability to search the global optimal in the vehicle routing problem.

vehicle routing problem(VRP);particle swarm optimization(PSO);chaos system

U116.2

A

1674-0696(2012)04-0842-04

10.3969/j.issn.1674-0696.2012.04.26

2011-11-28;

2011-12-21

重庆市科技攻关项目(2009AA6035)

李 毅(1986—)，男，四川绵阳人，硕士研究生，主要从事交通信息工程及控制方面的研究。E-mail:460900012@qq.com。