英语原文共 23 页

自动化集装箱堆场双轨道吊实时调度

Taejin Park · Ri Choe · Seung Min Ok ·

摘要：本文提出了基于启发式和基于本地搜索的实时调度方法，用于在自动化集装箱码头的一个箱区中工作的双轨道式龙门起重机（RMG）。当轨道吊完成工作时，这些方法会为给定的固定长度实时重新安排轨道吊。该问题的一个困难是有时需要执行额外的集装箱重新处理以完成所请求的工作，尤其是当其他集装箱堆叠在目标集装箱的顶部时。这些重新处理是轨道吊操作延迟的主要原因，导致自动导引车（AGV）或与起重机共同作用的外部卡车的等待时间延长。通过将重新处理操作视为我们解决方案中的独立工作，我们可以极大地促进两个轨道吊之间的协作。通过这种协作，两个轨道吊的工作量可以更好地平衡，并且可以更容易地避免干扰，从而最大化轨道吊的利用率。仿真实验表明，由于合作利用率的提高，自动导引车和外集卡的等待时间显著减少。

关键词：自动化集装箱码头；实时调度；轨道吊

1介绍

集装箱堆场轨道吊的吞吐量直接影响集装箱码头的质量控制效率，而质量控制效率被认为是集装箱码头生产效率的重要组成部分。然而，由于各种原因，通过自动导引车提供给轨道吊的服务经常被延迟。当一个轨道吊被要求去取一个被其他集装箱堆积在上面的集装箱时，在目标集装箱被抬起之前，目标集装箱顶部的集装箱必须被移动到其他地方。这些对其他集装箱的重新处理是造成堆场作业延误的主要原因。延迟还发生在轨道吊必须长途跋涉才能将容器转移到HP时，或者轨道吊遇到相互干扰的情况时。如果轨道吊以适当的顺序执行作业，这些延迟可以显著减少。

在本研究中，我们开发了一种双轨道吊工作在一个垂直铺设块的实时调度方法。我们假设两个轨道吊不能相互移动，并且轨道吊的操作没有不确定性。我们还假设外集卡的到达时间在实际到达一个箱区之前是未知的，而自动导引车的到达时间是由一个预定的时间表给出的。我们的调度目标是通过最大限度地提高轨道吊的利用率，使自动导引车的服务延迟和外集卡的等待时间最小化。可以在块中的任何时候请求新的作业，并且轨道吊的作业分配必须实时执行。提出并比较了两种调度方法:基于启发式的调度方法和基于局部搜索的调度方法。我们的方法在轨道吊完成任务后重新安排轨道吊。当一个轨道吊完成它当前的任务时，基于启发式的方法从请求的任务中选择一个，并将其分配给刚刚释放的轨道吊。该方法计算成本低，适用于实时情况。然而，由于其短视的性质，该方法不能提供一个真正有效的轨道吊计划。基于局部搜索的方法利用局部搜索算法来优化一个固定长度的轨道吊调度。通过同时考虑多个未来作业而不仅仅是下一个作业，基于本地搜索的方法比基于启发式的方法产生更好的调度，从而提高了轨道吊的利用率，并可能减少起重机的干扰。由于轨道吊通常需要几分钟来完成一项任务，因此该方法可以利用这段时间进行本地搜索。由于实时性的限制，前瞻视界的长度受到限制，使得搜索空间不会变得太大。

调度轨道吊的一个困难是处理重处理。如果我们将重新处理作为请求作业的一部分，轨道吊调度就会以效率为代价得到简化。另一方面，如果重新处理被视为独立的作业，它们可以分配给任何空闲轨道吊，并且可能在请求作业之前的任何时间执行。这可能有利于平衡轨道吊之间的工作负载，从而提高起重机的利用率。还有一种操作可以进一步改善负载平衡;这就是我们所说的重新定位。重新定位是指将出口或进口集装箱从原来的位置分别移动到离海滨或海滨港口更近的位置的操作。我们将重新处理作业和重新定位作业都称为辅助作业，因为它们不是显式请求的作业，而是空闲轨道吊可选执行的作业。

