AVS/RS系统动态分析及决策模型

Dynamic Analysis and Decision Making Model of AVS/RS System

方彦军　唐　猛

(武汉大学动力与机械学院，湖北 武汉　430072)

AVS/RS系统动态分析及决策模型

Dynamic Analysis and Decision Making Model of AVS/RS System

方彦军唐猛

(武汉大学动力与机械学院，湖北 武汉430072)

摘要：通过模拟自动小车存取系统(AVS/RS)中任务的动态排队过程，建立了一个基于动态排队网络的系统分析与决策模型。首先，描述了AVS/RS的系统构架、运行规则及任务场景概率。接着，根据系统任务特征构造了一个动态排队网络模型(DQNM)。最后，运用改进的聚合法对该系统模型进行求解，并对系统性能进行分析。分析表明，该模型能够找出系统的最佳小车-电梯组合方式，从而为优化系统的设计、提高设备的利用率、节约系统运行成本提供决策支持。

第一作者方彦军(1957-)，男，1988年毕业于武汉大学电力系统自动化专业，获博士学位，教授；主要从事自动化方面的教学与研究工作。

关键词：AVS/RS动态排队网络聚合法分析决策

Abstract：Through simulating the dynamic queuing process of the tasks in AVS/RS, the system analysis and decision making model based on dynamic queuing network is established. Firstly, the architecture, operation rules and probability of task scenaries of AVS/RS are described. Then the dynamic queuing network model (DQNM) is constructed in accordance with the characteristics of the system tasks. The system model is solved using the improved polymerization method; and the performance of the system is analyzed. The analysis show that this model is able to find out the optimal combination mode of vehicles and lifts, thus it provides decision support for optimizing system design, enhancing the equipment utilization and saving system operating costs.

Keywords：AVS/RSDynamic queuing network(DQNM)PolymerizationAnalysisDecision-making

0引言

自动小车存取系统(autonomous vehicle storage and retrieval systems，AVS/ RS)是一项关于实现智能立体仓储中单位负载自动存取的新技术[1]。在系统配置参数固定的情况下，可以通过改变运行小车及电梯的数量来满足系统不同的吞吐量要求，以提高设备利用率，节约运行成本。

目前，针对AVS/RS的性能评估,国内外学者进行了不同的研究[1-11]。Malmborg[5]提出了运用状态方程模型来预测双命令周期在AVS/RS中交叉使用的比例。Fukunari[7]提出了一个排队网络方法模型来估计预期资源利用率在AVS/RS中交错使用的策略。

本文通过模拟自动小车存取系统中任务的动态排除过程，建立了AVS/RS系统的动态分析与决策模型，对系统的所有任务情景进行评估，并找出了小车-电梯的最佳组合方式。该模型为系统的设计及运行提供决策支持。

1AVS/RS系统的描述

1.1　系统的描述

AVS/RS系统主要由自动小车、货架及轨道和升降电梯3部分组成。由于系统的主要运行成本为自动引导小车(RGV)和升降电梯，RGV占总成本的25%，存储货架的成本与传统的AS/RS系统相当,因此，需要根据系统的吞吐量需求来对运行RGV和升降电梯的数量进行调整。

由于智能仓储中货物的位置都是已知的，寻找货物位置的时间可忽略,因此，系统采用空间随机的存储策略能够降低系统的运行成本[3]。在这种策略下，特定货物的位置是一个随着时间变化的随机变量。对于同一个地址，不同的时间允许存放不同的货物，这样能够保证空间利用的最大化[4]。

系统中通常会包含两种类型的任务：存任务和取任务。存任务是指将单位负载从出入库节点(I/O)运送至可用的空闲货位节点；取任务是指从该负载所在货位节点取货并运送至出入库节点(I/O)。系统的运行规则具体如下。

① 小车的停靠位置为其最后一个存或取任务完成时所在节点；电梯的停靠位置为其最后一个垂直运动完成时所在节点。

② 存取任务的到达时间是均等的，都服从泊松分布；小车进出电梯的时间可忽略不计。

③ 每个电梯配备一个出入库口(I/O)，位于第一层靠近电梯的位置，电梯与I/O口之间的装卸传输时间Tt=14 s。

④ 任务的响应遵循先到先服务(first come first served,FCFS)的策略，需要使用同一部电梯的小车同样遵循先到先服务的策略。

