基于PSO算法的物流配送车辆路径问题的研究

赵宇橙

摘要：粒子群优化优化（PSO）算法是受自然界生物群体机制启发而得出的一种仿生进化算法。本文首先简要介绍了群智能、粒子群优化、物流配送和车辆路径问题。然后介绍了PSO算法的基本原理，与遗传算法比较证明其优越性。再在PSO算法的基础上，融入爬山算法，使算法性能有所提升，并应用于车辆路径问题。最后对全文进行总结，提出VRP发展的几点建议。

关键词：PSO算法；VRP；爬山算法；遗传算法；优化问题

中图分类号：TP18；O224 文献识别码：A 文章编号：1001-828X（2017）001-0000-03

ABSTRACT：The particle swarm optimizaton（PSO）algorithm is an evolutionary algorithm that simulates the mechanism of biologicaI swarm social behavior.Swarm Intelligence， particle swarm optimizaton， distribution and vehicle routing problem are firstly introduced Afterwards，compared to genetic algorithm，PSO has an obvious advantage，the basic principle of which is analyzed.In addition，the article combines PSO with genetic algorithm to improve algorithm performance and applies mixed algorithm to routing problems.Finally，some suggestions on VRPs development are put forward and summaries are included.

Key Words Particle Swarm Optimization Algorithm； Vehicle Routing Problem； Mounting Climbing Method； Genetic Algorithm； Optimization Problem

一、引言

简单来说，所谓的群智能（Swarm Intelligence），指的是就是一种对于自然界当中，蜜蜂、蚂蚁与鸟群等相关生物群体所进行的行为机制研究。在这当中，虽然说单一生物个体所产生的行为通常都比较简单，但是当许多简单的个体，通过合作来表现出的行为具有明显的复杂性，并且能够完成更加复杂的任务。粒子群优化（Particle Swarm Optimization）算法是群智能方法中较为典型的一种。其是于1995年，由美国的J.Kennedy和R.Eberhart提出的，其中，J.Kenned是一位社会心理学家，而R.Eberhart则是一名电气工程师。其中，PSO算法主要是从人工生命研究开始的，油漆是针对于鱼群与鸟群等的模仿，并且在这当中充分的加入了进化计算的思想。起初，这一算法主要是被运用在函数优化与神经网络的训练当中，之后，相关的研究人员又对其做出了进一步的优化，并开发出了不同的版本，来使的该工具成功的在多个领域中得以运用[1]。

就针对于我国而言，物流概念最早是于1979年出现的，一直到20世纪90年代中期，企业与政府开始重视物流，并赋予其“第三利润的源泉”的价值和战略地位。从本质上来说，物流配送是以供应链管理为基础的，而现阶段，由于存储环节的要求越来越弱化，使的配送变成了其中最为关键的一个环节。而就针对于配送来说，其最核心的部分，就是配送车辆的集货与货物的配送过程。在这个过程当中，怎样选择车辆的配送道路，来使配送更加合理，对于整个物流运输来说尤为重要[2]。这就使得车辆路径问题受到了广泛的关注。在VRP提出以后，其已经出现了许多相对成熟的算法，并很快得到了广泛的重视，在运筹与组合优化领域当中成为一个热点内容[3]。

本項目是研究基于PSO算法的物流配送车辆路径问题，查阅资料整合而成。本项目旨在在PSO算法的基础上融入爬山算法，实现物流配送车辆的路径的优化。

二、PSO算法基本原理

1.基本原理

简单来说，所谓的PSO算法，指的就是一种通过以种群为基础的优化算法。粒子定义成D维空间中的点xi（xi1，xi2，xi3，…，xid，…，xiD），D维空间是要优化问题的解空间，与此同时，粒子要具有一定的速度vi（vi1，vi2，…，vid，…，viD），粒子允许在搜索空间飞行。开始时，算法取一组随机解（x1，x2，x3，…，xN，N为粒子个数）初始化，随后粒子根据自身在解空间中的飞行经验和粒子群体的飞行状况更新自己的速度以及位置，还用有关函数和相应方法计算适应度的值来评价解的好坏，选出pbest（个体极值）和gbest（全局极值）并记录位置，再根据速度更新公式（2-1）和位置更新公式（2-2）更新下一代粒子的速度和位置，依次迭代寻找最优值。公式如下：

（2-1）

（2-2）

公式中，c1和c2指的是正的加速系数，而c1则代表了粒子对于自身记忆的依赖程度，c2则决定了整个粒子群体当中，所包含的其他粒子，对于自身所产生的影响程度，其能够让每个粒子分别向个体极值和全局极值的位置靠近。rand（）和Rand（）是均匀分布在[0，1]区间的随机数；Pid是个体极值的第d维分量。需要注意的是，在这当中，要求粒子的速度必须要地域上限vmax，并且，如果将vmax设置的比较大，其就能过有效的确粒子的种群全局搜索能力得以充分展现，而如果vmax较小，那么粒子种群的局部搜索能力将会得到进一步的强化，而vmax值过小会使算法陷入局部最优。

2.PSO与遗传算法的比较

通过对比可以看出，PSO和遗传算法之间存在许多的共同之处[4]：这两者都能随机初始化种群，并且，其都是通过运用评价函数，来评价个体的优劣程度，并根据这个评价，来得到一个适应值，并对其进行随机的搜索，不过，在实际的搜索过程中，PSO在性能比遗传算法更具优势，因为：