将辅助作业视为独立的作业，可以提高轨道吊作业的效率，同时使调度过程本身变得更加复杂。当这些额外的辅助作业被认为是独立的时，决策参数的数量在调度过程中增加。例如，当执行重新定位作业时，必须确定容器是否应该重新定位以及需要将其移动到何处。虽然基于启发式的方法不能处理这些决策参数中的大部分，但是基于局部搜索的方法可以通过采用适当的候选解的表示和解码方案来处理这些参数。通过仿真实验，比较了基于局部搜索的方法和基于启发式的方法的性能。由于很少有关于在垂直布局块中调度自动化双rmg的工作报告，因此基于启发式的方法可以为比较建立基线性能。

下一节详细介绍了集装箱堆场自动堆场调度系统的运行情况，并给出了调度双堆场调度问题的数学公式。第3节描述了我们的仿真系统，该系统考虑到轨道吊的状态、动作和可能的干扰来计算轨道吊的运动。第4节解释了基于启发式的起重机调度方法。第五部分介绍了基于局部搜索的起重机调度方法。第6节报告了仿真实验的结果，以评估我们的调度方法。最后，第七节提出了一些结论。

2 轨道吊调度问题

2.1轨道吊操作

自动化集装箱码头中的一个货舱通常配备两个大小相等的轨道吊。靠近海边箱区的一个称为海侧轨道吊，另一个称为陆侧轨道吊。由于这两个轨道吊不能互相移动，所以船舶作业分配给海边轨道吊, 外集卡作业分配给陆侧轨道吊。尽管有这样的作业分配，仍然会发生干扰。例如，当海侧轨道吊需要为装载操作提取一个出口集装箱时，如果该集装箱堆积在靠近箱区陆侧的位置，它可能会干扰陆侧轨道吊。图2显示了每个轨道吊的干扰概率分布在集装箱装卸发生的贝位。利用我们的仿真系统对这两条曲线进行了实证分析，如第三节所述。请注意，外集卡通过陆侧箱区携带的出口集装箱很可能堆放在陆侧箱区附近，否则陆侧轨道吊会干扰海侧轨道吊将这些集装箱转运到海侧区域。如果发生干扰，两个轨道吊中的一个必须让步，等待另一个完成它的工作。关于如何在调度轨道吊时考虑到这种干扰的进一步细节见第3节。

为了最大限度地发挥非交叉双轨道吊的性能，它们之间的合作是必不可少的。当工作负载集中于一个轨道吊时，希望另一个工作负载较轻的轨道吊帮助更忙的轨道吊。我们建议使用优先转售和优先重新定位作为轨道吊之间合作的有效手段。

装货或结转作业所花费的时间，不仅包括将目标集装箱转移到目标箱区所花费的时间，还包括在目标集装箱上方有其他集装箱时重新装卸所花费的时间。如果可以以某种方式提前执行重新处理作业，则可以在相当短的时间内完成请求的作业。另外，如果另一个轨道吊能够以更轻的工作量进行这种提前返工，则可以改善两台起重机之间的负载平衡，提高起重机的利用率。

由于这些模块是垂直于码头布置的，所以大多数通过一个模块的一端进入的容器会离开另一端。例如，通过陆侧箱区进入一个块的出口集装箱稍后通过海侧箱区取出。如果我们想节省陆侧轨道吊操作的时间，那么将进入的集装箱堆放在靠近陆侧箱区的位置是有利的。然而，当要求通过箱区海侧提取集装箱以便装载时，这会导致海侧轨道吊的旅行距离增加。此外，由于海侧轨道吊不得不向陆侧区域移动得更深，它更有可能干扰陆侧轨道吊。事先的重新定位有助于在很大程度上解决这个问题。如果一个闲置的轨道吊(海侧或陆侧)可以在实际装载作业之前的适当时间进行重新定位，不仅可以更好地平衡两个轨道吊的整体工作量，而且还可以大大降低起重机干扰的概率。