1.2　任务场景发生概率

为了得到完成预期任务的所需时间，需要对所有可能的任务场景进行考虑。本文根据任务类型、小车所在位置、目标货位所在层以及是否使用电梯,将所有任务共分为6个存任务场景和7个取任务场景，一共13个任务场景[12]。

由于智能仓储采用随机的存储策略，且小车在各层服从均匀分布，因此各任务场景的发生概率Pc的计算公式具体为：

Pc=P1P2P3

(1)

式中:P1=λS|R/(λS+λR)为任务类型的概率；P2为被占用小车处于所在层的概率，小车在第一层时为1/T，否则为(T-1)/T；P3为目标货位所在层的概率，目标在第一层时为P1(1/T)，否则为P1(T-1)/T。

2AVS/RS系统的动态排队网络模型

2.1　单任务动态排队网络模型

对于两种任务类型，如果小车需要运行至非当前位置所在层，则要使用电梯。本文令存取任务(S/R)为客户，AVs为二级资源，小车水平方向的移动及搭乘电梯所消耗的时间为服务器，且每个任务在进入队列之前需要分配一台自动小车(RGV)。因此，系统中包含两种类型的动态队列：一种是小车队列；另一种为电梯队列。由此可以构造一个半封闭的动态排队网络模型来模拟系统队列的动态过程[13]。

图1为单任务的动态排队网络模型。图1中，VQ1对应小车从当前位置运行至电梯节点的水平运动过程；LQ相当于电梯的运动过程，当电梯完成小车的运送后才可释放，LQ中存在多台并行的升降电梯；VQ2对应小车从电梯位置运行至目标货位所在节点的位置并加上存或取任务的装载或卸载过程。被占用的小车直到完成整个存或取任务后才会被释放。VQ1和VQ2是用来表示计算小车运行时间的虚拟服务器且存在多台并行的RGV，因此在VQ1和VQ2前分别存在一个虚拟的小车队列。即将到达系统的任务首先进入小车队列，随后进入电梯队列。任务和小车在同步站点中进行一一匹配。

图1　单任务的动态排队网络模型

当一台自动小车空闲时，则一个将要到达的任务就会立即进入系统的队列当中，并跟该小车进行绑定；否则该任务就需要在任务队列中等待，直到有空闲小车出现为止。当任务完成后，小车会回到缓冲区中等待下一个任务的到来。

2.2　多任务场景动态队列网络的合并

所有等级的外部任务到达系统的第一个节点为节点j的总概率可表示为：

(2)

(3)

从节点i流向节点j的任务流量为：

(4)

从节点i离开网络的流量为：

(5)

由式(3)和式(4)可得到整体路径矩阵为：

(6)

各节点服务时间的平均值和变异系数值：

(7)

(8)

i,j=1,2,…,n

图2为合并后的系统多任务综合排队网络模型，由图2可以看出,任务有两种离开对列的方式：从LQ离开或从VQ2离开。取任务可从LQ后离开系统，存任务可从VQ2后离开系统。

图2　AVS/RS综合排队网络

2.3　运行时间的计算

每个场景中RGV在每个阶段的路径及所需时间也不同。例如，若某任务场景中，小车不需要使用升降电梯，则小车将跳过LQ；若小车在I/O节点，则小车将不会访问VQ1；若执行取任务的小车与目标货位在同一层，则直接到达VQ2。VQ1和VQ2的运行距离是沿x、y轴两个方向进行计算，小车沿x轴表示在货架之间运动，小车沿y轴表示在货位之间运动。因此，整体运行时间可由全部运行距离/小车速度得到。同时，也要对小车和电梯的加速、减速和转向迟延时间进行考虑。运行时间的计算分为4个部分。

① 小车从当前位置至电梯所在节点(VQ1)：由于小车可能在任何一个货位，因此需要计算AB个场景的运行时间。

② 电梯从所在层运行至小车所在层(LQ)：电梯的位置可以在任意一层，因此需要计算出T(T-1)种可能的电梯运行时间。

③ 电梯搭载装载货物的小车运行至目标层(LQ)：同样，小车有(T-1)种可能从任一层到达目标层，将装载货物的时间计入运行时间。

④ 小车出电梯运行至目标货位所在节点并卸载货物(VQ2)：同样，需要计算出AB种可能的运行时间，同样将卸载货物的时间计入运行时间。

