一种面向多深度储货区的四向车调度策略

徐立云，陈 晨，占翔南，宓 宏

（1.同济大学 机械与能源工程学院，上海 201804；2.浙江衢州联州致冷剂有限公司，浙江 衢州 324004）

1 引言

由于仓储用地资源紧张，人力成本不断升高，社会对仓储的需求越来越大，要求仓储系统往密集化和智能化方向发展[1]。目前应用最为广泛的是堆垛式自动化立体仓储系统（Automated Storage and Retrieval System），但该仓储系统存在两方面的问题，一是当巷道中堆垛机发生故障时，其所服务的整条巷道随即处于瘫痪状态，无法进行相应的出入库作业；二是当堆垛式自动化立体仓储系统设计建造完成后，其出入库能力也随之固定。为解决这一问题，出现了多层穿梭车仓储系统（Multi-tier Shuttle Warehousing System），该仓储系统能够在一定程度上解决堆垛式自动化立体仓储系统的不足，但是由于该仓储系统的存储巷道深度大部分为单个货位，同时每条主干道只有一辆穿梭车执行存取任务，产生了存储空间利用率较低、货物存取不灵活等问题[2-3]。为满足市场需要，出现了一种新型的基于四向穿梭车的多深度仓储系统，该系统兼具上述两种系统的优势，同时在同一层货架中可以放置多辆四向车，能够根据出入库效率需求的不同，动态调整四向车数量，使得该类型的仓储系统具有较强的灵活性，并且多深度的存储巷道能够保证较高的仓储空间利用率。

国内外学者针对四向穿梭式多深度仓储系统进行了相应研究。Manzini 等[4]提出了四向车单车存取货物的行程时间数学模型，并进行了仓储系统布局优化。D’Antonio 等[5-6]提出了单次行程中包含多个存取货物任务的行程时间数学模型，基于该模型进行了四向车调度策略优化。然而，文献中提出的数学模型只针对单条主干道只运行一辆四向车的情况，无法解决多车同时运行的问题。Tappia 等[7]使用排队网络建立分析模型，评估单层和多层多深度仓储系统的运行情况，但模型并未考虑四向车的死锁和堵塞问题，使得结果和实际情况有较大偏差。付晓峰等[8]提出了针对四向车多深度仓储系统的货物入库上架过程和货位分配方法，但文中使用的区域控制方法使得一条储货巷道中同时只允许一辆四向车工作，处于等待状态的四向车会堵塞主干道，影响正常通行，导致系统效率较低。

本文针对仓储系统多深度储货区存在的问题，基于道路定向法提出了四向车多车调度策略，避免车辆冲突与任务死锁，保证了仓储系统高效运行，并结合实际案例验证了所提策略的有效性。

2 问题描述

多深度仓储系统由垂直提升机、四向穿梭车、多层货架及管理控制系统组成。四向穿梭车实现货架储货区托盘货物的水平转运，垂直提升机实现托盘货物的垂直转运和四向穿梭车的换层，控制信息系统负责整个仓储系统的设备监控和调度。储货区域为多层货架结构，每层布局相同，如图1所示，储货区由多条平行的储货巷道构成，每条储货巷道中有多个货位。每条储货巷道中只能存放同一品类同一批次的货物，即一个SKU（Stock Keep Unit），为保证仓储系统货物先进先出的原则，储货巷道内的货物同样采用先进先出的操作方式，即只从储货巷道一端入货，从另一端出货。

四向车采用电力驱动，能够与控制信息系统进行无线通讯，接收出入库任务。当到达目标货位时，通过托盘举升装置将托盘抬升或下降实现货物的装卸。四向车可沿巷道横向和纵向四个方向行驶，可深入储货巷道内部到达仓储系统中的任何一个储位，当四向穿梭车处于空车状态时，可以在存有货物的巷道中自由穿梭，当四向穿梭车为载货状态时，可以在空闲的储货巷道中借路通行。

图1 单层布局图

对于单层储货区来说，当空闲四向车接到货物入库命令时，四向车从当前位置寻路至每层的入库口处，从入库口的提升机处接取货物后，将货物运送至指定货位。执行出库命令时，四向穿梭车按照任务指示，寻路到待出库货物所在货位，将货物运送至出库口处的提升机。但在四向车运行过程中，多车同时执行任务会造成四向车之间、储货巷道内任务之间出现死锁与冲突，两类冲突如图2所示。

图2 四向穿梭车冲突类型

