求解VRP-SDPTW的改进差分进化算法研究

《求解VRP-SDPTW的改进差分进化算法研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、求解VRP・SDPTW的改进差分进化算法研究关键词:摘要：旨在有效整合前向物流与逆向物流，首次提出具有时间窗的同时送货和取货的车辆路径问题(VRP-SDPTW)的混合整数规划数学模型，通过对参数的设定，可以将其转换为其它经典的车辆路径问题。首次提出改进的差分进化算法(IDE)求解该问题，算法采用新颖的序数编码方法，并刈•不可行解设计惩罚机制，当染色体值超过规定的范围时，设计基于整数序规范的辅助算子解决变异问题,差分进化的交叉率随进化代数自动更新。数值实验表明，改进的差分进化算法能快速、有效地求解车辆路径问题，且计算性能优于遗传算法。逆向物流；车辆路径问题；差分进化算法；整数

2、规划；优化ResearchonImprovedDifferentialEvolutionAlgorithmforSolvingVRP-SDPTWAbstract:Thevehicleroutingproblemwithsimultaneousdeliveriesandpickupsandtimewindows(VRP-SDPTW)istheproblemofoptimallyintegratingforward(goodsdistribution)andreverselogistics(returningmaterials)forcostsavingandenvironme

3、ntalprotection.WeconstructedageneralmixedintegerprogrammingmodelofVRP-SDPTW.Themodelcontainedsomeclassicalvehicleroutingproblemsasspecialcases.Weproposedanimproveddifferentialevolutionalgorithm(IDE)forsolvingthisproblem.Inthealgorithm,wefirstlyadoptedthenovelordinalnumbercodingtoconstructa

4、ninitialpopulation,andintroducedapenaltymechanismtopunishtheinfeasiblesolution,thenusedsomeimproveddifferentialevolutionoperatorsunlikeexistingalgorithm,inmutationoperation,weuseanintegerordercriterionbasedonordinalnumbercodingmethod.Inaddition,inthecrossoveroperation,wedesignedaself-adapt

5、ingcrossoverprobabilitythatvariedwithiteration.Wedidsomenumericalexperimentsandcomparedtheperformanceoftheproposedalgorithmwithgeneticalgorithm(GA),theresultsshowedthattheperformanceoftheproposedmethodoutperformedGA.Keywords:reverselogistics;vehicleroutingproblem;improveddifferentialevolut

6、ion(IDE);integerprogramming;optimization1•引言“逆向物流”是物流过程的相反活动，美国物流管理协会对逆向物流的定义为：“计划、实施和控制原材料、屮间库存、终产品从制造、分销或使用点到恢复点或适当处置点的过程”[1]。为了节约成本和保护环境，与逆向物流相关的经典路径问题，如旅行商问题和车辆路径问题必须同时考虑运送货和回收货物两个过程。具有时间窗的同时送货和取货车辆路径问题(VehicleRoutingProblemwithSimultaneousDeliveryandPick-upandTimeWindows,VRP-SDPTW)有效整

7、合了前向物流和逆向物流，是经典车辆路径问题的有效扩展，是NP难组合优化问题。在VRP-SDPTW问题屮，所有送货任务都由车场开始，服务结束时所有的取货量被带冋车场，该问题的一个显著特征时在不违背车辆容量、时间窗口等约束的条件下，每个顾客都同时存在送货和取货服务。逆向物流是该问题出现的一个重要领域，许多国家跟环境保护相关的法律要求公司对其产品的使用和冋收负责，另外公司为了提高售后服务和降低成本也乐意对英产品进行跟踪服务和回收利用；退货所形成的车辆路径问题也是VRP-SDPTW问题的一种形式，VRP-SDPTW在实际配