在一般的引导路径布局中为自动导向车找到最佳停留点外文翻译资料

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

在一般的引导路径布局中为自动导向车找到最佳停留点

Jose A. Ventura，Subramanian Pazhani，Abraham Mendoza

1. 美国，宾夕法尼亚州立大学，哈罗德和英格马库斯工业与制造工程系，PA16802

2.墨西哥，泛美大学，工业工程系，45010

摘要：

在自动导引车辆（AGV）系统中，闲置车辆的停留点确定了提车请求的响应时间，从而影响了自动化制造系统的性能。在本文中，我们解决了在一般引导路径布局中为给定数量的AGV最优定位定位点的问题。基于最优性，我们提出了三个版本问题的新的混合整数线性规划（MILP）公式：（i）最小化系统中的平均响应时间，（ii）最小化系统中的最大响应时间，（ iii）考虑对车辆可用性的时间限制，最小化系统中的最大响应时间。鉴于解决MILP模型所需的计算时间随着引导路径网络的大小和可用AGV的数量而明显增加，因此我们还开发了可以应用于三个版本问题的通用遗传算法（GA）。即对单环路布局和二维网格网络的两个特殊情况进行了计算研究，目的是最小化平均响应时间并最大限度地减少最大响应时间。实验结果表明，提出的GA过程可以在合理的时间内产生最优或近似最优解。

1. 介绍

近年来，制造业重点通过应用与制造工艺和系统自动化相关的新概念，建立了可持续的竞争优势。 灵活的制造系统（FMS）用于有效地实现自动化制造环境。FMS用于生产低和中等体积的各种零件。 FMS的主要组成部分之一是物料搬运系统，通常在工厂生产成本中占很大比例。 材料处理估计占制成品总成本的15％至70％，其生产时间的87％。精心设计和有效管理的材料处理系统对于降低产品成本和生产周期时间至关重要。

许多使用FMS的组织也部署了自动配对导引系统（AGV），用于工作站移动材料。AGV是无人驾驶的车辆，其运动可以通过电线，策略定位的雷达或特殊磁带进行控制。AGV具有自动装载，运输和卸载能力。AGV系统已经在航空航天，汽车，化工，电子，塑料，食品和饮料，纺织品以及多式联运集装箱港口等行业中得到应用。AGV系统的使用可以更好的对生产进行计划和控制，提高安全性，降低成本，同时提高可靠性。 AGV还提供与日益使用的自动化仓储系统的无缝接口，可通过集成仓储管理技术进行控制。然而，只有在有足够的引导路径布局和车辆调度，路由和流量管理控制系统的情况下，才可以获得这些潜在的好处。

AGV系统实施中的物流问题包括接收点和交付点的位置，最佳导航路径设计，确定AGV的最佳数量和类型，AGV的定位，AGV的分配到接收请求，rou并派出AGV，解决僵局和路由冲突。在这些问题中，AGV的定位以及将AGV分配给接收请求是AGV系统实现中的重要控制问题。由于制造系统的工作量随着时间的推移而改变，因此设备中使用的材料处理设备的空闲时间是为了避免系统过载。因此，在AGV系统中，由于怠速车辆的位置确定到下一个接送请求的空行驶时间，所以有关的问题是在完成送达作业并且没有立即分配时决定AGV的位置，这被称为响应时间。

在本研究中，我们根据AGV采取的响应时间来考虑接收请求的目标。空闲车辆行驶时间的减少有助于减少总体材料处理时间，这是处理设计过程中的一个重要目标。 Hakam首先提出了两个目标来确定空闲AGV的停留点：（i）最小化最大响应时间，和（ii）最小化平均响应时间。特别地，最小化最大响应时间的目标在即时（JIT）制造环境和配送中心是重要的，其中重点是减少大的周转时间。在使用AGV系统的某些多产品多线组装系统中，特定组装操作所需的部件由AGV从存储箱运输到搭接台以形成套件。形成完整套件所需的时间取决于运输所需部件的AGV的最大行驶时间。在配送中心，必须收集与单一客户订单相关的物品进行包装和运输。这里，最大响应时间决定整个周转时间。缩短周转时间至关重要，因为订单拣货占典型配送中心运营成本的65％。然而，在其他制造环境（如作业车间）中，最小化平均响应时间是AGV系统的普遍操作性能测量，因为它有助于降低整体材料处理成本。

Egbelu考虑了定位AGV的驻留点的问题，以最小化单个循环引导路径布局中的最大响应时间。他为单向和双向引导路径中的单个AGV的位置提供了最佳解决方案，并提出了用于在两种类型的引导路径中定位多车辆的启发式算法。他使用小尺寸示例问题说明了该算法。 Ventura和Lee表示Egbelu启发式算法提供的解与最优解之间的偏差可能会很高。