当多车同时运行时，在道路交叉口处出现的四向车冲突与死锁，会导致整个单层储货区瘫痪。如图2所示，单层储货区中主要存在两种形式的车辆冲突。图2-a 为路口冲突，如果调度系统不加以控制，A、B 两车将在路口发生碰撞，图2-b 为相向冲突，该冲突类型会导致A、B两车死锁情况的发生。当在主干道发生车辆冲突与死锁时，会造成单层储货区的出入库任务无法正常执行，仓储系统吞吐量会受到大幅影响。

由于四向车的运行特性，四向车到达某个指定位置的路径可以有多条，本文中采用Dijkstra 算法为四向车选择最短路径，但是由于多车同时运行，四向车到达目的地的过程中存在等待路口使用权和停车转向造成的延迟时间，当两台四向车分别接收到同一巷道的出货命令时，先接到任务的小车并不一定先到达目标巷道，出货任务死锁如图3-a 所示，A 车需要出库a位置货物，B车需要出库b位置货物，而B车先进入巷道内部，这时B车取得货物之后无法离开巷道，a 位置货物会挡住B 车造成死锁。同理，入货任务死锁如图3-b所示，在两个同一巷道的入库任务同时执行时，也会出现类似死锁情况。另外，载货状态的四向车可以通过没有放置货物的储货巷道借路通行，由于四向车的路径规划是在接到任务后立即执行，有可能在路径规划时借路的储货巷道是空闲的，但当载货车经过一段时间到达借路储货巷道时，有可能已经存在新的货物，会造成借路死锁。

图3 储货巷道内任务死锁类型

3 调度策略

3.1 道路定向策略

为避免图2-a所示的路口冲突，采用路口使用权锁定策略。当A、B 两车需要同时通过路口时，均需要申请路口节点的使用权，只有路口使用权被释放时，下一辆四向车才能通过路口。同时在路口处维护一个四向车等待列表，路口按照通过等待列表中的次序依次放行每辆四向车。为避免如图2-b 所示的相向冲突导致的车辆死锁情况的发生，在满足巷道内货物先进先出特性的前提下，采用主干道定向策略解决四向车的死锁问题，保证了多辆四向车能够在仓储区域的流畅运行。主干道与储货巷道的定向结果如图4所示。

图4 主干道定向方向

3.2 任务交换策略

为解决储货巷道内的任务死锁问题，采用巷道内任务交换策略。利用巷道和货位的多种状态，灵活调整四向车最终执行的任务，当一条巷道内同时出现多个出库与入库任务时，四向车先寻路到目标货位所在巷道的入口处，从紧邻储货巷道出口的货位开始，沿巷道出入货反方向查询货位状态，选择第一个可以执行的对应任务，作为最终目标任务，从而避免任务死锁，保证一条巷道中的多个任务都能被顺利执行。货位状态S 和巷道状态T 不同状态对应的不同含义均在状态表中列出，见表1。

表1 状态表

四向车执行入库任务流程如下：

步骤1：空车状态的四向车接收到入库任务后，将对应货位状态代码S设置为3，表示该货位已被分配入货，防止被选为下个入库任务。

步骤2：将四向车当前目的地设置为入库口，使用Dijkstra 算法规划路径，并寻路至入库口完成取货操作。此时四向车为载货状态。

步骤3：将四向车当前目的地设置为目标货位巷道的入口处，使用Dijkstra 算法规划路径，如果规划路径中需借路通行，则将对应巷道的借路状态T+1。

步骤4：四向车按照规划路径到达巷道入口。如果途中出现借路通行，及时更新借路巷道对应的巷道状态T。

步骤5：从紧邻巷道出口的货位开始，沿巷道出入货反方向查询货位状态，选择第一个货位状态为3的货位，作为最终入库目标货位。将该最终目标货位状态S更改为5，表示有四向车向该货位入货，并且已经进入巷道，防止在巷道入口路段的下个执行入库任务的四向车选择这个货位为最终目标货位。

步骤6：进入巷道，到达目标货位后卸货，将该货位状态S设置为1，表示该货位已经有货存在，完成入库任务。此时四向车为空车状态，可以继续执行下个任务。

例如，当出现图3-a 情况时，B 车在巷道入口路段处将任务执行货位更改为a货位，解决出货巷道内入库任务间的死锁。

四向车执行出库任务流程如下：

步骤1：空车状态的四向车接到出库任务，如果四向车恰巧位于目标巷道内，并且目标货位位于小车当前位置到出货巷道出口之间，此时四向车可以直接出货。如果四向车可以直接出货，将出货货位状态S更改为4，表示该货位上的货物已被分配出货，并执行步骤3。否则，执行步骤2。

