多车型弧路径优化问题（MVCARP）研究

论文摘要

带容量限制的弧路径优化问题（CARP）在日常生活中的应用是非常普遍的,有效的解决CARP问题并将其投入实际的应用对于节约经济成本,提高社会生产效率有着非常重大的意义。尽管该项研究课题在过去的20多年时间里在国际上引起了众多域专家学者们的重视,并提出了许多富有成效的解决方案,但是总体上看,CARP的研究相对于我们通常所熟悉的VRP的研究仍然显得还不够全面,从现有已经发表的一些文献中搜集到的解决CARP问题的方法大多数存在比较大的改进空间。而对于应用中比较常见的多车型CARP问题（MVCARP）,作者还没有搜集到的非常有成效的解决方案。因此,在本篇论文中作者对CARP和MV-CARP的理论进行了深入研究,并提出一种高效的解决CARP问题及其扩展问题MVCARP问题的算法。CARP问题是NP难题,用普通的精确算法很难求得实用的解,因此有效的解决方法一般都是以启发式算法思想为基础。由于遗传算法具有良好的全局收敛性,并且在求解组合优化问题上有着优良的效果,因此作者在本文中将主要以遗传算法为工具来对CARP问题进行研究。本文对CARP问题研究的主要贡献有如下几个方面:①在对传统CARP问题的数学模型进行研究和分析的基础上,补充提出了多车型CARP问题的数学模型。②对现有解决CARP问题的算法中比较流行的Memetic Algorithm算法（MA）进行了细致的研究,分析了MA算法中的几个主要算法过程的时间复杂度及其对算法执行效率的影响,并指出了该算法无力解决多车型CARP问题的主要原因。③通过将传统遗传算法（TGA）与单亲遗传算法（PGA）进行结合,并对遗传算法的种群结构以及进化算子进行改进设计,进而提出了一种不但可以有效求解多车型CARP问题,同时在求解普通单车型CARP问题上也具有更加出色的运算速度的混合遗传算法。④为多车型CARP问题的研究提供了四组不同规模的测试数据集。在该四组数据集上对本文算法在求解多车型CARP问题时的有效性进行测试,取得了良好的效果。在国际上流行的三个公共测试集上对本文算法在求解普通单车型CARP问题的性能进行与Memetic Algorithm等已有算法的对比测试,从而验证了本文算法的高效性。本文研究的主要目的在于解决应用中常见的多车型CARP问题,同时针对于现有求解CARP问题的算法在运行过程中可能存在的一些缺陷,在不影响新算法求解质量的前提下对其进行避免,从而为CARP问题的求解提供另外一种更通用、更高效的求解方案。

论文目录

• 摘要
• ABSTRACT
• 1 绪论
• 1.1 研究背景及研究意义
• 1.2 国内外研究现状
• 1.3 遗传算法简介
• 1.4 论文所做工作及结构介绍
• 1.5 本章小结
• 2 研究内容以及MVCARP 数学模型
• 2.1 CARP 问题的研究内容
• 2.2 MVCARP 问题的数学模型
• 2.2.1 基本CARP 问题模型
• 2.2.2 多车型扩展CARP 问题
• 2.3 CARP 问题的网络模型
• 2.4 本章小结
• 3 MEMETIC ALGORITHM 研究与分析
• 3.1 MEMETIC ALGORITHM 算法简介
• 3.2 MA 算法的基本结构
• 3.3 MA 算法的性能分析
• 3.4 本章小结
• 4 求解MVCARP 的遗传算法设计
• 4.1 染色体编码设计
• 4.2 种群结构设计与初始化
• 4.2.1 遗传算法种群结构的设计
• 4.2.2 种群的初始化
• 4.3 遗传算法进化算子设计
• 4.3.1 选择算子
• 4.3.2 染色体基因重组算子
• 4.3.3 局部搜索（local search）
• 4.3.4 染色体替换
• 4.4 HEGA 算法主要执行流程
• 4.5 提高算法稳定性的重优化措施
• 4.6 本章小结
• 5 算法有效性测试
• 5.1 软件测试环境介绍
• 5.2 软件测试系统功能模块介绍
• 5.3 求解MVCARP 的实验
• 5.3.1 MVCARP 实验采用的实验数据集
• 5.3.2 MVCARP 实验结果与分析
• 5.4 求解单车型CARP 的实验
• 5.4.1 单车型CARP 实验采用的公共测试数据集
• 5.4.2 单车型CARP 实验结果分析
• 5.5 本章小结
• 6 总结与展望
• 6.1 研究总结
• 6.2 展望
• 致谢
• 参考文献
• 附录