岸桥调度问题的混合分布估计算法外文翻译资料

 2022-03-23 08:03

本科生毕业设计（论文）参考文献译文本

译文出处：Izquierdo C E, Velarde J L G, Batista B M, et al. Estimation of Distribution Algorithm for the Quay Crane Scheduling Problem[J]. Applied Soft Computing, 2013, 13(10):4063–4076.

院 系 物流工程学院

专业班级 物流zy1402班

姓 名 杨 强

学 号 0121418970422

指导教师 王强老师

2018年3月

岸桥调度问题的混合分布估计算法

摘要：集装箱码头的竞争力高度受制于集装箱船的在港时间。港口起重机的合理调度能够减少船只的在港时间，使其对船运公司而言更具吸引力。岸桥调度问题（QCSP）的目标是最小化起重机执行集装箱装卸任务的处理时间。本文提出了一种结合局部搜索的混合分布估计算法来解决岸桥调度问题。该方法包括了初始化步骤时的先验知识来达到搜索空间的潜力地区，还有一个重新启动策略，该策略可避免搜索过早地收敛。另外，还采用了一个近似评价方案来减少计算时间。此外，用统计学方法将它的性能与文献中最好的优化方法进行比较。数值试验结果表明该方法的鲁棒性和效率更高。最后，将对该计划的相关部件逐个分析以检查其有效性。

一、前言

如今，为适应市场需求，公共机构已建成大型海上集装箱码头。集装箱码头是多式联运网络内的集装箱交换的物流节点。其主要目标是实现不同运输方式之间有效的集装箱转运。通常情况下，集装箱码头的运输方式是海运（集装箱船）和陆运（火车和汽车）。这些设施的管理是复杂的，因为大量的过程相互关联。在 Vis和de Koster的工作中，Steenken 等人以及 Stahlbock和Voszlig;关于物流问题的研究中，对最突出的优化方法进行了综述。

有许多指标，试图衡量一个集装箱码头的生产力。最为突出的是一些与减少集装箱码头的集装箱船所花时间（称为“周转时间”）有关的指标。产生一个大的周转时间的主要原因是随着海上交通运输量增长而导致基础设施（泊位及现有设备）的利用率过高，以及服务于集装箱船的港口起重机的不合理使用。由岸桥处理的集装箱数量，可以反映码头的运转效率和机械特性。因此，增加每个码头装卸集装箱的数量以抵消集装箱船容量的增加，是每个集装箱码头管理者感兴趣的问题。最近，这个方向的研究已取得很多进展。在码头起重机生产率的主要增长中，双面操作系统结合、多举机或双小车岸桥不得不提。Chao和Lin[ 6 ]就提出了关于这些进展的分析。

集装箱船上的装卸作业在必须根据一个明确的配载计划执行。配载计划用湾、行、层构成的坐标系统来标明每个集装箱在船上的位置。通常情况下，同一目的地的集装箱，它们的大小或重量都属于同一等级，并且彼此相邻，这样可以简化它们的处理操作。基于此，我们把一个任务定义为一组根据某些特性所进行的操作。任务的定义是建立在集合层面的。例如，一个任务可以包括在某个海湾内进行的或是对属于同一组的集装箱所进行的装卸操作。因此，配载计划常常由几个任务组成。

本文讨论了岸桥调度问题（QCSP），其目标是确定分配的码头起重机的动作顺序，以便完成集装箱船的装卸任务。我们假定岸桥技术特性相似。此外，一个任务被认为是一组属于同一湾的集装箱船上的集装箱的装卸操作。该问题的目的是最小化整个集装箱船的服务时间（完工时间）。

为了解决岸桥调度问题（QCSP），我们提出了一种带有局部搜索的分布估计算法。该方案利用了关于该问题的先验知识，目标是达到高质量的解。此外还采用了一种新的重新启动策略，以防止搜索过早收敛，并引导它去向探索不足的区域。为了减少常规评价程序的计算负担，目标函数会被放松。最后，采用了一个自适应的停止标准，使搜索在恰当的时候结束。计算实验表明，所提出的方案的性能优于那些以前的相关的方法和其组成部分的适用性。Wilcoxon非参数检验（sheskin[ 35 ]）用来验证实验结果的相关性。

