粒子群优化算法在车辆路径规划中的研究

第２２卷第５期　２００８年１０月　江苏科技大学学报（自然科学版）　Ｊｏｕｒｎａｌ　ｏｆ　Ｊｉａｎｇｓｕ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｖｏ１．２２　Ｎｏ．５　０ｃｔ．２０ｏ８　

粒子群优化算法中粒子更新方法研究　

田雨波，朱人杰，李正强　

（江苏科技大学电子信息学院，江苏镇江２１２００３）　

摘要：粒子群优化算法是根据鸟或鱼群居社会行为而提出的随机优化算法，但标准粒子群优化算法存在早熟收敛和　搜索精度低等问题．因此模拟生物克隆选择中５％的Ｂ细胞自然消亡过程，在粒子群优化算法进化过程中分别基于代间　差分、混沌理论、变异原理等方法设计了８种粒子更新算法，并按照模拟退火方法进行更新后粒子的选择．通过数值实验　得出基于代间差分和混沌变异的粒子更新算法（即算法８）是一种很好的选择，并且当性能较差的２０％左右粒子按照这　种算法更新时效果较好．这种算法可以有效克服标准粒子群算法的早熟现象，并能够加快收敛速度．　关键词：粒子群算法；克隆选择；混沌；变异；模拟退火　

中图分类号：ＴＰ３０１．６　文献标识码：Ａ　文章编号：１６７３—４８０７（２００８）０５—００６７—０６　

Ｒｅｓｅａｒｃｈ　ｏｎ　ｕｐｄａｔｉｎｇ　ａｌｇｏｒｉｔｈｍｓ　ｉｎ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　

ＴＩＡＮ　Ｙｕｂｏ，ＺＨＵ　Ｒｅｎｊｉｅ，ＬＩ　Ｚｈｅｎｇｑｉａｎｇ　（Ｓｃｈｏｏｌ　ｏｆ　Ｅｌｅｃｔｒｏｎｉｃｓ　ａｎｄ　Ｉｎｆｏｒｍａｔｉｏｎ，Ｊｉａｎｇｓｕ　Ｕｎｉｖｅｒｓｉｔｙ　ｏｆ　Ｓｃｉｅｎｃｅ　ａｎｄ　Ｔｅｃｈｎｏｌｏｇｙ，Ｚｈｅ￣ｉａｎｇ　Ｊｉａｎｇｓｕ　２１２００３，Ｃｈｉｎａ）　

Ａｂｓｔｒａｃｔ：ＰＳＯ（Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　Ｏｐｔｉｍｉｚａｔｉｏｎ）ｉｓ　ａ　ｓｔｏｃｈａｓｔｉｃ　ｏｐｔｉｍｉｚａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｉｎｓｐｉｒｅｄ　ｂｙ　ｓｏｃｉａｌ　ｂｅｈａｖ—　ｉ０ｒ　ｏｆ　ｂｉｒｄ　ｆｌｏｃｋｉｎｇ　ｏｒ　ｆｉｓｈ　ｓｃｈｏｏｌｉｎｇ．Ｈｏｗｅｖｅｒ，ｔｈｅ　ｓｔａｎｄａｒｄ　ＰＳＯ　ｈａｓ　ｓｏｍｅ　ｓｈｏｒｔｃｏｍｉｎｇｓ，ｓｕｃｈ　ａｓ　ｐｒｅｍａｔｕｒｅ　

数字化 互联网+

数码世界 P.162基于改进粒子群算法的物流车辆路径优化问题研究

孟宪秋 邱春艳 姜建华 刘洋 吉林财经大学管理科学与信息工程学院

摘要：利用智能优化算法对车辆路径优化成为当前国际研究热点，有的智能优化算法存在易陷入局部最优，且收敛性速度不快等问题。本文应用改进的微粒群算法对物流车辆路径进行优化，将惯性因子设为0，通过仿真实验分析，改进后的粒子群算法更具有更好的收敛性（呈线性收敛），并且避免了局部极值代替全局最优值问题，最优解需要的迭代次数明显减少，也缩短了寻优时间。关键词：车辆路径 单目标优化问题 粒子群算法

引言：车辆路径问题（Vehicle Routing Problem，VRP）来源

