英语原文共 22 页，剩余内容已隐藏，支付完成后下载完整资料

自动导引车辆的调度和路径问题优化方法研究文献综述

Hamed Fazlollahtabar

·

Mohammad Saidi-Mehrabad

摘要：自动导引车辆（AGV）被用作柔性制造系统的物料搬运设备。传统上，AGV主要用于制造系统，但目前AGV的其他应用被广泛开发，比如,在仓库、集装箱码头和运输系统等领域。本文分析了AGV系统在制造，分配，转运和运输系统中的调度和路径这二个重要问题的不同优化方法的研究文献。我们将方法分类为数学方法（精确和启发式）、模拟研究、现代启发式方法和基于人工智能的方法。

关键词：AGV系统、文献调查、调度、路径

1介绍

自动导引车（AGV）是一种用于物料水平运输的无人驾驶物料搬运系统。AGV于1955年推出[62]。自推出以来，自动导引车的使用量大幅增长。应用领域和类型变化的数量显著增加。AGV可用于内外环境，如制造，配送，转运和（外部）运输领域。在制造领域，AGV用于运输与制造过程相关的所有类型的材料。根据Gotting[30]的文献，超过20,000个AGV被用于工业应用。作者指出，AGV的使用将为具有重复运输模式的环境带来回报。这些环境的例子是分配、转运和运输系统。仓库和跨库中心是分配区域的例子。 AGV在这些区域用于内部运输，像各部门如接收、存储、分拣和运输区域之间的运货板。在诸如集装箱码头之类的中转系统中，AGV负责在各种运输方式之间运输产品。Gotting[30]介绍了一种在集装箱码头可行的自动化技术的概况。此外，还描述了适用于各种室内、室外环境的导航和车辆引导系统。Haefner和Bieschke[32]指出，AGV系通过执行船舶和内陆运输之间的运输要求，可以为港口及其客户提供利益。也就是说，在非自动化码头中，这种运输过程是效率最低且成本最高的过程之一。AGV也可以用于室外运输过程。这种运输系统的一个例子是地下自动化运输系统，由AGV在公司和机场之间的管道中行驶（参见[94, 95]）。在这样的系统中，我们注意到了高密度交通流量和长时间管道行驶。其甚至研究了AGV是否可以用作工作站之间的通信系统（参见[59]）。显然，AGV的规格在不同环境下有所不同。运输集装箱时，AGV的容量应至不小于40吨。在仓库运输托盘只需要较少的运输能力。此外，自升式自动导引车（ALV）被使用在集装箱码头。对于这种类型的AGV，不需要其他设备将负载转移到车辆上。Vis和Harika[98]和杨等人[101]更详细地讨论了这种新型的AGV。

在本文中，我们将讨论文献关注AGV在制造业和新的应用领域，即分销、转运和运输系统中的使用。 传统领域和新的应用领域之间最重要的区别是使用的AGV数量、要求的运输量、AGV的占用率、要行驶的距离以及有满足要求的运输量的配送点的数量。在制造系统中，少量占用率相对较低的AGV用于在几个配送点之间的短距离小量运输。对于这些系统中的连续质量输送，使用输送机而不是大量AGV（参见[30]）。 与制造系统相比，大量AGV（高达400;[94]）被用来在集装箱码头和外部运输系统执行大量的重复运输任务。此外，在外部环境（集装箱码头和外部运输系统）中发现的运行条件，例如天气条件和空间尺寸，与内部区域（制造和分配系统）的运行条件不同。

表1中列出了研究调度和路径问题的目标函数。

在以前的研究中，一项对自动引导车辆设计和控制的调查研究被发现，该研究专注于AGV系统在制造、分配、转运和运输系统中的设计和控制问题有关的文献[97]。其得出的结论是，大多数模型可以应用于制造中心的设计问题。这些模型和新模型中的一些已经证明在大型AGV系统中是成功的。事实上，需要为大型AGV系统开发新的分析和仿真模型，以克服大量计算时间、NP完整性、拥塞、系统中的死锁和延迟以及有限的规划视野。

目前的工作讨论了与用不同的方法优化AGV系统，以解决制造、分配、转运和运输系统中两个重要的调度和路径问题相关的文献。我们将这些方法分类为数学方法、模拟研究、元启发式技术和基于人工智能的方法。

调度和路径分类的动机是基于它们在柔性制造系统中的重要性。不管目标如何决策功能，AGV移动的路径以及它到达商店或工作站的时间对于经济决策而言都是相当重要的。因此，对具有不同目标函数的不同优化方法进行分类可以更好地概念化并在研究和应用中实现这些系统。

一般而言，优化技术分为三类：精确法、启发式和元启发式。精确法寻求全局最优性，并且通常不能提供有关NP难解问题的良好解决方案（尽管存在许多反例）。启发式是特定于问题的方法，它利用问题属性来导出解决方案的策略。元启发式是一般的启发式方案，可以应用于许多优化问题。

表1调度和路径问题的目标函数

调度 路径

