详情

原文传递求解弧路径问题的遗传算法研究

论文题名：	求解弧路径问题的遗传算法研究
关键词：	车辆弧路径问题;memetic算法;局部搜索;遗传算法;交通运输服务系统
摘要：	车辆弧路径问题产生于现实生活中的交通运输服务系统，有着广泛的应用，近年来逐渐成为研究的热点。由于它是NP-难问题，精确算法的求解时间呈指数增长，因此无法处理大规模的问题，而现有的启发式算法虽然求解时间较短，但往往存在解质量效率低下的缺点。随着遗传算法的发展，它已被应用到这一问题的求解。已有结果表明，遗传算法可以很好地兼顾运算效率和解质量效率这两方面的要求，在解决车辆弧路径问题上具有很好的发展前途。本文在广泛深入地查阅国内外文献的基础上，对遗传算法的基础理论和方法进行了深入的理论研究，并应用遗传算法对车辆弧路径问题进行了实验分析，主要内容如下： 1.系统、详尽的介绍了遗传算法的一般流程和基本理论、方法。 2.简要介绍了弧路径问题及其起源和发展历史，归纳总结了其求解方法。在现有的算法基础上，提出了一种新的遗传算法来解决以车辆服务成本为目标的弧路径问题。新算法采用了改进的局部搜索技术，并对现有算法的其他部件做了一些调整。通过对多个实例的计算证明了该算法对大多数问题具有更好的效果。
作者：	郑仲民
专业：	运筹学与控制论
导师：	林丹
授予学位：	硕士
授予学位单位：	天津大学
学位年度：	2008
正文语种：	中文