毕业设计(论文)外文资料翻译系（院）：计算科学系专业：信息与计算科学姓名：学号：外文出处：LectureNotesinComputerScience5370,198-205(2008)(用外文写)AHybridAlgorithmforVehicleRoutingProblemwithTimeWindows附件：1.外文资料翻译译文；2.外文原文。
        指导教师评语：签名：2012年3月日附件1：外文资料翻译译文混合算法求解有时间窗车辆路径问题摘要：有时间窗车辆路径问题（VRPTW）是近年来一个引起相当大的注意的众所周知的复杂的组合问题。
    约束条件，但我们需要一个优越初始解，所以我们通过随机PFIH构造初步解决方案。鉴于为特点VRPTW问题，重新移动和重新插入过程如下所述。在这里，集合A是目前解决方案，c是将被从A删除客户，集合R是从A中删除客户，p是被删除客户数量，当P客户已经从A免去时，我们使用集合B表示部分解决方案。R中第一个少部分元素是从A中随意删除客户Z，从A其余客户中选出第二部分是和客户Z最大相关，根据与集合R关联性选择其余.每次被删除客户和集合R最大相关.上述程序将重复p-次，直到所有必需客户被选择，我们使用简单关联函数r,ij表示任何两个客户i和j之间关联，,RiR表示任何顾客i和R之间关联：r(i,j)=/(t'+v)ijij（）R,,jRiRrij（）其中'/max,ijijijijtttv如果i和j均由同一车辆，否则为；ijt是从i到j（本文行驶距离）时间。为了寻找一个新优顾客服务车辆必须在li之前到达。如果它在ei之前到达，它应等待为iw。那么基本上，VRPTW问题研究对象是为参加了各车队客户车辆，要找到一最值点,以减少总行程距离，或最大限度地减少所使用车辆数目。我们例子是根据所罗门[]中定义模型。minNNNijijkijkck()NNijkjikjjxx,,,,ikK()KNkjxijk,,,,ijn()NNiijkijqxq,,,kK()KNijkiiijijkixbstwb,,,jn()iiiieawliN()这里iS：为客户i服务时间；iq：客户i需求；ijt：i和j之间直接行驶时间；ijc：从客户i到客户j路程所需消费；ia：到达客户i时间；ib：开始服务客户i时间。如果车辆k直接从i行驶到j，ijkx，否则，ijkx，ij，jC。以尽量减少车辆行驶总成本：（）车辆承受能力，旅行时间和到达时间可行性约束。（）确保每辆车从节点和节点n+结束开始。此外，每个客户能而且只能由一辆车送达。（）在同一时间，车辆k服务客户所有需求，不能超过车辆k最大容量。（）表达式（）-（）为定义时间窗口。．一个混合动力系统VRPTW问题这项工作旨在构建一个混合动力系统基础上，结合模拟退火和大邻居搜索策略。为建设卓越初始SA算法解决方案，这项工作使用随机PFIH。读者可参考马吕斯所罗门[]PFIH算法细节。初步解决方案建立初始路线，并提议在[]中使用随机PFIH。这样能产生快速多元化解决方案。原PFIH[]是确定性，但不同是，它用随机选择PFIH来定义第一个客户为每个新路线。这是必要，可以产生多样初始解。产生新解决方案过程新解决方案过程原理是largeneighborsearch（LNS）改善，这是由PawlShaw（）提出建议。它从最初解决方案开始，根据不断重新移动和重返社会进程找到最佳解决方案。虽然LNS具有竞争力搜索技术中问题有复杂约束条件，但我们需要一个优越初始解，所以我们通过随机PFIH构造初步解决方案。鉴于为特点VRPTW问题，重新移动和重新插入过程如下所述。在这里，集合A是目前解决方案，c是将被从A删除客户，集合R是从A中删除客户，p是被删除客户数量，当P客户已经从A免去时，我们使用集合B表示部分解决方案。R中第一个少部分元素是从A中随意删除客户Z，从A其余客户中选出第二部分是和客户Z最大相关，根据与集合R关联性选择其余.每次被删除客户和集合R最大相关.上述程序将重复p-次，直到所有必需客户被选择，我们使用简单关联函数r,ij表示任何两个客户i和j之间关联，,RiR表示任何顾客i和R之间关联：r(i,j)=/(t'+v)ijij（）R,,jRiRrij（）其中'/max,ijijijijtttv如果i和j均由同一车辆，否则为；ijt是从i到j（本文行驶距离）时间。为了寻找一个新优间，提出了回归迭代策略。它可以使总等待时间为零。实验结果表明，该算法大大提高解决方案质量。与以往方法相比，它也为今后工作探索表明了方向，为其他本地操作者成立元启发式。参考文献.Alvarenga,G.B.,Mateus,G.R.:HierarchicalTournamentSelectionGeneticAlgorithmforthevehicleRoutingProblemwithTimeWindows.In:HIS,FourthInternationalConference,pp.–().Solomon,M.M.:Algorithmsforthevehicleroutingandschedulingproblemswithtimewindowconstraints.OperationsResearch(),–().Oliveira,H.C.B.,Vasconcelos,G.C.,Alvarenga,G.B.:Reducingtraveleddistanceinthevehicleroutingproblemwithtimewindowsusingamulti-startsimulatedannealing.In:IJCNN,pp.–,July-().Alvarenga,G.B.,Mateus,G.R.:Atwo-phasegeneticandsetpartitioningapproachforthevehicleroutingproblemwithtimewindows.In:Proc.thInternationalConferenceonHybridIntelligentSystems,pp.–().Lim,A.,Zhang,X.:Atwo-stageheuristicforthevehicleroutingproblemwithtimewindowsandalimitednumberofvehicles.In:ProceedingsofthethAnnualHawaiiInternationalConferenceonSystemSciences(HICSS),p.c().http://web.cba.neu.edu/~msolomon/problems.htm().Shaw,P.:UsingconstraintProgrammingandlocalsearchmethodstosolvevehicleroutingproblems.In:ProceedingofthethInternationalConferenceonPrincipleandpracticeofConstrantProgramming,pp.–()附录每一辆车在每一个客户出发最佳时机车辆:.....车辆:....车辆:...........车辆:............车辆:.......车辆:......车辆:.......车辆:.........车辆:..车辆:......顾客服务车辆必须在li之前到达。如果它在ei之前到达，它应等待为iw。那么基本上，VRPTW问题研究对象是为参加了各车队客户车辆，要找到一最值点,以减少总行程距离，或最大限度地减少所使用车辆数目。我们例子是根据所罗门[]中定义模型。minNNNijijkijkck()NNijkjikjjxx,,,,ikK()KNkjxijk,,,,ijn()NNiijkijqxq,,,kK()KNijkiiijijkixbstwb,,,jn()iiiieawliN()这里iS：为客户i服务时间；iq：客户i需求；ijt：i和j之间直接行驶时间；ijc：从客户i到客户j路程所需消费；ia：到达客户i时间；ib：开始服务客户i时间。如果车辆k直接从i行驶到j，ijkx，否则，ijkx，ij，jC毕业设计(论文)外文资料翻译系（院）：计算科学系专业：信息与计算科学姓名：学号：外文出处：LectureNotesinComputerScience,-()(用外文写)AHybridAlgorithmforVehicleRoutingProblemwithTimeWindows附件：.外文资料翻译译文；.外文原文。指导教师评语：签名：年月日附件：外文资料翻译译文混合算法求解有时间窗车辆路径问题摘要：有时间窗车辆路径问题（VRPTW）是近年来一个引起相当大注意众所周知复杂组合问题。组合优化这类问题是NP困难问题，最好是用近最优化启发式解决。在这里，我们提出了VRPTW问题两阶段优化策略。首先，为建设一个好初始解，我们使用随机PFIH，保证初步解决方案多样性。然后提出优化一个基于SA和LNS组合混合动力系统初始解。其次，用回归迭代策略调整时间窗口为客户提出并找出每个车辆离去最佳时间。它可以使总等待时间为零。这项测试工作是在所罗门有时间窗车辆路径问题中C-型情况下执行。实验表明，我们算法可以快速有效地解决有时间窗车辆路径问题。关键词：随机PFIH，迭代策略..介绍：车辆路径问题（VRP）是一个通用名称，简称为一类为客户服务车辆数目组合问题。这是许多物流系统一个重要元素。有时间窗车辆路径问题（VRPTW问题）是一种约束VRP版本，其中每个顾客服务必须在指定时间窗口内送达。VRPTW问题实例经常发生许多行业，如快餐交付，产品交付，邮递，校车路线等。略有改善解决方案甚至可能会节省大量成本。因此，VRPTW问题在于管理科学，物流管理日益增长兴趣和计算机科学。然而，时间窗车辆调度问题是NP-hard。因此，目前研究这个问题需尝试运用启发式技术，以获得局部最优最理想解决方案来解决问题。在这些启发式，混合方法是常用。OliverivaH.C.B.[]提出了一种在模拟退火和随机启动（启动）爬一座小山战略相结合基础上不同方法。Alvarenga.G.B.[]提出了一个使用高效遗传算法和一组分区制定强大启发式方法。Andrew.L[]提出了m-VRPTW问题两阶段算法，首先最大化一个弹射池服务客户数量来拥有临时服务器提供服务客户，然后使用经典多启动迭代爬坡算法包括广义弹射链来最小化总行程距离。在我们论文中，我们首先构建初始随机PFIH解决方案，然后使用结合模拟退火和大邻居搜索策略混合算法。最后，回归迭代战略提出了为客户调整时间窗口，并找出每辆车出发最佳时间，这样可以使总等待时间为零。.论文提交程序：在VRPTW问题中，每一位顾客i,iC={,,...,n}有一个给定需求qi。我们目是，用这样一种方法为每部车辆找到路径：（）每个在C顾客在其服务时间被拜访一次；（）所有线路在节点开始,在节点n+,N={,,...,n+}结束；（）每个线路上客户需求总合不能超过车辆流量q，所有车辆都属于同一类型，并有同样动力；（）每一个顾客i，有一个服务时间Si和服务时间窗口[e,l]ii，也就是为顾客服务车辆必须在li之前到达。如果它在ei之前到达，它应等待为iw。那么基本上，VRPTW问题研究对象是为参加了各车队客户车辆，要找到一最值点,以减少总行程距离，或最大限度地减少所使用车辆数目。我们例子是根据所罗门[]中定义模型。minNNNijijkijkck()NNijkjikjjxx,,,,ikK()KNkjxijk,,,,ijn()NNiijkijqxq,,,kK()KNijkiiijijkixbstwb,,,jn()iiiieawliN()这里iS：为客户i服务时间；iq：客户i需求；ijt：i和j之间直接行驶时间；ijc：从客户i到客户j路程所需消费；ia：到达客户i时间；ib：开始服务客户i时间。如果车辆k直接从i行驶到j，ijkx，否则，ijkx，ij，jC。以尽量减少车辆行驶总成本：（）车辆承受能力，旅行时间和到达时间可行性约束。（）确保每辆车从节点和节点n+结束开始。此外，每个客户能而且只能由一辆车送达。（）在同一时间，车辆k服务客户所有需求，不能超

文档预览结束

找同类相似 下载到手机