[译]AGV系统区域控制循环死锁的预测与避免

自动导向小车(AGV)在自动化物料搬运系统、柔性制造系统甚至海港集装箱搬运应用中正变得越来越流行。它的性能直接影响整个系统的效率。死锁的形成是一个严重的问题,因为它拖延了AGV系统。本文的目的是为集装箱港口作业开发一种有效的AGV死锁预测和避免算法,死锁在广义上是指系统中至少有一部分发生死锁的情况。多数情况下,系统可能会失速(效率低),而这些情况大多可以通过控制和导航系统来避免。本文讨论了一种有效的预测和避免AGV系统大规模死锁的策略,目前已有多种死锁检测算法,但这些方法主要适用于网络布局,简单地、仅使用少量AGV的制造系统。本研究中的AGV系统布局复杂,包含近80辆AGV。利用Automod仿真软件实现了该方法,并给出了该方法的性能。仿真结果表明,该方法能够检测并避免所有可能的死锁情况。此外,该策略计算效率高,能够在1.5秒的采样时间内为所有车辆提供运行决策。


Rajeeva Lochana Moorthya, Wee Hock-Guana, Ng Wing-Cheongb, Teo ChungPiaw
Singapore-MIT Alliance, Singapore
University of Hong Kong, China
Department of Decision Sciences, National University of Singapore, 15 Law Link, Singapore 117591, Singapore
Received 20 February 2001; accepted 28 August 2002


1. 简介

全球化步伐的加快,大大增加了对物流和运输的需求,特别是对集装箱海运的需求。随着全球集装箱运输量的增加,集装箱码头已成为物流网络的重要组成部分。集装箱码头是集装箱从一艘船转运到另一艘船或转运到铁路和卡车等其他运输方式的枢纽。由于每个制造商都在缩短上市时间、降低库存成本和更好的客户服务方面相互竞争,因此对高效终端的需求比以往任何时候都更为重要。一个高效的集装箱码头是一个允许快速转运集装箱进出船舶的码头。这种快速的操作对承运人和港口都很重要,因为它提供了显著的操作效率,而港口每天可以处理大量的船只。不幸的是,许多码头现在都在(或接近)满负荷运转,政治和商业部门对增加码头吞吐量和(特别是)减少港口船舶周转时间施加了巨大压力。在大多数情况下,这需要发展先进的、高度自动化的集装箱运输系统,使集装箱能够在码头区域内高效地移动。

自1993年以来,荷兰的大型集装箱码头一直在运营自动导向车辆(AGV)车队,在位于新加坡的世界最大集装箱码头,其总部运营商计划在其新的高度自动化的集装箱码头内运营一支(120–150辆)AGV车队。大型集装箱码头的AGV运营规模通常非常大,灵活自由的AGV在复杂的车道和交叉口网络中移动(见图1)。AGV在码头区和集装箱储存区之间运输集装箱。这些双向的AGV拥有先进的导航系统,引导它们通过复杂的网络,将集装箱从多个出发地高效地运输到多个目的地。

图1. AGV系统布局的一部分,显示一个泊位。

常规的运行规划和控制方式在该系统中存在以下问题:AGV向交通作业的调度、AGV的路由以及车道和交叉口网络中的交通控制。船舶和卡车装卸作业产生的运输作业被分组在一起,并通过AGV调度模块分配给一个可用的AGV。然后,调度的AGV将被指示遵循路由模块确定的路线,该模块包含从作业起点到目的地的车道和交叉口的详细信息。为了行车安全,将复杂的车道和交叉口网络划分为大量的区域,并采用限制性的车辆运动规则。在每个区域内,任何时候都只允许一个AGVis占领;因此,任何其他想要使用该区域的AGV必须在外面等待移动许可。因为AGV系统的吞吐量取决于每个区域的大小;区域越大,速率越低。通常,区域的最小尺寸大约等于通过使用正常控制的制动机构使AGV从最高速度停止所需的距离,并且停止AGV所需的时间小于10 s。