Kim提出了一种算法，用于确定新车辆在单回路导向路径布局中的最佳位置，目的是在一些空闲车辆已经停放在布局中的某些位置时最小化平均响应时间。他的算法不允许重新定位已经停放的车辆的停留点并且他考虑了单向和双向的导向路径布局。

Chang和Egbelu考虑了单循环引导路径布局中单个AGV的驻留点位置问题，其中在车站中拾取的材料随着时间的推移而变化。作者认为，随着车辆在一段时间内完成某些任务，其最佳停留点位置也可能发生变化。他们提出了精确的算法来解决单向和双向引导路径中的问题，以便最小化车辆的预期响应时间。使用示例问题说明算法。

Gademann和Van de Velde考虑了单向循环引导路径布局，并提出了一种动态规划（DP）算法来最小化响应时间的任何常规函数。所提出的DP算法具有O nm3的复杂度，其中m是拾取点的数量，n是AGV的数量，在使响应时间的任意规则函数最小化中，并且在最小化最大响应时间时O m2 log m。他们的工作不包括任何计算研究来显示所提出的DP算法的有效性。

Lee和Ventura考虑了单循环引导路径布局，并开发了一种多项式时间DP算法，用于最优化AGV的多个驻留点，从而最小化平均响应时间。考虑了单向和双向引导路径。他们还进行了仿真实验，以比较四种不同的空闲车辆定位规则，并得出结论，在停留点定位空闲车辆的规则将平均响应时间最小化。 Ventura和Lee考虑了单向单环导轨布局，并解决了为AGV最佳定位多个停留点的问题，目的是最小化最大值响应时间。同时其开发了具有O（n（m-n）²）复杂性的DP算法，以最佳地解决该问题。

Kim和Park评估了半导体制造线中的不同怠速车辆循环政策，目的是最小化平均交货时间。基于模拟研究，他们得出结论，空闲车辆循环政策对系统的效率有显着的影响。对于本研究中考虑的半导体制造线示例布局，连续移动单元策略在空闲车辆在预定义单元空闲时保持循环，具有最佳的平均提前期性能。

Ventura和Rieksts开发了一种DP算法，用于解决单向单回路系统中的空闲车辆定位问题，以便在考虑对车辆时间可用性的限制时将最大响应时间最小化。 他们还确定了处理提货请求工作量的最少车辆数量。 Hale等人提出了一种方法，以最佳地确定架空桥式起重机的停留点位置，目的是最小化预期响应时间。

Montoya-Torres和Bello开发了一个整数线性规划模型，用于在串联回路系统中优化定位闲置车辆，以最大限度地减少最大响应时间。 他们假设串联回路中的每个区域由至多一个车辆服务，并且区域的分区是已知的。

近年来，作为格栅式布置的特殊情况的具有交叉通道和倾斜通道结构的一般导轨布局在制造业和仓库中变得越来越普遍，以便更有效地利用空间并减少地点。据我们所知，没有出版物考虑在一般的引导路径布局中定位空闲的AGV。本文讨论了在一般定向引导路径网络中优化多个AGV的驻留点的问题。主要贡献是为三个不同版本的问题开发混合整数线性规划（MILP）模型：（i）最小化系统中的平均响应时间，（ii）最小化系统中的最大响应时间，（iii ）考虑到对车辆可用性的时间限制，最小化系统中的最大响应时间。鉴于解决提出的MILP模型所需的计算时间随着AGV的数量和引导路径网络的节点数量的增长而显着增加，我们还提出了可应用于所有三个版本的通用遗传算法（GA）的问题。这种元启发式程序可以在合理的时间内为大规模版本的问题生成最佳或近似最优解。

1. 一般指导路径布局的驻留点位置模型