于交通运输，由Dantzing和Ramser在1959年首次提出的运输组

织优化中的核心问题，也是运筹学的一类经典组合优化问题。智能优

化算法是一种基于物理或仿生学原理的元启发式算法，如模拟退火

算法，禁忌搜索算法，遗传算法，粒子群优化算法等，智能优化算法

能够在有限的时间内求解车辆最优路径，成为求解车辆路径问题的

常用算法。由于粒子群在求解车辆路径问题时性能良好，因此该方面

的研究逐渐得到学术界的广泛重视。

国内学者在解决车辆路径问题时主要采用两类策略：一类是使

用非智能算法进行求解车辆路径问题，此方法可以有效的结解决车

辆路径问题；另一类是智能算法进行求解车辆路径问题，包括单目标

算法，改进的单目标算法以及混合的智能算法。本文采用粒子群优化

(Particle Swarm Optimizer,PSO)算法，将惯性因子设为0，可以

增加收敛性且增强局部搜索能力，因此较为客观。

1基本问题描述及模型建立

1.1问题描述

车辆路径优化也就是旅行商问题，即对每辆车所走的路径进行

优化，以达到整体路径最短。

问题描述：一个中心仓库序号为0，7个仓库序号为1-7，其位置

坐标见表1，中心仓库有3辆车，容量均为1，由这3辆车向7个需求

点进行货物配送，出发点和收车点都是中心仓库，求解物流配送车辆

第２５卷第４期　计算机仿真　２００８年４月　

文章编号：１００６—９３４８（２ＯＯ８）Ｏ４—０２６７—０４　

车辆路径问题的改进混合粒子群算法研究　

王正初　

（台州学院机电工程学院，浙江台州３１８０００）　

摘要：针对各种启发式算法在求车辆路径问题（ＶＲＰ）中的缺陷，提出了改进的混合粒子群算法（ＭＨＰＳＯ）的求解方法。分析　

了基于速度一位置更新策略传统粒子群算法在解决离散的和组合优化问题的不足。考虑到算法在求解过程中种群多样性　的损失过快，引进了种群的多样性测度参数一平均粒距，以保持种群的多样性。同时利用混沌运功的随机性、遍历性和规律　

性等特性，采用混沌初始化粒子编码。详细讨论了该算法在车辆路径问题中的求解策略。针对同一个实例，将改进的混合　粒子群算法与遗传算法从多个角度进行比较。仿真结果表明，论文所提出的算法性能较好，可以快速、有效求得车辆路径问　

题的优化解或近似优化解。　

关键词：车辆路径问题；粒子群优化；群智能；优化　

中图分类号：ｏ２２４　文献标识码：Ａ　

Ｒｅｓｅａｒｃｈ　ｏｎ　Ｉｍｐｒｏｖｅｄ　Ｈｙｂｒｉｄ　Ｐａｒｔｉｃｌｅ　Ｓｗａｒｍ　

Ｏｐｔｉｍｉｚａｔｉｏｎ　ｆｏｒ　Ｖｅｈｉｃｌｅ　Ｒｏｕｔｉｎｇ　Ｐｒｏｂｌｅｍ　

ＷＡＮＧ　Ｚｈｅｎｇ—ｃｈｕ　

（Ｃｏｌｌｅｇｅ　ｏｆ　Ｍｅｃｈａｎｉｃａｌ　ａｎｄ　Ｅｌｅｅｔｒｏｎｉｃａｌ　Ｅｎｇｉｎｅｅｒｉｎｇ，Ｔａｉｚｈｏｕ　Ｃｏｌｌｅｇｅ，Ｔａｉｚｈｏｕ　Ｚｈｅｊｉａｎｇ　３１８０００，Ｃｈｉｎａ）　

ＡＢＳＴＲＡＣＴ：Ｍａｎｙ　ｍｏｄｅｒｎ　ｈｅｕｒｉｓｔｉｃ　ａｌｇｏｒｉｔｈｍｓ　ｈａｖｅ　ｂｅｅｎ　ａｐｐｌｉｅｄ　ｔｏ　ｔｈｅ　ｖｅｈｉｃｌｅ　ｒｏｕｔｉｎｇ　ｐｒｏｂｌｅｍ（ＶＲＰ）ａｎｄ　ｔｈｅｙ　

