蚁群算法在有时间窗的VRP问题中的应用分析

《蚁群算法在有时间窗的VRP问题中的应用分析》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、首都经济贸易大学硕士学位论文《蚁群算法在有时间窗的VRP问题中的应用研究》摘要随着市场竞争的日益加剧，世界经济一体化的加强，物流运输已经成为企业提高市场竞争力和核心竞争力的重要手段。其中物流配送的车辆路径优化问题(VRP)涉及面较广，需要考虑的因素较多，对企业提高服务质量、降低物流成本、增加经济效益的影响较大，因而是一个亟待解决的重要问题。特别是随着Internet的普及和电子商务的发展，传统VRP算法已无法应付快速回应(QuickResponse)顾客需求对物流配送提出的要求，于是时间窗的概念应运而生。带有时间窗的车辆调度问题是比VRP复杂程度更高的NP

2、难题，以往的求解方法可以分为精确算法和启发式方法。精确算法由于引入严格的数学方法，无法避开指数爆炸问题，只能有效求解小规模的VRPTW问题。由于VRPTW问题是强NP难题，只能寻找近似算法。为此，人们把主要精力花在构造高质量的启发式算法上。在这些启发式算法中，蚁群算法因其很强的鲁棒性、分布式计算和比较容易与其他算法工具相结合的优点越来越受到人们的关注。然而，蚁群算法在求解大规模问题时，存在搜索空间和时间性能上的矛盾，易出现过早收敛于非全局最优解以及计算时间过长的弱点。另外，算法参数的选择多凭借经验。针对这些弱点，本文在前人工作的基础上，开展了关于改进型蚁群

3、算法在VRPTW中的研究，经仿真实验证明改进后的算法较原算法更合理有效。并针对国内运输调度系统的空白，设计和分析了基于多种业务模型的运输调度优化系统。主要研究工作如下：1、通过一系列的仿真实验，对蚁群算法参数的合理选取进行了较为深入的研究，提出了最优算法参数组合。较于以前完全凭经验和试探来选取参数，大大提高了效率。2、将蚁群算法应用于VRPTW问题的求解，通过引入匀称度、启发路径数以及吸引力等概念对算法的转移策略和更新策略进行改进，构造了具有动态调整功能的蚁群算法。实验仿真结果表明所设计的算法具有较强的搜索能力，计算效率较高，能够有效地解决加速收敛与停滞现

4、象之间的矛盾。3、在分析多种物流配送运输调度业务的基础上，分析和设计了针对多种业务需求的手工处理和计算机处理相结合的运输调度系统。具有实践意义。关键词：带时间窗口的车辆路径问题蚁群算法启发路径数I首都经济贸易大学硕士学位论文《蚁群算法在有时间窗的VRP问题中的应用研究》AbstractAstheintensifyofmarketincreasinglyandtheenhanceofglobalecnomics，logistics becameanimportantmeasureforenterpnsestopromotethepowerofmarketan

5、dcore competition．ThereintoVehicleRoutingProblem(VRP)oflogisticsdistributioninfluence onservicequality，logisticscostandbenifitofenterprise．soit’sanimportantproblemto solvetheproblem.Inparticular，asprevalenceofInternetanddevelopmentofelectronic commerce，Itisimpossibletousetradition

6、alVRParithmetictodealwithquickresponseof logisticdivitionforcustomer，uponthattheconceptottimewindowsemergeasthetimes require．VehicleRoutingProblemwithTimeWindows(VRPTW)isanNP-hardcomplete optimizationproblem，whichmorecomplexthanVehicleRoutingProblem．Thesolution methodwasdividedtop

7、recisonalgorithmandheuristicalgorithm．Precisonalgorithm can’tkeepawayfromexponentblastproblembeacauseofit’sstrictmathematicsmethod andcansolvebrushfireVRPTWonly．InvirtueofVRPTWisaNP-completeproblem， wecanfindapproximationalgorithmonly．Thereformostpeoplespenttimeto conformationofhe

8、uristicalgorithmwithhighquality．A