带时间窗车辆路径问题的粒子群算法.pdf

2004年4月系统工程理论与实践第4期

文章编号:100026788(2004)0420130206

带时间窗车辆路径问题的粒子群算法

李宁1,2,邹彤1,孙德宝1
1.华中科技大学控制科学与工程系,湖北武汉430074;2.武汉理工大学计算机科学与技术学院,湖北武汉430070)

摘要:将粒子群算法(PSO)应用于带时间窗车辆路径优化问题(VRPTW),构造车辆路径问题的粒子
表达方法,建立了此问题的粒子群算法,并与遗传算法作了比较L实验结果表明,粒子群算法可以快速、
有效求得带时间窗车辆路径问题的优化解,是求解带时间窗车辆路径问题的一个较好方案L
关键词:车辆路径问题;粒子群算法;优化
中图分类号:O221.1;U116.2文献标识码:A

ParticleSwarmOptimizationfor
VehicleRoutingProblemwithTimeWindows

LINing1,2,ZOUTong1,SUNDe2bao1
(1.DepartmentofAutomaticControl,HuazhongUniversityofScience&Technology,Wuhan430074,China;2.Schoolof
ComputerScience&Technology,WuhanUniversityofTechnology,Wuhan430070,China)

Abstract:Thispaperintroducesaproposaltoextendtheheuristiccalled“ParticleSwarm
Optimization”(PSO)todealwiththeVehicleRoutingProblemwithTimeWindows(VRPTW),and
proposesanovelParticlepresentationforthevehicleroutingproblem.ThePSOiscomparedwithGAin
thesameVRPTWinexperiments.ExperimentalresultsindicatethatthePSOcaneffectivelyandquick2
lygetoptimalresolutionofVRPTW,soitisprovedtobeaneffectivemethodforVRPTW.
Keywords:vehicleroutingproblem;particleswarmoptimization;optimization

1引言
车辆路径问题(VehicleRoutingProblem,VRP)由Dantzig和Ramser于1959年首次提出的,它是指
对一系列发货点(或收货点),组成适当的行车路径,使车辆有序地通过它们,在满足一定约束条件的情况
下,达到一定的目标(诸如路程最短、费用最小,耗费时间尽量少等)[1],属于完全NP问题,在运筹、计算
机、物流、管理等学科均有重要意义L
带时间窗的车辆路径问题(VehicleRoutingProblemWithTimeWindows,VRPTW)是在VRP问
题上加了客户要求访问的时间窗口L由于在现实生活中许多问题都可以归结为VRPTW问题来处理(如
邮政投递、火车及公共汽车的调度等),其处理的好坏将直接影响到企业的服务质量,所以对它的研究越来
越受到人们的重视L先后出现了一般启发式算法和神经网络、遗传算法、禁忌搜索和模拟退火等智能化启
发式算法,也取得了一些较好的效果[1]L
粒子群算法(PSO,ParticleSwarmOptimization)[2]是最近出现的一种模拟鸟群飞行的仿生算法,有
着个体数目少、计算简单、鲁棒性好等优点,在各类多维连续空间优化问题上均取得非常好的效果[3]L本文
将PSO应用于车辆路径问题求解中,取得了很好的效果L

收稿日期:2003204230
资助项目:航天技术创新基金项目.
作者简介:李宁(1972-),男(汉),湖北京山人,博士研究生,主要研究方向:系统工程、人工智能、演化计算、人工生命;
孙德宝(1941-),男(汉),湖北云梦人,教授,博士生导师,研究方向:人工智能、信号处理等
第4期带时间窗车辆路径问题的粒子群算法131

2有时间窗车辆路径问题的描述及数学模型

有时间窗车辆路径问题一般描述为:有一个中心仓库,拥有车K辆,容量分别为qk(k=1,2,⋯,K);

现有L个发货点运输任务需要完成,以1,2,⋯,L表示Z第i个发货点的货运量为gi(i=1,2,⋯,L),

(max(g)iFmax(qi)),完成发货点i任务需要的时间(装贷或卸货)表示为Ti,且任务i且必须在时间窗口

[ETi,LTi]完成,其中ETi为任务i的允