ａｌｌ　ｈａｖｅ　ｔｈｅｉｒ　ｓｈｏｒｔｃｏｍｉｎｇ．Ｍｏｄｉｆｉｅｄ　ｈｙｂｒｉｄ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ（ＭＨＰＳＯ）ｉｓ　ｐｒｏｐｏｓｅｄ．Ｔｈｅ　ｉｎｓｕｆｆｉｃｉｅｎｃｙ　ｏｆ　

Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄＡｐｐｌｉｃａｔｉｏｎｓ计算机工程与应用　

改进粒子群算法在机器人路径规划中的应用　

马千知，雷秀娟　

ＭＡ　Ｑｉａｎｚｈｉ，ＬＥＩ　ＸｉｕｊＨａｉｌ　陕西师范大学计算机科学学院，西安７１００６２　Ｃｏｌｌｅｇｅ　ｏｆ　Ｃｏｍｐｕｔｅｒ　Ｓｃｉｅｎｃｅ，Ｓｈａａｎｘｉ　Ｎｏｒｍａｌ　Ｕｎｉｖｅｒｓｉｔｙ，Ｘｉ’ａｎ　７　１　００６２，Ｃｈｉｎａ　

ＭＡ　Ｑｉａｎｚｈｉ，ＬＥＩ　Ｘｉｕｊｕａｎ．ＡｐｐＨｃａｄｏｎ　ｏｆ　ｉｍｐｒｏｖｅｄ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｆｉｍ￣ａｔｉｏｎ　ａｌｇｏｒｉｔｈｍ　ｉｎ　ｒｏｂｏｔｉｃ　ｐａｔｈ　ｐｌａｎｎｉｎｇ．　Ｃｏｍｐｕｔｅｒ　Ｅｎｇｉｎｅｅｒｉｎｇ　ａｎｄ　Ａｐｐ￣ｃａｆｌｏｎｓ，２０１１，４７（２５）：２４１－２４４．　

Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ　ｔｏ　ｔｈｅ　ｄｅｆｅｃｔ　ｏｆ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｔｈａｔ　ｉｔ　ｉｓ　ｅａｓｉｌｙ　ｔｏ　ｆａｌｌ　ｉｎｔｏ　ｌｏｃａｌ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ，ｃｏｍｂｉｎ－　

ｉｎｇ　ｗｉｔｈ　ｔｈｅ　ｍｏｄｅｌ　ｏｆ　ｒｏｂｏｔｉｃ　ｐａｔｈ　ｐｌａｎｎｉｎｇ，ａ　ｎｏｖｅｌ　ｐａｒｔｉｃｌｅ　ｓｗａｒｍ　ｏｐｔｉｍｉｚａｔｉｏｎ　ｗｉｔｈ　ｐｅｒｔｕｒｂａｔｉｏｎ　ｍｅｃｈａｎｉｓｍ　ｉｓ　ｐｒｏｐｏｓｅｄ．Ｉｎ　

ｐｅｒｔｕｒｂａｔｉｏｎ　ｍｅｃｈａｎｉｓｍ，ｔｈｅ　ｎｅｗ　ｍｏｄｉｆｉｅｄ　ｐａｒｔｉｃｌｅｓ　ａｒｅ　ｐｒｏｄｕｃｅｄ　ｔｏ　ｔａｋｅ　ｐｌａｃｅｓ　ｏｆ　ｔｈｏｓｅ　ｐａｒｔｉｃｌｅｓ　ｗｈｉｃｈ　ｋｅｅｐ　ｎｏ　ｅｖｏｌｕｔｉｏｎ—　Ｔｈｉｓ　ｍｅｔｈｏｄ　ｌｅａｄｓ　ｔｈｅ　ａｌｇｏｒｉｔｈｍ　ｔｏ　ｆｉｎｄ　ｔｈｅ　ｆｅａｓｉｂｌｅ　ｐａｔｈ　ａｎｄ　ｉｓ　ｈｅｌｐｆｕｌ　ｆｏｒ　ｅｓｃａｐｉｎｇ　ｔｈｅ　ｌｏｃａｌ　ｏｐｔｉｍａｌ　ｓｏｌｕｔｉｏｎ．Ｓｉｍｕｌａｔｉｏｎ