英语原文共 15 页
基于集束搜索的堆场集装箱翻箱操作优化
摘要
集装箱翻箱问题（CRP）涉及用最小的翻箱次数检索集装箱堆场的全部集装箱。集装箱翻箱问题是一个非确定性多项式难题（NP-hard problem），以至于在合理的计算时间内无法通过精确的求解方法求得大规模实例的最优解。本文提出了一种嵌入启发式算法的集束搜索（BS）算法来评估这些问题。所提出的集束搜索在基准实例上进行测试，并与文献中的其他主要启发式方法进行比较。计算结果表明，光束搜索算法与其他启发式算法兼容，并且可以在短时间内获得良好的解决方案。
1.介绍
近来，对于海运集装箱的需求增加导致了许多巨型集装箱船的建设，其中许多能够运载超过18,000个20英尺当量单位（TEU）的集装箱。集装箱码头在处理这种巨大交通状况时面临的挑战迫使其制定有效的战略提高码头生产力，降低运营成本。
本研究从集装箱堆场翻箱的角度考虑卸货问题。 容器通常以堆栈形式存储，以最大化空间利用率，特别是在存储空间有限的码头中。如图1所示，通过集装箱垂直堆叠获得堆栈。 连续的几排堆栈形成一个隔间，隔间并排放置以形成集装箱块。
翻箱涉及集装箱从一个堆栈移动到另一个堆栈，每当有容器位于所需容器（最高优先级）的顶部时，必须操作该容器。我们称此立即需要的容器称为目标容器。翻箱操作无法避免，因为容器的位置不能始终根据他们的检索优先级进行安排。出口集装箱的检索优先顺序取决于它们在船舶上的装载顺序。然而，运输出口集装箱的外部卡车随机地到达集装箱码头，因此，集装箱不一定根据装载顺序放置在舱内。另一方面，航运公司在出口集装箱到达时提供的存放计划可能不准确或改变。显然，翻箱是非增值活动，必须将其最小化以提高集装箱码头的运营效率并提高客户满意度。在本文中，我们研究了出口集装箱之间的关系问题，集装箱必须根据船舶的装载计划以预定的顺序检索。
根据需被重新定位集装箱的移动方式，卸载问题可以被分类为受限或不受限制两类。在受限制的情况中，只能重新定位目标容器上方的阻塞容器。另一方面，在不受限制的情况中，允许位于其他堆叠的容器的自由移动（或清洁移动）。 本研究的重点是受限情况，其中集装箱按照预定顺序检索，并且重新安置次数最少。
为了处理受限制情况下的重定位问题，我们首先提出一种新的启发式方法，通过考虑目标容器上方的所有阻塞容器来估计CRP的上限。 此启发式算法与基准实例上的其他最先进算法进行了比较。 启发式嵌入在集束搜索（BS）算法中作为评估启发式。 集束搜索的结构类似于树搜索算法，但只有允许的节点才被保留在搜索程序中。根据提出的评估试探法选择允许的节点，该评估试探法确定具有可变序列的重新定位的容器的位置。 BS的性能通过文献中的基准实例的实验来验证。
本研究的其余部分安排如下。第2节中进行了相关工作的回顾。第3节定义了容器重定位问题。 第4节介绍评估启发式，第5节描述了嵌入在第4节的评估启发式中的集束搜索方法。第6节介绍了从各种场景中得出的实验结果。 最后，在第7节中，我们总结了我们的发现。
2.相关文献
自20世纪80年代以来，集装箱码头的集装箱搬迁引起了相当多的关注。关于集装箱搬迁问题的相关问题的回顾可以在Carlo（2014年）、Lehnfeld和Knust（2014年）等人的文章中找到。前一篇文章重点介绍了存储问题的布局，材料处理设备和其他特性。后一篇文章回顾了有关装载和卸载操作的优化问题。 Caserta等人（2011a）对海运集装箱码头集装箱的重新装卸提供了一个全面的总结。我们可以参考上面的文章了解详情。
Kim（1997）提出了一种方法，用于在检索特定容器时评估预期的重定位数。该方法可以解决堆栈数量范围从2到10以及层数为4到12的问题。Kim和Kim（1999）通过根据隔离政策分配进口容器来扩展这项工作，其中集装箱从船舶中卸载到空槽为止。 他们将问题定义为搜索堆叠高度，从而最大限度地减少预期的重新定位次数。两个数学模型被制定，一个用于进口集装箱的循环到达率，另一个用于随机到达率。为了最小化一个出口集装箱堆场的翻箱数，Kim等人（2000）在每种类型的到达概率事先已知，并在整个卸载过程中保持稳定假设下，根据其权重对指定集装箱的优先级进行分类。他们提出了一种动态编程方法，通过最小化预期的翻箱次数来优化堆叠过程。 张（2010）等人纠正了Kim等人推导出的模型转换中发现的错误（2000年）。
Murty等人（2005）为香港国际货柜码头（HIT）提供决策支持系统（DSS）。 使用称为重新洗牌索引（RI）的简单规则解决了进口集装箱安置中的重新定位问题。Yang和Kim（2006）提出了翻箱问题的一般概念。 但是，他们假设每当翻箱时，物品将永久地从存储区域移除。
Kim和Hong（2006）是集装箱堆场卸货问题的早期研究者之一。他们的目标是在必须根据预定优先级检索海湾中的所有集装箱时最小化翻箱数。他们提出了一种分支定界算法和一种启发式方法来估计检索过程中预期的额外翻箱数。Wan等人（2009）为检索问题制定了整数规划模型，并基于能够有效获得近似最优解的模型开发了一种启发式算法。后来，Wu等人（2010）开发了禁忌搜索算法，在该算法中，解决方案的长度可变。将计算结果与小规模问题的分支结果进行了比较。 Wu和Ting（2010）通过考虑与先行机制（RIL）打破关系扩展了Murty等人（2005）的重新洗牌指数启发式。他们还开发了一个简单的分支和界限来比较新启发式的效率。 卡塞塔等人（2011b）使用一种启发式启发式处理CRP，称为走廊法（CM），它基于动态编程算法对解决方案空间进行额外限制。它仅探索了当前隔间配置的有限邻域（或走廊）。
朱等人（2012）提出了针对受限和非限制问题的迭代深化A 算法（IDA）。 还开发了几种用于生成可行解和两个下界的启发式算法作为IDA的子例程。Caserta等人（2012）通过将CRP转换为NP完全的互斥调度（MES）问题，证明了翻箱问题是NP-hard的。 他们还提出了限制性CRP的启发式算法，以及两种数学模型：BRP-I和BRP-II，分别用于无限制和限制的重新安置问题。 Expoacute;sito-Izquierdo等人（2014）开发了一种A算法，以获得限制和非限制CRP的最优解。他们还提出了一种特定领域知识的启发式算法，以便与现有方法相比有效地获得良好的解决方案。
Forster和Bortfeldt（2012）解决了无限制的集装箱翻箱问题，其中集装箱被归类为单独的组和给定组中的每个容器具有相同的检索优先级。 提出了下限和树搜索启发式来处理该问题。 Petering和Hussein（2013）提出了一种改进的整数规划模型，称为BRP-III，对于无限制问题具有较少数量的决策变量。 尽管BRP-III提供了较低的下限，但它可以通过分支定界算法比BRP-I更快地实现最优解。 作者也扩展了Caserta等人启发式，开发了一种称为LA-N的前瞻性启发式算法。（2012年）。 Jin等人（2015）考虑了一组容器的无限制翻箱问题，其中同一组中的集装箱具有相同的检索优先级。 作者以贪婪的方式通过前瞻性启发式解决了这个问题。
最近的几项研究为限制性问题提供了算法。 Jovanovic和Voss（2014）扩展了Caserta等人开发的启发式算法，提出了一个链条启发式算法（2012年）。 他们的方法进一步考虑了下一个容器重新定位顶部容器时需要重新定位。 Zehendner和Feillet（2014）基于Caserta等人提出的BRP-I，提出了限制性重新定位问题的分支和价格算法。（2012年）。 应用列生成以克服BRP-I的缺点，随着问题的大小增加，需要大量的决策变量。 Expoacute;sito-Izquierdo等（2015）研究了受限制的集装箱搬迁问题的确切方法。 然后提出改进的配方来固定由Caserta等人开发的BRP-II模型。（2012年）。 此外，他们还提出了一种基于分支和边界的方法，与解决BRP-II模型相比，它可以显着缩短计算时间。
一些研究考虑了搬迁问题的延伸。 Lee和Lee（2010）考虑了双目标容器检索问题，该问题最大限度地减少了起重机处理所需的运动次数和时间。在检索过程中，容器的重定位被建模为多个阶段并且迭代地解决。他们提出了一种三阶段启发式算法，其中包含了基于优化软件CPLEX的最后两个阶段中包含的两个优化模型。 Zhao和Goodchild（2010）讨论了卡车到达时间信息对减少集装箱搬迁操作的影响。仿真结果表明，卡车到达终端信息的小幅改进可以显着减少码头的集装箱搬迁。 Uuml;nluyurt和Aydin（2012）通过两个目标处理搬迁问题：最大限度地减少搬迁次数和搬迁次数乘以起重机的行程距离。他们还提出了两种启发式方法，一种是基于Kim和Hong（2006）的方法，另一种是基于容器检索优先级的差异。
Rei和Pedroso（2012）考虑了搬迁问题的延伸，其中容器的到达时间和出发时间是事先知道的。 还提出了三种贪婪的建设性启发式方法来增强其实用性。 Akyuz和Lee（2014）为动态容器重定位问题（DCRP）提出了整数规划模型和波束搜索启发式算法，其中使用各种启发式方法来提供波束搜索的上限和下限。Ji等（2015）考虑了船舶和船厂的积载计划，并整合了装载顺序和重新处理策略。为解决这一问题，开发了三种重新处理策略的数学模型和遗传算法。 林等人（2015）扩展了Lee和Lee（2010）提出的无限制问题，该问题考虑了起重机的移动次数和工作时间。 他们提出了一种基于关于运动次数和工作时间的指数的启发式算法。 唐等人（2015）改进了Wan等人提出的数学模型（2009）并提出了五种启发式方法来解决它。 开发了离散事件仿真模型来测试启发式的性能并分析最坏情况的性能。
该研究考虑了受限制的容器重定位问题（CRP），涉及在检索过程中为重新定位的容器选择适当的槽，以使重新定位的总数最小化。 采用波束搜索（BS）算法来解决该问题。 波束搜索类似于分支界限以及广度优先搜索。 但是，每个级别中只有少数有希望的节点被保留用于进一步的搜索过程。 还提出了两种启发式方法来确保有效的BS节点选择。
3.集装箱翻箱问题
集装箱翻箱问题考虑到在集装箱海湾中最初分配了N个集装箱，并且每个容器具有预先已知的不同检索优先级。 该问题涉及通过遵循检索优先级来最小化从海湾检索集装箱时的翻箱总数。 堆场起重机将集装箱重新定位到同一海湾中的堆叠要快于不同海湾中的堆叠。 庭院起重机使用提升小车在同一个海湾中处理容器; 但是，它必须前进和后退才能到达不同海湾的集装箱。 因此，本研究仅考虑单个海湾内的翻箱问题。
在本文中使用的术语定义如下。在中立即检索的容器称为目标容器，包含目标容器的堆栈称为源堆栈。 源堆栈中目标容器上方的容器称为阻塞容器，必须将其重定位到其他堆栈以允许访问目标容器。 放置重定位容器的堆栈称为目标堆栈。 删除目标容器后，具有最高检索优先级的下一个容器将成为新的目标容器。程序重复检索，直到所有需要的容器从海湾检出。
图2中的示例示出了图2（a）中具有二维渲染海湾的重定位问题，其中列和行分别表示堆栈和层。方块表示容器，方块（容器）内的数字表示其检索优先级。在本文中，分配给容器的数字的值越小，检索优先级就越高。因此，要取回的第一个容器被指定为容器1.在该示例中，两个阻塞容器位于目标容器（容器4和5）的顶部。需要重新定位才能释放目标容器。在这种情况下，这涉及将阻塞容器从堆叠2移动到堆叠3，并且可以从隔间取回容器1（图2（a）-（c））。图2（d）显示了在取回容器1之后具有新目标容器（容器2）的配置。对剩余容器应用类似的程序，直到隔间为空。在最后阶段（图2（f）），在重新安置集装箱5之后不需要重新安置，并且重新安置的总数是4。
在该问题中，进行以下假设：
1.所有容器的尺寸都相同。
2.给出了托架中的堆栈W和层H的数量。
3.重新安置的容器只能在同一个托架内移动。
4.预先知道托架的初始堆叠配置和每个容器的检索优先级。
5.在检索过程中没有新容器到达。
6.只有放置在目标容器上的阻塞容器可以重新定位
由于我们专注于检索出口集装箱，因此我们不会像第五个假设那样将新集装箱装入海湾。 最后的假设在实践方面是合理的，它将重定位仅限于源堆栈处的阻塞容器，这使得这成为一个受限制的问题（Zehendner和Feillet，2014）。 在没有假设A6的情况下，相反地，这呈现出不受限制的问题，这允许在释放目标容器的过程期间在其他堆栈而不是源堆栈处重新定位容器。 由于重定位问题是NP难的（Caserta等，2012），因此无法在合理的计算时间内使用精确求解方法（例如分支定界）来解决。为克服这一困难，本研究采用了建设性启发式算法和波束搜索算法。
4. 评估启发式
嵌入在波束搜索中的启发式是影响解决方案质量的主要因素。 启发式算法基于预定义规则来确定重定位容器的目标。 对启发式算法的准确评估可以有效地指导波束搜索以获得良好的解决方案。 在本节中，将在以下小节中介绍为解决容器重定位问题而开发的两种启发式方法。
4.1 最小的差异启发式
本文提出了一种最小差异启发式（SDH），它采用一种简单的规则来考虑两个容器之间检索优先级的差异。 Uuml;nluyurt和Aydin（2012）以及Caserta等人（2012）也提出了同样的想法。 本研究中介绍的SDH类似于Caserta等人的启发式算法。（2012年）。 它为我们在下一部分开发一种新颖的启发式提供了基础。 我们将此启发式称为最小差异启发式，因为目标堆栈是根据重定位容器与堆栈中容器的最高优先级之间的优先级的最小差异来选择的。 考虑一个必须重新定位的具有检索优先级b的阻塞容器，堆栈s的索引DI由容器b与堆栈中最高检索优先级（即f s）之间的检索优先级的差异来定义，如公式1所示。（1）。 如果堆栈为空，则f s设置为N 1。
重新定位容器的目
资料编号：[4852]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