为了支持两个轨道吊之间的合作，当一个装载或结转作业被要求取回一个容器时，重新定位和重新打包作业应该作为额外的独立作业生成。注意，没有为卸载和携带作业生成这样的辅助作业。当根据请求生成用于装载或携带轨道吊的主作业时，还将为该集装箱生成重新定位作业。然后，为堆在目标集装箱之上的集装箱生成重新处理作业，除非已经为其他一些请求生成了这些作业。图3显示了一个示例，展示了当按给定顺序取出三个集装箱C3、C1和C5时，应该如何生成作业。主要的工作由阴影圈来区分。Li、Oi、Ri和Pi分别表示与集装箱Ci相关的装载、结转、重新处理和重新定位作业。当需要装载集装箱C3时，将生成主作业L3和辅助作业P3、R2和R1。作业L1和P1是在再次请求集装箱C1加载时生成的。然后，当集装箱O5被请求执行时，将生成作业O5、P5和R4。由于RMGs只能在堆场的顶部获取集装箱，因此通过存储目标集装箱的堆场的配置对这些作业施加了一些优先约束。例如，在执行O5和P5作业之前，应该先执行作业R4。图3b中的箭头表示这些优先约束。

与主要作业L和O分别只分配给海边RMG和陆上RMG不同，辅助作业R和P可以分配给这两个轨道吊中的任何一个，从而实现了两个轨道吊之间的合作。例如，在图3中，当海侧轨道吊忙于装载作业L1时，如果陆侧轨道吊分配并执行作业R2,海侧轨道吊可以更早地完成L3。同样，如果海侧轨道吊繁忙时可以由陆侧轨道吊执行重新定位作业，那么海侧轨道吊较晚的装载作业可以在较短的时间内执行，因为旅行距离缩短了。

然而，这种合作并不总是有利的。分配给主要任务的轨道吊之外的轨道吊的辅助任务可以增加干扰的可能性。假设图3中的集装箱C1、C2和c3堆放在贝 5处。由图2可知，海侧轨道吊作业R2的再处理作业干扰概率约为0.01，而陆侧轨道吊作业R2的再处理作业干扰概率增加到0.37。此外，重新定位作业实际上会创建额外的拾取和下拉操作，如果不重新定位就直接从块的原始位置检索目标集装箱，则不需要这些操作。因此，辅助作业和协作的需要应该通过调度算法仔细确定。

调度轨道吊的问题类似于车辆路径问题。在我们的问题中，两辆轨道吊(车辆)用于从集装箱(货物)的初始位置到交付位置的运输。每台轨道吊一次只能运送一个集装箱，有时一个集装箱可以由辅助作业存储在临时位置，最终由主作业移动到交付位置。对于我们的问题，假设主要工作所需要的辅助工作和轨道吊之间合作所需要的辅助工作都已经生成为独立的工作，并且已经确定了主要工作的交付地点和辅助工作的临时位置。在我们的问题公式中，根据一个顶点对应于拾取或下拉操作的图，使用了以下符号:

顶点iisin;D1表示容器ci的主作业在交付位置的下落操作，顶点(n i)isin;P1表示容器ci初始位置的上落操作。注意ci = cn i。从ci可以直接搬到一个临时位置从初始位置的辅助工作的主要工作,顶点(n i)的传感器操作可以辅助工作而下降操作的顶点我应该是主要的工作。顶点jisin;D2和(n j)isin;P2是容器cj辅助作业在同一临时位置上的操作。注意ci = cn j, lj = ln j。虽然顶点j是辅助作业的下拉操作，但顶点(n j)是cj的另一个辅助作业或主作业的拾取操作。注意顶点(n j)的拾取操作不能与顶点j的辅助操作相同。

