具有跨多层式自动导向小车的物料运输系统排队网建模与分析

刘晓鹏，陈炫锐，林 军，陈庆新，毛 宁，张惠煜

(1.广东工业大学 广东省计算机集成制造系统重点实验室，广东 广州 510006；2.中国电子产品可靠性与环境试验研究所，广东 广州 510610)

由于土地成本提升和工艺流程多样化，企业开始将生产车间向三维空间发展[1]，建立一种多层单元流水式车间，其典型结构如图1 所示。该类车间适用于目前兴起的个性化定制生产，能够满足生产批量小、品种类型繁多、交货期紧、生产系统需要高度柔性等多个生产需求。但多楼层的车间布局使得车间物流储运需求分布呈现高度的时空不均衡性，因此，一个机动性高，面对生产波动时能够快速调配储存能力的物料运输系统必不可少。

图1 多层单元流水式车间典型结构Figure 1 The typical structure of a multi-floor flow shop

对于多层单元流水式车间，基于单向导向路径网络 (unidirectional guided-path network, UGN) 的多台自动导向小车 (automated guided vehicle, AGV) 物料运输系统比具有多辆双向行驶功能的AGV 所组成的物料运输系统更合适。首先，前者的配置、运作、优化成本更低；其次，在死锁预防及避免方面具有一定的优越性，结合在不同的楼层之间往返的升降机，可实现AGV 跨多层和各层AGV 数量调配的功能，这是来回于两道工序的传统专用 AGV 不具有的，但也带来了一定的复杂程度和分析难度：1) 路径网络更加复杂，无法通过简单的路径概率来描述，使得建模困难；2) 物流储运需求多变，必须考虑一般分布的排队网模型，进一步增加求解难度。

目前国内外对于AGV 物料运输系统的研究按应用场景分为两类：1) 由AGV 运输单元耦合多个加工站的生产系统；2) 由AGV、升降机和立体货架组成的自动小车仓储系统 (autonomous vehicle storage and retrieve systems, AVS/RS)。对于由AGV 运输单元耦合多个制造单元的生产系统，一般采用开排队网模型，通过一系列节点描述在制品的加工和运输等过程。Smith[2]利用一种与状态相关的排队网模型对物料搬运系统的性能建模和优化进行研究，大量的实验证明了该模型在物料搬运系统的设计过程中具有良好的鲁棒性。Smith[3]还针对具有有限缓冲区和一般服务时间队列的排队网模型，提出了一种二阶矩方法近似计算物料搬运系统的吞吐量、在制品和周期时间等性能指标，并对缓存容量与系统性能的关系进行了推导。廖勇等[4-5]分别对具有随机路径和具有非同等并行的AGV 搬运系统进行研究，根据其特点建立具有有限缓存的开排队网模型，并改进了传统的状态空间分解法，结合马尔科夫链分析节点状态转移的规律，最终构造迭代算法以近似求解系统的各项性能指标。虽然关于AGV 物料运输系统的研究已有一定成果，但跨多层式AGV 物料运输系统的路径网络更加复杂，且物流储运需求多变，因此以上方法并不适用于本文研究的物料运输系统。

对于由AGV、升降机和立体货架组成的AVS/RS，一般采用混合排队网模型，即开排队网和闭排队网相结合 (semi open queuing networks, SOQN)，通过引入同步站的概念描述运输过程和加工过程的约束关系。最早是由Jia 等[6]提出将SOQN 引入到AVS/RS的性能分析中。此后，Erken 等[7-8]将SOQN 用于分析法国一个使用AVS/RS 的仓库，分别用聚合法和矩阵几何法估算系统的性能指标；Roy 等[9-10]将SOQN 用于分析AVS/RS 不同层的配置参数，如存储数量位置、深宽比和车辆数量等，使用基于分解的方法对排队网络进行评估，模拟了单位荷载垂直运输过程中车辆和升降机之间的相互作用；陈炫锐等[11-12]针对定制型装备制造企业，优化了AVS/RS中运输设备的资源配置，将启发式算法与排队网络分析模型相结合，为该类系统的工程设计人员提供了一种有效工具。以上研究在其领域均已有重大突破，虽然研究对象与本文不同，但其建模思路和求解方法存在可借鉴性。因此，本文根据多层车间的生产特点，将SOQN 拓展至跨多层式AGV 物料运输系统的研究中，采用两矩近似法描述具有一般分布的节点服务时间，通过迭代算法近似求解该系统的性能指标，并对其进行敏感性分析。