将②和③中的值相加可得出LQ的值，3种服务器的访问顺序为VQ1-LQ-VQ2。不同的任务访问服务器的次数也有差别，因此对于整个系统的分析需要根据式(7)和式(8)将任务各环节的消耗时间进行合并。

3 AVS/RS任务排队模型的求解及分析

本文运用改进的聚合法[14]对该系统网络模型进行求解，需要经历4个步骤。

① 将DQN模型转化成CQN模型，将同步站点设为第一个站点，任务在此等待小车。

② 将同步站以外的所有站点视为一个CQN模型，计算出任务的相关吞吐率。

③ 用步骤②计算得到的任务相关指数服务器代替同步站点。

④ 考虑同步站点的隔离并通过求解M/M/1模型[15]，计算得出外部队列数量的平均值。

由于模型中每个节点存在多个并行的服务器，因此本文采用基于λ(n)/Ek/m(m为任务数)的CQN扩展模型分析法。

① 任务的相关到达率：假设任务到达每一个节点的概率等于其离开此节点的概率，则节点j的任务到达(离开)率λj(n)可根据式(9)进行迭代[13]，得到以下计算公式：

(9)

式中:θj(n)为当节点j中含有n个任务时的服务率；Pj(n)为整个网络中含有N个任务时n个任务到达节点j的概率。

(10)

对于Erlang-k阶段型分布，任务从第一阶段进入到下一阶段的概率总是保持不变的。由于每个任务在每个阶段所消耗的时间都服从指数分布，因此，每个阶段的任务到达率相同。

③ 系统性能指标计算如下。

各节点(站点)的吞吐率为：

(11)

各节点(站点)中的平均任务数量为：

(12)

则各节点(站点)中任务的平均消耗时间为：

(13)

整个网络的吞吐率为：

(14)

式中:ej为单个任务访问节点j的平均次数。

4实例应用与分析

本节以某省级电力公司电能计量设备检定中心智能仓库为实例来验证本文提出的分析算法。该系统参数为：RGV数量V=12台，升降电梯数量L=8部，货架长度Lx=12m，高度Ly=11.5m；货架数量A=24排，均为双排货架，每排层数T=23，单层每面货位数B=13，共43 056个货位；单元货位高度h=0.5m，宽度w=0.8m。RGV的水平速度Vv=2m/s，升降机的速度VL=2m/s。λS为存任务的到达率，λR为取任务的到达率。

运用软件ARENA12.0对第三节提出的SCQN模型求解步骤和系统分析方法进行仿真验证，得到实例系统的性能参数如表1和表2所示。通过改变存任务和取任务的到达率λS和λR来对不同小车和升降机数量的配置组合进行分析比较。

表2中，M为每小时任务数，n1~n3为各站点的任务数。

由第三节可知，本系统的排队网络模型转化成了一个不包含同步站点的CQN模型，因此共含有3个工作站点，表1为仿真得到的3个站点的性能参数。

表1　系统性能参数a

表2　系统性能参数b

表3~表6为本文满足存取任务每小时到达率相等的前提下，即：λS=λR(λS、λR分别为存任务和取任务大到达率)，在3种不同任务到达率的情况下按照本文提出算法得到的4个最佳V-L组合的系统性能分析结果。其中，Lex为电梯外部对列平均长度，Ln为网络中任务(小车)的平均数量(包括正在等待服务)，Lv为在小车缓冲区中的小车平均数量，Ln/(Ln+Lv)为小车的平均利用率，Wex为电梯外部队列的平均等待时间，UL为电梯的平均使用效率。

表3　V=11，L=7时的系统效率

表4　V=11，L=6时的系统效率

表5　V=10，L=7时的系统效率

表6　V=10，L=6时的系统效率

由以上表格可以看出，当λS+λR=200时，V=10、L=6组合的队列长度要小于其他3种组合，电梯外部队列的等待时间最短，且小车与电梯的平均利用率同为最高，说明在此情况下，该种组合为系统的最优运行方式。同理，当λS+λR=250时，系统各项性能指标均最优，应当选取V=11、L=6组合作为其运行方式。对于组合V=11、L=7，虽然在此任务到达率区间，表面上看小车数量的增加会加快任务的进度，但是由于等待时间的加长会使任务的完成时间变得相对更长一些，此时小车与电梯的平均使用率均为最低，从而降低了整个系统的利用率，这就说明在此组合下系统的成本较高且小车与电梯在相当长的一段时间处于闲置状态。因此，要选择小车平均利用率较高的组合作为系统的运行方式。