由于除了主作业之外还有两种类型的辅助作业，所以一个容器最多可以移动三次，直到它在交付位置被放置为止。这意味着一个容器最多可以有三个拾取点和三个下拉点。图4显示了顶点之间的弧和优先约束，其中iisin;D1, j, kisin;D2， (n i)isin;P1， (n j)， (n k)isin;P2。作业对应于从拾取顶点到下拉顶点的弧。例如，arc (n i, j)是将ci从初始位置移动到临时位置的一个可能的辅助作业(例如重新处理作业)。rc (n j, k)是将ci从之前的临时位置移动到另一个临时位置的另一种可能的辅助作业(例如重新定位作业)。注意，任何弧(n i, i)、(n j, i)和(n k, i)都可以成为容器ci的主要任务。哪个(n i), (n j)和(n k)真正成为主要工作取决于的皮卡顶点的相对顺序访问的三个顶点下降,j和k。自从ci从初始位置到交货地点,顶点(n i)访问第一个顶点,我最后一个在六个顶点,顶点(n i)和我完全应该去一次。然而，辅助作业只是可选的，因此顶点j、k、(n j)和(n k)可以访问一次，也可以不访问。如果arc (n i, i)是ci的主要作业，则从其初始位置直接移动到交付位置，而不需要任何中间辅助作业。一旦一个容器被移动到一个临时位置，它就必须在相同的位置被取走。因此，如果访问顶点j或k，则必须在访问这六个顶点中的任何一个之前访问其对应的拾取顶点(n j)或(n k)。此约束由图中的虚线箭头表示。注意，虚线箭头不是弧，因为它不代表作业。虽然没有显示在图中，但是下拉顶点通过外弧线连接到另一个容器的所有拾取顶点，而拾取顶点通过外弧线连接到另一个容器的所有拾取顶点，拾取顶点通过内弧线连接到另一个容器的所有拾取顶点。

其中M是一个很大的正数。

目标函数(1)最小化加权和自主移动小车的延迟时间和等待时间的ETsalpha;1和alpha;2反映的相对重要性船工作,等工作,分别。自船工作被认为是更重要的比等工作,? 1通常大于多少? 2。约束条件(2)和(3)规定每个顶点iisin;P1cup;D 1cup;{2n 1,2n 2}必须恰好访问一次，每个顶点iisin;P2cup;D2可以访问一次，也可以不访问。约束条件(4)和(5)保证起重机k的路径从顶点2n k开始，终点2n 3，约束条件(6)保证流量守恒。根据约束(7)，访问临时位置的下拉顶点后，应先访问临时位置的拾取顶点。约束(8)表示容器堆叠配置施加的优先约束。约束(9)确保完成时间与旅行和操作时间一致。根据约束(10)，海边HPs上agv的操作只能由海边RMG来处理，陆上RMG上ETs的操作只能由陆上RMG来处理。约束(11)表示agv和ETs的操作只能在车辆到达后开始。

轨道吊调度问题具有不确定性和动态性。对外集卡操作的请求是不可预测的，因为对外集卡的到达时间表知之甚少。虽然每艘船都有装货/卸货计划，但是由于码头吊车作业的延误以及自动导引车之间的干扰等原因，自动导引车到达箱区海侧的时间仍然存在不确定性。然而，我们假设调度问题是静态的在一个前瞻性的地平线内，并解决了它的船舶作业在地平线内和外集卡作业，其车辆已经到达箱区之前调度过程开始。因此，每当发生更改时，例如将新作业添加到作业列表中，或者AGV延迟到达箱区，都需要重新解决该问题，因为先前解决方案的最优性不再适用。然而，在我们的方案中，只有当RMG完成一个任务时，才会重新构建一个面向未来的时间表。在重新调度间隔期间发生的任何更改都将在该间隔结束时执行后续调度时反映出来。

采用混合整数规划和分枝定界算法等精确方法进行优化，由于不能满足实时性的要求，在实际应用中是不可行的。如果T是轨道吊执行一个作业所花费的平均时间，那么作业分配的决策必须平均在T /2内做出，因为有两个起重机要调度。在一个真正的集装箱

资料编号：[5419]