本文的研究方法，与前人相比的创新之处如下。

1) 研究对象为多层车间中的物料运输系统，其中AGV 可跨多层，和各层AGV 数量可调配，目前尚未见到类似系统的文献，是对现有研究领域的一种补充。

2) 充分考虑运输路径复杂和储运需求多变的影响，研究具有一般分布的排队网模型，提高了排队网在生产领域的适用性。

1 问题描述

图2 为多层车间中某一楼层的层内具体分布，由多个区块组成，区块中包含若干同等或非同等柔性加工单元，每个区块代表一道加工工序，每道工序有多个上下料 (input/output, I/O) 口。物料的大致流向为：粗加工区→半精加工区→精加工区→装配区→成品区。在物料流动过程中AGV 负责将在制品由原工序的下料口运往下一道工序的上料口进行加工，若两道工序不在同一楼层，则由升降机负责将AGV 运往目标楼层。当AGV 完成任务后，AGV 变为空闲状态，在驻留点等待执行新的任务。整个过程中，当任务到达时没有空闲的AGV，则任务需要在待转运缓存区等待；若升降机正在进行运输任务，则AGV 需要在升降机前等待。

图2 多层车间楼层内部分布Figure 2 The internal structure of a multi-floor shop

根据以上流程，本文基于排队网理论建立如图3所示的排队网模型，包含的符号及含义见表1。

表1 相关参数定义Table 1 Definitions of related parameters

图3 跨多层式AGV 物料运输系统排队网模型Figure 3 The queuing network model of a material handling system with multi-floor AGVs

2 排队网模型性能分析

2.1 模型假设

图3 所示为跨多层式AGV 物料运输系统的排队网模型，由3 个表示运输过程的服务节点组成，分别为AGV 空载运输过程、AGV 负载运输过程和升降机运输过程。该模型表示当运输任务进入系统后，存在4 种服务流程，具体如下。

1) P1：AGV 空载运行，到达装货位置后，AGV 负载运行至卸货位置，任务离开系统，AGV返回驻留点，经过节点的顺序为：V1, V2。

2) P2：AGV 空载运行，经升降机到达其他楼层，AGV 空载运行至装货位置，AGV 负载运行至卸货位置，任务离开系统，AGV 返回驻留点，经过节点的顺序为：V1, L, V1, V2。

3) P3：AGV 空载运行至装货位置，AGV 负载运行经升降机到达其他楼层，AGV 负载运行至卸货位置，任务离开系统，AGV 返回驻留点，经过节点的顺序为：V1, V2, L, V2；

4) P4：AGV 空载运行，经升降机到达其他楼层，AGV 空载运行至装货位置，AGV 负载运行经升降机到达其他楼层，AGV 负载运行至卸货位置，任务离开系统，AGV 返回驻留点，经过节点的顺序为：V1, L, V1, V2, L, V2。

该模型满足的假设条件如表2 所示。

表2 假设条件Table 2 Assumptions

2.2 路径概率计算

由于AGV 存在多个可停留的驻留点，并且每次的运输任务都是不固定的，即运输路径具有不确定性。因此需要按照任务类型定义多种可能存在的场景，然后计算相应场景发生的概率，最后根据两矩近似法求解物料运输系统的性能指标[13-14]。根据多层车间中的区块数量，以及每个区块的上下料口数量，可以计算出AGV 可能前往的目的地数量，即可能存在的任务类型数量：其中部分任务类型为目的地不在任务起始楼层，需要升降机将AGV 运往目标楼层，再由AGV 运往目的地；另外也可能存在AGV 不在任务起始层的情况，具体结果如表3 所示。

表3 场景概率Table 3 Probabilities of various scenarios

其中wr,m表示各种任务类型的比例，即车间中各道工序的储运需求。对于物料运输系统的研究，一般是已知任务类型的比例和输入速率，但在多层车间中由于存在大量不确定因素，各道工序之间存在复杂的耦合关系，它们之间的储运需求是相互影响的，因此必须通过参数分解法[15]计算各节点的输出速率，具体计算方法详见文献[16]，限于篇幅原因，下面只介绍任务类型比例的计算方法。

