英语原文共 18 页，剩余内容已隐藏，支付完成后下载完整资料
跨车间路线的多车间车辆路线问题
伯努瓦泽维尔,弗朗西斯科尔多，吉尔伯特拉波特
摘要
这篇文章解决了多车间车辆路线问题的延伸，其中车辆可以沿着其路线在中间仓库补充。它提出了一种启发式结合自适应记忆原理，解决子问题的禁忌搜索方法和整数规划。测试是在随机生成的实例上进行的。
关键词：多车间车辆路径问题; 补货; 适应性记忆; 禁忌搜索; 整数编程
1.介绍
我们研究了多车间车辆路线问题的一个变体，车间可以作为沿车辆路线的中间补充设施。这个问题是车辆路径问题（VRP）的泛化。 经典版本的VRP定义在曲线G = (Vc cup;Vd, A)，其中Vc= {v1，v2，...，vn）}是客户集合，Vd= {Vn 1}是存储集合并且A = {（vi，vj）：vi，vjisin;[Vccup;Vd，ine;j}是G的弧集合。容量为Q的车辆的尾数位于Vn 1。 每个客户都有一个需求qi和一个服务持续时间dj。 成本或旅行时间cIJ与图表的每条弧线相关联。VRP包括确定满足以下条件的最小成本的m条路线：（i）每个顾客恰好出现在一条路线上;（ii）每条路线在车厂开始和结束;（三）任何路线上的顾客不会超过Q;（iv）路线的总持续时间不超过预设值D.
几种算法可用于VRP。 因为这是一个很难组合的问题，所以精确的方法在大型实例中往往表现不佳，这就是为什么开发了大量启发式算法的原因。这些包括经典启发式算法，如构建和改进程序或两阶段方法，以及模拟退火，禁忌搜索，变邻域搜索和演化算法等元启发式算法。有关调查，请参阅Laporte和Semet[22]，Gendreau等人[15]和Cordeau等人[8].
在某些情况下，可以将多条路线分配给车辆。 例如，当车队较小时或者当一天的长度相对于路线的平均持续时间较长时，遇到了多次使用车辆（VRPM）的车辆路线问题。 Fleischmann[12]可能是第一个提出这个问题的启发式方法。它基于路线建设的节约原则，并结合分配车辆路线的装箱程序。Taillard等人[29]已经开发了适应性记忆和禁忌搜索启发式，再次使用仓包装过程来分配车辆路线。其他启发式方法已经被提出用于VRPM，例如Brandao和Mercer[3,4] 或Zhao等人。[34] 基于禁忌搜索，或者在车辆路径上下文中，由Suprayogi等人提出的方法[28] 和Fagerholt[11] 通过解决旅行商问题（TSP）和解决赋值部分的整数程序（Suprayogi等人提出了一组分区问题）来创建路线。
多车间车辆路线问题（MDVRP）是VRP另一个众所周知的概括。在这个扩展中，每个客户都是由位于几个仓库之一的车辆来访问。在标准MDVRP中，每条车辆路线必须在同一个车间开始和结束。这个问题只存在少数精确的算法。Laporte等人[20] 以及Laporte等人[21] 已经开发出了精确的分支定界算法，但是，如前所述，这些算法仅适用于相对较小的情况。MDVRP已经提出了几种启发式方法。Tillman开发了基于简单构造和改进程序的早期启发式算法[30]，蒂尔曼和赫林[32]，蒂尔曼和凯恩[31]，Wren和Holliday[33]，吉列特和约翰逊[16]，Golden等人[17]，和筏[24]。 最近，Chao等人[6] 提出了一个结合Dueck#39;s的搜索程序[10]记录到当地记录客户重新分配到不同车辆路线的方法，然后是Lin的2-选项程序[23]以改善个人路线。Renaud等人[26] 描述了禁忌搜索启发式，其中通过首先将每个客户分配到其最近的仓库来构建初始解决方案。 由相同作者开发的花瓣算法[25] 然后用于解决与每个仓库相关的VRP。它最终使用一个改进阶段，使用4-选择程序交换的一个子集来改进单个路线，在来自相同或不同站点的路线之间交换客户或在三条路线之间交换客户。Cordeau等人的禁忌搜索方法。[7]可能是MDVRP最有名的算法。通过将每个客户分配到其最近的仓库来获得初始解决方案，并且通过扫描算法为每个仓库生成VRP解决方案。通过将客户转移到同一个仓库的两条路线之间或通过将客户路线事件重新定位到另一个仓库来完成改进。重新插入是通过GENI启发式进行的[13]。该算法的主要特点之一是在整个搜索过程中允许不可行的解决方案。 通过惩罚频繁的动作来实现持续的多元化。
研究人员没有收到多车间车间路径问题（MDVRPI）。Jordan和Burns讨论了这个问题的简化版本[19]和约旦[18] 他假设客户需求全部等于Q，并且站间路线包括两个仓库之间的来回路线。作者将这个问题转化为一个匹配问题，并通过贪婪算法解决。 Angelelli和Speranza[2]已经开发了一种适用于周期性车辆路线问题（PVRP）的版本的启发式算法，其中允许在中间设施处进行补充。他们的算法基于Cordeau等人的禁忌搜索启发式[7]。问题的一个版本在哪里时间窗口被认为是由Cano Sevilla和Simon de Blas提出的[5]。该算法基于神经网络和蚁群系统。
我们对MDVRPI的兴趣来自于蒙特利尔地区现实生活中的杂货分销问题。在车辆的路线可以由中间仓库中的多个停靠站组成以便补充车辆的情况下遇到若干类似的应用。当使用卡车和拖车时，补货可以通过拖车的开关完成。Angelelli和Speranza[1] 在废物收集方面提出了类似问题的应用。
我们的目标是为MDVRPI开发启发式，并为此问题引入一组基准实例。 本文的其余部分组织如下。 这个问题在Section中阐述启发式在章节中描述。计算结果在Section中给出,接下来是第一节的结论。
2.公式
MDVRPI可以如下配制。假设G = {Vccup;Vd, A}为Vc= {v1，v2，...，vn}为客户集的有向图Vd = {vn 1，vn 2，...，vn r}是一组r仓库，A={(vi，vj）：vi，vjisin;Vccup;Vd，ine;j}是弧集。需求qi和服务持续时间dj被分配给客户cij，并且成本或旅行时间cij与弧（vi，vj）相关联。这里我们使成本，旅行时间和距离互换。容量为Q的车辆可以同等运输。让s代表车辆停靠在车间所需的时间。所有路线的集合分配给车辆的轮转被称为轮转，其总持续时间不能超过预设值D.单个仓库路线在同一个仓库中开始和结束，而仓库间路线连接两个不同仓库路线h以其包含的一组客户为特征。
因此，定义eih和fhl系数如下
对于MDVRPI，我们的公式使用等于1的二元变量xkh当且仅当路径hisin;T是
h
分配给车辆k。并且当且仅当车辆k的旋转开始于仓库l时，定义等于1的二元变量ylk，并且整数变量zkl等于车辆k到达并离开车间仓库l的次数路线。 定义参数pi;h作为路线h的行程持续时间。如果路线h开始并在同一车厂结束，则通过在h的顶点上求解TSP获得pi;h;如果h是车间间路线，则通过确定链接两个车间的最短哈密顿路径来获得pi;h。另外，定义与路线h的总持续时间相对应的参数Uh如下：
l
l
并定义了这些集合：
Iisin;T：一组车间间路线;
D（S）isin;T：以S开始和结束的路线集合，其中Sisin;V;
W（S）isin;T：S中有一个仓库而另一个仓库在S以外的路线集合，其中Sisin;V
公式如下：
约束条件（4）保证每个客户只被访问一次，而约束条件（5）则规定每个车辆至多会分配一次旋转。 约束条件（6）确保当车辆驶入中间仓库时，它也会离开它。 约束条件（7）对旋转的总时间长度施加了限制。 最后，（8）是小消除约束：给定SV\，如果车辆k的至少一条路线属于D（S）（在这种情况下，不等式的左边是正数），那么必定存在在W（S）中至少有一条旋转路线，否则S的一个仓库必须是该车辆旋转的起始仓库（因为否则右侧的不等式等于零）。
�
3.算法
由于MDVRPI是VRP的延伸，并且只能精确地解决VRP的小实例，很明显，不能指望用上述公式解决MDVRPI。 因此，我们选择了禁忌搜索（TS）启发式的发展。 这种选择的动机是TS对经典VRP和MDVRP的成功（参见例如Cordeau et al。[8]).
在本节中，我们将描述MDVRPI的算法方法。 它部分基于Rochat和Taillard提出的自适应记忆原理[27]通过组合先前获得的解决方案的元素来创建解决方案。这里将把单车间和车间间路线合并起来。这些路线将通过禁忌搜索启发式方法生成，该启发式适用于将MDVRPI分解为MDVRP，VRP和车间间子问题所导致的三种类型的问题。在一个货场间问题中，一组最小成本路线在由客户和两个仓库组成的网络上生成，每个路线从一个仓库开始到另一个仓库结束。从解决方案到刚描述的子问题，底层的单个仓库和库间路线将被提取并插入到解决方案池T中。接下来，MDVRPI解决方案将通过执行基于上述集合分区算法公式。因此T的路线将被选择以产生一组可行的旋转，其中每个顾客都被访问。 最后，为了改进解决方案，将执行后优化阶段。
本节先后介绍了我们方法的ve分量：（1）禁忌搜索启发式;（2）申请生成解决方案池的程序;（3）路线生成算法;（4）集合划分算法，以及（5）后优化阶段。该描述之后是该算法的伪代码。
3.1禁忌搜索启发式
我们的禁忌搜索启发式是基于Cordeau等人提出的TS启发式算法。[7] 这对于解决各种经典车辆路径问题，即PVRP，MDVRP以及包含时间窗口的这些问题的扩展已经证明是高度有效的[9]。 我们现在回顾一下这种启发式的主要特点。
解决方案通过从当前路中移除客户并通过GENI过程将其重新插入另一个路中获得[13]。在MDVRP中，可以在与同一个仓库或另一个仓库相关的车辆中插入。 为了实现VRP的禁忌，首先定义指示顾客i在车辆k的路线上的一组属性（i，k）。每当一个客户从路由k中被移除时，属性（i，k）被声明为禁忌，并且在路由k中重新插入客户i被禁止重复数量为h的迭代。MDVRP与属性（i，k，l）一起工作，这意味着客户i位于车间l的车辆k的路线上。如果新的解决方案是可行的并且比具有该属性的最有名的解决方案的成本更低，则属性的禁忌状态被撤销。
为了扩大搜索范围，可以通过将惩罚目标f（s）与每个解决方案关联来允许不可行的中间解决方案。该函数是三个项的加权和：实际解成本c（s），容量约束的违规q（s）以及持续时间约束的违规d（s）。全局成本函数为f（s）= c（s） aq（s） bd（s），其中a和b是在整个搜索过程中动态更新的正参数。如果解是可行的，则两个函数c（s）和f（s）重合。 这种机制首先由Gendreau等人提出[14]在VRP的背景下。它允许搜索在可行和不可行的解决方案之间摆动，并且可以使用简单的邻域，而不必保留可行性。参数调整程序在第一节中描述导致在整个搜索过程中检查几个好的可行解决方案。应用连续多样化机制来惩罚频繁
全文共19403字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[16505]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