本文的主要贡献是提出了一种结合了局部搜索的混合分布估计算法来解决岸桥调度问题。与文献中提到的其他算法相比，该算法大大降低了计算时间，并能得到高品质的调度结果。该算法的效率为集装箱船舶管理做出了重要贡献，因为当许多不同的物流问题集成时，它可以整合更多的一般方法。问题的整合将最终导致开发一个更贴近实际情况智能系统。

本文的剩余部分的结构如下：第二部分概述了和QCSP有关的工作以及显著贡献，第三部分提供了QCSP的详尽描述，第四部分提出了一种结合了局部搜索的混合分布估计算法来解决岸桥调度问题，第五部分进行了计算实验，第六部分给出了主要结论和未来的工作展望。

二、文献综述

根据一个集装箱货轮的周转时间最低值，通过在集装箱末端安排一架港岸起重机，大量的调查得以引导。然而，考虑到集装箱组有单独的货轮和定义明确的，通过服务时间能大量提供的港岸起重机，只有少许研究可以开展实施.Kim和park运算出QCSP(码头装卸桥调度的问题)是一个混合型完整的程序设计模型。这篇论文基于研究空间的缩小以及目标功能价值范围的降低提出分支定界限算法来达到理想的计划。因为分支定界的高频率运算次数限制了他在可行方案中的应用，作者们也提出了一个贪婪随机自适应搜索算法，它可以通过更少的运算次数来获得高质量计划。

Moccia等人对于Kim 和 park提出的模型进行了更详细的分析，并指出这里存在各种情形，起重机之间会出现一些冲突。这篇论文提供了一种修改后的数学运算法则，为了克服论述的不足。同时，大量有效的不等式也被并入分支切割算法来解决大规模实例。运算结果可以论证相比于Kim和park提出的分支定界限算法，分支切割算法有更好的成效。

Sammarra等人将QCSP分为两个问题，一个是运送问题，来决定由单独的起重机配送的任务，另一个是安排问题，来计算任务的开启和结束次数。为了解决运送问题，开展了紧急搜索。全面考虑的地区建筑物运用已定的运动轨迹来减少通用计划的完工时间。

在搜索过程中达到计划使用析取图进行评价。紧急搜索的结果可以比得上moccia和联盟提出的分支切割算法。

bierwirth 和 meisel公开了由moccia等人提出的数学模型的错误，事实上就一切情况而言它不能探测起重机之间的计划冲突。一个关于QCSP的运算法则得到发展，两个已包括的任务之间有暂时性合适的距离。基于树型检索，他们提出一个启发性教学，UDS。 UDS探索出单向计划的空间，也就是说，初始复位后不改变移动方向的时间表，并且每一个岸吊具有相同的运动方向。UDS达到通过很短的计算时间在以往的工作中所使用的基准测试套件的最著名的时间表。试验在更复杂的情况中放大检查UDS的行为。在任何情况下，UDS可以在限制一个小时的计算时间内获得高品质的时间表。

Chung和Choy提出了一种用于QCSP的遗传算法，从最初的随机生成的人口，多个交叉和变异算子，以达到高品质的时间表。这项工作解决了只有有限的来自从文献的实例。尽管这项工作是比以前的分析更新颖，其作者不使用最后的数学公式（由Kim和park提出的），但是它建立于由Kim和park提出的模型和由moccia等人提出的改良版，因此，这项工作中有些计划是不正确的。

Legato等人对于QCSP中并入的码头起重机的准备时间及到期日期和起重机个体加工时间几个实际问题，提出了一种新的模型。本文由bierwirth和meisel提出一个关于UDS的延伸，称为LTM方法战略。新的边界和分支的标准的提出是为了加快搜索，同时考虑工程问题的新实践方面。此外，作者描述了一种基于拉格朗日松弛的方法，基于旨在降低计算限度的方法。最后，一个可信专用网（TPN）的方法决定了整体的集装箱船的服务时间，还有完成每个任务和码头起重机的时间。计算测试表明，该新方案的性能，克服了上述的问题。