假设多层车间中原材料的输入速率 λ 已知，可以推导出各个加工节点的输出速率，即运输任务的输入速率 λr,m，对各类运输任务进行累加[17]，可得

根据各种任务场景发生的概率，分别计算4 种运输路径的概率：

2.3 节点服务时间计算

2.3.1 升降机服务节点

节点L 表示升降机的运输过程，由于仅考虑升降机负载运行过程，因此具体路程与移动的楼层数量相关，对于一个s层车间，总共有种移动情况，升降机各种移动情况的概率均相等，即根据升降机的运行速度和加速度对节点的服务时间进行估算，分升降机到达最大速度和没有到达最大速度两种情况，期望服务时间为

式中，y(s) 表示升降机在垂直方向的路程，y(s)=r×h。

2.3.2 AGV 服务节点

节点V1和V2分别表示AGV 空载和负载的运输过程，由多段水平方向的路程组成，具体路程与AGV 的驻留点和目的地相关，可根据AGV 的运行速度和加速度对节点的服务时间进行估算。考虑AGV 在过弯时需要减速为0，分AGV 到达最大速度和没有到达最大速度两种情况，期望服务时间为

其中， AGV 在任意驻留点位置的概率均相等，即P(d)y(r,m) 表示AGV 在水平方向的路程，具体数值详见第3 节算例分析。

与升降机不同的是，AGV 的运输路径较为复杂，虽然在驻留点位置的概率均相等，但要前往的目的地受储运需求的影响，其概率并不是相等的，因此根据两矩近似法[14]对其服务时间均值和变异平方系数 (square coefficient of variation, SCV) 进行修正。

式中，qk表示路径k经过的节点数量；qkι表示路径k经过的第 ι 个节点；1 {(k,ι):qkι=j} 表示路径k是否经过节点j；表示第k类路径的输入速率； τkι和表示第k类路径在第 ι 个节点的服务时间和SCV。

2.4 迭代求解

为了分析跨多层式AGV 物料运输系统的性能指标，本文基于文献[11]中的迭代算法对上述排队网模型进行求解。该方法通过不断估算系统中正在运输的设备数量和等待运输的设备数量，在达到稳态时与实际运输设备的数量进行对比，当估算值与实 际 值 的 差 距 δ 小 于 ε 时 结 束 迭 代，其 中 ε 取 值 为0.001。关于聚合法[18]的求解在此处不作阐述，具体求解步骤如下。

步骤1初始化。

假设初值 L ow=λ ， H igh=2λ 。

步骤2迭代过程。

步骤2.1 计算各个加工节点的输出速率 λr,m；

步骤2.2 由式 (1) ～ (6) 计算运输路径的概率{P1,P2,P3,P4}；

步骤2.3由式 (7)～(12) 计算各个节点的服务时间和

步骤2.4 通过聚合法估算各个节点和物料运输系统的吞吐率

步骤3收敛检验。

步骤3.1 计算 δ =L+Lv1+Ll+Lv2-na；

步骤 3.2 如 果 δ ＜-ε ，重 设 边 界 为 L ow=λ ，High=2θ，返回步骤2；

步骤 3.3 如 果 δ ＞ε ，重 设 边 界 为 L ow=θ ，High=2λ，返回步骤2。

步骤4指标计算。

迭代终止，物料运输系统的吞吐率为 θ ，等待中的AGV 数量为L，运输中的AGV 数量为Lv1+Ll+

3 算例分析

本文提出的相关算法在Matlab 软件平台编程实现，电脑配置为Microsoft Win10 操作系统，CPU 2.90 GHz，8.00 GB RAM 的硬件环境，在Demo3d软件上建立三维仿真模型。为了避免因实验初始启动数据带来的影响，根据大数定理，所有实验模型均在95%的置信水平独立下重复5 次，每次实验时间500 d，统计稳态后100 d 的数据，以准确描述生产系统的仿真结果。

3.1 仿真模型

跨多层式AGV 物料运输系统的三维仿真模型如图4 所示，物料大致流向为：原材料首先进入二层粗加工区，完成若干道工序后由升降机运往三层精加工区，在制品加工完成后回到一层装配区，经过组装打包后进入成品区。本文通过计算百分比误差∆1=((θA-θS)/θA)×100% 和 ∆2=((LA-LS)/LA)×100% ，来验证所提出方法的准确性。其中，Δ1表示平均吞吐误差率，Δ2表示AGV 利用误差率。A 表示文本所提方法，S 表示仿真方法。

