适于配送车辆导航路径规划的遍历模型的改进型粒子群优化算法*

章权 温惠英 孙博

(1.长安大学公路学院，陕西 西安710064;2.广东省公路管理局，广东广州510075;3.华南理工大学土木与交通学院，广东广州510640)

车辆路径规划，是指在旅行前或旅行中为驾驶员提供参考行驶路线的一个过程，是车辆导航系统的基本功能之一，同时也是配送车辆导航系统中的技术难点，是一个NP-hard问题，直接影响着物流配送车辆导航的实时性能［1］.车辆路径规划问题本质上是一个旅行商问题(TSP)，又是一个非确定性多项式问题即NP问题.由于车辆路径规划需考虑多旅行商多目标、交发货时间、车辆容量限制、行驶里程限制、时间限制等限制因素［2］，该问题比TSP更复杂.

配送车辆导航路径规划(VND)不同于普通物流配送车辆路径规划，它是指单个车辆从配送中心到各个货物需求点的路径规划，是对单个车辆行驶过程中的动态路径优化［3］，而普通物流配送车辆路径规划优化的结果在车辆行驶过程中一般是不变的［4-6］.文中建立了VND问题的遍历模型，并用改进粒子群算法求解，最后通过仿真实验证明模型的合理性和算法的有效性.

1 配送车辆导航路径规划遍历模型的建立

如果把城市路网中的交叉路口表示为节点，则任意两个交叉路口之间的道路就是连接两节点的边(也称为弧)，边的权值由路网提供.这样，城市路网可以表示成一个带权有向图G=(V，{E})，其中V是节点(也可简称为点)的集合，E是边的集合，＜i，j＞是E中从节点i至j的边.物流配送车辆导航的其中一个重要特点是遍历性，即每辆车都有自己需要访问的多个货物需求点.在物流配送车辆导航中，遍历模型是指单个车辆遍历所有货物需求点的路径规划模型.通常每辆车所需要访问的货物需求点有多个，即要考虑多个货物需求点的遍历问题，该问题是一个NP问题.

设对权值产生影响的因素共有l种，遍历模型可以描述为:

式中:tij∈{0，1}，如果 tij=1 表示边 ＜ i，j＞ 被选中，否则为未被选中;αk为比例系数，表示第k种因素的权重;fk(tij)表示第k种因素对边＜i，j＞产生影响后的值，若边未被选中，则无影响，fk(tij)=0.

式(1)为目标函数，约束条件式(2)表示节点ui(i=1，2，…，n－1)有且只有一个出口，目标节点 un无出口;式(3)表示节点uj(j=2，3，…，n)有且只有一个入口，起始节点无入口.

物流配送车辆导航的遍历问题和一般的遍历问题不同处如下.

(1)一般的遍历问题，如TSP，起始节点和目标节点可以是任意的.而对于文中的VND问题，起始节点和目标节点是确定的.

例如，设节点有 3个(A，B，C)，则 ABCA 和BCAB都是TSP问题的可行解.但对于VND问题，如果节点A对应的是起始节点，则BCAB不是可行解.

(2)在TSP问题中，每个点既有出口也有入口.在VND问题中，既包含起始节点有入口的情况(车辆刚出发时，此时起始节点为物流配送中心，车辆完成任务后必须回到该点)，也包含起始节点没有入口的情况(车辆开始行驶时，起始节点是车辆的当前位置，不再是物流配送中心).

(3)对于TSP问题，起始节点和目标节点一般是相同的，而对于物流配送车辆导航的遍历问题，起始节点和目标节点可以不同.

2 基本粒子群优化算法及改进思路

2.1 粒子群优化算法概述

粒子群优化算法PSO是一种群智能优化算法，由Kennedy等［7］于1995年首次提出.PSO源于对鸟群捕食行为的研究，鸟群觅食时，总是有一只鸟对食源的大致方向具有较好的洞察力，同时，在找寻食源的途中，它们通过一套自己独有的方式随时相互传递着信息，特别是较好的信息.在“好消息”的指引下，导致鸟群“一窝蜂”的奔向食源，达到在食源的群集.在PSO算法中，每一只鸟称为一个“粒子”，解群相当于一个鸟群，从一地到另一地的迁徙相当于解群的进化，“好消息”相当于解群每代进化中的最优解，食源相当于全局最优解［7］.PSO算法优点在于算法流程简单易实现，算法参数简洁且无需复杂的调整.

基本 PSO 算法由 Shi和 Eberhart提出［8］，但是该算法在计算的早期收敛较快，精度较低.文中将把遗传算法中的交叉和变异的思想引入到PSO算法中，建立适于VND的PSO算法.