Meisel和bierwirth提出了一个平台，通过基准测试套件的下一代，目的在于比较QCSP的优化模型和技术。该发电方案是基于无偏性和重复性的相似性原理和一组集装箱的服务参数。

Exposito等人在解决QCSP算法的同时研究EDAs的适用性。他们的研究是一个初步的工作，基于EDAs的框架，一些有用的一般准则被明确来达到设计一种优化技术的目的。与本文不同的是，他们的工作不包括任何杂交计划和重新启动策略。

值得一提的是，在近几年与QCSP有实际关联的几个变种在集装箱码头出现，他们中的大部分都与码头起重机的可用性有关。对此，迈泽尔提出码头起重机的时间可用性；即，码头起重机只能在事先确定的时间内进行操作。此外，摩纳哥和exposito等人的作品体现了优化技术，来解决QCSP的新变种：起重机的运动被限制在界限明确的地区码头。与本文件相反，他们追求的目标函数是基于得出一个时间表，可以完成即将到来的船的运行，只在给定的操作工作变化中。最后，在Chen等人的工作中要面对缩进泊位的QCSP。

三、问题描述

岸桥调度问题可以表述如下。令表示待处理的任务集合（对同一集装箱组的装卸操作），表示起重机的集合。在任务集合中，加入0和分别表示一艘集装箱船开始接受服务的时间和服务结束时间。因此，新的任务集合表示为，每个都有一个处理时间（）并且在船上有一个位置（用海湾编号表示）。因为任务可以在同一个区域内的不同的地方，并且有的任务必须在其他之前处理。例如同一个海湾内，卸载任务必须在装载任务之前处理。同时，位于不同的海湾的任务不能被同时处理，因为码头起重机因安全原因不能靠得太近。因此，用表示存在先后关系约束的任务对的集合，用表示不能同时进行的任务对的集合。注意到。在每一个集装箱湾内，优先关系完全决定了相应的任务的唯一处理顺序。

我们假定岸桥技术特性相似。它们移动速度为分隔间/单位时间，并且有相同的转运效率。每个码头起重机的位置是，最早能在准备时间后开始操作。此外，码头起重机必须从自己的初始位置开始，从左向右移动。起重机从初始位置移动到某一任务的位置所需的移动时间可以表示为。类似地，在两个分隔间，之间移动所需的时间可以表示为。此外，现有的码头起重机安装在一个沿码头的轨道系统内。几个码头起重机不能同时在同一个分隔间运行，而且它们不能互相交叉。也就是说，服务期间起重机必须保持一个安全的距离（以分隔间为单位），以防止它们相互碰撞。

QCSP的目的是确定每个任务的处理时间，使得虚拟任务的完成时间（即整体完工时间）最小。已经知道QCSP是一个 NP难的问题，完整的数学证明已由Bierwirth和Meisel给出。

Bierwirth和Meisel曾指出，只考虑单向排程解决QCSP是码头的一种普遍做法。这项策略可以显著减小搜索空间，并且在大多数情况下，它可以找到一个遵循单向策略的最优排程。因此，设计程序来探索单向排程是一种很有前途的快速获取近似解的方法。基于此，本文提出了一种结合了局部搜索的混合分布估计算法。搜索的目的是探索按预先设定的方向运动（从左至右或者从右到左）的解构成的解空间。有了这个目标，搜索过程必须被应用两次，即在每个案例中改变一次起重机的移动方向。

表1说明了一个小规模的QCSP实例的输入数据。它由10个沿集装箱船操作的任务和2个可用的码头起重机构成。对于每一个任务，其分隔间的位置和处理时间展示如下。此外，优先级和非同步约束也已事先约定。

表1 小规模的QCSP实例的输入数据

图1给出了该实例的图形化的解释。在每个分隔间内，相应的任务根据已定义的优先级关系排成自底向上的顺序。在本例中，分隔间1、3、4、6、7、8内至少有一个任务，而分隔间2和5内没有任务。由于优先级关系，任务1必须在任务2和3之前处理，任务2必须在任务3前处理，等等。

图1 表1中实例的图形化解释

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章