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

Memetic algorithm for vehicle routing problem with time windows

作　　者：吴雷[1] 魏臻[1] 葛方振[1] 

机构地区：[1]合肥工业大学计算机与信息学院,合肥230009

出　　处：《计算机应用研究》2012年第1期60-62,71,共4页Application Research of Computers

基　　金：国家自然科学基金资助项目(60873195;61070220);高等学校博士学科点专项科研基金资助项目(20090111110002)

摘　　要：提出一种模拟文化进化的Memetic算法求解带时间窗的车辆路径问题。设计了一种实数编码方案,将离散的问题转为连续优化问题。采用邻域搜索帮助具备一定学习能力的个体提高寻优速度;采用禁忌搜索帮助部分个体跳出局部最优点,增强全局寻优性能。实验结果表明,该算法可以更有效地求出优化解,是带时间窗车辆路径问题的一种有效求解算法。This paper proposed a Memetic algorithm,which simulated the process of culture evolution,to solve vehicle routing problem with time windows（VRPTW）.To convert VRPTW into continuous problem,it designed a real coding method.The memetic algorithm helped the particles which had certain learning capacity accelerate convergence rate by local search strategy.Meanwhile,because of helping some particles which fell into the local optimum escape from local optimum by tabu search,it enhanced the diversity of swarm.The experimental result shows that the proposed algorithm can get the solution more effectively and it is an effective method for VRPTW.

关 键 词：带时间窗车辆路径问题 文化基因算法 粒子群算法 禁忌搜索 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]