蚁群算法求解MDVRP的设计与实现

论文摘要

多中心车辆路径问题（ MDVRP ）是一个复杂的组合优化问题,其复杂性甚于车辆路径问题（ VRP ）,该问题在现实生活中普遍存在,与人们的生活息息相关。蚁群算法（ ACO ）作为一种比较新的元启发算法,目前在一些路径优化问题上的应用效果卓著,但是关于ACO在MDVRP问题上应用的论述还很少。本论文中针对MDVRP的特征,提出了两种ACO求解MDVRP的算法模型:分治法和综合法。前者是采用分治的求解思路,用分配算法将一个MDVRP分割成几个VRP ,然后用ACO求解VRP ,再将它组合成MDVRP的解,这是一种多蚁群算法。综合法则是另起炉灶,即和其他的用ACO求解的NP-hard问题一样,不需要将问题分割,而将MDVRP作为一个有机的整体来对待,这是一种单蚁群算法。本文在MDVRP标准测试集上进行了测试,两种算法各有特点,分治法在4个测试实例上得到了最优解,综合法在6个测试实例上得到了最优解。对于其余实例,在小规模的测试实例（顾客节点数n≤100）上综合法获得的结果优于分治法,大规模的测试实例（顾客节点数n > 100）上综合法则不如分治法。

论文目录

• 摘要
• Abstract
• 第一章 引言
• 1.1 论文背景
• 1.2 研究的意义
• 1.2.1 研究MDVRP 的意义
• 1.2.2 研究蚁群算法的意义
• 1.3 本文的主要工作
• 1.4 本文的组织结构
• 第二章 MDVRP 概述
• 2.1 VRP 概述
• 2.1.1 引言
• 2.1.2 VRP 类问题的约束条件及分类
• 2.1.3 求解VRP 的基本思路
• 2.2 MDVRP 概述
• 2.2.1 MDVRP 问题描述
• 2.2.2 组合优化问题的一般解决方案
• 2.2.3 精确算法解决MDVRP 的尝试
• 2.2.4 启发式算法解决MDVRP 的尝试
• 2.2.5 ACO 解决VRP 的尝试
• 2.2.6 MDVRP 测试实例库
• 2.3 本章小结
• 第三章 分治法求解MDVRP
• 3.1 引言
• 3.2 分配算法
• 3.3 多蚁群求解MDVRP 算法
• 3.3.1 总体设计
• 3.3.2 信息素的更新
• 3.3.3 独立子蚁群求解VRP
• 3.3.4 局部搜索策略
• 3.4 算法参数调谐
• 3.4.1 参数α的调谐
• 3.4.2 参数β的调谐
• 3.4.3 其他支持
• 3.5 分治法求解MDVRP 的测试结果
• 3.6 小结
• 第四章 综合法求解MDVRP
• 4.1 引言
• 4.2 综合法求解MDVRP
• 4.2.1 解的构造
• 4.2.2 启发信息
• 4.2.3 信息素的更新
• 4.2.4 主要数据结构
• 4.3 综合法求解MDVRP 测试结果
• 4.4 综合法与分治法的对比
• 4.5 小结
• 第五章 总结
• 5.1 已完成工作总结
• 5.2 今后的研究展望
• 参考文献
• 发表文章目录
• 致谢
• 代码说明
• 代码片段