英语原文共 15 页，剩余内容已隐藏，支付完成后下载完整资料
灾后道理清理工作延迟的降低
摘 要
自然灾害发生后，道路和桥梁可能被破坏或堵塞，造成医院、救灾中心、避难所和受灾地区等重要地区之间的交通不便。我们对这种灾后道路情理问题进行了研究，旨在提供一种快速有效的方法来确定一只负责清理阻塞道路的工作队的路线。问题的关键在于为工作团队找到一条路线，从仓库开始，并通过所有的重要地点。目标是最小化重点节点的总延迟，其中节点的延迟被定义为从仓库到该节点的路程所耗时间。关于这个问题的数学模型已经在文献中得到发展。然而，对于具有七个或以上的重要节点的实例，这个公式不能再3小时内最优解决问题。为了在较短时间内找到一种近似最优解，我们提出了一种能够在变幻后的网络上求解混合整数规划的启发法，并提出了一种求最优延迟的较低的界限法。另外，我们开发有了一种基于贪婪随机自适应搜索法（GRASP）和变领域搜索（VNS）相结合的元启发式算法。我们对伊斯坦布尔数据的数学发和元启发式进行了测试，并证明了最优或近似最优解是在几秒钟内得到的。我们还将我们的算法与文献中已有的成果进行了比较。最后，我们进行了一个分析，以观察总延迟和最大延迟之间的权衡。
序章
地震或飓风等严重灾害破坏手影响地区的基础设施，造成大量残骸堆积，包括建筑材料（如混凝土、砖块、木材）、车辆、纸杯（如倒下的树木）和道路基础设施的瓦砾。为了便于立即采取应急行动，必须在尽可能短的时间内清楚道理上的碎片。此外，从长远来看，废物管理和修复受损道理使该区域回复的重要活动。在这项研究中，我们侧重于及时反映阶段，例如在灾后的72小时中着力于优化清除残骸的决定。
灾后恶劣的道路状况妨碍了医院、救援来源、庇护所和伤亡地等重要地区之间的交通。利于，2011年日本地震和海啸使十万人滞留在灾区。典型的，为了清理道路，并可能恢复重度损坏的路段，一个或多个工作团队配备了重要的在最初的损坏评估阶段后立即被派遣。在大多数情况下，在时间限制的显示反应阶段清除所有受影响的道路是不可能的。因此，有必要选择最有利的清楚任务，以便在短时间内到达关键位置。越早到达相应的关键地点，就越有可能避免生命的损失或者其他的痛苦。
这项研究的目的是指定一种有效且适用的方法，通过建立一个清理小组的路线来决定哪些道路应该按照什么顺序被清除或修复。我们注意到在这份文件中，我们交替使用道理清楚和解除阻塞的行动，意见进入阻塞的边缘地带，也可能包括修理。在我们的问题定义中，道路用网络标识，关键位置即为节点的子集。每个边缘都有一个遍历耗时，另外，一致的边界子集在给定的预计清楚时间内被阻塞。如果阻塞边缘被清楚，他可能会在稍后的时间再次被遍历。总行程时间包括路线中所有边缘的遍历时间和阻塞时的清除时间。路由应该访问所有关键节点，以确保他们是可到达的。该弧路由问题的目的是最小化所有关键节点的总延迟。关键节点的延迟定义为访问之前的时间。也就是说，他是从操作开始到到达关键节点位置的路程时间，从起始点（仓库节点）开始的。
图1对于相同的最大等待时间值具有不同总等待时间的示例。
可在回应范围内考虑其他目标。例如，最小化最大延迟，这与路由的总时间相同。然而，当我们最小化最有一次访问关键节点的延迟时，解决方案可能会让人们不必要的等待。在图1的简单示例中，假设从节点零分派清理小组，节点1、2和3是关键的，所有的边缘都被封锁了。边上的数字是遍历时间加上额外的解锁时间。有两条路径（0-1-3-2和0-2-3-1）连接关键节点，其中两条路径的上次一访问节点的延迟为15。翠玉第一条路径，节点1、3和2的延迟分别为5、8和15，因此总延迟等于28.对于第二条路径，节点2、3和1的延迟分别为5、12和15.此路径的总延迟为32.虽然这两条路径的最大延迟是相通的，但它们对应的总延迟值是不同的。这个简单的例子说明了为什么我们喜欢最小化总延迟而不是最大延迟。但是，我们还提供了一个分析，其中可以在最大延迟上设置上限，同时最小化总延迟。
1.1我们的贡献
这个正在被考虑的问题曾经被研究过，正如我们在文献评论一节中所解释的。我们的主要贡献是我们开发的启发式方法以及较低的界限法。我们证明了我们的启发式方法在很大程度上优于BERKTAS等人提出的启发式方法，就计算时间而言，它能够解决更大的实例。对于大型数据集，特别是随着临界节点数的增加，BERKTAS等人提出的精确公式产生宽松的上下界。因此，我们提出了一种在求解多个混合整数规划模型（MIP）的基础上，为具有更高临界节点的情形生成强下界的新方法。为了找到高质量的解决方案，我们提出了一种数学方法，它解决了在转换后的网络上的MIP问题，该算法见笑了网络的规模，并在短时间内运行。我们注意到，在下界格式中使用的MIP和在数学中使用的MIPs是不同的。考虑到从业者可能无法获得商业解决者，我们提出了另一种方法，即元启发式。元启发式算法是一种混合算法，它运行贪婪随机自适应搜索过程（GRASP）的构造步骤，然后可变邻域搜索（VNS）改进步骤。我们的两种启发式方法在实际大小的数据集中运行时间很短，证明了他们在灾后相应阶段的适用性。总之，与BERKTAS等人提出的数学理论相比，数学和元启发式算法的计算时间都要小得多。这解决了同样的问题。此外，当最大节点变大时，我们的最优性差距比他们要好，我们用更大的网络和更多的关键节点来检测我们的算法，并且任然保持比较小的执行时间。此外，我们的启发式方法是用于任何不完全网络，从而适用于（涵盖了）更实际的情况。我们用一种新的下界格式来报告启发式界的最优区间。本文的其余部分难以下方式组织。第二节回顾了相关研究，第三节介绍了问题描述，第四节提供了较低的边界方法，第五届讨论了两种解决方案方法。在第六节和第七节中，我们分别描述了数据集并给处理计算结果。在第八节中演示了总延迟和最大延迟之间的权衡。最后在第九节给出了结束语。
文献综述
我们首先讨论了灾后道路清理和垃圾清理的研究，然后，我们回顾了在灾难环境下最小化路径延迟问题。
2.1道路清理
与道路清理有关的初步研究侧重于确定需要修复的阻塞道路，而不是为工作人员建造最佳路线。在这里，我们把负责清理道路的工作团队称为“车辆”。Duque和Srensen研究了一个受灾影响严重的网络，其中一些道路被封锁。根据城镇的重要性分配了权重。在预算限制下，目标是尽量减少每个城镇到期最近的区域中心的加权总耗时时间。他们得求解方法是基于抓取和VNS元启发式方法，阿克苏和兹达马尔以两个目标解决了多车辆碎片清楚问题。第一个是操作的完成时间最小化，而第二个使整个网络在整个清理操作中的可访问性最大化。他们建立了一个数学模型和一个基于规则的启发式算法，在确定阻塞边缘的清楚顺序和车辆恢复任务分配的同时，在这两个目标之间提供了一个平衡。虽然受损道路的修复任务分配给车辆，车辆的路线是不被考虑的。阿克苏和兹达马尔(2014)建议了一种基于路径的动态MIP，该MIP决定在资源受限时，在3天的时间范围内清除哪些阻塞的边缘。在土耳其的两个数据集上测试了该多车辆问题的算法性能。Liberatore、Ortuntilde;o、Tirado、Vitoriano和Scaparra(2014年)制定了一个多标准模式，以优化受损道路的恢复和向海地受飓风影响的人民分发商品。他们将可靠性、时间、成本和安全性作为标准，以决定哪些道路应该及时清理。严和施(2007)提出了最小化网络总恢复时间的MIP公式。提出了一种启发式算法，将网络划分为较小的网络，从而为每个较小的网络解决一个子问题。然而，没有一个子问题能够在规定的时间内得到解决。因此，在另一项研究中，严和施(2012)开发了一种基于蚁群系统的元启发式算法，以解决实际中看到的大小问题的实例。严和施(2009)发展了一个基于时空网络的多目标、多商品的MIP模型。他们的模型同时考虑了时间窗约束下的应急道路抢修和救援分配。目标是将所有损坏的道路修复之前的总时间最小化。在他们的案例研究中，作者还提出了一种有效的启发式算法来解决大型网络的相同问题。进一步的研究解决了在确定要清除的阻塞边的同时的路由问题。Duque，Dolinskaya和Souml;rensen(2016)开发了一个精确的动态规划(DP)模型，该模型可以获得维修人员的时间表和路线。然而，DP不能解决大型实例。因此，作者开发了一种迭代贪婪-随机化构造过程，该过程对于求解大型实例是有效的。Shin、Kim和Moon(2019年)开发了MIP和蚁群优化(ACO)算法，以在灾难后恢复网络。他们的模型考虑了救援车辆和维修人员的时间表和路线。在最近的另一项研究中，Moreno，Munari和Alem(2019年)提出了一个基于Bders分解的精确模型来解决机组人员调度和路线问题。作者利用可行性削减、多重最优性削减和专门的有效不等式来获得高质量的解。Shin，Kara，and Karasn(2016)提出了一个精确的模型和一种启发式方法，以最小化直到所有关键节点被访问的时间。此目标与最小化最大延迟相同。在他们的计算测试中，他们使用了伊斯坦布尔一个地区的数据，该地区有七个关键节点。Berktas斧头等人。(2016)提出了数学模型和启发式算法，以最大限度地减少(I)最大延迟，如Shin等人所述。我们当前研究中的关键节点的总延迟。虽然他们改进了SHIN等人的方法。(2016)对于计算时间上的最大延迟问题，他们没有用更大的数据来测试这些方法。我们注意到，他们的模型只有在三角不等式成立的情况下才有效。此外，在他们的启发式方法中，每次车辆经过相同的阻塞边缘时，清除时间都被添加到目标函数中。因此，这导致了对客观价值的过度计算。这一事实可能会导致找到次优解，特别是当阻塞边的数量很高时。
几项研究考虑到公路坝龄导致网络断开的情况，Kasaei和Salman(2016)开发了两个数学模型以及启发式方法来查找清理堵塞道路的车辆的路线，以实现连通性。第一个模型最小化恢复所有断开的组件的总时间，第二个模型通过在给定的时间限制内连接组件来最大化收集的总时间。Vodaacute;k，Biacute;l和Krivaacute;nkovaacute;(2018年)ˇ提出了一种基于蚁群优化的元启发式方法，在最小的总时间内连接所有不连通的组件。在他们的工作中，他们通过仅使用组件的边界节点来减小网络的大小。因此，他们的方法能够求解多达723个节点的网络。Akbari和Salman(2007b)为Kasaei和Salman(2016)中的第一个问题的多车辆情况开发了数学模型和启发式算法，Akbari和Salman(2007a)研究了第二个问题，也是用多个车辆。在以前的工作中，作者提出了一种解决问题松弛的方法，并实现了一个可行的步骤，随后是一个邻域搜索算法。在后面的工作中，他们开发了一个数学模型和一个数学方法，将问题分解成单个车辆的问题，并用更新的奖品背靠背地解决它们。他们通过松弛的MIP的拉格朗日松弛导出了这个极大化问题的上界，并证明了一些最优性验证性质。他们在随机生成的欧几里得和伊斯坦布尔公路网实例上测试了他们的方法，这些实例最多有350个节点和大约700条边。他们得出了最优或接近最优的解决方案，差距很小。我们注意到，在多车辆路径问题中，由于任何道路在其解堵过程完成之前都不允许穿越，因此需要车辆路线的协调。在另一项研究中，Morshedlou，Gonzaacute;lez和Barker(2018)开发了两个数学模型，处理同步路由问题，用于计划和安排灾难后的恢复工作。为了增加其模型的灵活性，作者将指定给每个被破坏部件的修复人员的数量作为决策变量。此外，在第二配方中，允许每个被破坏的组件在其恢复过程中部分活跃。作者采用一种带有一些有效不等式的松弛MIP来获得协调路径。Shanelik，Ergan和Keskinocak(2015)定义了一个随机碎片清除问题，在这个问题中，道路清理时间是不确定的。在这个多周期问题中，目标是重新连接供应节点和需求节点。在每个时段内，清关时间以及其他信息都会更新。主要的决定是找出在每个时期清理的一系列道路。作者开发了一种启发式策略。请注意，最近，圣克里克(2016)从多学科的角度提出了一项关于网络恢复和恢复的调查，其中还包括关于道路清理问题的相关研究。
2.2.最低化总延迟
最小时延问题(MLP)是一个边不阻塞、每个节点都需要访问的单车节点路由问题。这个问题出现在维修服务等应用中，其中顾客的总等待时间(而不是车辆的出行成本)是人们关心的问题，也被一些作者称为出行维修员问题。Sahni和Gonzalez(1976)证明了MLP在一般度量下是NP-难的。尽管与旅行商问题(TSP)有一些相似之处，但Goemans和Kleinberg(1998)证明了MLP比TSP更难计算。Angel-Bello、Alvarez和Garca(2013)使用多级网络表示为MLP开发了强大的数学模型。这些模型仅适用于完整的输入网络，并使用多达40个节点进行了测试，对于最大的实例，平均计算时间为100秒。Sarubbi，Luna和Miranda(2008年)通过一种基于Bders分解位置的分枝切割算法，解决了具有多达80个节点的非对称实例的时变多商品多目标规划问题。Meacute;ndez-Diacute;az，Zabala和Lucena(2008)提出了一个三指标MIP公式以及与其MIP相关的几个有效不等式。该模型能够求解多达40个节点的实例。Luo，Qin，and Lim(2014)提出了一种带距离约束的多车辆MLP的精确分枝定价割算法，即所有节点只访问一次。为了解决定价问题，提出了一种基于双向搜索策略的自组织标签设置算法。他们测试了多达50个节点的180个实例，平均差距小于0.5%。一些研究集中于为MLP开发启发式和元启发式方法。Salehiour，Souml;rensen，Goos和Brauml;ysy(2011)发展了一种元启发式方法，该方法基于对构建阶段的把握，以及针对改进步骤的可变邻域下降(VND)和VNS。它们通过对最小生成树的边进行排序来获得下界，并从最近邻居启发式中推导出上界。他们将元启发式解决方案与多达1000个节点的数据上限和下限进行了比较。元启发式的执行时间对于超过500个节点的实例来说是非常高的(500个节点超过3个小时，与下限和上限的平均差距分别为50%和
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[236998]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