步骤2：将目标货位状态S设置为4，表示该货位上的货物已被分配出货，设置四向车目的地为该货位所在巷道入口处，使用Dijkstra 算法规划路径并寻路至巷道入口。

步骤3：从紧邻巷道出口的货位开始，沿巷道出入货反方向查询货位状态，选择第一个货位状态为4的货位，作为最终入库目标货位。并将该货位状态S更改为6，表示有四向车从该货位出货，并且已经进入巷道，防止在巷道入口路段的下个执行出库任务的四向车选择这个货位为最终目标货位。

步骤4：四向车启动，到达最终出库目标货位完成取货操作，将该货位状态S 更改为2，表示货位为空。此时四向车变为载货状态。

步骤5：将四向车目的地设置为出库口，并使用Dijkstra 算法规划路径，如果规划路径中需要借路通行，则将对应巷道的借路状态T+1。

步骤6：四向车按照规划路径到达出库口，执行卸货操作，完成出库任务。如果途中出现借路通行，及时更新对应巷道状态T。此时四向车为空车状态，可以继续执行下个任务。

例如，当出现图3-b 情况时，B 车在巷道入口路段处将任务执行货位更改为a货位，解决储货巷道内出库任务间的死锁。

当载货四向车规划路径时，会选择没有存放货物并且没有生成入库任务的空闲储货巷道借路，出现借路情况时，将借路储货巷道状态T+1，表示会有一辆四向车借路，在四向车通过该储货巷道时及时将巷道状态T-1，表示借路四向车已经通过。并且不生成储货巷道状态T大于0巷道的入库任务，解决借路载货车造成的任务死锁问题。

4 案例分析

某企业冷库的多深度仓储系统的储货区初步规划如图1所示，并给出三种不同的出入库口布局方案，如图5所示。仓储系统设计要求及设备参数见表2。

图5 三种布局

表2 仓储系统设计要求及设备参数

4.1 建模仿真

采用Plant Simulation 软件对仓储系统单层进行仿真建模，如图6所示。以下为针对仿真模型做出的假设：

（1）初始货物容量为总库位的80%；

（2）系统随机产生的出入库任务均满足储货巷道先进先出的出入货条件；

（3）四向车充电一次能够连续工作8h；

（4）四向穿梭车连续执行出入库任务以期获得最大吞吐量；

（5）忽略提升机对出入库的影响。

为选择最佳布局和四向车数量，对于每种布局，四向车的数量从1变化至25 辆，仿真时间设置为24h，每个实验重复进行10次，对吞吐量取平均值。

4.2 结果分析

实验结果如图7所示，布局1能够在12辆车时满足企业所提出的最大吞吐量为300托/h的要求，布局2和布局3均无法满足该要求。

三种布局的吞吐量变化趋势曲线类似，在四向车数量较少时，四向车数量与吞吐量呈线性相关，而当四向车数量达到10-16辆时，三种布局的吞吐量分别达到饱和状态，之后增加四向车数量并不能使吞吐量增长，这是由于多车之间的堵塞抵消了车辆增多带来的吞吐量增长。四向车整个工作过程中的等待时间（包括装卸货时间、转向时间和多车堵塞时间）占比更加印证了这一点。如图8所示，当四向车数量较少时，多车堵塞现象较少，等待时间占比相对稳定，而当四向车数量达到10-16 辆时，多车堵塞导致等待时间占比迅速增加，随着四向车数量的不断增加，四向车的使用效率不断下降。

布局1能够获得更多的吞吐量，该布局出入库口不在同一位置，能够减少多车堵塞对吞吐量的影响。而在四向车少于8 辆时，多车堵塞现象较少，布局1相较布局2 更加有优势，出入库口位于同一位置，四向车出货时无需绕路，完成单个任务效率较高。布局3 相较于其他两个布局没有优势。企业可以灵活调整四向车数量以满足不同的吞吐量需求。

图6 仿真建模结果

图7 出入库口位置对吞吐量的影响

图8 四向车等待时间占比变化趋势

5 结语

本文对四向穿梭车多深度仓储系统的调度策略进行了研究。采用道路定向的方式解决四向车冲突问题，提出任务调度策略解决储货巷道中的任务死锁问题，保证单条巷道中执行不同任务四向车可同时工作，提高整个仓储系统的工作效率。针对实际案例，通过仿真分析和优化，解决了仓储布局选择和四向车数量配置的问题，在工程应用中具有指导意义。