基于规则的环形穿梭车系统调度算法的应用研究

张可义，徐 健，田 博，向 旺，蔡 苗

（北自所（北京）科技发展有限公司，北京 100120）

0 引言

环形穿梭车作为运行在固定轨道上的智能物流设备，在物流仓储行业中的应用越来越广泛。环形穿梭车系统常用于连接自动化立体仓库系统和出入库站台系统，具有方便快捷和灵活高效的特点，比数量繁多的直行穿梭车系统和布局复杂的输送机方案具有更大的优势。而数量众多的穿梭车在环形的固定轨道上运行时，如何尽量避免堵塞、合理地分配穿梭车的作业则是我们关注的重点。

传统的调度算法往往通过上位机系统采集信息、依据算法分析信息、通过特殊软件计算得出优化结果后下发给穿梭车执行作业任务。面对环形穿梭车系统的站台变化快、高速运行时位置信息随时变化等实际情况，传统的调度算法模式用时较长，还可能会错过最佳站台位置。因为RGV在环形轨道上大部分时间是在高速运行中，当RGV收到作业任务时，RGV可能刚刚通过了需响应的作业站台位置，可能会错过一些最优路径的调度作业，这就要求我们努力寻找一种实时性更好、适应性更强的调度算法。于是，我们提出了基于规则的环形穿梭车作业调度算法，提出了三种作业调度区域规则的概念和一些辅助规则，通过在PLC控制系统融入这些规则，从而实现对环形穿梭车系统作业的优化调度。

1 环形RGV系统调度算法优化的理论分析

环形RGV一般是在固定的封闭式环形轨道上单方向运行，根据输送系统的布局，设定顺时针运行或逆时针运行。环形RGV系统也多采用单工位类型，能够实时获取自身和相邻RGV的位置、状态和作业情况，沿着轨道一圈可以完成一个或者多个作业。环形RGV系统如图1所示。作为自动化立体仓库和入出库站台的重要枢纽，进行货物的传递和输送，是自动化物流仓储系统很重要的组成部分。

图1 环形RGV系统

环形RGV的作业任务主要包含：取货、行走和送货三个过程，完成一个完整作业时间如下：

式中，t总为RGV一个完整作业时间，tw为RGV全程行走总时间，包括：加减速运行时间ta，匀速运行时间tc和停车等待时间tp。tl为RGV取货或送货输送时间（二者通常相等且固定不变），t0为RGV的信息交互时间（通常是固定不变的）。

根据式(1)，一个完整的作业任务的快慢主要由tw来决定，而tw与行走过程中是否堵塞关系很大，堵塞的次数越多，停车和减速次数就越多，必然造成所用时间增多，故要提高环形RGV系统效率，就得需要合理调度RGV作业，使得RGV在环形轨道中运行时，尽可能多和尽可能早的形成作业，才可能提高环形RGV系统效率。所以，目标简化为：作业次数多和堵塞次数少，建模如下：

式中，tc是第c台RGV在固定时间内作业次数，Bc(q)为第c台RGV在固定时间内因为堵塞而停车等待的次数，也即堵塞次数，n为整个轨道上RGV的数量。

基于以上的理论分析，本文提出的基于规则的调度算法，也是主要考虑尽量多形成复合作业和尽量避免堵塞两个主要方面，当然也考虑了对站台的预判断，系统提前响应站台取货请求和提前启动作业等措施。基于一些特殊的规则，通过PLC程序对这些规则进行实现，从而达到提前、快速和及时响应站台作业请求，形成调度作业，执行作业任务。

2 基于规则的调度算法的实现

在环形穿梭车系统中，基于规则的调度算法，是把环形RGV系统和上位机调度系统的功能融为一体，作为一套独立的系统，基于一定的规则，通过PLC控制系统实现调度算法，各个RGV作为智能从站，实时对各个站台的作业请求进行智能判断，根据算法规则的优先级进行筛选，在具备条件的情况下以最短的时间形成作业任务，迅速去执行，并及时把相关信息传送给地面主控制器，地面主控制器作为枢纽，进行相邻RGV或者作业相关的RGV之间的信息传递。各RGV根据地面主控制器传递的相邻RGV的信息进行避让和对作业调度区域进行调整，PLC控制系统的网络图，如图2所示。

