同时送取货车辆路径问题算法研究综述.pdf

《同时送取货车辆路径问题算法研究综述.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第30卷第2期2013年2月计算机应用研究ApplicationResearchofComputersVoI．30No．2Feb．2013同时送取货车辆路径问题算法研究综述木王科峰1’2，叶春明1，李永林1(1．上海理工大学管理学院，上海200093；2．河南理工大学能源科学与工程学院，河南焦作454000)摘要：针对同时送取货车辆路径问题的研究算法进行了评述。将该问题的求解方法分为精确算法、构造型启发式、现代启发式以及并行算法四个大类。从算法的原理、性能、适用环境，以及算法之间差异性等方面对各类算法进行了较为全面的介绍。最后，说明了V

2、RPSDP算法研究在节点具有双重需求车辆路径问题理论研究方面的意义，并提出未来VRPSDP算法研究的两个发展方向，即适合多处理器上运行的并行现代启发式算法，以及有效的混合算法如量子行为粒子群算法。关键词：车辆路径问题；同时送取货；精确算法；构造型启发式算法；现代启发式算法；并行算法中图分类号：0221；U116．2文献标志码：A文章编号：1001-3695(2013)02-0334—07doi：10．3969／j．issn．1001-3695．2013．02．004Algorithmreviewofvehicleroutingprobl

3、emwithsimultaneousdeliveryandpickupWANGKe．fen91”，YEChun—min91，LIYong—linl(1．BussinessSchool，UnitersityofShnghaiforScience＆Technology，Shanghai200093，China；2．SchoolofEnergyScience&EngineeringHenanPolytechnicUniversity，JiaozuoHenan4540130，China)Abstract：Thispapergaveareview

4、aboutthealgorithmsforthevehicleroutingproblemwithsimultaneousdeliveryandpickup(VRPSDP)．ItdividedthesolvingmethodsintofoUrmainclasses：exactalgorithm，constructiveheuristicsalgorithm，meta—heuristicsalgorithm，andparallelalgorithm．Italsogavethedetailintroductionsofthealgorith

5、msfromtheprinciple，perform—ance．applicationenvironment，andthedifferencesbetweenthem．Intheend，itintroducedthesignificanceofthealgorithmresearchofVRPSDPinthetheorydevelopmentofthevehicleroutingproblemwithnodehavingdoubledemands．Afterthat．itproposedtworesearchdirectionsinth

6、efuture．whichwereparallelmetaheuristicsbasedonmultipleprocessors．andtheeffec．tivehybridalgorithmsuchasquantum．behavedparticleswamioptimization．Keywords：vehiclemutingproblem；simultaneousdeliveryandpickup；exactalgorithm；constructiveheuristicalgorithm；moydemmetaheuristicsal

7、gorithm：parallelalgorithm0引言随着人们对环境问题给予越来越多的关注，关于要求私营企业保护环境的法律条文相继地增加，而减少废物的排放量和能源的消耗成为相关法律规定的两个主要内容。由于能源消耗直接关系到企业成本，所以一直受到企业界的重视。随着新的法律法规的制定，以及人们社会责任感的增强，也使得废物的排放问题逐渐成为人们关注的焦点。为了尽量减少废弃物的排放，使用过的商品在它们生命周期结束的时候可以被部分或全部回收、拆卸、组装得以重新使用。此外，包装和装载设备也可以再循环使用。许多国家已经就原材料的再循环率、产品包装的

8、回收，甚至产品全部生命周期(包括义务进行产品使用期结束后的回收)，对工业界提出一系列强制性的要求。所有这些活动导致了原材料从终端客户回溯到上游供应链的流动。如果将正向和逆向物流分开考虑，对于每一个方向，是一