自动导引车（AGV）的有效控制策略对于运营柔性制造系统的公司最大限度地提高生产率非常重要。在本文中，我们设计并分析了Pickup-or-Delivery-En-Route（PDER）--一种多负载AGV调度算法。PDER 是一种任务决定规则，它使部分装载货物的车辆在前往卸货目的地的途中，可以拾取和/或卸下原本会经过的货物。我们通过模拟实验来评估 PDER 算法的有效性。结果表明，在使用多负载 AGV 的柔性制造系统中，PDER 可对系统吞吐量和时间产生显著的积极影响。
随着商业环境、客户偏好和技术的不断变化，企业不能再指望通过生产标准化产品来获得超额收益。为了解决产品定制、扩大产品范围和减少订单数量等问题，许多企业试图通过从大规模生产向柔性制造转型来重新发展自己的竞争优势。Shivanand、Benal 和 Koti（2006 年）将柔性制造系统（FMS）定义为由自动物料处理系统相互连接并由集成计算机控制系统控制的一组工作站和存储系统。这种系统有几个复杂的特点，如产品变化大、物料流模式随机、需求随机等，传统的物料搬运系统（如输送机）已无法应对在整个系统的工作站之间搬运产品的挑战。
AGV 可以大大提高物料搬运系统的灵活性，并根据产品加工顺序采取有效路径运送在制品（WIP）。然而，AGV 的行驶速度慢、装卸时间长、容量有限，会限制制造系统的生产能力。因此，高运输强度的 FMS 可能需要大量的 AGV 才能实现高效的物料流动和分配。此外，庞大的 AGV 车队还涉及大量的车辆资本成本、AGV 维护、交通拥堵问题和空间需求。
为了减少所需的 AGV 数量，一种替代方案是采用多负载 AGV。与单载荷 AGV 相比，多载荷 AGV 通常可以帮助 FMS 以较小的车队规模实现较高的吞吐量（Ozden，1988 年）。多载荷 AGV 的其他一些优点包括更好地利用 AGV 和提高机器利用率（Bilge 和 Tanchoco，1997 年）。管理多负载 AGV 所面临的主要挑战是，额外的负载空间会增加 AGV 的决策状态。Ho 和 Chien（2006 年）指出，单载荷 AGV 只有空载和载荷状态，而多载荷 AGV 则可能处于空载、部分载荷和满载状态。此外，他们还定义了与多负载 AGV 管理相关的四个主要问题：
本研究的目的是开发一种任务确定规则，使多负载 AGV 能够在部分负载时利用空位，从而最大限度地提高系统吞吐量，并最大限度地减少 FMS 系统中零件的平均在系统时间。具体而言，我们将所提出的策略称为 "沿途取货或交货"（PDER），该策略可使部分装载的车辆在前往卸货目的地的途中取货和/或卸货，否则该车辆将在前往原目的地的途中经过这些货物。
本文的其余部分安排如下：第 2 部分概述了相关工作；第 3 部分解释了提议的 PDER 规则的细节；第 4 部分介绍了在两种 FMS 系统配置下比较备选调度规则的模拟实验；最后，第 5 部分讨论了我们的结论。
在 AGV 调度算法领域有大量的研究工作。LeAnh 和 Koster（2006 年）对 AGV 管理面临的挑战和方法进行了全面研究，Fazlollahtabar 和 SaidiMehrabad（2015 年）对 AGV 调度、分派和路由问题的现有策略进行了回顾。许多作者关注单载 AGV 的取货调度问题。一些常见的拾取-调度规则包括最短距离（STD）、修改后的先到先服务（MFCFS）、最大产出-队列规模（MOQZ）、单位负载-店铺-到达时间（ULSAT）规则（Egbelu 和 Tanchoco，1984 年）。其他研究人员的研究表明，在某些情况下，多属性调度算法优于单属性规则（Jeong 和 Randhawa，2001 年；Bilge 等人，2006 年；Guan 和 Dai，2009 年；Caridá、Morandin 和 Tuma，2015 年）。
Azimi、Haleh 和 Alidoost（2010 年）开发了一种模糊多属性决策（MADM）方法，用于评估多负载 AGV 的控制策略，该方法考虑了十项性能标准，如系统吞吐量、零件平均流动时间、取货点和交货点的平均排队长度等。Ho 和 Chien（2006 年）比较了处理多负载 AGV 任务确定问题的三种规则，即交付任务优先规则（DTF）、取货任务优先规则（PTF）和负载率规则（LR）。DTF 规则建议 AGV 在部分装载时始终选择放下剩余的货物。在 PTF 规则下，AGV 应始终先执行取货任务，即使送货和取货任务对它来说都是可用的。与给予送货或取货任务更高的优先级的 DTF 或 PTF 规则不同，LR 规则根据车辆的负载率决定 AGV 的下一项任务。结果表明，DTF 规则在系统吞吐量和零件平均延迟时间方面普遍优于 PTF 和 LR 规则。
在这项工作中，我们以上述研究中获得的见解为基础，设计了一种规则（PDER）来解决 AGV 在部分装载并前往目的地的途中所采用的拾取和放下策略，以尝试提高系统性能。
取货-或交货-途中（PDER）规则的基本目标是最大限度地利用多载荷 AGV 的载荷空间。因此，PDER 允许部分装载的 AGV 在驶向下一个目的地的途中拾取更多货物。多负载 AGV 在取货点或交货点完成所有必要操作并部分装载后，AGV 会在取货点位于 AGV 当前位置和下一个目的地之间最短路径上的作业中寻找新的任务。这些工作被称为低成本工作，因为 AGV 提取这些工作非常方便。如果存在一个或多个低成本工作，AGV 将在前往原目的地的途中拾取/放下这些工作。
PDER 算法与指定的取货调度规则协同工作，以控制多负载 AGV 的行动。PDER 算法如图 1 所示，其中使用了以下符号：
𝑖 系统中的运输任务（负载）。
𝐼 系统中所有未分配工作的等待列表。
系统中的 AGV。
𝐷𝑉 AGV 𝑉 的目的地列表，与 AGV 𝑉 分配和运载的工作相对应。
𝑃𝑉位于 AGV 当前位置和下一个目的地之间的取货点列表。
𝐼𝑉 在取货点 𝑃𝑉 等待的低成本工作集，其中 𝐼𝑉 ⊆ 𝐼。当发生工作中心启动事件或车辆启动事件时，系统会启动 PDER 算法。
工作中心启动事件发生时，负载会根据其加工顺序产生新的请求，要求被传送到下一个工作站。当一个部件在一个工作站完成后，就会生成一个运输任务 𝑖 。如果此时没有一辆 AGV 处于闲置状态，工作 𝑖 将被保存到等待列表 𝐼 中。如果只有一辆闲置的 AGV 𝑉，工作 𝑖 将被分配给 𝑉。如果有多辆空闲的 AGV，则 AGV 将根据工作中心启动的规则竞争作业 𝑖。一些常见的规则包括最近车辆（NV）、最长闲置车辆（LIV）和最少使用车辆（LUV）（Egbelu 和 Tanchoco，1984 年）。
当 AGV 到达取货点或送货点时，就会发生车辆启动事件。AGV 将首先执行为分配或承载的工作预先确定的取货或送货任务。AGV 完成预定任务后，将处于三种情况之一：
在情况 1 和 2 中，当作业 i 被分配给𝑉 并从等待列表 I 中删除后，𝑉 的后续状态将遵循情况 2 或情况 3。换句话说，𝑉 不会离开取货点或送货点，除非车辆已分配完毕（情况 1 中的𝑉 是空车，或情况 2 中的𝑉 是空车）。由于下一个目的地被定义为𝑉 的目的地列表中最近的取货点或送货点，因此交付-调度决策始终遵循 STD 规则。
在本节中，我们将介绍一个基于仿真的实验，以评估 PDER 任务决策规则和四种可供选择的取货-派送规则的有效性。在两种 FMS 系统配置的背景下，我们将 PDER 与交货任务优先 (DTF) 任务决定规则（Ho 和 Chien，2006 年）进行了比较，在这两种配置中，我们改变了系统中 AGV 的数量以及 AGV 的容量。我们进行了模拟实验，根据系统吞吐量和系统平均时间等性能指标，比较了不同系统配置下规则组合的性能。
我们考虑了两种柔性制造系统配置，即 FMS 1 和 FMS 2。这两种系统都基于拉动概念运行，因此当入口站的队列长度小于其容量时，一个随机零件类型的新零件将进入系统。在这两种配置中，AGV 装载和卸载每个零件的时间均为 15 秒，行驶速度为每小时 2 英里。
第一个 FMS 配置（FMS 1）的布局如图 2 所示。FMS 1 采用单回路地面布局，由 8 个工作站组成，以单向路径连接，可生产 5 种零件类型。输入站的输出缓冲区容量为 12 个。当 AGV 从输出缓冲区拾取一个零件后，一个随机零件类型的新零件将根据表 1 中的生产量百分比流入系统。此外，表 1 还列出了每种零件类型的处理顺序以及平均处理时间。我们假设工件在工作站的加工时间呈指数分布。完成的零件将从出口站离开系统。
第二个 FMS 配置（FMS 2）的布局如图 3 所示，是根据 Ho 和 Chien（2006 年）使用的布局设计的。该系统由 10 个工作站组成，生产六种不同类型的零件。表 2 列出了每种零件类型的加工顺序和体积百分比（随机抽样）。如表 3 所示，每个工作站不同工件类型的加工时间遵循相同的正态分布。
在实验中，我们使用了几种 AGV 控制规则，包括工作中心启动规则、拾取调度规则、交付调度规则和负载选择规则。
当产生新的运输请求且有多辆 AGV 处于闲置状态时，就会应用工作中心发起的规则。其任务是确定由哪辆闲置车辆取货。根据 Egbelu 和 Tanchoco（1984 年）的研究结果，我们采用了最近车辆（NV）规则。在选择车辆时，每辆 AGV 都要找到通往作业取货点的最短路径。到取货点的行驶距离最小的 AGV 将被分配工作。
四种取货调度规则与任务确定相结合使用。取货调度规则用于确定 AGV 应访问哪个取货点。考虑的四种规则是：系统内最长时间（LTIS）、拾取点最长等待时间（LWTPT）、最短行驶距离（STD）和最大队列长度（GQL）。有关这些规则的更多详情，请参阅 Ho 和 Liu (2006)。
当 AGV 装载多个负载时，交付调度规则用于确定哪个负载应首先交付。在本研究中，采用了最短距离（SD）规则进行配送调度--参见 Ho and Chien (2006)。货物选择规则用于确定应从取货点取货的货物。在本研究中，我们采用了 "先进队列-先出（FIQFO）"规则，即队列中等待时间较长的部件具有较高的优先级（Ho 和 Liu，2006 年）。在 DTF 任务确定规则下，当 AGV 到达其决定访问的拾取点时，将调用装载选择规则。AGV 将继续根据装载选择规则装载零件，直到装满或输出队列变空为止。如果采用 PDER 任务确定规则，则会在任务分配过程中调用负载选择规则，并确定 AGV 应被分配到哪个低成本任务。
使用 Simio 仿真软件（Simio 2017）构建了所考虑的两个 FMS 系统的仿真模型。对标准 Simio 车辆路由逻辑进行了几处比较重要的修改/添加，以便能够实施和执行各种车辆控制规则，包括 PDER 任务确定规则--详见 Li (2017)。
基于仿真的实验比较了 PDER 和 DTF 任务确定规则与两种 FMS 配置中的四种备选取货-调度规则的性能。考虑的其他因素包括 AGV 车队规模从 1 到 4 辆不等，车辆类型包括双负载和三负载 AGV，共产生 128 个测试场景。实验因素及其水平如表 4 所示。本实验考虑的主要性能指标是平均吞吐量和系统平均时间。
模拟实验设定每个因素组合运行 20 次，连续运行 500 小时，其中包括 FMS 1 和 FMS 2 分别为 6 小时和 12 小时的预热期。
对于模拟实验中的每个处理组合，都记录了吞吐量和系统运行时间的统计数据。图 4 和图 5 分别显示了 FMS 1 和 FMS 2 的平均吞吐量。
作为参考点，运行了一个假定瞬时物料搬运的模拟配置，以确定吞吐量的上限。FMS 1 的上限为 6000 个零件，FMS 2 为 9800 个零件。从图 4 和图 5 中显示的结果来看，我们发现了系统产能不足的几种情况（FMS 1 使用一台 AGV，不考虑 AGV 的产能；FMS 2 使用一台或两台双载荷 AGV 和一台三载荷 AGV）。此外，在 FMS 1 中，当使用四辆 AGV 时；在 FMS 2 中，当使用四辆双载荷或三或四辆三载荷 AGV 时，系统的 AGV 容量会过剩。也就是说，有足够的车辆容量，AGV 控制规则不会对吞吐量产生显著影响（𝛼 ≤ 0.05）。因此，我们将分析重点放在表 5 中的情景上。
表 6 和表 7 分别显示了 FMS 1 和 FMS 2 中所选方案的吞吐量平均值和标准偏差。对于每种方案，我们都在 0.05 的显著性水平下进行了 Tukey 多重均值比较测试，以比较每对 AGV 控制规则下的平均吞吐量。阴影中的吞吐量值表示相应的规则组合在该方案中产生的吞吐量最高。在某一特定方案中，如果多个值都有阴影，则平均吞吐量处于最高组别，但平均值之间没有显著差异。
从表 6 中我们可以看出，使用带 PDER 规则的 STD 总是能实现最高吞吐量。当有 3 辆双载荷 AGV 和 2 辆三载荷 AGV 时，只要与 PDER 任务确定规则相结合，任何取货-调度规则都能达到最高吞吐量。如果使用相同的拾取-调度规则，PDER 的吞吐量优于 DTF。同样，在表 7 中，当使用 3 辆双载荷或 2 辆三载荷 AGV 时，PDER 规则的吞吐量总是最高的。在这两种情况下使用相同的拾取-分配规则时，PDER 规则的吞吐量更高。
除了吞吐量，我们还分析了 AGV 控制规则在系统中零件平均停留时间方面的性能。表 8 和表 9 分别总结了 FMS 1 和 FMS 2 中每个选定方案的系统内平均时间的平均值和标准偏差。我们对这些平均值进行了类似的多均值比较测试，并选出了每个方案中表现最好的一组。从表 8 中我们可以看出，采用 PDER 规则的 STD 实现了最短的系统平均时间。当使用相同的拾取-调度规则时，PDER 在大多数情况下都优于 DTF 规则。唯一的例外是在 2 个双负载 AGV 上使用 LTIS 与 DTF 规则时。在表 9 中，使用 STD 和 PDER 规则时，系统平均耗时最少。在使用 STD、LWTPT 和 GQL 取货-发货规则时，PDER 规则优于 STD 规则。
总体而言，就系统吞吐量而言，PDER 规则优于 DTF 规则。当使用相同的取货-调度规则时，PDER 通常会产生更高的吞吐量。唯一的例外是在第二个 FMS 中使用 2 个双负载 AGV 时，采用 PDER 的 GQL 和采用 DTF 的 GQL 并列第一。在 FMS 2 中，PDER 规则对吞吐量的影响较小。由于 PDER 规则允许 AGV 在前往下一个目的地的途中拾取更多工作，因此出现空 AGV 的几率变得非常小。因此，采用 PDER 规则的 AGV 通常不会被分配给系统中优先级最高的作业，而是选择 AGV 当前路线上优先级最高的低成本作业前往下一个目的地。换句话说，AGV 通常不会分配给系统中优先级最高的作业，而是选择相对重要且更方便拾取的作业。在 FMS 1 中，由于只有一条路线连接所有工作站，因此经过每个工作站的次数分布更均匀，从而缓解了这一问题。
PDER 规则在零件在系统中的平均停留时间方面也有突出表现。在使用相同的取货调度规则时，除 LTIS 情况外，PDER 规则的性能均优于 DTF 规则。LTIS 规则的基本目标是最大限度地减少零件在系统中的停留时间。与工作站输出缓冲区中的零件相比，在入口站取货点等待的零件在系统中的时间总是较短。因此，AGV 将推动制造系统集中精力完成已离开入口站的零件。这种效应可确保系统中的时间最小化，但会减少进入系统的零件数量，从而限制吞吐量。
最后，我们发现当 PDER 规则与 STD 规则搭配使用时，在产量和系统停留时间方面都有很好的表现。因为 STD 专注于最大限度地减少滞留行程，而 PDER 规则则减少了 AGV 从上游工作站拾取零件，同时经过下游准备进一步向下游移动的零件的问题。因此，PDER 规则有可能显著提高使用多负载 AGV 的 FMS 系统的生产率。
本文提出了一种适用于多负载 AGV 的 "取货-或交货-路径 "任务决策规则。通过仿真实验，比较了 PDER 规则和 DTF 规则在不同车队规模和 AGV 类型的两种系统配置中的效果。通过这项研究，我们展示了使用 PDER 规则的强大潜力，它可以显著提高使用多负载 AGV 的 FMS 的生产率。在这项初步工作的基础上，我们计划进行更深入的分析，以确定使用 PDER 规则最有利的 FMS 特性。