图2 设备网络图

基于规则的调度算法中，各个RGV会根据环形轨道的布局、轨道上RGV数量和站台布局等因素进行智能判断，得出不同区域RGV与相邻RGV的最佳距离，也就是说每一台RGV每次作业完成后，都会根据后面相邻RGV的相关信息，很快停靠在一个最佳位置，以此类推，整个系统各个RGV很快会处于动态平衡状态，整个系统就能够随时选择RGV以最快的速度和最小的距离及时响应任意站台的作业请求，同时也能够避免环形轨道上的堵塞。

3 作业调度区域规则

基于各个RGV在轨道上的合理动态分布，选择了环形RGV的不同作业调度区域作为调度算法的主要规则，再依据一些特定的规则，通过PLC控制系统实现环形RGV的最优调度方案，调度方案是通过各个RGV在特定作业调度区域内进行作业调度，作业调度区域主要包括：标准调度区域、扩展调度区域和全局调度区域。

3.1 RGV标准调度区域

RGV标准调度区域为前RGV所在位置到本RGV所在位置所覆盖的区域，如图3所示,RGV沿着逆时针单方向运行，RGV1的标准调度区域为站台L01-L04之间，RGV2的标准调度区域为站台L05-L06之间,RGV3的标准调度区域为站台L07-L11之间。标准调度区域主要体现了调度作业分配的优先近处规则。环形RGV根据一定规则分布在整个轨道上，所有RGV的标准调度区域囊括了整个轨道区域的所有站台，为每个有作业请求的站台都提供了相对均等的机会，也避免了传统调度算法可能形成同一区域多个作业容易导致堵塞的情况。

图3 RGV标准调度区域

3.2 RGV扩展调度区域

在标准调度区域的基础上，为了预先更快形成调度作业，我们提出了RGV扩展调度区域的概念，如果某个RGV前面的RGV正在执行取货作业时，后面RGV可以把调度区域扩展到前RGV取货作业站台位置后面的站台位置，如图4所示，比如RGV4正在执行从L14站台的取货作业，则RGV3的调度区域可扩展到如图4所示的站台L13的位置，这样当前面RGV4还在站台L11-L12位置处，RGV3就可以把调度区域扩展到站台L13处，从而提前进行调度作业，当此时站台L12或L13处有作业需求时，能够预先形成调度作业，在RGV4前进时，RGV3就同时前进去站台L12或L13处进行取货作业，对站台请求进行预先判断，提前形成作业任务以便提前启动RGV运行，从而提高系统的整体运行效率。

图4 RGV扩展调度区域

3.3 RGV全局调度区域

在扩展调度区域的基础上，我们进一步优化提出了RGV全局调度区域的概念。当RGV相邻的前面RGV正在作业时，且已经完成了从起始站台取货，正在往目的站台运行时，本RGV调度区域可以再次扩展到前RGV的优化调度台列（此优化调度站台列与运行的目的地址以及自身前车RGV的位置信息等有关），前车的优化调度站台列可能再次扩展到前车的前车优化调度站台列，以此类推，若前面几辆车都处于已经取完货正往目的站台运行的情况，本RGV的调度区域就可能进一步扩展到环形轨道很大区域甚至是扩展到全部区域，这样RGV就能更早的捕捉到更大区域的站台作业请求，显著地提升了环形RGV系统的作业效率和响应速度。全局调度区域体现任务调度的全区域覆盖性，也体现了调度任务的更早的预判性。如图5所示，假如RGV2正在执行从站台L06的取货作业，准备送往站台L19,RGV3正在执行从站台L10取货，准备送往站台L18，则RGV1的调度区域可以扩展到从站台L01到站台L11的更大区域，以此类推，每个RGV均有可能出现调度区域扩展到全区域的可能性，从而更早更快的响应站台的作业请求。

图5 RGV全局调度区域

4 辅助的规则

除了基于三种调度区域的规则外，我们还提出了一些辅助的规则，通过这些规则的应用，环形穿梭车系统各个RGV能够有条不紊的作业，有效的避免堵塞和不必要的等待，这些规则主要包括：调整站台优先级规则、合理停靠区域规则和空闲不停车区域规则。