2.2 适于VND模型的基本PSO算法改进思路

VND本身的特点决定了基本PSO算法不能直接用于求解VND问题［3］，需要对基本PSO算法进行编码、初始种群的产生、种群的进化策略等方面的改进.参考文献［3，9-10］，文中采用可行解空间的搜索方式对PSO算法进行改进.对于物流配送车辆导航的两种不同的路径规划模型，采用相同的编码方案，即将一个路径规划问题的可行解定义为一串字符串，假设P表示起点为S到目标节点为E的可变字符串，P=A1A2…Ak，其中 Ai(i=1，2，…，k)为路网中的节点，且Ai和 Ai+1直接连通(i=1，2，…，k－1)，A1=S，Ak=E.可行解P的值定义为其中dAiAi+1为节点Ai和Ai+1之间的连结权值.

3 遍历模型的粒子群优化算法

下面结合VND本身的特点，通过改进初始种群的产生方法和种群的进化策略，提出适于VND遍历模型的改进型IPSO(Improved Particle Swarm Optimization)算法.

3.1 初始种群产生方法的改进

文中采用将节点进行随机排列的方式产生初始种群.由于物流配送车辆导航中，起始节点和目标节点往往是固定的，所以起始节点和目标节点不参与随机排列.比如节点只有5个，起始节点和目标节点的编号分别为1和5，那么随机排列产生的个体只可能有6种情况，分别是(1，2，3，4，5)，(1，2，4，3，5)，(1，3，2，4，5)，(1，4，2，3，5)，(1，3，4，2，5)，(1，4，3，2，5).

3.2 种群进化策略的改进

这里将交叉运算引入PSO算法中，以改进VND遍历模型求解的进化策略，使得PSO算法中的粒子能进行优化组合.在VND遍历模型求解中，两个解之间的差实际上是解所在路网中节点的位置不同.因此，可以用节点位置的差别来表示PSO算法中的距离.设和是两个不同的可行解，则最多只需要进行l次交换就可以使其中一个解变成另一个解，可以将交换的次数看作是两个粒子间的距离.

设需更新的粒子是u1，其更新目标是u2(u2可以是gbest1或pbest2，这里的gbest1、pbest2指的是种群最优解)，它们之间的距离是l，具体做法是:

(1)产生一个［0，l］之间的随机整数l0;

(2)随机扫描u1和u2共l0次;

(3)如果扫描到某一位置时，两个粒子中的节点不同，则以u2为准对u1进行更新.

这样，经改进后的 IPSO算法就可以应用于VND遍历模型求解.

3.3 适于VND遍历模型的改进型PSO算法

通过大量实验发现，PSO算法在开始时收敛很快，但在计算的后期收敛速度很慢，且粒子慢慢趋于同一个方向，陷入了局部最优解.受小生境思想的启发，文章提出适于VND遍历模型的改进型IPSO算法，该算法通过缩短每个粒子的寿命来达到跳出局部最优解的目的.具体做法是:当结果在几次飞行后(实验中取20次)没有改善时，保留该群粒子所找到的最好结果，然后让其它的粒子消失，它们所保存的历史记录也随之消失;再重新产生一群新的粒子来继续进行PSO算法流程.

采用14个节点的标准TSP问题对算法进行测试.各节点的坐标分别为{(16.47，96.10)，(16.47， 94.44)， (20.09， 92.54)， (22.39，93.37)， (25.23， 97.24)， (22.00， 96.05)，(20.47， 97.02)， (17.20， 96.29)， (16.30，97.38)， (14.05， 98.12)， (16.53， 97.38)，(21.52， 95.59)， (19.41， 97.13)， (20.09，94.55)}.为简单起见，节点之间的权值取节点之间的欧氏距离.实验中，种群大小为100，从粒子第1次飞行到粒子倒数第2次飞行的时间限定为5 s，此时飞行次数不固定.共测试100次，每次实验如果找到最优解，则立即停止.

算法进化情况见图1、图2，改进型PSO算法与基本PSO算法的性能比较见表1，由实验结果可知:

(1)在获得全局最优值的前提下改进型IPSO算法比基本PSO算法的迭代次数更少，收敛速度较快，具有更高的搜索效率;

(2)改进型IPSO算法最好结果的平均总代价和平均计算时间都比基本PSO算法的小，因此，改进型IPSO算法总体性能要优于基本PSO算法.

图1 两种算法进化代数曲线比较图Fig.1 Algebraic curve of evolution comparison for two algorithms

图2 两种算法最好结果曲线比较图Fig.2 Curve of the optimum relation comparison for two algorithms

表1 算法比较Table 1 Algorithm comparison