第一，在PSO当中，不存在交叉和变异等遗传操作，其主要是通过运用个体在空间当中的随机速度，来对个体加以改变的，与进化代数相比来说，其解具有更强的随机性，因此，其计算的复杂度也就相对于遗传算法更低一些。

第二，粒子本身有着显著的“记忆”的特性，其可以通过“自我”学习，或者是通过向“他人”学习，来让下一代解能够更好的结成这些信息，并在更短的时间中，找到一个最优的解。

第三，相对于遗传算法来说，PSO有着不同的信息共享机制。因此，在遗传算法当中，染色体能够对信息进行互相的共享，因此，就针对于整个种群的移动而言，其通常是比较均匀的，来向着最优区域移动的。

三、基于PSO的VRP问题优化

为了提高PSO性能，采用惯性权重（inertia weight）法。惯性权重w是与前一次速度有关的比例因数。在（2-1）和（2-2）的基础上进行变化。仍设所搜索的空间为D维，总粒子数为n。第i个粒子位置表示为，速度为，其他向量类似。粒子的位置按如下式进 行变化：

具体操作步骤是：

第一步：初始化粒子群，从1～（K+L-1）中取一个实数作为任一粒子位置向量X的其中一维，从-（ K+L-2）～（K+L-2）取一实数作为每个速度向量V的每一维。设定参数w，c1，c2，R（评价函数中用到）；

第二步：用每个粒子的总路径取代其位置向量；

第三步：评价每个粒子的适应值，将一开始的评价值作为个体极值，并求全局极值；

第四步：每个粒子按照（3-1）求得速度V，再按照（3-2）计算下一代的位置X，如果计算的V、X超过边界值，就用总路径取代X；

第五步：评价每个粒子的适应值，并将其与个体极值以及全局极值之间进行对比，如果说其适应值更小，那么就对全局或者个体极值进行更新。如果说其适应值更小，那么就对全局极值进行更新，一直到其能够满足其所规定的爬山次数为止。

第六步；如果不满足终止条件就返回第四步。

2.混合爬山算法的方案二

在PSO的基础上加入爬山算法的混合PSO算法方案二流程图见图3-2。

具体操作步骤是：

第一步：初始化粒子群，从1～（K+L-1）中取一个实数作为任一粒子位置向量X的其中一维，从-（ K+L-2）～（K+L-2）取一实数作为每个速度向量V的每一维。设定参数w，c1，c2，R（评价函数中用到）；

第二步：用每个粒子的总路径取代其位置向量；

第三步：评价每个粒子的适应值，将一开始的评价值作为个體极值，并求全局极值；

第四步：每个粒子按照（3-1）求得速度V，再按照（3-2）计算下一代的位置X，如果计算的V、X超过边界值，就用总路径取代X；

第五步：对各个粒子的适应值进行评价，并对粒子进行相应的爬山操作，若其适应值更小，那就对个体极值进行更新，一直到其能够达到规定的爬山次数为止。接着再把个体极值和全局极值进行比较，如果适应值更小，就更新个体极值。

第六步；如果不满足终止条件就返回第四步。

3.VRP举例与结果分析

（1）VRP举例

在本次研究当中，我们所参考的文献[5]里面，有一个算例问题为：8个连锁店和1个配送中心的配送系统。其中，在这个配送中心当中，有2辆用来进行配送的车辆，并且，车辆容量均为8吨。在这当中，各个连锁店之间的距离（km）与需求量（吨）见下表。

将标准PSO、PSO混合爬山算法的方案一和混合方案二分别进行20次运算，运算结果参考文献[6]表4-2部分数据，整合成表3-2。通过表3-2数据比较可以得出结论：①在PSO基础上融入爬山算法并应用于VRP问题，性能均优于标准PSO算法 ；②三种方法比较，混合PSO算法方案二收敛速度最快，是一种实行可用的优化方法，能较好地求解物流配送路径问题。

四、结语

为了优化物流配送车辆问题，需要借助改进优化的算法。在查阅大量文献的基础上，本项目对物流配送、粒子群优化算法、遗传算法和车辆路径问题做了简单的介绍和总结，选择了基于粒子群优化算法的混合粒子群算法进行研究。

物流配送车辆路径问题是一个典型的组合优化难题，根据问题的提出形式及约束条件的变化，其求解的复杂度各有不同，本文只针对其中的一部分进行了研究，今后要做的工作还很多，下面几点建议可以作为未来的研究方向：1.多配送中心以及多车型的配送路线优化。2.随机型配送路线优化。3.开发物流配送车辆调度系统。4.PSO算法与其他优化算法的比较、融合和应用。

参考文献：

[1]倪庆剑，邢汉承，张志政，王蓁蓁，文巨峰.粒子群优化算法研究进展[J].模 式识别与人工智能，第20卷第3期：350.

[2]王惠.引入顾客满意度求解车辆优化调度问题[D].辽宁：大连海事大学.2006：1-13.

[3]李军，郭耀煌.物流配送车辆优化调度理论与方法[M].北京：中国物资出版社，2001.

[4]沈艳，郭兵，古天祥.粒子群优化算法及其与遗传算法的比较[J].电子科技大学学报，2005，5（34）：696-699.

[5]赵燕伟，吴斌，蒋丽，等.车辆路径问题的双种群遗传算法求解方法[J].计算机集成制造系统，2004，10（3）：303-306.

[6]陈利.基于混合粒子群算法的物流配送车辆路径问题的研究[D].湖南：中南大学，2007：38.