原文传递
用多种群自适应混合遗传算法求解车辆路径问题
| 论文题名： | 用多种群自适应混合遗传算法求解车辆路径问题 |
| 关键词： | 遗传算法;车辆路径问题;好坏种群;精英种群;二次遗传 |
| 摘要： | 人工智能(Artificial Intelligence)一直以来是计算机科学中的重要的研究方向,而智能规划(Intelligent Planning)领域又是人工智能研究中的重要分支.智能规划研究的是如何利用计算机高速度高性能的计算来优化规划问题中经常出现的冗余现象,由此节约大量的人力和物力.在智能规划领域中存在的一个重要问题是车辆路径问题(Vehicle Routing Problems,VRP),即研究如何利用有限的运输资源来完成一定量的运输任务,并且使得运输成本最低.如果在此基础上加上时间窗的限制,问题就演变成了有时间窗的车辆路径问题(Vehicle RoutingProblems with Time Windows,VRPTW).有时间窗的车辆路径问题由于其巨大的经济效益,所以从它被提出以来一直就是计算机学者和管理者研究的重要课题,并且在过去的40多年间得到了突飞猛进的发展.各种方法,包括:线性规划方法、非线性规划方法、动态规划方法、组合优化方法、启发式方法、分枝界定法、爬山法、贪婪法等,都被应用于问题的求解,并且取得了不错的求解效果.然而,以往的这些方法都不可避免地存在各自的缺点,例如求解时间过长,容易陷入局部最优,系统资源消耗过大等.该文在以往方法研究的基础上,对传统的遗传算法进行改进,提出了多种群自适应混合遗传算法(Multiplepopulation AdaptiveHybrid Genetic Algorithms),并设计开发出了基于改进遗传算法的有时间窗的车辆路径问题求解系统.实验结果表明,经过改进的遗传算法比一般算法收敛速度更快,求解质量更为优良. |
| 作者： | 曹亮 |
| 专业： | 计算机软件与理论 |
| 导师： | 姜云飞 |
| 授予学位： | 硕士 |
| 授予学位单位： | 中山大学 |
| 学位年度： | 2004 |
| 正文语种： | 中文 |
检索历史
应用推荐