综上所述，本文模型可以根据系统的预期吞吐量为系统的前期设计提供方案，同时在系统实际运行时，系统管理者可以根据不同的任务量(到达率)来调整系统的运行方式，即：小车和升降电梯的数量组合，从而为系统的使用率最大化和成本最小化提供决策支持。

5结束语

针对AVS/RS系统的特点 ，本文提出了一个基于半封闭动态排队网络的分析与决策模型。首先，对系统的构架及运行规则进行描述与定义，并分析各任务场景的发生概率。其次，构造了一个系统的排队网络模型，将多种任务排队模型转化为一个单级的排队网络(DQN)模型。然后，对该模型进行求解，并对其性能进行分析，得出系统的性能指标。最后，以某省电力公司计量检定中心的智能立库为例，运用本文提出的分析决策模型及算法对不同V-L组合下的系统效率进行仿真分析。结果表明，本文方法能够准确地模拟制造过程和实际应用当中所遇到的问题，为系统的优化设计及提高设备使用率、节约运行成本提供决策支持。

参考文献

[1] 罗键，吴长庆，李波，等.基于改进量子微粒群的轨道引导小车系统建模与优化[J].计算机集成制造系统，2011,17(2)：321-328.

[2] Fuku M,Mborg C J.An network queuing approach for evaluation of performance measures in autonomous vehicle storage and retrieval systems[J].European Journal of Operational Research,2009,193(1):152-167.

[3] 吴长庆，何善君，罗键,等.自动小车存取系统中轨道引导小车环路死锁控制的研究[J].计算机集成制造系统,2008，14(9):1767-1773.

[4] Banu Y,Sunderesh S.An approximate solution for semi-open queuing network model of an autonomous vehicle storage and retrieval system[J].Transaction on Automation Science and Engineering,2013,10(1):205-215.

[5] Tsai H,Lin Y.Modification of the fish swarm algorithm with particle swarm optimization formulation and communication behavior[J].Applied Soft Computing,2011,11(8):5367-5374.

[6] Pan Q K,Tasgetiren M F,Suganthan P N,et al.A discrete artificial bee colony algorithm for the lot-streaming low shop scheduling problem[J].Information Sciences,2010,181(12):2455-2468.

[7] Fuku M,Mborg C J.A network queueing approach for evaluation of performance measures in autonomous vehicle storage and retrieval systems[J].Operational Research,2009,193(13):203-205.

[8] Wang X,Tang L.A tabu search heuristic for the hybrid flow-shop scheduling with finite intermediate buffers[J].Computers & Operations Research,2008,36(3):907-918.

[9] Kuo P H,Krishnamurthy A,Malmborg C J.Performance modelling of autonomous vehicle storage and retrieval systems using class-based storage policies[J].Computer Applications in Technology,2008(31):238-248.

[10]Ekren B Y,Heragu S,Krishnamurthy A,et al.Simulation based experimental design to identify factors affecting performance of AVS/RS[J].Computer Engineering,2010(58):175-185.

[11]Tsai H C,Lin Y H.Modification of the fish swarm algorithm with particle swarm optimization formulation and communication behavior[J].Applied Soft Computing,2011,11(8):5367-5374.

[12]Ekren B Y,Heragu S S.Simulation based regression analysis for the rack configuration of an autonomous vehicle storage and Retrieval system[J].Production Research,2010(48):6257-6274.

[13]Wang Ling,Zhou Gang,Xu Ye,et al.Advances in the study on hybrid flow-shop scheduling[J].Control and Instrument in Chemical Industry,2011,38(1):1-8.

[14]Avi-Itzhak B,Heyman D P.Approximate queueing models for multiprogramming computer systems[J].Operational Research,2013(21):121-128.

[15]Dallery Y.Approximate analysis of general open queueing networks with restricted capacity[J].Performance Evaluation,2009(11):209-222.

中图分类号：TP273

文献标志码：A

DOI:10.16086/j.cnki.issn1000-0380.201501005

修改稿收到日期：2014-06-17。