英语原文共 7 页
可行性约束下的带时间窗车辆路径问题
Amine Dhahri1,2,3, Kamel Zidi1,2,3, Khaled Ghedira3
- 加夫萨大学,加夫萨科学系,Zarroug，Gafsa 2112，Tunisia
- 国立计算机科学学院(ENSI),Tu-nis,Tunisia-2010 Manouba
- SOIE-管理高等学院,41,Rue de la liberteacute;,Cite Bouchoucha Le Bardo 2000,Tunisie.
khaled.ghedira@isg.mu.tn,kamel.zidi@fsgf.rnu.tn,aminedhahri@gmail.com
摘要：应急管理是一个新兴的领域，该领域的运算研究技术被用于处理许多环境中的延迟问题。Yu Gang定义了应急管理的概念lt;在经济周期的开始，通过使用优化模型，得到一个最优的或者近似最优的计划。在该计划被执行的时候，由内在或者外在的因素引发的干扰有可能出现，原计划可能不再是最好的选择甚至不再具备可行性，因此，我们需要准备一个新的修改之后的计划，该计划需要对应环境变化后的约束和目的，用以最小化干扰造成的影响。gt;在这篇论文中，我们描述了一个基于变领域搜索的启发式算法，该算法用以解决在供应一组客户之后的一个或更多的车辆需要进行预防维护的情况下的带时间窗车辆路径问题。
关键词：启发式算法；车辆路径问题；变领域算法；应急管理；VRPTW
引言
供应链有许多活动组成，比如生产、供应等。自从最优结果消除了时间浪费，很长一段时间内，物流研究的目的都是对活动进行最优化。运输活动是物流领域最重要的活动之一，而更好的组织主要是车辆路径的活动展现了经济潜力。因为这些经济上的重要性，研究者们在车辆路径问题上投入了很多的关注。
与供应链相关的研究大部分都是建立在所有车辆均是可用的环境下。然而，在现实中的情况并不是这样简单的，实际上，像车辆这样的实体资源或许会由于各种原因而不可用，如车辆损坏、由维修部门进行的预防维护，或者其他的情况。因而，在时间日期均固定并且已知的阶段，车辆会变得不可用(决定论)。在最初解决应急管理的研究中，Yu和Yang是第一批探究与航空运营实时控制相关问题的专家，并且，他们观点的成功应用引发了对应急管理领域的广泛关注。当出现意料之外的情况时，该基本观点认为当前管理是不合理的。应急管理的技术被广泛用于各个领域，如项目管理中的生成计划[3]、单机调度[4]、平行机调度[5]、动态拨号盘问题[6]等等。在这些领域中，处理供应链中应急管理的著作中存在相关的研究。这些研究在论文[7]、[8]、[9]中。我们这篇论文不同的地方在于在前置条件中添加了时间的因素，该时间与较小概率但是存在较大影响并且很难去进行预测和处理的事件相关，这篇论文目的是尝试建立一个分析模型，该模型用以分析在带时间窗车辆路径问题中的应急管理问题。
这篇论文的新奇之处可以总结为一下几点：在第一部分给定了重计划问题的定义，由于原计划与干扰之后的计划的偏差，该定义不同于经典的带时间窗车辆路径问题。在重计划模型中，并不关注于解决所有顾客的需求，而是仅服务于那些在他们的时间窗未能得到供应的顾客，因此我们试图将他们的路线进行重建。在第二部分我们对基于数学模型的应急管理进行了解释；在第三部分，提出了用于解决应急管理的变领域启发式算法，并且在第四部分，我们发现了提出的重计划模型。在第五部分我们通过已发现的结果进行了推测，最后我们以对该工作的观点看法结尾。
带时间窗车辆路径问题下的应急管理
应急管理可以被定义为再干扰发生之后重解或者恢复环境和努力。通常，定义VRPTW的所有参数均可以成为干扰。在这篇论文中只考虑车辆故障的情况，即需要预防维护的车辆。对于这类干扰问题，最近出现了许多思想和方法，其中较具代表性的可以总结为以下三类：
- 对不确定的VRP研究，主要包括随机VRP、动态VRP、模糊VRP。这些研究试图找到适应各种环境的最佳计划。然而，在理论计划和实际执行之间总会存在多种差异，因此理论结果是有可能相悖于实际的最佳计划。
- 计划 重计划的方法研究主要涵盖两个方面，即原计划和重计划。车辆起初执行原定计划，当干扰发生时进行重计划，该计划为基于相同目的的最优选择。
- 基于紧急计划 人类经验类型的干涉方法研究。这类方法相信，对某些范围，干扰事情实际上将会被解决。但是正如论文[10]所提到一样，一个紧急计划考虑到所有的问题是不可能的，除此之外，当执行计划和紧急计划存在微少的差异时，基于直觉和经历的人类经验在处理问题时会产生干涉。
在这篇论文中，我们关注第二个问题，即在一定数量的车辆将进行预防维护后，我们试图找到一个针对VRPTW的新计划。正如图1所示，一个矩形代表一个仓库，一个小圆代表一个顾客。当车辆R3正在执行原计划时，在时间T它必须要进行预防维护，车辆R3便不能为顾客i,j,k提供服务，因此车辆R1和R2将会代替车辆R3为这些顾客提供服务。这就是一个故障车辆不能服务原定顾客的例子，因此当车辆进行维护时，需要提供备用方案以快速有效的做出决定。
图一.对未服务顾客的备用计划举例
VRPTW下的变领域算法
由Hansen和Mladenovic提出的变领域搜索算法VNS是一种启发式算法，该算法在搜索时基于领域系统化改变的原理，控制变化时存在着几条至关重要的规则。基本方法Basic VNS作用于几种特别的场合，如图二所示。首先，该算法要求存在不同领域结构的定义，通常由不同大小的V1hellip;VMAX来表示。在这些结构之间定义着一个和问题相关的关系规则。从起初的解决方案s开始，s的领域将会被选中，并随机使用领域结构V1，如果在运用局部搜索方法后得到的新解优于原解，VNS从新解开始重复搜索过程，否则，该解的挑选将会在一个更大的范围中进行，比如领域结构V2，运用局部搜索来寻求解，等等。这个方法避免了如果该解是一个小于最大范围的局部最优解而成为局部最优的情况。
初始选择一组领域结构NK,k=1hellip;Kmax,选择一个基于随机变量的分布方法和局部搜索算法，定义一个初始解和终止标准。
重复下列的过程，直到检验到终止标准。
(1)K = 1;
(2)当Klt;Kmax时重复下列过程
(a)偏移：从当前K的领域中产生一个随机解y(yisin;Nk(x))
(b)局部搜索：以当前解y为基础应用局部搜索方法得到一个局部最优解y1
(c)改变：如果局部最优解y1优于y，则用y1代替解y，并且在N1(K=1)中继续搜索过程，令k=k 1
A 初始解
基于启发式的最简化插入解用来进行初始解的产生，命名为I1。这个启发式方法的基本观点是以一个空路线开始。第一个被选择的顾客被命名为种子顾客，在这篇论文中，种子顾客被视为离仓库最远的一个点。顾客点会被纳入执行路线，直到路线完全满足时间和空间约束。
在通过种子顾客产生初始路线后，启发式算法使用两个准则c1（i,u,j）和c2(i,u,j)并在所有可能的相邻的顾客i和j之间来选择插入的顾客。让带有i0 和im 的执行路线(i0, i1, i2, im)来代表仓库，而对每个未能服务到的顾客u，我们将计算出路线中最可行的插入点。
被插入最优的顾客点u*满足
顾客点u*插入在i(u*)和j(u*)之间。当有更多的顾客点有了可能的插入点时，启发式算法产生了一条新路线。
diu , duj和dij代表相应顾客(c i , c u ), (c u , cj) 和(c i , c j )之间的距离，bj_new是在插入之后的总等待时间，b j表示插入前的仓库。最后的alpha;1, alpha;2 和 alpha;3是由用户决定的参数值。
B.偏移
总体领域结构的产生是这篇论文基本VNS算法最重要的部分，本论文设计了五个领域结构，结构之间存在着基于相同路线改变和基于两种不同路线改变的内部路线。
- 领域内部路线
- 两个选择：由Cores在其论文[14]中提出的两种选择，基本观点是当路径方向变反时，用两个其他的相同路线来代替路线中的两个弧段。
- 另一个选择是在旅行商问题中提出的，基本观点是迁移一组连续的点，当维持路线方向不变时，以其他路为参考，在初始路线中的三段弧段的迁移来实现点的迁移。
- 领域交互路线
- 两个选择：由Potvin在其论文[16]中提出的两种选择。两种选择基本观点是当维持路线方向不变时，在另一条其他路线中第一个顾客之后，合并两条路线，插入后一条路线的顾客。
- 交互：由Taillard在其论文[17]中提出。操作员使给定领域结构delta; ? [1,5]中，两种不同路线的delta;顾客间的值交互成为可能。
- 迁移：由Lin在其论文[18]中提出。基本观点是在另一条路线中改变其中一个顾客的位置。在我们的实例中，我们交换了处于连续的初始路径delta; ? [1,5]中delta;顾客们的位置。
表1:一组领域结构并且KMAX = 12
|
K |
Operator |
Segment Length |
|
1 |
Two-OPT |
1 |
|
2 |
Two-OPT* |
1 |
|
3 |
Or-opt |
2 |
|
4 |
Relocate |
1 |
|
5 |
Relocate |
2 |
|
6 |
Relocate |
3 |
|
7 |
Exchange |
1 |
|
8 |
Exchange |
2 |
|
9 |
Exchange |
3 |
|
10 |
Exchange |
4 |
|
11 |
Exchange |
5 |
|
12 |
Exchange |
6 |
C.局部搜索
为了通过偏移过程来优化获得的解，需要使用变领域下降搜索算法。变领域下降是一种局部增强优化的策略。其观点是在两个不同领域结构N1和Nn之间进行系统化的改变。VNS中使用的工作参数与VND使用的参数相同，除了领域搜索期间，我们使用五个基于最优策略的启发法，即两个选择，顶点的再迁移，两个选择(*)，一个顶点的再交互和两个顶点的再交互。
D.接受标准
在偏移和局部搜索全部完成之后，产生的新解需要与当前解进行比较。我们基于接受标准决定它是否被挑选。在基本VNS中，只有优化了成本的解才会被选择，但是我们很容易在局部最优中发现这个解。因此，在大多数情况下，针对某些确定的条件，有一个接受并没有改善结果的解的策略是必要的。我们构建了一个由模拟退火算法激发的
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
您可能感兴趣的文章
- GIS矢量地图的鲁棒水印方案外文翻译资料
- 中国相似地理位置发达地区房价影响因素的差异——以西安高新区和沣渭新区为例外文翻译资料
- 集成数据在城市土地利用变化时空动态监测的应用——以印度金奈都市为例外文翻译资料
- 全球地表水及其长期变化的高分辨率制图外文翻译资料
- 造成沿海大型城市内涝灾害的主要因素识别——以中国广州为例外文翻译资料
- 基于SFPHD框架的中国快速城市化地区城市生态系统健康综合评价方法外文翻译资料
- 基于绿地演变的未来城市地表热岛强度的多情景模拟预测外文翻译资料
- 中国大陆272个城市地面和冠层城市热岛强度的长期趋势外文翻译资料
- 与孟加拉湾热带气旋有关的中国低纬度高原远距离降雨事件外文翻译资料
- 新丰江水库流域GPM IMERG降水产品评价及水文效用研究外文翻译资料
