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

时间：2025-05-12

第28卷第11期2011年11月计算机应用研究

ResearchofVol．28No．11Nov．2011

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

李

信阳464000）摘

娅，李

丹，王

11东，杨文茵

（1．佛山科学技术学院机电与信息工程学院计算机系，广东佛山528000；2．信阳供电公司科技信息部，河南

要：为求解车辆路径问题提出一种改进的混沌粒子群优化算法。该算法在基本混沌粒子群优化算法（CP-

SO）基础上，引入逻辑斯特函数，对惯性权重因子w进行非线性调整，提高了算法的寻优能力，有效避免了算法陷入局部最优并防止过早收敛。采用该算法应用于车辆路径问题，仿真结果表明该与标准遗传和双种群遗传算法比较，具有一定的优势。

关键词：粒子群；车辆路径问题；混沌；非线性；逻辑斯特函数中图分类号：TP202.7

文献标志码：A

文章编号：1001-3695（2011）11-4107-04

3695．2011．11．028doi：10．3969/j．issn．1001-

Improvedchaosparticleswarmoptimizationalgorithmforvehicleroutingproblem

LIYa1，LIDan2，WANGDong1，YANGWen-yin1

（1．Dept．ofComputer，SchoolofElectrical＆InformationEngineering，FoshanUniversity，FoshanGuangdong528000，China；2．Technology＆InformationCenter，ElectricPowerofXinyang，XinyangHenan464000，China）

Abstract：ThispaperproposedanimprovedchaosparticleswarmoptimizationalgorithmforVRP．Basedonclassicalchaos

linearlyadjusttheinertiaweightoftheclassicialparticleswarmoptimization（CPSO）algorithm，itusedlogisticfunctiontono-PSOalgorithmtoimprovetheabilitytofindthebestswarmandtoovercometheshortcomingoftrappedinlocalminima．Test

showsthatthealgorithmisbetterthantwokindsofgeneticalgorithm（CA）todealwithVRP．Keywords：particlesswarm；vehicleroutingproblem（VRP）；chaos；nolinear；logisticfunction

随着市场经济的发展和物流技术专业化水平的提高，物流配送业得到了迅猛发展。（VRP）是亟待解决的一个重要问题。该问题由Dantzig和Ramser于1959年首次提出，它是物流决策中的关键环节，直接影响到顾客的服务对提高物流经济效益，实现物流科学化起着质量与运作成本，

重要作用。其任务是根据顾客的需求情况和配送中心的条件，设计运输工具组合、线路组合和时间组合，从而实现运作过程的最优化和经济效益的最大化。目驶路线，

前，利用启发式算法如微粒群、遗传、蚁群、仿真退火等能较好地求解VRP。其中，微粒群算法也称为粒子群优化（particlePSO）算法，swarmoptimization，，且鲁棒性易于实现，能以较大的概率找到优化问题的全局最优解等好、

优点，引起了广大学者的广泛关注。但是由于PSO算法的寻粒子本身，PSO。近年来，人，

1］在PSO中引入混沌们对粒子群算法作了许多改进。文献［

这种可以跳出局部极值的技术，利用混沌具有的随机性、遍历在一定范围内能够按其资深的性和对初始条件的极度敏感性，

规律不重复地遍历所有状态等特点，对PSO每次找到的全局极值进行混沌搜索，使算法避免陷入局部最优解，最大可能地2］提出了随着迭代的进行线性减小w找到全局最优解。文献［

惯性权重的策略。由PSO粒子的搜索特征不难发现，线性减

收稿日期：2011-04-06；修回日期：2011-05-12

小不能满足开始搜索速度快些，搜索后期速度慢些的要求；而且PSO在实际搜索过程中是非线性的且是高度复杂的，致使算法在求解复杂问题的后期易发生早熟收敛。

1，2］本文在文献［的基础上根据粒子群算法进化的特点，结合逻辑斯特函数提出一种新的粒子群优化算法。

1车辆路径问题的描述

VRP的数学描述如下［3］：已知k个客户和1个配送中心，

第i个客户的需求为qi，从配送中心派出载重为Q的m辆车为客户服务，最后回到配送中心。已知qi≤Q，求一条最佳的服务路线（运作费用少）。dij表示从点i到点j的运作成本（如时路程、花费等）。配送中心编号为0，每个客户均以点i（i=间、

1，2，…，k）来表示，2，…，m）。定义变各辆车的编号为s（s=1，量为

xijs=yis=

{

车s从点i行驶到点j否则

（1）（2）

{

客户i的任务由车s来服务否则

建立模型的目标就是使得总运作费用最少。而运作费用与车辆的行驶路径成正比，行驶路径越短，车辆的耗油量就越司机的工作时间也越少，从而总运作费用就越少。因此建少，

基金项目：广东省自然科学基金资助项目（10152800001000029）

bh@163．com）；李丹（1973-），作者简介：李娅（1978-），女，湖北黄石人，讲师，硕士，主要研究方向为智能优化算法及应用（li-男，湖北黄石人，工程师，主要研究方向为计算机网络、信息管理；王东（1970-），男，黑龙江甘南人，副教授，博士，主要研究方向为组合优化、智能计算；杨文茵（1982-），女，广东开平人，讲师，博士，主要研究方向为计算机网络．

·4108·

立以总行车路径最短为目标函数的VRP数学模型为

minZ=∑∑∑dijxijs

i=0j=0s=1k

计算机应用研究

粒子的平均粒距：

（3）（4）（5）（6）（7）

D（t）=

·∑N·Li=1

第28卷

i=0

∑qiyis≤Q∑yis=1