1. 完工时间 全球运输成本
2. 总计（加权）完成时间 司机和车辆的固定成本
3. （加权）平均流量时间 车辆和/或司机的数量
4. 平均等待时间 平衡路线
5. 迟到 没有/部分服务的客户的处罚
6. 滞后 –

调度

到目前为止关于AGV的调度讨论的文献几乎没有考虑（侧面）限制方面，诸如让运输工作可行的机器的容量限制、其他类型设备的调度和车辆的有限停车空间。这些侧面约束在具有大型AGV系统的现实生活情况中变得越来越重要。考虑到这些限制因素，应该更加注意不同类型物料搬运设备的综合调度，这些设备同样满足空间和容量要求。

• 1. 数学优化
     1. 精确法算法

精心设计和高效管理的物料处理系统在柔性制造系统的规划和运行中发挥着重要作用。大多数研究人员将机器和车辆调度作为两个独立的问题进行研究，大部分研究仅着重于单一目标优化。具有冲突目标的调度的多目标问题本质上是更加复杂且联结的，并且几乎没有独特的解决方案。

在[70]文献中，对集装箱码头中的自动引导车辆的调度问题进行了定义，并将其制定为最低成本流量模型。然后通过扩展标准网络单纯形算法（NSA）的新算法NSA 解决问题。与NSA一样，NSA 是一个完整的算法，这意味着如果在可用时间内找到一个解决方案，它将保证解决方案的最优性。为了补充NSA ，一个不完全算法Greedy车辆搜索（GVS）被设计且实施。 NSA 和GVS进行比较和对比，以评估其相对强弱。利用多项式时间复杂度，NSA 可用于解决非常大的问题。

Nishi等人[64]提出了一种双层分解算法，用于解决自动制导车辆的同时调度和无冲突路径问题。总体目标是最大限度地减少与这些任务有关的一组工作的总加权滞后时间。混合整数公式分解为两个层次：任务分配和调度的上层主控问题;以及低层路径子问题。主问题通过使用拉格朗日松弛法来解决，并且可获得下限。解决方案要么被证明对于较低层次是可行的，要么构造了一个可行的解决方案，并且获得了一个上限。如果不满足收敛，则在再次解决主要问题之前生成削减以排除先前的可行解。如此提出了两种削减方式来减少二元性差距。从计算实验中验证了所提出的方法的有效性。

Bing [4]、Veeravalli等人[96]和Zaremba等人[104]提出了AGV调度的分析模型。Sinriech和Palni[84]针对在有限规划范围内在闭环中行进的单个多负载车辆开发了最优调度算法。每个工作的到达时间和处理时间都是已知的。辛里奇和科特拉斯基[83]扩展了该算法，使其可用于在单个循环中动态调度多个载荷的车辆，同时最大限度地减少作业的传送时间和车辆行驶的循环次数。由于算法的动态特性，可以对

调度计划进行更改以对突发事件做出反应。这显示出此动态算法从周期时间和发展中胜过现有的常用非动态调度规则。

Hartmann [34]为集装箱码头的物料搬运设备的排程引入了一个通用模型，以使工作的平均延误时间和平均设置时间最小化。与其他文献相比，该模型不适用于单一类型的设备，但它可以用于多种类型的设备，如AGV和跨运车。

Meersmans [60]给出了集装箱码头自动化处理设备集成调度的数学模型，如AGV和自动堆垛起重机。 他提出精确的启发式算法来解决这些模型。为了测试这些算法的性能，他进行了计算研究。

Meersmans和Wagelmans [61]提出了一个模型，用于处理自动化集装箱码头上所有类型物料处理设备的综合调度。目标是通过最小化调度的完工时间来优化集装箱码头的整体性能。一种分支定界算法被提出，其产生最优或接近最优的调度。针对大问题，一种波束搜索启发式算法被提出。已经证明，通过启发式解决方案，可以在合理的计算时间内获得接近最优的解决方案。Meersmans的综合方法[60]和Meersmans和Wagelmans[61]没有考虑到AGV在等待起重机装（卸）载时的空间有限。

在表2显示了精确法的总结

2.1.2启发式算法

柔性制造系统的调度是一个众所周知的NP难题，由于诸如材料处理、替代路由和替代机器之类的附加考虑因素，该问题非常复杂。通过适当整合和同步调度，有效利用其资源，可以期望提高灵活制造系统的性能。

雷迪和拉奥[

您可能感兴趣的文章

• 现代单元结构在压缩载荷作用下的影响外文翻译资料
• 水下浇口凸轮衬套注塑模设计与分析外文翻译资料
• 机械微机械加工的最新进展外文翻译资料
• 考虑尺寸效应的物料流动特性建模外文翻译资料
• 智能移动机器人的无人监督人体活动分析外文翻译资料
• 手臂的视觉感知操纵着触觉的体验快感外文翻译资料
• 稀土元素对6061铝合金真空钎焊接头组织和性能的影响外文翻译资料
• 定向凝固铝硅镁共晶合金的组织、力学和电学特性研究外文翻译资料
• 机床进给传动装置外文翻译资料
• 数控机床工业设计方法的研究及其实现和应用前景外文翻译资料