由于码头作业的动态性,如AGV或集装箱装卸设备的故障、集装箱装卸的意外延误等,AGV的计划路线可能会干扰另一辆AGV的路线,从而导致相关运输作业的完成时间延误。例如,当AGV转弯时,如果在一定距离内有车辆,则可能导致碰撞(图2)。与不存在物理约束的通信网络中的路由系统相比,这是不同的。这种情况将由导航系统处理,并且在特定车辆移动之前,还需要检查许多其他状况。

图2. T0时刻的位置(左)T1时刻的位置(右)

在某些严重的情况下,可能会形成死锁,从而导致参与死锁研磨的AGV停止。如果没有某种形式的干预,每个AGV都将永远等待指令继续。agv系统中的死锁主要是由于用于避免车辆碰撞的区域划分策略造成的。对于特定的AGV组,当每个AGV的计划路线中的下一个移动区域被组中的另一个AGV阻塞时,形成死锁(参见图3)。

图3. 区域控制AGV中阻塞现象的说明。

死锁的出现会降低系统的效率。因此,需要监控每辆AGV的运动情况,并预测死锁形成的可能性。预测的频率取决于每个区域的大小、AGV运动学特性以及向AGV发出新的运动指令的频率。

在一个典型的AGV系统中,每辆AGV都装有大量的传感器,定期采集AGV的位置、速度、车辆行驶方向、AGV附近的图像等基本信息,经车载计算机处理后,通过车辆的通信设备发送到AGV中央控制系统。周期通常很短(小于2秒),因此中央控制系统有准确的信息和足够的时间对车辆故障等意外事件作出反应。中央控制系统收到信息后,必须决定是否向每辆AGV发出新的移动指令,以调整其航向或速度。在做出这样的决策时,需要一个有效的算法来预测每个周期中死锁形成的可能性。

本文主要研究集装箱码头环境下AGV系统的死锁预测问题;因此,将系统的其他方面视为给定的输入。本文的目标是开发一种有效的死锁预测算法和避免策略。第二节回顾了死锁预测的相关工作。第三节提出了一种新的预测算法和一种有效的避让策略。第四节给出了详细的数值结果,最后一节对全文进行了总结。

2. 问题陈述和文献综述

这些问题是AGV系统中可以形成的几种死锁形式。根据车辆的布局和路线,根据AGV的控制逻辑,可能存在多种形式的死锁。在本节中,将讨论三种最常见的死锁类型,包括死锁的一般形式,即循环死锁,其中车辆形成对区域请求的循环。

2.1. 交叉道死锁

第一种死锁是两辆车想换车道。图4中示出了这一点的图示。
例如,假设AGV1想要进入工作车道,AGV2想要进入行驶车道。如果AGV2离交叉口太近,可能会出现AGV1无法转向工作车道的情况,即AGV1在转向工作车道时可能会撞到AGV2。车辆上的导航系统将通知AGV1停止。这对于AGV2也是一样的,这会导致两辆车等待对方移动,但没有人可以移动。
这种死锁可以通过智能导航系统来解决,即决定车辆在等待时应该停在哪里。安装更多的传感器来告诉车辆在哪里停车可以做到这一点。

图4. 两辆车交叉进入对方车道时死锁的图示。
2.2. 车间死锁

另一种被称为车间死锁的死锁(Chang等人,1997年提出)可能发生在图5所示的超载车间中,当车辆不小心调度时。在集装箱堆场中,每个储存区域的容量有限。如果所有存储空间都用完了,则可能出现如图5所示的情况。它显示了一个车间死锁,AGV1希望卸载其集装箱,但存储空间已达到极限,AGV2正在等待提取集装箱,导致两辆车都在等待。起重机正在吊运集装箱,不能被派往AGV1吊运集装箱。
为了防止车间死锁,可以同时实现三件事。首先是路由。在图5中,只有一条车道可供车辆移动。因此,可以如图6所示提供附加车道和车道之间的交叉口。
如Chang等人(1997)所解释的,这些额外的通道加上集装箱在整个堆场的良好分配方法和银行家算法可以防止车间死锁的发生。在本文中,由于基于新加坡的终端算子有自己的分布算法,保证了空间约束不会太紧,因此没有实现对这种死锁形式的预测。

