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

论文摘要

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

论文目录

• 中文摘要
• ABSTRACT
• 第一章 绪论
• 1.1 遗传算法的理论与应用简介
• 1.2 弧路径问题及其发展概要
• 1.3 本文所做的工作及安排
• 第二章 遗传算法简介
• 2.1 遗传算法的产生与发展
• 2.2 遗传算法的基础
• 2.2.1 遗传算法的基本原理
• 2.2.2 遗传算法的基本术语
• 2.2.3 遗传算法的基本操作
• 2.2.4 遗传算法的收敛性
• 2.2.5 遗传算法的基本特性
• 2.3 遗传算法的应用
• 第三章 容量约束弧路径问题（CARP）
• 3.1 CARP 问题的定义和描述
• 3.1.1 CARP 问题的定义
• 3.1.2 实际应用中推广的CARP 模型（ECARP）
• 3.1.3 禁止转向，转向处罚，距离矩阵
• 3.1.4 路径的确定和解的基本表示
• 3.2 现有算法
• 3.2.1 三个构造性启发式
• 第四章 求解CARP 问题的遗传算法
• 4.1 算法描述
• 4.1.1 Memetic 算法介绍
• 4.1.2 算法的基本部件
• 4.1.3 算法设置与流程
• 4.2 数值试验
• 4.2.1 测试问题集
• 4.2.2 参数设定以及终止条件
• 4.2.3 计算结果
• 参考文献
• 发表论文和科研情况说明
• 致谢