基于Memetic算法的带时间窗车辆路径问题研究.pdf

《基于Memetic算法的带时间窗车辆路径问题研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第29卷第1期2012年1月计算机应用研究ApplicationResearchofComputersV01．29No．1Jan．2012基于Memetic算法的带时间窗车辆路径问题研究吴雷，魏臻，葛方振(合肥工业大学计算机与信息学院，合肥230009)摘要：提出一种模拟文化进化的Memetic算法求解带时间窗的车辆路径问题。设计了一种实数编码方案，将离散的问题转为连续优化问题。采用邻域搜索帮助具备一定学习能力的个体提高寻优速度；采用禁忌搜索帮助部分个体跳出局部最优点，增强全局寻优性能。实验结果

2、表明，该算法可以更有效地求出优化解，是带时间窗车辆路径问题的一种有效求解算法。关键词：带时问窗车辆路径问题；文化基因算法；粒子群算法；禁忌搜索中图分类号：TP301．6文献标志码：A文章编号：1001—3695(2012)01—0060-03doi：10．3969／j．issn．1001—3695．2012．01．016MemeticalgorithmforvehicleroutingproblemwithtimewindowsWULei。WEIZhen，GEFang-zhen(Schoolof

3、Computer＆htformation，HefeiUniversity矿Technology，uPfei230009，China)Abstract：ThispaperproposedaMemeticalgorithm，whichsimulatedtheprocessofcultureevolution，tosolvevehicleroutingproblemwithtimewindows(VRPTW)．ToconvertVR刀Wintocontinuousproblem，itdesigneda

4、realcodingmethod．Thememeticalgorithmhelpedtheparticleswhichhadcertainlearningcapacityaccelerateconvergenceratebylocalsearchstrate-gY．Meanwhile，becauseofhelpingsomeparticleswhichfellintothelocaloptimumescapefromlocaloptimumbytabusearch，itenhancedthedi

5、versityofswarm．Theexperimentalresultshowsthattheproposedalgorithmcmlgetthesolutionmoreeffee．tivelyanditisaneffectivemethodforVR唧．Keywords：VRPTW；Memeticalgorithm；PS0；tabu0引言车辆路径问题(vehicleroutingproblem，VRP)1959年由Dantzig和Ramser首次提出，一直是组合优化领域的热点和前沿问题”]。

6、随着VRP研究的不断深入，考虑到需求点对于车辆到达时间有所要求，因此车辆路径问题中加人了时间窗的限制，便成为了带时间窗的车辆路径问题(VRPwithtimewin-dows，VRFFW)。VRPTW是一个NP难问题，对它的研究越来越受到国内外学者的重视，其算法的研究主要集中在粒子群算法、遗传算法、禁忌搜索法和模拟退火法等各种启发式算法上，并取得了一些不错的效果

7、2“J。Memetic算法是一种模拟文化进化过程的新型进化方法，通过混合局部搜索和进化算子来解决优化问题，是一种基于种群的全局搜索和基于

8、个体的局部启发式搜索的结合体。它的这种全局搜索和局部搜索的结合机制使其搜索效率在某些问题领域比传统种群优化算法(如粒子群算法、禁忌算法等)快几个数量级¨1。因此，有必要深入研究如何将Memetic算法应用在车辆路径问题的求解中，使得种群的个体之间能够通过传递有效的知识经验来提高进化速度并快速适应复杂的求解环境，以此弥补标准种群优化算法的不足，从而大幅提高算法的寻优性能。，本文利用基于Memetic的混合粒子群算法(hybridparticleswa／nloptimizationalgorithm

9、basedonMemetic，HM—PS0)来解决带时间窗的车辆路径问题。a)提出了一种新的实数编码方案，将离散的带时间窗车辆路径问题转换为连续型的优化问题．b)基于拉马克学习策略，融合了禁忌搜索算法，弥补了单一的粒子群算法在解决优化问题时收敛度较慢、易陷于局部最优的缺陷；e)通过两个VR胛w实例的实验结果证明，所提算法在搜索准确度和搜索时间花费方面都具有一定的优势。1带时间窗的车辆路径问题数学模型VRPTW描述⋯为：一个配送中心为n个客户提供服务，配送中心拥有车辆数为m，车辆最大容量为Q，车辆