图5. 一种车间死锁
图6. 避免车间死锁
2.3. 循环死锁

最后一个死锁是最常见的,如图7所示的循环死锁。当有一系列车辆请求区域(资源)时,这种形式的死锁就会发生,这些车辆以这种方式请求区域的循环请求。这种形式的死锁预测在车辆的控制系统中是不可用的。为了解决这一问题,需要一种预测和回避算法。

图7. 区域控制AGV系统中的循环死锁
2.4. 循环死锁的预测和检测方法

在现有文献中,Hyuenbo等人(1995)、Lee和Lin(1995)、Viswanadham等人(1990)、Yeh和Yeh(1998)讨论了预测和检测循环死锁的方法。Coffman等人(1971)和Gold(1978)的工作包含了通信网络中死锁形成的主要理论结果。文献中提到的预测死锁的方法要么复杂,要么计算量大。对于我们的例子,预测这种死锁的计算时间必须很小,因为控制系统的每个采样时间都在1.5–2 s的范围内。接下来,本文讨论了文献中提到的方法为什么不可行。

Lee和Lin(1995)以及Viswanadham等人(1990)使用petri网理论来预测和避免FMS和AGV系统中的循环死锁。整个网络必须以矩阵的形式表示。我们实现的AGV系统由1370个节点和几千个弧组成。矩阵的维数约为几百万个元素,这将占用巨大的内存空间。为了检测循环死锁,需要进行矩阵向量运算。对于我们的实现,矩阵太大,每次迭代的计算量是O(mn),其中n是节点数,m是网络的弧数。因此,采用这种方法来解决这个问题是不可行的。

Hyuenbo等人(1995)使用图论来检测即将发生的死锁。为了做到这一点,必须找到作者Reveliotis中定义的有界电路。由于网络过于复杂,我们的网络中有界电路的数目非常大,因此也放弃了这种方法。

Yeh和Yeh(1998)通过识别动态有向图中的循环,讨论了一种非常有效的死锁预测策略。虽然目前工作的动机源于Yeh和Yeh(1998)提出的算法,但没有提供一个鲁棒(健壮)的回避策略。在下面的讨论中,我们证明了预测算法的性能取决于网络结构,对于复杂的AGV系统网络,一个好的回避策略对于提高吞吐量至关重要。

2.5. 多循环死锁(Multi-cyclic deadlock)

在仿真研究过程中,发现了一种改进的循环死锁形式。多循环死锁是由于多个循环的拥塞和合流而形成的。任何循环检测算法都无法预测这种情况,因为每个循环本身并不完整。有关多循环死锁的更多细节,请参见第3节。

据作者所知,上述方法都没有在实践中实现,更不用说在实际集装箱码头环境中运行的方法了。此外,在检测多循环死锁情况方面还没有已知的工作,如果不检测到这种情况,将使整个AGV系统失速。

3. 死锁预测算法

针对现有方法的不足,本文提出了一种简单有效的方法,较好地解决了这一问题。其主要思想是在一个区域步长后动态地投影每辆车的位置,并从新的位置检测循环形成。这种方法的主要优点是循环检测算法依赖于系统中AGV的数量,在这种情况下,AGV的数量远小于终端布局中的区域数量。

3.1. 阶段1:循环死锁预测

