蚁群算法在车辆路径问题中的应用研究

论文摘要

车辆路径问题是组合优化和物流领域研究的热点问题。车辆路径问题的搜索空间随着客户点和约束条件的增加而增大,基于基本车辆路径问题的框架,在庞大的空间中寻找最优解,需要大量的求解时间,因此,研究一种求解时间短且能得到质量较高的近似解的算法,对解决此类问题来说,是具有理论意义和现实价值的。蚁群算法是受大自然中蚂蚁觅食启发而产生的一种智能仿生算法,具有简单通用、鲁棒性强,正反馈机制,适合分布处理等特点,因此借助蚁群算法解决车辆路径问题具有重要的意义。本文通过对国内外相关文献进行分析、总结和提炼,对车辆路径问题的起源、发展、研究应用的价值以及各种解决此问题的研究现状进行了综述,阐明了论文研究的背景及意义。通过对几种改进的蚁群算法的介绍,编写解决旅行商问题的程序代码,并运算比较其结果,深入了解几种蚁群模型以及蚁群算法数学模型中参数对算法性能的影响。对于MMAS算法,选择改进后的状态转移策略和信息素更新策略,设计改进的蚁群算法解决车辆路径问题的方法。针对车辆路径问题和带有时间窗的车辆路径问题,基于改进的蚁群算法采取不同的和优化方式,克服蚁群算法在大规模问题中易陷入局部极值的缺陷。分别求解已有文献中的20个配送点和Solomon提供的标准测试问题,并运算后将得到结果进行对比,证明改进的蚁群算法均可得到较优的解。

论文目录

• 摘要
• Abstract
• 1 绪论
• 1.1 课题背景及意义
• 1.2 课题的研究现状
• 1.3 论文的主要内容
• 1.4 论文结构
• 2 基本蚁群算法
• 2.1 蚁群行为描述
• 2.2 蚁群优化的特点
• 2.3 基本蚁群算法的数学模型
• 2.4 基本蚁群算法的实现步骤
• 3 蚁群算法中的参数设置
• 3.1 参数对算法性能影响的实验
• 3.1.1 信息素残留因子对蚁群算法性能的影响
• 3.1.2 信息启发因子蚁群算法性能的影响
• 3.1.3 期望启发式因子蚁群算法性能的影响
• 3.2 α、β、ρ组合配置对蚁群算法性能的影响
• 4 现有几种改进蚁群算法的介绍
• 4.1 一种自适应蚁群算法
• 4.2 最大最小蚁群算法
• 4.3 实验数据对比
• 5 蚁群算法求解车辆路径问题
• 5.1 车辆路径问题
• 5.1.1 VRP问题与TSP问题的区别
• 5.1.2 VRP问题的数学描述
• 5.2 带时间窗的车辆路径问题
• 5.2.1 VRPTW问题的描述
• 5.2.2 VRPTW问题的数学描述
• 5.3 改进的MMAS在车辆路径问题中的应用
• 5.3.1 求解VRP问题的算法设计
• 5.3.2 求解VRPTW问题的算法设计
• 5.4 数值实验及结果分析
• 5.4.1 VRP实验及结果分析
• 5.4.2 VRPTW问题实验及结果分析
• 6 总结与展望
• 致谢
• 参考文献