论文部分内容阅读
车辆路径问题(Vehicle Routing Problem，VRP)是近年来交通运输、管理科学、运筹学、图论、网络分析等学科研究的热点问题之一，在现实中有着广泛的应用，例如公交线路、物流配送、网络路由等等。研究此类问题具有很强的现实意义。本文着重研究带能力约束的车辆路径问题(Capability—constrained Vehicle Routing Problem，CVRP)，CVRP是在基本VRP上添加能力约束条件后的一种变化形式，是更为复杂和特殊的问题。VRP已被证明是NP—hard组合优化问题，当问题规模较大时，很难得到问题的精确解。如何设计有效的算法，从而在较短的计算时间快速获得较好的解，成为现阶段研究的重点。
蚁群算法是受自然界中蚂蚁觅食行为的启发而发展起来的一种元启发式优化算法，是一种本质并行的算法，全局搜索能力强。蚂蚁之间通过信息交流加速了进化过程，利用了正反馈原理和学习机制，具有较强的搜索能力，近年来改进蚁群算法在在二次分配(QAP)、网络路由、车间调度(JSP)、车辆路径(VRP)等组合优化问题得到广泛应用。
本文基于蚁群算法对车辆路径问题进行系统研究，主要工作如下：
首先，介绍VRP问题国内外研究现状，在对VRP问题从构成要素、分类和界定几个方面做概述的基础上，深入探讨了VRP问题的理论框架：包括从TSP问题到VRP问题的描述及模型建立，并对求解VRP问题的精确算法、传统启发式算法和元启发式算法进行分析和总结。
然后，介绍蚁群算法的基本原理，分析归纳蚁群算法的主要特点，并对蚁群算法近年来的发展变化做简要总结，最后对蚁群算法在组合优化领域的应用情况，尤其在VRP问题上的应用情况进行概述。
最后，基于对VRP问题的研究，结合物流配送中的实际情况，建立带能力约束车辆路径问题(CVRP)数学规划模型。并在基本蚁群算法(Ant Algorithm)的基础上，设计出求解CVRP问题的简易蚁群算法(BA)和三个逐步改进的蚁群算法(AA1，AA2，AA3)，经过编程调试和反复实验仿真，上述算法在求解中小规模CVRP问题上效果令人满意，在较大规模的CVRP问题的快速求解上获得成功，实验结果表明，本文所设计的算法是有效的，具有较快的收敛速度，解的全局性也较好。