图8所示的流程图说明了算法的阶段1是如何工作的:

  • 步骤1:提取即将进入新区域的选定车辆(如Vi)的下一个区域的位置(Lp)(即控制点)。对于每个采样时间,即1.5–2 s,检查车辆是否移动到新区域。如果有,则选择车辆,以便对其下一个区域步骤进行死锁预测。
  • 第2步:检查下一个区域(Lp)是否被其他车辆占用。如果车辆被占用,则返回“车辆被阻塞”(A),否则,转至步骤3。
  • 第3步:提取Vi的下2个区域(即“下一个”区域)的位置(Lq)。
  • 步骤4:检查是否有其他车辆占用Lq:如果没有占用,返回“车辆可以安全行驶,未预测死锁”(B),否则,转到步骤5。
  • 步骤5:提取占用Lq的车辆的下一个区域位置(Lr)并将Lq更新到位置Lr:步骤6:检查Lp是否等于Lq:如果它们相等,则返回“车辆无法安全行驶,预测死锁”(C),否则,返回步骤4。
图8. 用于预测死锁的算法流程图(一个区域的步骤)。

图9中的示例示出了四个车辆AGV1–AGV4,阴影节点是车辆的位置。每个节点中的弧都指向车辆路线的下一个位置节点,例如AGV4的下一个位置将是节点2。按照给定的一个区域步骤死锁预测算法,假设AGV1即将进入一个新区域,即节点2。它检查节点2是否被占用(此处,节点是空闲的)。然后检查其“下一个”节点,即节点3。它发现AGV2正在占用该节点,因此,检查AGV2的下一个节点,即节点4。发现AGV3正在占用节点4,然后它继续检查AGV3的下一个节点,即节点5,并发现AGV4正在占用该节点。最后检查AGV4的下一个节点,即节点2是AGV1想要进入的同一个节点。如果AGV1被允许进入node 2,那么将会有一个循环的资源请求,这意味着一个循环死锁。因此,算法将返回一个值,表示在下一步预测死锁。当预测到死锁时,系统可以选择重新路由所涉及的agv或选择等待直到死锁被清除。本文以后者为主要研究对象,研究死锁预测算法的有效性,将路由选择过程作为一个黑箱过程,港口集装箱运营商可以随时改变。

图9. 一个区域步骤死锁预测的图示。

假设V表示整个AGV系统中的车辆数。在最坏情况下,每个循环检测阶段最多执行O(V)次操作(例如,在涉及大多数车辆的巨大循环链中),因此算法的计算复杂度处于最坏情况O(V平方),对于每个车辆为O(V)。

在控制系统中,AGV何时准确进入新区域,即刚刚越过前一区域和新区域的边界线,将很难检测到。这是由于采样时间的关系,每1.5秒的数据就被发送到中央控制系统,这样就无法准确地检测到跨越区域边界的情况。为了检测车辆是否进入了一个新的区域,对车辆的先前取样位置和新取样位置进行了比较。如果区域发生变化,则车辆已进入新区域。这里,假设车辆不能在1.5 s内穿过整个区域。

将此思想推广到双区级死锁预测中是可能的。这一目的基本上是为了促进系统更好的性能。如果死锁提前预测,那么可以采取更好的避免措施。或者,当车辆的目的地不在预测的死锁区域时,可以重新路由车辆,以避免潜在死锁区域中的拥塞。这种预测的缺点是这里做了温和的近似。这些近似之所以生效,是因为车辆在理论时间内没有从一个点到另一个点移动。预期时间与实际所用时间之间的这种差异会导致错误。随着区域步数的提前预测,预测误差也会增大。

3.2. 阶段2:多循环死锁的解决

目前的研究表明了存在一种改进形式的循环死锁情况。这种情况称为多循环死锁,是在多个即将到来的循环争夺特定资源时形成的。图10示出了示例情况。

现有的方法只寻找即将到来的循环,显然,任何循环检测算法都会让AGV1、AGV2和AGV3永远等待。

图10. 多循环死锁情况的说明。

在图10中,我们看到AGV1想要进入空节点。它是与AGV3的next节点相同的next节点。现在,AGV1运行死锁预测算法并找到即将发生的死锁。根据“等待并继续”,AGV1等待死锁清除。这与AGV2和AGV3相同,它们各自的“下一个”位置如图所示。因此,AGV2和AGV3将等待死锁清除后再继续。在这里,循环死锁是通过“等待并继续”措施避免的,但它反过来又会创建另一个死锁,它不是循环的,而是有许多共享单个空资源的循环。

