资源描述：
《车辆路径问题的改进遗传算法_张丽萍》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2002年8月系统工程理论与实践第8期文章编号:1000-6788(2002)08-0079-06车辆路径问题的改进遗传算法张丽萍,柴跃廷(清华大学自动化系CIMS中心,北京100084)摘要:通过引入新颖交叉算子,构造了一种改进遗传算法,此算法摆脱了对群体多样性的要求,不存在传统遗传算法常见的“早熟收敛”问题.将该算法用于解决车辆路径问题,实验结果表明,此算法可以有效求得车辆路径问题的优化解,是求解车辆路径问题的一个较好方案.关键词:遗传算法;车辆路径问题;交叉算子;群体多样性;早熟收敛中图分类号:O224文献标识码:A⒇ImprovedGeneticAlgorithmf
2、orVehicleRoutingProblemZHANGLi-ping,CHAIYue-ting(AutomationDepartment,TsinghuaUniversity,Beijing100084,China)Abstract:Inthispaper,aimprovedgeneticalgorithm(IGA)isproposedbasedonthenovelcrossoveroperator.IGAavoidseffectivelythecommondefectsofearlyconvergenceandthediversityofpopulationintrad
3、itionalgeneticalgorithm.Thisalgorithmcanfindtheoptimalornearlyoptimalsolutiontotheve-hicleroutingproblemeffectively,whichisprovedbyanumberofexperimentsprovidedbythispaper.Keywords:geneticalgorithm;vehicleroutingproblem;crossoveroperator;populationdiversity;earlyconvergence1引言车辆调度问题(Vehicle
4、RoutingProblem简称为VRP)是一个极具魅力的优化问题,吸引着全世界无数的科学家、工程师和管理者为之探索.这不仅是因为它是一类求解较难的组合优化问题,是对人类智慧的考验,而主要是因为它有很强的使用背景,可产生极其可观的经济效益.该问题是一个NP完全问题,只有在需点数和路段数较少时才有可能寻求其精确解.因此,如何针对车辆路径问题的特点,构造运算简单、寻优性能优异的启发式算法,这不仅对于配送系统而且对于许多可转化为车辆路径问题求解的组合优化问题都具有十分重要的意义.先后涌现出一大批启发式算法,如Clark和Wright提出的节约法,Gillett和Miller提出的
5、扫描法,Bramelt和Simchi-Levi提出的基于选址问题转换的LBH法,Fisher和Jaikumar建立的一般分派算法,Christofides和Minggozzi等建立的不完全树搜索算法等.这些算法为求解车辆路径问题提供了有效的方法,但也存在一系列问题,如节约法存在未组合点零乱、边缘点难于组合的问题;扫描法为非渐进优化;LBH法则存在问题转化麻烦且选址问题本身难解等等.近年来,遗传算法、神经网络、禁忌搜索和模拟退火等智能化启发式算法的出现为求解VRP问题提供了新的工具,并且在理论上也取得了一些较好的效果.2问题的描述及数学模型车辆路径问题可以这样描述:假定配送中
6、心最多可用K辆车对L个商店进行运输配送,每个车辆载重为bk(k=1,2,…,K),每个商店的需求为di(i=1,2,…,L),商店i到商店j的物耗值为cij,商店i到商店j的时耗值为tij.设nk为第k辆车所包含的商店数(若nk=0表示未启用第k辆车),用集合Rk表示第⒇收稿日期:2001-01-03作者简介:张丽萍(1969-),女,硕士研究生.研究领域为管理与决策;柴跃廷(1964-),男,副教授.研究领域为CIMS分析与设计、管理与决策、供需链、BRP等方面的研究、开发与应用.80系统工程理论与实践2002年8月k条路径,其中的元素rki表示商店rki在路径k中的顺序
7、为i(不包含配送中心).令rk0=rk(nk+1)=0表示配送中心,则有如下表示的车辆路径问题的数学模型:minnnKkKkλ∑∑crk(i-1)rki+crknkrk(nk-1)sign(nk-1)+(1-λ)∑∑trk(i-1)rki+trknkrk(nk-1)sign(nk-1)(0)k=1i=1k=1i=1nks.t.∑drki≤bk,k=1,2,…,K(1)i=10≤nk≤L,k=1,2,…,K(2)K∑nk=L(3)k=1Rk={rki
8、rki∈{1,2,…,L},i=1,2,…,nk}(4)Rk∩Rk
