基于蚁群算法的车辆路径问题的研究

《基于蚁群算法的车辆路径问题的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于蚁群算法的车辆路径问题的研究摘要随着我国经济的迅速发展和信息技术的进步，物流行业已经被确定为我国国民经济的重要产业和经济发展的新增长点，其中物流配送路径的优化是物流系统中的关键一环，选择合理经济的配送路线可以极大的降低配送成本，提高配送效率，增加企业的经济效益。本文以如何科学的解决配送路径的优化问题为出发点，分析比较了各种算法在解决VRP中的特点与利弊，由于蚁群算法有着良好的正反馈机制与较强的鲁棒性和灵活性，本文选择了蚁群算法作为解决VRP问题的算法，并结合VRP问题本身的特点，针对蚁群算法存在的过早收敛等不足进行改进，最后将改进的蚁群算法应用在本文所建立的

2、VRP模型中，并通过仿真试验，证明了蚁群算法在解决大规模动态VRP问题中的有效性和可行性。论文主要研究工作和创新性成果有以下几个方面：(1)设定了一类配送点位置不变，需求时间不定的动态带软时间窗的VRP问题。利用时间段的概念，将动态VRP问题转化为连续时间段内的静态VRP问题进行研究，构造了该问题的模型，提出了动态VRP问题的求解方案。(2)结合VRP问题的特点，针对蚁群算法的早熟等不足，对蚁群算法进行改进，通过对伪随机概率公式的改进，配送点的二次选择机制，局部参数优化的方式，提高了蚁群算法的运算效率，并应用于本文VRP问题的解决中。(3)在Matlab上选定S

3、olomonBenchmarkproblems数据集中的数据进行仿真试验。首先对时间段内的静态VRP问题进行试验，将实验结果与其他算法结果进行比较，证明了算法在解决时间窗内静态VRP问题的收敛性和有效性。随后对整个动态VRP问题进行试验，通过对SolomonBenchmarkproblems中rcl01问题的求解，证明在合理选择时间段的情况下，该算法能有效地解决配送数目较多的动态带时间窗的VRP问题。关键词：车辆路径问题，蚁群算法，时间窗，Solomonbenchmark问题ResearchonVehicleRoutingProblembasedOilAntCo

4、lonySystemAbrstractWiththerapiddevelopmentineconomyandadvancementininformationtechnologyinChina，thelogisticsindustryasaneweconomicgrowthpointisanimportantpartinnationaleconomy．TheVehicleRoutingProblemoptimizationwhichdirectlyrelatestotheeconomicbenefitsinmodernlogisticsservicecanredu

5、cecosts．improvedistributionefficiencyandincreasetheincomeofcompany．StartingwithhowtosolvetheVehicleRoutingProblemscientifically，thispaperanalysesandcomparesdifferencesamongvariousalgorithms，forgoodpositivefeedbackmechanismandstrongrobustnessandflexibility,theAntColonySystemiSchosen，t

6、henwiththecharactersofVRP,asolvingstrategy，basedontheAntColonySystem，isproposed．TheimprovedalgorithmhasbeentestedontheMatlab。Theresultsshowthattheimprovedalgorithmcanbeeffectivelyusedinlarge-scalevehicleroutingproblems．Themaincreativeworksandachievementsinthispaperareasfollows：(1)ADy

7、namicVehicleRoutingProblemwithtimewindowsisexamined，in(2)(3)whichthelocationsofcustomersareknown，buttheservicetimearechanging．Atimeparameterhasbeensettodealwiththedynamicproblem，andamodelstructurehasbeenproposedforsolving．WiththecharactersofVRP,aimingattheshortness，byimprovingthepseu

8、dorandomprob