带有时间窗的车辆路径问题的混合蚁群算法研究

摘要

车辆路径问题(VehicleRoutingProblem，VRP)是近几十年来运筹学、应用数学、网络分析、图论、计算机应用及交通运输等学科研究的一个热点问题，其产生于现实的公路交通运输领域，并在通讯、生产、国防、生物、计算机应用等领域得到了广泛的应用。本文着重研究有时间窗的车辆路径问题(VehicleRoutingProblemwithTimeWindows，VRPTW)，VRPTW现已被证明为NP-hard问题，当问题规模较大时，将很难得到问题的精确解。探讨如何经过少量的计算，得到一个相对满意的解，已成为现阶段学者研究的重点。 蚁群算法是受自然界中真实蚁群觅食行为的启发而提出的一种模拟进化算法，在求解VRPTW等组合优化问题上取得了很好的效果，自蚁群算法提出后，人们又提出了大量蚁群算法的改进算法，其性能和原算法相比，有了明显的改进。 本文研究的主题，就在于提出更好的蚁群算法的改进算法，使求解问题的速度更快、结果更好。主要研究工作如下： (1)以第三方物流配送中心的角度，通过对VRPTW模型的复杂性分析，构建合理的VRPTW数学模型。 (2)通过对目前蚁群算法的分析及实验的测试，概括总结出各种算法的优劣，提出蚁群算法的改进算法-混合蚁群算法，为快速、有效地求解VRPTW开辟了途径，这是本文的核心部分。 (3)通过对混合蚁群算法的分析，利用面向对象的思想实现该算法，采用一系列BenchmarkProblems对算法进行测试，实验结果表明混合蚁群算法在求解VRPTW上是有效的。 本文提出用混合蚁群算法求解VRPTW，有效的缓解了信息传递快速与物流反应缓慢的矛盾，提高了物流配送的科学化效率，对电子商务物流配送的发展具有一定的理论意义与应用价值。