在本节中，我们提出三个MILP模型，以最佳地定位一般（或常规）导向路径布局中的AGV的驻留点，其可以被建模为定向网络，其中节点表示拾取和下降（P / D）车站和过道交叉口和弧线是连接节点的导向路径。引导路径布局拓扑的考试包括圆形或循环布局，串联循环布局，单维网格布局和二维网格布局（参见图1）。在一维网格布局中，所有AGV都沿同一方向顺时针或逆时针移动，而在二维网格布局中，车辆可以根据其正在经过的弧线改变方向。 AGV引导路径的基础拓扑可以被建模为通用定向网络G（V，A），其中V是节点集合，A包括由V中的节点对定义的弧。可以定义交点作为至少三个引导路径段相交的点，其可以或可以不与P / D站重合。请注意，虽然圆形或循环布局没有交点，但一维和二维网格类型布局必须至少有两个。 G的节点可以是P / D站，交点或与P / D站的交点。令Ifrac14;{v1，v2，...，vm}是包含m个P / D站的集合。令Q = {y1，y2，...，yq}为包含引导路径中的q个交点的集合。然后，V = I [注意，在精心设计的引导路径系统中，G的所有节点的外部程度必须至少为1.否则，具有零度度的节点将产生死锁状态。

图1.AGV系统的一般引导路径布局拓扑示例

令J = {x1，x2，...，xn}是G中的一组驻留点，其中n个AGV在空闲时被定位。 另外，考虑到来自任何P / D站的所有请求都由同一个AGV服务，则S = {S1，S2，...，Sn}是集合I的分区，其中Sj包括由 AGV分配到驻留点xj。 显然，当不考虑对车辆可用性的时间限制时，当P / D站被分配到位于最靠近的停留点的AGV时，获取最小的拾取请求响应时间。 注意，一对（J，S）为驻留点位置问题提供了可行的解决方案，只要J中的驻留点属于G，S是I的分区，并且满足车辆时间限制。

令d（xj，vi）是从驻留点xj到拾取站vi的最短距离，对于，。假设d（xj，vi）= 0，当且仅当vi=xj; 否则，d（xj，vi）gt;0。我们使用Floyd-Warshall算法来确定驻留点和P / D站之间的最短路径的长度。 将sE作为车辆行驶时的速度，并且rji=d（xj，vi）/ sE是从停留点xj到捡拾站vi的响应时间。 来自位于驻留点xj的AGV处理的P / D站vi的请求的响应时间rji是从xj到vi的空行程时间。

Ventura和Rieksts证明存在一个最佳的驻留点集合，其最小化循环引导路径布局中的最大响应时间，其中所有驻留点与P / D站位置一致。在本研究中，下面的定理1将其结果扩展到通常的引导路径布局中的响应时间的任何常规性能测量，其中驻留点是P / D站位置或至少为2度的交点。为了证明定理1，将Q中的交集点划分为Q0和Q“，其中Q0是G中的交点与out-degree等于1，Q”是G中的交集节点，因此，和。此外，令f（J，S）是表示定理1中使用的响应时间的常规性能测量的驻留点位置问题的目标函数。因此，fr（J，S）是响应的非递减函数时间{。

理论1.将fr（J，S）作为一般导向布局中具有n个车辆和m个P / D站的AGV系统的响应时间的常规性能测量。那么，存在一个最优解（Jn，Sn），其中驻留点是P / D站位置或具有至少2的外部程度的交点，即。

证明：令（）是其中至少一个停留点与I中的站点或中的交点不一致的最优解，即。令是J的子集，其中包含与站点位置或交点至少为2的超出点的所有驻留点。让是包含剩余停留点的非空子集。现在，J2rsquo;中的驻留点被J2rsquo;rsquo;中的驻留点所替代，形成如下新的解决方案：每个被替代，其中是在运动方向上与至少为2的最远的站或交点。那么，压缩新的驻留点集，这样。现在，对于来自P / D站的任何接收请求，我们比较服务请求的AGV从驻留点到新的的响应时间：

，

其中r（xjrsquo;，vk）和r（xjrsquo;rsquo;，vk）是相应的响应时间。由于这种关系适用于在J2rsquo;rsquo;中新建驻点处设计的AGV服务的所有提取请求，所以解（Jrsquo;rsquo;，Srsquo;）是可行的，并不比最优解（Jrsquo;，Srsquo;）更差，即fr (Jrsquo;rsquo;，Srsquo;）fr（Jrsquo;，Srsquo;）。这意味着（Jrsquo;rsquo;，Srsquo;）中也是最优解。

现在我们用一个例子来说明定理1。 图。 图2示出了具有五个P / D站（v1至v5）和两个交点（y1和y2）的二维网格布局。

为了说明的目的，让我们假设G中每对节点之间的单位距离，即P / D站和交叉点位置。 在本例中，I = {v1，v2，v3，v4，v5}，Q = {y1，y2}，系统中的AGV数假定为n = 2。 基于定理1，我们只需要考虑解决方案（J，S），其中和Q”= {y2}。 最佳的驻留点集合为Jn = {x1=y2，x2=v2}，最大响应时间为2.在该解中，分配给x1的站组为S1 = {v1，v4，v5}，x2为S2 ={v2，v3}

我们考虑三个不同版本的问题，参考车辆对AGV系统车站接收请求的响应时间，并开发用于通用引导路径布局的MILP模型。

图2. 说明性例子（定理1）

该问题的目的是最佳地确定在通用引导路径布局中最小化平均响应时间的空闲AGV的驻留点。

基于定理1，= {x1，x2，...，xp}是定位空闲AGV的潜在停留点集合，其中”是“的基数，q”是交点数 点数至少为2.将fik设为从站vi到站vk在每个时间单位的接收请求中的流量（例如，每班单位负荷），i为i; k = 1; 2 :::; m，并且w i是与站vi相关联的接收请求的权重，对于i =1,2,......m。 与站点vi相关联的提取请求的权重可以计算如下：

，

其中，i=1,2,......m.

因为所有车站都有负载转移,,其中，i=1,2,......m。按照定义，。

<p

剩余内容已隐藏，支付完成后下载完整资料</p

资料编号：[142063]，资料为PDF文档或Word文档，PDF文档可免费转换为Word