要发生这种死锁,必须满足以下条件:

  • 必须有多个“循环”。
  • 循环必须共享一个公共空节点。
  • 循环必须是唯一的,即不同的开始节点和结束节点(不包括空节点)。
  • 每个循环结束时车辆的“下一个”位置必须是另一个循环的开始。

这种混合死锁情况的发现基本上导致了上述预测策略的发展。预测机制具有前瞻性,因此解决多循环死锁的方法不止一种。

3.3. 阶段3:多循环死锁的解决

在算法的第二阶段,我们通过以下方式解决这些死锁(见图11):

  • 在该死锁所涉及的每个循环结束时,取一辆AGV。例如,AGV2。
  • 检查所有公共节点的前向星节点(即检查与公共节点相邻的所有节点)。
  • 对于每个前向星,检查AGV2进入公共节点时是否进入循环死锁。
  • 如果没有检测到即将发生的死锁,则通过该前向星重新路由它。
  • 否则,请查看其他前星。
图11. 解决多循环死锁。

请注意,每当出现这种情况时,需要确定新的AGV路线。这种方法不能完全解决多个循环死锁,当公共节点的所有前向星都是即将发生的循环死锁时,这种方法就失败了。幸运的是,对于集装箱港口AGV系统布局来说,多周期死锁主要发生在船舶装卸区,这里有大量的小循环相互连接。在这个区域中,每个节点都有大量的前向星(即每个节点可以转到许多其他节点)。因此,如果泊位区域中的车辆数量保持在合理的值,则进入所有前向星具有即将发生的循环死锁的情况的概率很小。

3.4. 阶段4:备用多循环死锁解决策略

另一种避免死锁的方法是使用动态路由系统。通过确定AGV从当前位置到目的地的最短路径的路由策略和智能弧权更新策略,该系统是可行的。由于AGV的运动决策需要实时给出,因此宜采用半动态方法。以下程序给出了此类系统的指南。

  • 将“工作”分配给特定车辆,并将始发地和目的地信息传递给路由系统。
  • 车道上的行驶时间根据预计的拥堵情况进行更新(Leighton等人,1988年)。在这里,预测拥挤是指交通信息被及时预测,而未来的拥挤是假设AGV按照预期进行计算的。
  • 根据预测的拥挤效应计算出最短路径。
  • 车辆沿着计算出的路线从起点移动到目的地。

只有在车辆路径中预测到死锁时,才需要重新计算路线。该过程称为半动态过程,因为计算的路线是存储的,车辆使用存储的路线。以下是路由的重要组成部分:

3.5. 路由的计算和存储(Calculation and storage of routes)

Gallo和Pallottino(1988)详细讨论了寻找最短路径的各种算法。结果还表明,算法的性能主要取决于底层网络的结构。根据所研究的网络,可以选择合适的算法。此外,在建议的半动态系统中,仅当下列条件之一成立时,才需要重新计算车辆路径:

  • AGV返回目的地,并为该特定车辆分配一个新作业。
  • 死锁预测算法可以预测死锁的形成,并为AGV请求新的路由。
3.6. 更新弧权重(Updating the arc weights)

系统中的弧权重是动态计算的,这样车辆可以使用最小拥挤的路径,同时尽量行驶最小距离到达目的地。

Leighton等人(1988)已经证明,在O(c+d)可以为给定的布局构造。这里,’c’是最大拥塞,’d’是扩张,即最长路径的长度。因此,减少“c”和“d”的值会直接影响计划长度。利用这个结果,我们可以构造一个弧权重更新策略来模拟这些影响。此外,这意味着这样计算的车辆路径将采用最不拥挤的路径,因此多循环死锁情况的形成将是不易发生的。

4. 实施