4 改进型粒子群优化算法仿真实验

实验中，取系数 c0=1，c1=1，c2=1，r1、r2每次迭代均取［0，1］之间的随机数，种群规模为100，节点之间的权值取节点之间的欧氏距离，节点数据为14个节点的标准TSP问题.实验环境:CPU 1.66GHz，内存512MB DDR2，WindowsXP，Matlab7.0.图3、图4分别给出了初始解中的最优解及最终计算结果.

图3 初始解中的最优解Fig.3 Optimum relation of initial evolution

图4 IPSO算法实验结果Fig.4 Tests results of IPSO

针对此问题，本算法在第19代得到最优解，耗时0.19s.文献［9］中对同一问题在20000代得到了最优解，IPSO算法总代价曲线图如图5所示.

图5 IPSO算法总代价曲线图Fig.5 Total cost curve of IPSO

根据实验结果可知，改进型IPSO算法可以大大减少在解空间中的搜索量，收敛速度较快，在第19代得到了最优解，每代搜索了100个解，共搜索1900个解.而对14个节点的物流配送车辆导航遍历模型的路径规划问题，可行解共有13个，文章的改进型IPSO算法只搜索了整个解空间的0.000030512%.

5 结论

文中结合VND问题的实际特点，建立了VND遍历模型.分析了PSO算法存在的不足之处，即计算初期收敛很快，但在后期收敛速度很慢，结果基本上没有改善，而粒子也慢慢趋于同一个方向，陷入了局部最优解.针对PSO算法的缺陷，文中引入小生境思想来缩短每个粒子的寿命，对PSO算法在初始种群的产生方法和种群的进化策略方面进行改进，并提出了适于求解VND遍历模型的改进型PSO算法，使原本不能直接用于求解VND模型的PSO算法，在求解VND问题上取得了很好的效果.仿真实验表明，改进后的IPSO算法具有运算快速，收敛效果好等优点，在求解VND遍历模型问题时，大大缩短了计算时间，较基本PSO算法有较大的改进.

［1］温惠英，沈毅贤.基于层次分析法的物流配送车辆导航路径规划求权方法［J］.公路交通科技，2008，8(25):114-118.Wen Hui-ying，Sheng Yi-xian.A method of computing weight of logistics navigation route planning based on analytic hierarchy process［J］.Journal of Highway and Transportation Research and Development，2008，8(25):114-118.

［2］姜大立.车辆路径问题的GA研究［J］.系统工程理论与实践，1999(6):40-45.Jiang Da-li.GA research of vehicle routing problem ［J］.Systems Engineering-Theory ＆ Practice，1999(6):40-45.

［3］温惠英，李俊辉，周玮明.适于车辆路径规划的改进型粒子群优化算法［J］.华南理工大学学报:自然科学版，2009，37(7):1-5.Wen Hui-ying，Li Jun-hui，Zhou Wei-ming.Improved particle swarm optimization algorithm for vehicle routing planning［J］.Journal of South China University of Technology:Natural Science Edition，2009，37(7):1-5.

［4］蒋忠中，汪定伟.物流配送车辆路径优化的模糊规划模型与算法［J］.系统仿真学报，2006，18(11):3301-3312.Jiang Zhong-zhong，Wang Ding-wei.Fuzzy programming model and algorithm of logistics distribution vehicle routing problem ［J］.Journal of System Simulation，2006，18(11):3301-3312.

［5］Schwefel H.Evolution and optimum seeking［M］.New York:John Wiley ＆ Sons，1994.

［6］Maniezzo V，Colorni A.The ant system applied to the quadratic assignment problem［J］.IEEE Trans on Knowl Data Eng，1999，1(5):769-798.

［7］Kennedy J，Eberhart R.Particle swarm optimization［C］∥Proceedings of IEEE International Conference on Neural Networks.Piscataway:IEEE Service Center，1995:1942-1948.

［8］Eberhart R C，Shi Y.Particle swarm optimization:developments，applications and resources［C］∥Proc Congress on Evolutionary Computation.Piscataway:IEEE Press，2001:81-86.

［9］张利彪，周春光，马铭，等.基于PSO算法的模糊C-均值聚类［J］.吉林大学学报:理学版，2006，44(2):217-222.Zhang Li-biao，Zhou Chun-guang，Ma Ming，et al.Fuzzy C-mean clustering based on particle swarm optimization［J］.Journal of Jilin University:Sci Ed，2006，44(2):217-222.

［10］Van Den Bergh F，Engelbrecht A P.Using cooperative particle swarm optimization to train product unit neural networks［C］∥IEEE International Joint Conference on Neural Networks.Washington D C:［s.n.］，2001.