外文翻译---混合算法求解有时间窗车辆路径问题

《外文翻译---混合算法求解有时间窗车辆路径问题》由会员分享，可在线阅读，更多相关《外文翻译---混合算法求解有时间窗车辆路径问题（10页珍藏版）》请在毕设资料网上搜索。

1、PDF外文：http:/   淮  阴  工  学  院  毕业设计 (论文 )外文资料翻译   系   （院）：  计算科学系  专     业：  信息与计算科学  姓     名：  卞小婕  学     号：  1084101101 外文出处：  Lecture Notes in Computer Science 5370,198-205(2008) ( 用外文写 )

2、A Hybrid Algorithm for Vehicle Routing Problem with Time Windows 附     件：  1.外文资料翻译译文； 2.外文原文。   指导教师评语：       签名：                                           &nb

3、sp;                 2012 年  3 月   日  附件 1：外文资料翻译译文  混合算法求解有时间窗车辆路径 问题  摘要： 有时间窗车辆路径问题 （ VRPTW） 是近年来一个引起相当大的注意的众所周知的复杂的组合问题。组合优化这类问题是 NP 困难问题，最好是用近最优化的启发式解决。在这里，我们 提出了 VRPTW 问题的两阶段优化策略 。首先，为建设一个好的初始解，我们使用随机 PFIH，保证初步解决方案的多样性。然后提出优化一个基于

4、SA 和 LNS 组合的混合动力系统的初始解。其次，用回归迭代策略调整时间窗口为客户提出并找出每个 车辆离去的最佳时间。它可以使总等待时间为零。这项测试工作是在所罗门 有时间窗车辆路径问题 中 的 C - 101 型情况下执行。  实验表明，我们的算法可以快速有效地解决 有时间窗车辆路径问题 。  关键词： 随机 PFIH， 迭代策略 . 1.介绍 ：  车辆路径问题（ VRP）是一个通用名称，简称 为 一类 为 客户服务的车辆数目的组合问题。这是许多物流系统的一个重要元素。有时间窗的车辆路径问题（ VRPTW问题）是一种约束的 VRP 版本，其中每个顾客 的服务

5、 必须 在 指定的时间窗口内送达。  VRPTW 问题的实例经常发生许多行业，如快餐交付，产品交付， 邮递，校 车路 线 等 。略有改善的解决方案甚至可能会节省 大量 成本。因此，  VRPTW 问题在 于 管理科学，物流管理日益增长的兴趣和计算机科学。  然而，时间窗车辆调度问题是 NP-hard 。因此，目前研究这个问题 需 尝试运用启发式技术，以 获得 局部最优 的 最理想的解决方案 来 解决问题。在这些启发式，混合方法是常用的。 Oliveriva H.C.B. 3提出了一种 在 模拟退火和随机启动（启动）爬一座小山战略相结合的基础上 的 不同的方法。 A

6、lvarenga.G.B.4提出了一个使用高效的遗传算法和一组分区制定 的 强大的启发式方法 。 Andrew. L5提出了m-VRPTW问题的两阶段算法， 首先最大化 一个 弹射池 服务的 客户数量 来拥 有临时服务器提供服务的客户，然后使用经典的多启动迭代爬坡算法包括广义弹射链 来 最小化 总行程距离。  在我们的论文中，我们首先构建初始随机 PFIH 的解决方案，然后使用结合模拟退火和大邻居搜索策略 的 混合算法。最后，回归迭代战略提出了为客户调整的时间窗口，并找出每辆车出发的最佳时间， 这样 可以使总的等待时间为零。  2. 论文提交程序 ：  在 VRP

7、TW 问题 中 ，每一位顾客 i, i C = 1 , 2 ,.,n 有一个给定的需求 qi 。 我们的目的是， 用 这样一种方 法 为每部车辆找到路 径： （ 1）每个在 C 的顾客在其服务的时间 被拜访 一次 ； （ 2）所有线 路 在节点 0 开始 ,在 节点 n + 1 ,N = 0 ,1 ,.,n + 1 结束  ；（ 3）每个 线 路 上 客户的需求 的总合 不能超过车辆的流量 q ，所有的车辆都属于同一类型，并有同样的 动 力 ；（ 4）每一个顾客 i ，有一个服务时间 Si 和服务时间窗口 e,lii ， 也就是 为 顾客服务的车辆必须 在 li 之前到达。如果它在

8、ei 之前到达，它应等待的为 iw 。那么基本上，  VRPTW 问题的 研究 对象是 为 参加 了各 车队的客户的车辆，要找到一最值点 ,以减少总行 程 的的距离，或最大限度地 减少的所使用的的的车辆的的数目。  我们的 例子 是根据所罗门 2 中定义的模型。  0 0 1m in NNN ij ijki j kck                                    

9、;(1) 111NNijk jikjjxx     0 , 1 , 2 , ,i k K               (2) 101KNkjxijk         , 1, 2, ,i j n                    (3) 00NNi ijkijq x q       1, 2, ,kK     &n

10、bsp;              (4) 00KN ijk i i ij i jki x b s t w b   1, 2, ,jn           (5) i i i ie a w l        iN                           (6) 这里 iS ：为客户 i 的服务时间； iq ：客户 i 的需求；ijt： i 和 j 之间的直接行驶时间；ijc：从客户 i 到客户 j 路程所需消费； ia ：到达客户 i 的时间； ib ：开始服务客户 i 的时间。  如果车辆 k 直接从 i 行驶 到 j ， 1ijkx ， 否则， 0ijkx ， ij ， jC 。以尽量