利用AutoMod仿真软件对死锁预测算法和AGV操作进行了仿真。在描述如何对工作负载进行建模之前,我们首先提供一些重要术语的定义。

  • 堆场起重机是将集装箱从车辆运至堆场的起重机,反之亦然。
  • 桥式起重机是在混凝土平台上运行的庭院起重机。
  • 码头起重机是将集装箱从车辆运送到船舶上的起重机,反之亦然。
  • 卸货过程是将集装箱从船上卸到集装箱堆场。
  • 装载过程是将集装箱从集装箱堆场装载到船舶上。终端的工作量按以下方式生成:
  • 泊位随机分配给到达的船。
  • 每隔1/2小时就有一艘船到达。
  • 每个集装箱堆场由9个集群组成。
  • 每个簇由3个控制点组成。
  • 在任何时候,单个集群只能由码头起重机用于卸货或装货目的。可以移动码头起重机,但此处不模拟这种移动。
  • 每艘船舶配备四台码头起重机。
  • 每个码头起重机处理的集装箱百分比:
  • 第一台码头起重机:18%,第二台码头起重机:25%,第三台码头起重机:27%,第四台码头起重机:30%。
  • 卸货集装箱的百分比呈三角形分布(0,50,100)。
  • 装货集装箱的数量是卸货集装箱的数量。
  • 处理的每个集群的每批(容器数量)遵循(1、12、24)的三角形分布。
  • 码头起重机装卸集装箱所用的时间呈三角形分布(1.25、1.63、2.00)分钟。
  • 桥式起重机装卸集装箱所用的时间遵循三角形分布(2.00、2.50、3.00)分钟。
图12. 即将发生的单区步骤死锁情况的说明。小立方体代表AGV,大立方体95代表AGV承载。

我们将不详细讨论单区步骤死锁预测和避免(wait-and-procedue)算法的实现,而是通过一个例子简要地勾勒出实现的思路。考虑如图12所示的情况。假设AGV1想要移动到其下一个控制点,并且当前正在其当前控制点停止。当AGV1即将进入下一个控制点时,它调用死锁预测算法。在本例中,如果AGV1移动到下一个控制点,死锁预测算法将返回循环死锁预测。此时,AGV1的出站程序将以0.2 s的离散时间步长(您始终可以更改时间步长)重复调用死锁预测算法,直到没有预测到死锁或没有车辆阻塞其下一个控制点。与此同时,其余车辆正在执行分配的任务。

即使AGV1接近当前控制点(图12所示的控制点),同样的情况也适用。当检测到预测到死锁时,“减速正常”功能指示车辆停止。当车辆停在图9所示的当前控制点时,它寻找的下一件事是过程是否与之相关联。在此示例中,没有与此控制点相关联的过程,当车辆即将离开其当前控制点时,将调用离开站点过程。在此之后,它将执行与前面描述的相同的操作。

4.1. 休眠车辆(Sleeping vehicles)

在实施过程中遇到的一个问题是,如果在将集装箱交付至堆场或船舶后,车辆未分配任何工作,则车辆将在该位置“休眠”或“停车”。这将导致一种“死锁”形式,在这种情况下,车辆在分配新工作之前不会离开。因此,如果有另一辆车的目的地是“休眠”车辆,则必须等到“休眠”车辆被分配了新工作并离开目的地。这会浪费时间。为了解决这种情况,提出了一种执行“碰撞”操作的算法。当车辆想要移动到“休眠”车辆所在的位置时,会进行“碰撞动作”。“颠簸”的车辆将向“沉睡”的车辆发出信号,让其醒来,并在别处“沉睡”或找到工作。

4.2. 虚拟控制点(Virtual control points)

到目前为止,我们只关注死锁预测。即使预测阶段在理论上是万无一失的,在装载和卸载过程中,由于车辆路径的不确定性,也可能发生死锁。例如,装载集装箱的车辆到达目的地,卸货过程(起重机提升集装箱)开始。在此期间,车辆的下一步工作仍不得而知。由于不知道卸货过程需要多长时间,如果没有下一个作业,将没有起点和终点,因此没有车辆路线。仿真环境要求所有车辆都有一个起点和终点,以便算法正常工作。