4.1 调整站台优先级规则

在调度区域内，调度站台的优先级是根据站台请求的等待时间长短来判断的，这体现了先进先出的规则。如图6所示，假如RGV2的调度区域为站台L05-L06，则根据L05-L06站台的等待时间最长的站台优先形成调度作业，假如站台L05和站台L06均有作业请求，而L05等待时间更长，按照本文上面介绍的标准调度区域的规则，RGV2应该形成从站台L05的取货作业，若后面RGV1处于空闲状态，根据本文上面介绍的扩展调度区域规则，RGV1可能会形成从L06取货的作业，若完全按照以上分析的调度规则执行，可能会形成RGV1准备往L06处运行时，RGV2还在站台L05处取货，堵塞了RGV1，只能等待RGV2从站台L05取货完毕，离开站台L05，RGV1才能继续前进到站台L06处进行取货作业，针对此种情况，我们提出了调整站台优先级的规则。

图6 调整站台优先级规则

当后车空闲时，若本车调度区域内有两个或两个以上的站台均有取货作业请求时，若后面站台优先级高的时候，需要调整前后站台的优先级，先执行前面站台的取货作业，以便后车及时过来执行后面站台的取货作业，也就是说提前给后车留机会，这样前车和后车均可以迅速到达这两个站台处，同步进行取货作业，之后同步向前运行，避免了堵塞，提高了系统整体的作业效率。

4.2 合理停靠区域规则

为进一步合理布局RGV无作业时在环形轨道上的动态分布，我们还提出了合理停靠区域规则。如图7所示，此环形RGV沿着轨道逆时针单向运行，根据合理停靠区域规则，我们会调度RGV在出库作业区L19站台和入库作业区L20站台之间近距离停靠多辆RGV，以便入库站台L20-L22有取货请求时，多辆RGV系统能够及时迅速的形成调度作业，把入库站台L20-L22上的货物及时快速的取走，从而提高环形RGV系统效率。

图7 合理停靠区域规则图示

4.3 空闲不停车区域规则

针对环形轨道区域中一些无站台的区域和出库作业区域，我们提出了空闲不停车区域的概念，此区域范围有空闲RGV时，继续前进以便停靠在更合适的区域，避免在个别特殊区域不该停车时停车，同时能避免需要停车的区域RGV数量不足，从而整体及时快速响应站台取货请求。如图8所示，L16和L19的区域之间就不适合停放空闲的RGV，同样在L22到L01的区间也是不适合停放RGV的，此类区域若有空闲RGV，需及时运行到入出库站台之间或者立库站台区域的合适位置。

图8 空闲不停车区域规则图示

5 工程应用

综合以上的三种调度区域和辅助规则，我们形成了一套基于规则的调度算法，环形RGV系统各个RGV能够根据站台布局、前后RGV作业状态及站台作业情况等因素，合理调度作业、合理停靠在环形轨道的最佳位置，更早更快的响应站台的作业请求，大大的提高了环形RGV的系统效率。

在某化纤企业成品立体仓库中的应用中，环形轨道长度248米，其中直道230米，弯道18米，站台33个，环形RGV共设置8台RGV，环形轨道直道速度120米/分钟，弯道24米/分钟，输送机速度16米/分钟，托盘交接输送距离1.6米，托盘输送方向为1.2米，RGV与站台交接响应时间0.5秒。

根据式(5)，得出t总=tw+12.5

tw=0.5秒，tl=1.6/16×60秒=6秒，2tl+t0=12.5秒，一个完整作业时间主要取决于tw的值。

根据式(6)计算能得到行走时间。经现场实际测试，采用了基于规则的调度算法后，实测的12小时的均值为320托/小时，原有系统的实测12小时均值为238托/小时，效率提高了34.5%。

这种基于规则的环形穿梭车调度算法，后经在多个项目的运行测试，具有一定的实用性和稳定性。作为一个独立的系统，通过PLC控制系统来实现调度作业，基于特定的规则，脱离了上位机调度系统，避免了复杂的智能算法和实效性差的弊端，既为企业节约了成本，又满足了系统对高实时性的要求，使得效率得到了很大的提升，合理的满足了项目的需求。