图4 跨多层式AGV 物料运输系统三维仿真模型Figure 4 The 3D simulation model of a material handling system with multi-floor AGVs

3.2 算例Ⅰ——任务输入率对系统性能的影响

以某机器人生产企业为背景，根据其多层车间中的设备参数进行分析，具体参数如表4 所示。通过变化任务输入率和任务节点服务过程的分布类型，分别取SCV=0.5、1 和1.5，即二阶爱尔朗分布、负指数分布和二阶超指数分布，计算其系统的性能指标，对比结果如表5 所示。

表4 系统参数设置Table 4 Settings of system parameters

表5 算例Ⅰ实验结果及其相对误差Table 5 Experimental results and relative errors of Example Ⅰ

由表5 可以看出，与仿真结果相比，在计算系统吞吐率和AGV 利用率方面，本文所提方法的误差在可接受的范围内，对于AGV 平均利用率的计算效果很好，误差均低于3%，平均误差为1.26%。如图5 所示，随着任务输入率的增长，系统的平均吞吐率和AGV 的平均利用率均有明显的递增趋势；但系统平均吞吐率的增长越来越缓慢，这是因为高任务输入率的情况下，使得物料运输系统接近满负荷运行状态，AGV 多为忙碌状态，当系统中没有空闲的AGV 时，系统平均吞吐率将不再上升。

图5 算例Ⅰ性能指标变化曲线Figure 5 Curves of system performance indicators in Example Ⅰ

对于较高任务输入率的物料运输系统的性能，需要通过权衡系统吞吐率和AGV 利用率的关系，进而合理增加AGV 的数量或提高AGV 的运行速度，否则当系统中可利用资源不足时，容易造成任务等待时间过长和缓存区堵塞等问题，影响了物料运输的速率，最终导致在制品的平均生产周期变长。

3.3 算例Ⅱ——AGV 数量对系统性能的影响

本算例分析AGV 数量对物料运输系统性能的影响，系统参数设置如表4 所示。假设任务输入率为1.2，通过变化AGV 的数量na分别取值7、8、9 和10，得到系统的性能指标，计算结果如表6 所示。

表6 算例Ⅱ实验结果及系相对误差Table 6 Experimental results and relative errors of Example Ⅱ

由表6 可以看出，与仿真结果相比，在计算系统吞吐率和AGV 利用率方面，本文所提方法的误差在可接受的范围内，对于系统平均吞吐率的计算效果很好，误差均低于4%，在SCV=1 时，平均误差为1.07%。如图6 所示，随着AGV 数量的增加，系统平均吞吐率有明显的递增趋势，但增长的速度越来越缓慢，原因是生产系统的物流储运需求接近满足，而AGV 的平均利用率降低，这是因为当系统中的物流储运需求接近满足时，空闲的AGV 数量会越来越多，虽然有利于生产系统的运行，但也造成了一定程度的资源浪费。

图6 算例Ⅱ性能指标变化曲线Figure 6 Curves of system performance indicators in Example Ⅱ

综上所述，增加AGV 的数量可以提高物料运输系统的吞吐率，但提高了投资的成本，同时在有效的运输轨道内，多台AGV 容易造成拥堵的问题，进而影响运输的效率，因此合理地配置运输设备的数量显得尤为重要，特别是在较高任务到达率的系统中，合理的运输设备配置既有利于生产系统的运行，同时也能减少投资的成本。

4 结束语

针对多层车间中的AGV 物料运输系统，充分考虑其可跨多层且路径随机的特点，研究各种运输路径和任务类型对应的场景概率，同时结合实际生产情况，提出一般分布的混合排队网模型，描述系统中物流储运需求的多变性，从而有效求解系统性能指标值。建立一个集有效性和精确度验证为一体的三维仿真实验平台，对不同方法的求解结果进行对比，并分析任务输入率和AGV 数量对系统吞吐率和AGV 利用率的影响，其结论可为该类物流系统的设计人员提供相关的指导建议。

本文研究具有跨多层式AGV 的物料运输系统，运输设备由AGV 和升降机组成，其中升降机的数量和位置也是影响系统性能的重要因素之一，今后将针对更复杂的物料运输系统进行研究。