为了解决这种情况,必须在车辆装载和卸载过程中为其创建虚拟“下一个控制点”。有了这个虚拟点,可以肯定的是,如果车辆下一个作业的实际路线是通过这个虚拟点的,则不会发生死锁。如果车辆下一个点的实际路线未通过该虚拟点,则可能发生死锁。如果检测到死锁,将安排一条新路线,使车辆通过虚拟控制点。

我们用图13来说明这一现象。假设AGV1正在当前控制点卸载其容器,如图所示。它没有新作业,因此没有关联的路由。当其他车辆运行死锁预测算法时,在该位置为AGV1创建一个虚拟控制点。因此,如果AGV1在接收到新路由时实际移动到虚拟控制点,则不会发生死锁。这是因为当每辆车运行其死锁预测功能时,每次移动都是预期的。如果AGV1没有移动到虚拟控制点,而下一个控制点是AGV2的位置,则如果存在上图所示的下一个控制点的循环请求,则会发生死锁。循环请求发生在AGV1、2、3和4之间。因此在这种情况下,AGV1检测到死锁,然后它将通过虚拟控制点重新路由。这将确保不会发生死锁。

图13. 所遇到问题的说明。

5. 结果和讨论

首先在一个小规模的模型上实现了一步死锁预测和避免算法,然后将其扩展到实际模型上进行测试。实际模型布局包括四个泊位和80辆AGV。生成的工作负载遵循前面提到的负载分布的简化版本。首先讨论了该算法在小尺度算法上的有效性,然后给出了实际模型。

图14. AGV路径布局示例。此处所示的交叉点是控制点,必要时车辆将通过这些控制点停车。

算法的测试在图14所示的8辆车的路径布局中完成。工作量分布是随机的。模型中使用的规避措施是“等待并继续”方法。模型模拟52周,未发生循环死锁事件。如果不采用死锁预测和避免算法,模型很快就会在20min内陷入死锁。

模拟中使用的实际模型的布局如图15所示。实际模型中有80辆AGV。根据给定的信息模拟了工作负载分布。

图15. 实际模型的布局。

在不采用预测算法的情况下,模拟在40分钟内进入循环死锁状态,典型死锁如图16所示。

图16. 实际模型中的循环死锁。

利用预测算法对仿真模型进行了验证。已成功检测到的即将发生的死锁情况如图17所示。在图中,循环未完成,不允许更多AGV进入循环,直到循环中的车辆离开。

图17. 算法检测到即将发生的死锁。

该算法已在各种情况下进行了测试,表1显示了一周内预测的死锁数。模拟运行了20辆、40辆和80辆车,采用的回避措施是“等待并继续”。在表中,我们可以观察由于车辆数量和交通影响而形成的死锁数量之间的关系。令人惊讶的是,即使有少量AGV,死锁也会很快形成。此外,需要注意的是,随着AGV的减少,使用的船舶数量也减少了。这表明,任何通过减少车辆数量来防止死锁形成的尝试都是不值得的。因此,为了提高服务率,必须使用更多的车辆。

表1还显示了死锁形成率,即预测的死锁数量与服务船舶数量的比率。这是由于通信量影响而形成的死锁的度量。随着车辆数量的增加,网络变得更加拥挤,容易形成更多的死锁。但需要注意的是,使用80辆车时的死锁形成率仅略高于使用40辆车时的死锁形成率。这表明形成的大多数死锁仅由较小的循环组成。

图18是示出在7天期间中形成的死锁的数量的条形图。通过对80辆汽车进行仿真,得到了仿真结果。我们注意到这个结果证实了先前的结果,即死锁形成率为1.9。当使用80辆车时,一天服务的船舶数为10艘,预计一天的平均死锁数为19艘。

图18. 预计7天内会出现死锁。

