【DOC】-外文翻译---混合算法求解有时间窗车辆路径问题-其他专业

【DOC】-外文翻译---混合算法求解有时间窗车辆路径问题-其他专业 淮 阴 工 学 院 毕业设计(论文)外文资料翻译 系 (院): 计算科学系 专 业: 信息与计算科学 姓 名: 卞小婕 学 号: 1084101101 Lecture Notes in Computer Science 外文出处: 5370,198-205(2008) A Hybrid Algorithm for Vehicle Routing Problem with Time Windows (用外文写) 附 件: 1.外文资料翻译译文,2.外文原文。 指导教师评语: 签名: 2012 年 3 月 日 附件1:外文资料翻译译文 混合算法求解有时间窗车辆路径问题 摘要:有时间窗车辆路径问题(VRPTW)是近年来一个引起相当大的注意的众所周知的复杂的组合问题。组合优化这类问题是NP困难问题，最好是用近最优化的启发式解决。在这里，我们提出了VRPTW问题的两阶段优化策略。首先，为建设一个好的初始解，我们使用随机PFIH，保证初步解决 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 的多样性。然后提出优化一个基于SA和LNS组合的混合动力系统的初始解。其次，用回归迭代策略调整时间窗口为客户提出并找出每个车辆离去的最佳时间。它可以使总等待时间为零。这项测试工作是在所罗门有时间窗车辆路径问题中的C - 101型情况下执行。 实验表明，我们的算法可以快速有效地解决有时间窗车辆路径问题。 关键词:随机PFIH，迭代策略. 1.介绍: 车辆路径问题(VRP)是一个通用名称，简称为一类为客户服务的车辆数目的组合问题。这是许多物流系统的一个重要元素。有时间窗的车辆路径问题(VRPTW问题)是一种约束的VRP版本，其中每个顾客的服务必须在指定的时间窗口内送达。 VRPTW问题的实例经常发生许多行业，如快餐交付，产品交付，邮递，校车路线等。略有改善的解决方案甚至可能会节省大量成本。因此， VRPTW问题在于管理科学，物流管理日益增长的兴趣和计算机科学。 然而，时间窗车辆调度问题是NP-hard 。因此，目前研究这个问题需尝试运用启发式技术，以获得局部最优的最理想的解决方案来解决问题。在这些启发式，混合方法是常用的。Oliveriva H.C.B. [3]提出了一种在模拟退火和随机启动(启动)爬一座小山战略相结合的基础上的不同的方法。Alvarenga.G.B.[4]提出了一个使用高效的遗传算法和一组分区制定的强大的启发式方法。Andrew. L[5]提出了m-VRPTW问题的两阶段算法，首先最大化一个弹射池服务的客户数量来拥有临时服务器提供服务的客户，然后使用经典的多启动迭代爬坡算法包括广义弹射链来最小化总行程距离。 在我们的论文中，我们首先构建初始随机PFIH的解决方案，然后使用结合模拟退火和大邻居搜索策略的混合算法。最后，回归迭代战略提出了为客户调整的时 间窗口，并找出每辆车出发的最佳时间，这样可以使总的等待时间为零。 2. 论文提交程序: 在VRPTW问题中，每一位顾客有一个给定的需求。我们qi, iC={1, 2,...,n},i C的目的是，用这样一种方法为每部车辆找到路径:(1)每个在的顾客在其服务的时间被拜访一次; (2)所有线路在节点0开始,在节点结束 ;(3)n+1,N={0,1,...,n+1} 每个线路上客户的需求的总合不能超过车辆的流量，所有的车辆都属于同一类型，q 并有同样的动力;(4)每一个顾客，有一个服务时间和服务时间窗口，也iS[e,l]iii 就是为顾客服务的车辆必须在之前到达。如果它在之前到达，它应等待的为。lewiii那么基本上， VRPTW问题的研究对象是为参加了各车队的客户的车辆，要找到一最值点,以减少总行程的的距离，或最大限度地减少的所使用的的的车辆的的数目。 我们的例子是根据所罗门[2 ]中定义的模型。 NNN (1) minck,,,ijijk,,,001ijk NN ikK,,0,1,2,,？xx,,1 (2) ,,,,ijkjik,,11jj KN ijn,1,2,,,？xijk,1 (3) ,,,,,,10kj NN kK,1,2,,？qxq, (4) ,,,,iijkij,,00 KN jn,1,2,,？ (5) xbstwb，，，,,,，，,,ijkiiijijki,,00 iN,eawl,，, (6) ，，iiii iiitSqj这里:为客户的服务时间;:客户的需求;:和之间的直接行驶时间;ijii iiicjab:从客户到客户路程所需消费;:到达客户的时间;:开始服务客户的ijii 时间。 kix,1x,0jij,jC,如果车辆直接从行驶到， ，否则，，，。以尽量ijkijk 减少车辆行驶总成本:(1)车辆的承受能力，旅行时间和到达时间的可行性约束。(2)确保每辆车从节点0和节点n +1结束的开始。此外，每个客户能而且只能由 kk一辆车送达。(3)在同一时间，车辆服务的客户的所有需求，不能超过车辆的最大容量。(4)表达式(5)-(6)为定义的时间窗口。 3(一个混合动力系统的VRPTW问题 这项工作旨在构建一个混合动力系统的基础上，结合模拟退火和大邻居搜索策略。为建设卓越的初始SA算法的解决方案，这项工作使用随机PFIH的。读者可参考马吕斯所罗门[2]的PFIH算法的细节。 初步的解决方案 建立初始的路线，并提议在[ 1 ]中使用随机PFIH 。这样能产生快速多元化的解决方案。原PFIH [2]是确定性的，但不同的是，它用随机选择的PFIH来定义的第一个客户为每个新的路线。这是必要的，可以产生多样的初始解。 产生新的解决方案的过程 新的解决方案的过程原理是large neighbor search(LNS)的改善，这是由Pawl Shaw(1998)提出的建议。它从最初的解决方案开始，根据不断重新移动和重返社会的进程找到最佳的解决方案。虽然LNS的具有竞争力的搜索技术中的问题有复杂的约束条件，但我们需要一个优越的初始解，所以我们通过随机PFIH构造的初步解决方案。鉴于为特点的VRPTW问题，重新移动和重新插入的过程如下所述。 在这里，集合A是目前的解决方案，c是将被从A删除的客户，集合R是从A中删除客户，p是被删除的客户的数量，当P客户已经从A免去时，我们使用集合B表示的部分解决方案。 RAZA中第一个少部分元素是从中随意删除客户，从的其余客户中选出的第 ZR二部分是和客户最大相关的，根据与集合的关联性选择其余的. 每次被删除客户和集合R最大相关.上述程序将重复p- 2次，直到所有必需的客户被选择，我们使 ir,ijRiR,j用简单的关联函数表示任何两个客户和之间的关联，表示任何顾客，，，，iR和之间的关联: r(i, j)=1/ (t'+v) (7) ijij R,,iRrij, (8) ，，，，,jR, 其中如果i和均由同一车辆，否则为0 ; 是从i到(本文tttv'/max,1,,tjj，，ijijijijij行驶距离)的时间。 为了寻找一个新的优越的解决方案，我们使用重新插入的过程，就是，在中R的元素重新插入到。但当我们将其插入到时，在中会有很多客户重新插入位BBR 置，所以我们为了保证重新插入过程的可行性设计了如下的算法。 首先，为每一位在R的客户修复最好的插入位置:一个不可行客户的最佳可行插入位置是能最大限度地减少目标函数值增量的位置，并记录目标函数值。在此之后，排列刚刚记录的所有目标函数值，并选择具有最小的增量值的客户。然后将c它重新插入到B 并从R中删除。同时，搜索可以重新将R中其他客户插入到B所有的解决方案，重复上述步骤直到R为空，也就是从B中删除的所有客户又插入B。然后，我们比较我们发现所有的解决方案和B方案，如果B优越，选择目前最佳的 B解决方案型。 VRPTW问题的综合算法 本文中的混合算法分为两个阶段:首先，利用随机PFIH产生更好的初始解;其次，我们扩大搜索空间以避免陷入局部最优，并结合LNS和SA优化路径来寻找最佳的解决方案。整个过程描述如下: fS步骤1 :用随机PFIH产生初始解和计算目标函数值。修正初始温度S，，00 lTLTT,的。对于每个 ，最大值为的迭代时间是 ，是现在不不断接受新的解m0 M决方案的次数，的上限为。 m TT,'T'步骤2:如果(是终止温度)，则转到步骤3，否则转到步骤6。 lL,mM,mM,步骤3:如果而且，则转到步骤4;如果，则转到步骤6。 S' ffSfS,,':产生一个新的解决方案步骤4，计算，如果，则 f,0，，，，0 S'S'S新解决方案就被自动接收替换，然后转到步骤3;否则，接受新的解决方案0 fT/m,0e将取决于设立的概率大都市 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 ，如果接受，则，转步骤3 ，否则，mm,，1 ，转步骤3 。 TTT,,步骤5:的降低取决于公式 ，转步骤2 。 kk，1 步骤6:导出最佳的解决方案。 4 客户时间窗的回归策略 由于目标的可行途径，不仅是为了最大限度地减少总行驶距离，而且要尽量减少总的等待时间，甚至到零。因此，本文中，将最大限度地减少总行驶距离作为第一目标，我们也考虑在等待交通成本，并为客户提出了战略调整的时间窗口，找出为每辆车出发的最佳时机，所以它可以使总的等待时间为零。我们定义它回归迭代战略如下: ，，设“”是车辆可行的路线，是客户的时间窗。时间Kel,0vv0,,,？vvv1niii，， ，，窗调整后，为 。是车辆K的时间窗。整个路线为每个v,1,2,..., nel,el',',,,,vvi00ii，， 顾客调整时间窗的步骤的是: 步骤1eeetslllts'max,,'min,,,,,,,:计算。 ,,,,vvvvvvvv00,00,nnnnnnnn ，，步骤2:将 的时间窗更新为，重复步骤1，计算的新时间vel','vv,,？vvn,11nnn，， 窗。 Kel,步骤3:令eetllt,,,,','，是车辆从起点离开的时间窗。 ,,kvvkvv,0,0kk1111 从回归迭代战略，第一步，我们可以发现这样的事实:对于任何e'和vilvn'1,2,,,？，它们满足以下条件:el'',。否则，该解决方案将是不可行,,，，vivviii 的解决方案，违反时间窗口。以提高战略的可行性，我们提出了一个定理，并证明它。 定理4.1:在新的时间窗，同一航线相邻的任何两个客户，车辆不必等待或等候时间为零。 iiKKjj证明:假设和是车辆服务的顾客，在这里，是的前一战，车辆访问 ，，iel','el','早，我们调整所有的时间窗口后，他们的新的时间窗口是和。服,,jjii，， iiw'b'jb'w'j务顾客和的新时间表示为和。和分别是顾客和新的等候时间，jjii 然后， ebleeetslllts''','max,','min,',,,,,,,,。 ,,,,iiiiijijiiijiji,, ijw'0,显然，在新的时间窗口访问客户和是可行的，现在我们将证明和i 。 w'0,j i(1) 如果顾客是车辆访问的第一个顾客， 。现在客户是第二个，Kw'0,ji webtsebtsetsbeb'max0,'',''''''0,,，，,，，,,,,,,,，，，，，，,,jjiijijiijijijiiii ，即。 w'0,j thi(2) 如果客户是，客户是下一个，，。 mw'0,jw'0,ji ththi因此，当客户是，是，我们刚才证明出而且。 m，1m，2w'0,jw'0,ji i综上所述，当客户是车辆K服务的任意客户，总有，。 w'0,w'0,ji 这就完成了证明。 5 实验结果 VRPTW问题，有许多出版物使用启发式和元启发式，所罗门的56基准问题经常用于比较不同的启发式。这项工作的测试是在所罗门VRPTW问题的实例C101型下执行。因此，我们的算法至少在总行驶距离方面比以前的方法有可比性，控制 参数见表1 。 表1 Paramenters算法 VRPTW问题中我们的算法取得的最好的成果和最好的公布结果[4] 相比 。根据表2 ，我们的算法生成的同类解决方案在C101 。同时，从每个节点出发，每部车辆的时间是载于附录。 表2 C101的结果 我们可以通过表3看到在一些文献的比较。 表三 在一些文献中的比较 6 总结 在本文中，我们提出了VRP的两阶段优化策略与时间窗的问题。该算法首先构造了一个初步的解决方案的随机PFIH提供优越的初步方案，然后使用结合SA和LNS的解决方案混合算法优化初始方案。最后，为客户调整的时间窗口和找出每辆车出发的最佳时间，提出了回归迭代策略。它可以使总的等待时间为零。 实验结果表明，该算法大大提高解决方案的质量。与以往的方法相比，它也为今后的工作探索表明了方向，为其他的本地操作者成立元启发式。 参考文献 1. Alvarenga, G.B., Mateus, G.R.: Hierarchical Tournament Selection Genetic Algorithm for the vehicle Routing Problem with Time Windows. In: HIS 2004, Fourth International Conference, pp. 410–415 (2004) 2. Solomon, M.M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 35(2), 254–265 (1987) 3. Oliveira, H.C.B., Vasconcelos, G.C., Alvarenga, G.B.: Reducing traveled distance in the vehicle routing problem with time windows using a multi-start simulated annealing. In: IJCNN 2006, pp. 3013–3020, July 16-21 (2006) 4. Alvarenga, G.B., Mateus, G.R.: A two-phase genetic and set partitioning approach for the vehicle routing problem with time windows. In: Proc. 4th International Conference on Hybrid Intelligent Systems, pp. 428–433 (2004) 5. Lim, A., Zhang, X.: A two-stage heuristic for the vehicle routing problem with time windows and a limited number of vehicles. In: Proceedings of the 38th Annual Hawaii International Conference on System Sciences (HICSS 2005), p. 82c (2007) 6. ~msolomon/problems.htm (2004) 7. Shaw, P.: Using constraint Programming and local search methods to solve vehicle routing problems. In: Proceeding of the 4th International Conference on Principle and practice of Constrant Programming, pp. 417–431 (1998) 附录 每一辆车在每一个客户出发的最佳时机 车辆1: 21.3944 121.394 216.394 308.394 494 589 682 774 867 960 1052 1062.2 车辆2: 20.7934 123 214 306 401 494 589 682 774 867 962.385 1054.39 1070.2 车辆3: 21.1933 126.326 217.326 309.326 402.154 495.76 588.76 681.922 774.158 866.394 960 1052 1145 1160.81 车辆4: 0.220282 106.773 199.773 291.773 383.773 476.773 569.602 661.602 753.602 846.602 938.838 1032 1125 1217 1235.03 车辆5: 24.3845 135 230 321 417 510 605.831 698.659 791.659 884.488 978.093 1000.45 车辆6: 20.5979 141.404 236.789 328.789 422.394 516 608 703 798 893 926.54 车辆7: 17.9921 139.615 231.615 327 422 517.831 609.831 704.831 799 798 893 926.541 车辆8: 24.1807 161.615 254.615 346.615 536.615 629.615 723.615 814.615 910 961.478 车辆9: 21.1942 142 236 329 424 519 614 706 799 837.079 车辆10: 24.6148 149.615 241.615 336.615 432 618 711 811.44 846.497