车辆路径问题的启发式算法研究

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

1、摘要物流配送中的车辆路径问题是运筹学和组合优化领域的研究前沿与热点问题。车辆路径问题是对一系列已知需求量的客户，组织适当的行车线路进行服务，在不违反任何约束条件下，优化路线使得总成本达到最小。有效地解决该问题可以提高车辆的利用率，降低配送成本，提高配送时间的准确率，从而提高物流服务水平。由于车辆路径问题是典型的NP难题，使用传统的优化方法很难得到问题的最优解或满意解，因此构造高质量的启发式算法成为研究该问题的主要发展方向。本文针对有时间窗的车辆路径问题提出了两种求解算法——基于／【．交换的局部下降搜索算法和基于自然数编码

2、的遗传算法。前者是一个两阶段启发式算法，可以有效地获得该问题的可行解。然而局部搜索算法易于陷入局部极小，因此具有一定的全局搜索能力的遗传算法在求解组合优化问题时显示出了优越性。遗传算法是基于“适者生存”的一种高度并行、随机和自适应的优化算法。虽然遗传算法没有传统的优化算法复杂的运行机制，但是遗传算法具有很强的搜索能力，能以很大概率找到问题的全局最优解，并且由于它固有的并行性，能有效地处理大规模的优化问题。因此，与基于^．交换的局部下降搜索算法相比，基于自然数编码的遗传算法可以更好的解决有时间窗的车辆路径问题。本文研究内容

3、的一个重点和难点是集货和送货一体化的车辆路径问题。本文采用了新颖的自然数编码方法，设计了遗传算法对该问题进行求解。在求解过程中，对集送一体化、多种配送车辆类型的问题进行了有效处理，同时考虑了车辆载重量和时间窗等约束。通过求解Solomon提出的标准化有时间窗的车辆路径问题的56个实例，将本文提出的两种启发式算法的求解结果与笔者已知的最优解进行了比较。比较说明本文提出的两种算法可以较好的解决Solomon标准化问题中的部分实例并且具有较好的平均性能。本文还通过实际的北京市劲松地区路网，验证了求解集送一体化的车辆路径问题的遗

4、传算法，实验证明该算法是可行和实用的。关键词车辆路径问题；启发式算法；遗传算法；编码北京工业大学工学硕士学位论文ABSTRACTThevehicleroutingproblem(VRP)inlogisticsisaresearch矗onfierandhotspotproblemofoperationalresearchandcombinatorialoptimizationfield．Inthevehicleroutingproblem．asetofgeographicallydispersedcustomerswitl

5、lknowndemandsaretobeservedbyafleetofvehicles．Theoptimizedroutinesforeachvehiclearescheduledastoachievetheminimaltotalcostwithoutviolatinganyconstraints．SolvingVRPsuccessfullyCanincreasetheutilizationratioofvehicle，reducetheworkingcostsandimproveaccuracyrateofserv

6、icetime．Soitwillenhancelogisticslevel．BecauseVRPisatypicalNP—hardproblem．traditionalalgorithmsarehardtoobtaintheoptimalorsatisfactorysolution．Inviewofit，exploitingtheheuristicsofhighqualityhasbecomethemainresearchingtrend．Thjspaperdescribestwoalgorithmstosolveveh

7、icleroutingproblemwithtimewindows(VRPTW)．Oneislocalsearchdescentmethodbasedon，l-interchange，theotherisgeneticalgorithmbasedonnaturenumbercoding．1’lleformerisatwo—phasedheuristic．AnditCanobtainthefeasiblesolutionofVRPTWeffectively．Howeverthelocalsearchmethodissubj

8、ecttoconvergetolocalminimum，thegeneticalgorithmthathasspecificglobalsearchabilityhasshownsomeadvantagesinsolvingcombinatorialoptimizationproblem．Geneticalgorit