带软时间窗的开放式车辆路径问题研究

《带软时间窗的开放式车辆路径问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、中南大学硕士学位论文带软时间窗的开放式车辆路径问题研究姓名：肖天国申请学位级别：硕士专业：交通运输规划与管理指导教师：符卓20090401硕士学位论文摘要交通运输营运管理和物流配送管理中都要面对这样一个共同的问题：如何为其载运工具(汽车、列车、轮船和飞机，以下统称为车辆)确定行驶路线及其时刻表，才能有效地运送各站点间的旅客和货物。运筹学晃将此类问题统称为车辆路径问题(VRP)。为了便于对VRP进行系统的研究，运筹学界将其分为两大类：闭合式VRP和开放式VRP。当车辆完成运输任务后必须返回原出发点时，称之为闭合式VRP，一般就简称为

2、车辆路径问题；当不要求车辆完成任务后返回原出发点，或者是要求其沿原去程路线返回时，称之为开放式VRP(OVRP)。由于OVRP问题是NP一难问题，所以启发式算法是目前求解OVRP的主流。本文的重点是研究如何应用启发式算法求解开放式车辆路径问题。首先，分析了目前开放式车辆路径问题的研究现状及相应的求解算法，并在此基础上简述了本文重点研究的问题类型——带软时间窗的开放式车辆路径问题(0VRPSTW)。然后，基于经典启发式算法思想设计了求解OVRPSTW的最近邻域搜索算法，构造了邻域的评价函数并进行了算例测试。其次，基于现代启发式算法思

3、想设计了求解OVRPSTW的遗传算法，对遗传算法所必须考虑的关键问题如编码、繁殖和遗传算子等进行了分析。最后，对遗传算法的性能测试和结果比较分析，分别比较了使用不同选择算子、不同交叉算子和不同交叉变异概率后遗传算法的性能，并可从中选取性能较好的排序加最佳个体保留、交叉算子A加单亲遗传算子和自适应交叉变异概率等策略；更进一步，用标准测试算例对算法进行测试，并将遗传算法结果与文献中算法结果和最近邻域搜索算法结果相比较，证明遗传算法求解OVRPSTW具有良好的性能。论文的研究，表明：遗传算法在求解开放式车辆路径问题方面有优良特性，能够使

4、问题得到较优满意解。为针对开放式车辆路径问题相关的实际问题设计更有效的遗传算法奠定了基础。关键词：车辆路径问题，开放式车辆路径问题，软时间窗，最近邻域搜索算法，遗传算法硕士学位论文英文摘要ABSTRACTTransportationoperationsmanagementandlogisticsdeliverymanagementa11facesuchacomlTlOnproblem：howtomakeroutesandtimetablesforthevehicles(trucks，buses，trains，shipsandair

5、planes)thatpassengersandgoodscanbetransportedfromoneplacetoanotherefficiently．Theseproblemsaregenerallyknownasvehicleroutingproblems(VRP、)inthecirclesofoperationsresearch．Forresearchingthe憎systematically,itisdividedintotowkindsbythecirclesofoperationsresearch：Closed卿a

6、ndOpen眦印乃enthevehiclesarerequiredtoreturntothedepotafterfinishedthetransportationassignment，itiscalledClosedⅥRP(ⅥRPingenerally)；whilethevehiclesalenotrequiredtoreturntothedepot，oriftheyarerequiredtodoSObyrevisitingthecustomersassignedtotheminthereverseorder,itiScalled

7、OpenVRP(OVRP)．The0VRPiSanNP-hardproblem．SOHeuristiciSthemain．streamofsolvingOⅥ冲SOfar．ThemaincontentofthisthesisishowtoapplyHeuristictosolveO眦First．itreviewsthepaststudiesonopenvehicleroutingproblemandtheirsolutionalgorithms，focusingonthepresentationoftheopenvehiclerou

8、tingproblemwithtimewindowswhichiSresearchedinthisthesis．Then．theshortestneighborhoodsearchalgorithmiSdesignedforOⅥ冲STWbasedo