1.车辆路径规划的连续多目标优化模型设计及其求解方法.pdf

《1.车辆路径规划的连续多目标优化模型设计及其求解方法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、摘要车辆路径规划问题(VRP)是物流配送过程中的关键问题之一，对车辆路径规划问题的研究尤其是对带时间窗的车辆路径规划问题(VReTW)的研究，有助于提高物流经济效益，实现物流科学化。带时间窗的车辆路径规划问题是组合优化问题中的带多个约束条件的NP．完全问题，早期作为单目标优化问题被广泛研究。近年来，随着进化多目标优化算法的发展，许多研究者开始使用进化多目标优化的方法对该问题进行多目标优化，在优化目标方面则普遍采用了传统的车辆数和总行车距离两个目标建立优化模型。然而，有研究表明，车辆数和总行车距离两个目标之问冲突性并不强，并且车辆数为离散目标函数，因此目前基于车辆数．总行车距离模型的多目标优

2、化算法均未能得到包含丰富非支配解的代表性Pareto前端。另外，单纯的进化优化方法在求解组合优化问题时也存在效率不高，收敛慢的问题。本文基于当前研究现状的不足，提出了一种新颖的连续多目标优化模型，并且将LK启发式局部搜索同非支配领域免疫算法(NNIA)：十fl结合设计了求解该模型的新的Memetic算法。本文的主要工作有：(1)针对带时间窗的车辆路径优化问题，建立了服务质量一服务代价两目标车辆路径优化模型MOM．CQ(ContinuousMulti．objectiveVehicleRoutingModelBasedOnServiceCostandQuality)，具体又包括严格考虑约束的M

3、OM．CQC和将约束转化为目标函数的MOM—CQUC两个模型，通过车辆到达时间的早晚衡量服务质量，建立服务质量目标函数，沿用车辆总行驶距离衡量服务代价。两种模型目标函数均为连续目标函数，通过构造求解VRPTW的NNIA算法对两个模型进行了求解，实验结果表明MOM．CQC模型具有普遍强烈的冲突性，非常适合连续多目标优化并且较MOM—CQUC模型适用性更强。(2)针对提出的MOM．CQC模型，利用车辆路径优化问题同旅行商问题天然的相似性，在NNIA的框架下引入Lin—Kemighan(LK)启发式搜索算法，并重新设计了已有的进化算子，构造了密母免疫多目标车辆路径优化算法(MIA)。算法对优势种

4、群使用LK作局部搜索，提高了优势种群的质量，加快了算法收敛速度，克服了NNIA稳定性不足的缺点，并且提升了算法最终得到的解的路径质量，提高了算法最终得到的Pareto前端收敛程度。关键词：车辆路径规划多目标优化连续优化模型局部搜索密母算法AbstractVehicleRoutingProblem(VRP)isoneofthekeyissuesinlogisticsdistribution，theresearchofoptimizationforVRPespeciallyforVRPwithtimewindows(vRPTW)callnotonlyhelptoincreasetheprofi

5、tsoflogisticseconomic，butalsohelptoachievemorescientificlogistics．Incombinatorialoptimization．theclassicVRPTWisaNP-Completeproblemprovidedwithmanyconstraintsandithasbeenresearchedextensivelyasasingle—objectiveoptimizationprobleminearlyyears．Inlater，withthedevelopmentofmulti-objectiveevolutionaryop

6、timizationalgorithm(MOEA)，manyresearchersbegintoregardVRPasamulti—objectiveoptimizationproblemanduseMOEAstooptimizeit．Mostoftheseresearchersadopttraditionalobjectivesofvehiclenumberandtotaltraveldistancetoformthemulti—objectiveoptimizationmodel，butrecentstudieshaveindicatethattheconflictrelationsh

7、ipbetweenthesetwoobjectivesispoor．Additionally，theobjectiveofvehiclenumberisadiscretevariablewhiletraveldistanceiscontinuous，theseabovemakesMOEAsbasedonthismodelcannotobtainedarepresentativeParetofrontwithrichsol