在模拟中使用的路由是从AutoMod获得的。AutoMod有一个静态路由策略,不考虑拥塞影响。当采用动态路由时,当我们限制拥塞时,出现多循环死锁情况的概率也可以期望是最小的。
仿真结果表明:

  • 对于一个复杂的网络,死锁的形成与使用的车辆数量无关。如果车辆数量非常少(如2辆或3辆),则不会形成死锁,但如果车辆数量过少,则会影响吞吐量。
  • 形成的死锁数量与车辆数量成正比(当考虑合理的车辆数量时)。但是,由于大多数死锁是以小循环的形式形成的,所以当车辆增加时,死锁的形成率不会增加。
  • 为了增加吞吐量,需要更多的车辆,但更多的车辆意味着过度拥挤。
  • 死锁的形成取决于工作量和工作负载的分配。更多的车辆意味着更多的船舶被服务,因此更频繁的死锁。

6.管理见解和结论

信息技术的最新进展改变了物料处理过程的操作方式;尤其是在集装箱码头等物流供应链的关键环节。在更先进的大型集装箱码头,AGV正在取代传统的重型卡车在码头内运输集装箱。AGV系统提供了极大的灵活性,可以有效地处理由频繁的集装箱移动引起的动态运输请求。这样一个系统是资本密集型的,需要高生产率才能使其在经济上可行。与大多数全自动系统一样,AGV系统容易出现死锁,如果处理不当,会大大降低系统的生产率。一种有效的死锁预测算法使系统能够进行频繁的预测,并采取必要的预防措施来避免死锁的形成。

前面的数值结果表明,在大型集装箱码头AGV系统中,死锁的形成是非常频繁的。有必要进行频繁的预测,以避免死锁的形成。然而,目前开发的死锁预测算法都是计算密集型的,因此只适用于小规模AGV操作。本文提出了一种复杂度为O(V平方)的有效死锁预测算法,其中V是AGV系统中的车辆数。这种有效的算法使得在每一个发布新的AGV运动指令的短决策周期内进行预测成为可能。这些频繁的预测对于防止死锁的形成至关重要。

从数值结果可以看出,死锁形成的频率随着终端负载的增加而增加,特别是在负载分布极不均匀的情况下。在终端的不同部分进行适当的工作负载平衡可以降低频率。建议调查工作负载分布对死锁形成可能性的影响。

引用(References)

  • Chang, W.K., Tanchoco, J.M.A., Koo, P.H., 1997. Deadlock prevention in manufacturing systems with AGV systems:
  • banker’s algorithm approach. Journal of Manufacturing Science and Engineering 119, 849–854.
  • Coffman, E.G., Elphick, M.J., Shoshani, A., 1971. System deadlocks. ACM Computing Surveys 3 (2), 67–78.
  • Gallo, G., Pallottino, S., 1988. Shortest Path Algorithms.
  • Annals of Operations Research. J.C. Baltzer Scientific Publishing Company.
  • Gold, E.M., 1978. Deadlock prediction: easy and difficult cases. SIAM Journal on Computing 7 (3), 320–336.
  • Hyuenbo, C., Kumaran, T.K., Richard, A.W., 1995. Graph theoretic deadlock detection and resolution for flexible manufacturing systems. IEEE Transactions on Robotics and Automation 11 (3), 413–421.
  • Lee, C.C., Lin, J.T., 1995. Deadlock prediction and avoidance based on petri nets for zone control automated guided vehicle systems. International Journal of Production Research 33 (12), 2349–3265.
  • Leighton, T., Maggs, B., Rao, S., 1988. Universal packet Routing Algorithms. IEEE Transactions.
  • Spyros, A.R., Conflict Resolution in AGV Systems. School of Industrial & Systems Engineering, Georgia Institute of Technology.
  • Viswanadham, N., Narahari, Y., Johnson, T.L., 1990. Deadlock prevention and deadlock avoidance in lexible manufacturing systems using Petri net models. IEEE Transactions on Robotics and Automation 6 (6), 713–723.
  • Yeh, M.S., Yeh, W.C., 1998. Deadlock prediction and avoidance for zone-control AGVS. International Journal of Production Research 36 (10), 2879–2889.

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

14 − 10 =