多层穿梭车调度系统技术及应用

文｜中国船舶集团第705研究所昆明分部 张云成

本文主要对密集存储系统中多层穿梭车调度系统的设计及关键技术进行分析，对如何实现穿梭车路径规划、交通管控、自动充电等智能调度问题，提出了一套完整可行的方案，详细论述了其技术原理和方法，可为类似密集存储系统中穿梭车的调度系统开发提供参考。

随着自动化物流发展，密集存储得到越来越广泛地应用，成为未来发展方向之一。作为密集存储系统中关键设备之一，穿梭车的调度是一个技术难点，目前相关技术应用的研究还比较少，尚未形成一套有针对性的成熟理论和实现方案。本文借鉴行业内应用广泛、技术成熟的AGV调度相关技术，结合多层穿梭车系统的特点和项目实践经验，详细阐述了其中的理论原理和关键技术。

一、密集存储系统简介

多层密集存储系统是一种利用穿梭车进行存取货物的特殊货架系统，由穿梭车、升降机、充电站、货架导轨以及上位调度管理软件组成，可实现货架深度上货物的连续存储，达到存储密度最大化。

密集存储系统的工作流程是，在货架深度方向设置穿梭车导轨，入库时只需将货物输送到升降机入口站台，系统根据货物存储位置控制升降机，将货物输送到相应的层；同时，调度穿梭车到升级机站台取货，然后将货物搬运到货架内指定的位置，出库过程与之相反。密集式多层穿梭车系统适用于“先进先出”或“先进后出”的自动化仓储场景。

穿梭车是一种在轨道上作业的智能机器人，可以在系统控制下实现出入库、盘点、放置等任务，并可与上位WMS系统进行通讯或者通过手持终端控制，结合应用RFID、条码等技术，实现自动识别、自动存取等功能。

穿梭车调度系统是自动化立体仓库中的监控和调度中心，主要负责对穿梭车、升降机、充电站等相关设备的参数进行配置以及状态监控，接收来自业务系统的入库、出库、移库等业务工单，能根据业务工单和在轨穿梭车状态对任务进行分解，依据调度策略及路径规划方法，形成穿梭车调度工单并下达给穿梭车，还需具备对穿梭车充电管理及异常情况处理的能力，实时向业务系统反馈任务完成情况。并且，能将系统操作内容、操作时间及设备状态记录到数据库，作为系统日志管理，具备断电恢复能力。

二、问题描述

对于多层密集式货架的其中一层来说，存货巷道X向是连通的，Y向只有行走巷道是连通的，所有巷道均是双向可行，即穿梭车可往复行驶。根据货架特点，为便于计算机处理，很自然地将货架区域进行栅格化处理。要想规划出穿梭车行驶的最优路径，就需要建立一个数字地图（如图1所示），该地图以货格大小，将仓库划分为大小相同的栅格，每个货位、每个行走巷道、出入库口、升降机都是一个栅格节点。每个栅格节点都有一个坐标，由层数、巷道数、货位排数、节点间距和是否换向等属性来描述。

图1 二维平面栅格地图

多层穿梭车调度，需要解决以下主要问题：

1.三维动态路径规划问题：穿梭车调度系统属于实时性要求较高的控制系统，需要在三维立体货架空间、多车动态环境下进行最优路径规划，并且保证算法的高效率。

2.路径冲突和锁死问题：由于穿梭车对路径资源具有独占性，穿梭车运行过程中不可避免会存在路径冲突，在某些情况下甚至会出现系统锁死现象。

3.穿梭车运行过程中遇到故障报警，或外界干扰等突发事件，如何进行处理的问题。

为解决上述问题，对系统设定如下规则：

• 每个栅格可双向通行，每个栅格只能通过一辆车；

• 小车具备障碍探测能力，可减速或紧急停车；

• 每个任务在下达时指定优先级，出库优先级大于入库优先级、载货优先级大于空载优先级、充电优先级大于空闲，排队靠前的任务优先级高于靠后的任务；

• 任务根据缓急之分有不同优先级；

• 穿梭车一次只能执行一个任务，当且仅当完成当前任务才能响应下一任务。

在密集式货架某一层中，穿梭车之间是否存在冲突，可根据两车之间同一坐标方向的距离判断。若两辆穿梭车的坐标分别为、，那么它们之间的距离为或中较大的。

设定一个运行安全距离，为两个栅格大小。

如果则存在冲突可能性，然后对两个车辆的路径进行对比，如果路径中存在重叠的栅格且通过时间差不大于1个栅格的通行时间，就认为冲突存在，需要进行交通管控。当确定了两辆穿梭车之间存在冲突后，则需对冲突类型加以判断。

根据穿梭车上传的信息可以知道小车的行驶方向，而冲突类型可通过两车行驶方向的夹角进行确定。若两车之间的夹角为180°内，则判断两车的冲突类型为相向冲突；若两车之间的夹角为0°内，则判断两车的冲突类型为追赶冲突；若两车之间的夹角为90°内，则判断两车的冲突类型为路口冲突。

多个穿梭车在执行任务的过程中，需要占用货位、行走通道、出入库口（升降机可视为出入库口）等资源，可能出现三种交通冲突：相向冲突，追赶冲突和路口冲突，如图2所示。

图2 小车冲突的三种情况

密集存储穿梭车调度系统需要解决以上穿梭车运行过程中的交通管理基本问题，这三种冲突本质上就是对资源使用的时空重叠问题，只有解决冲突才能保证穿梭车无碰撞运行，避免系统死锁等问题。

三、关键技术应用

1.路径规划

多层密集式存储货架垂直方向穿梭车换层都需要通过升降机进行，穿梭车跨层作业路径规划可视为三维立体空间栅格化的路径求解问题，需要在二维栅格平面的基础上增加垂直方向的Z坐标。根据已知货架的三维栅格地图信息，为满足穿梭车调度控制实时性要求，穿梭数量车路径规划采用A*算法求解，能得到穿梭车行驶的最优路径。

A*算法是一种典型的启发式最优路径求解搜索算法，把评价函数定义为，从初始栅格经过第栅格到达目标栅格的最小代价路径的代价估计值，其一般形式是，式中是从初始栅格到第栅格的实际代价，是从第栅格到目标栅格的路径估计代价，被称为启发性函数。

基于密集式存储货架栅格地图的特点，在本设计中采用作为启发函数，这个估算路径距离在大多数情况下与穿梭车实际行走的距离非常接近或相等（穿梭车在货架中只能前后、左右和上下六个方向移动），所以规划出的路径一定是最优路径，并且搜索效率非常高。

穿梭车在分配到任务后，将需经过的地址对（包含起点、终点）顺序输入调用的A*算法规划出最优路径，再将最优路径中每一段路径转化为穿梭车可执行指令（包含栅格内的转向操作），依据穿梭车运行状态下达指令。

当穿梭车装载货物后，A*算法调用的地图信息主要包含货位上是否有货的障碍物信息以及其它车辆状态；当穿梭车空载并被分配一个任务时，A*算法调用的地图信息包含其它车辆当前的位置信息，并将其作为障碍物而不考虑货位上是否有货的障碍物信息，采用这种方式可有效减少或避免载货和空载穿梭车之间的冲突。

在二维平面栅格地图下，采用A*算法规划出的穿梭车出入库最优路径，如图3所示。

图3 出入库路径规划

2.交通管控

本文采用基于任务优先级时间窗控制方法进行穿梭车交通管控，这种路径规划方法属于预测式防冲突控制方法。系统有两种解决交通冲突的策略：基于时间窗的几何路径解决策略和基于优先级排队调节解决策略，两种策略优先级不同，当采用几何路径无法找到路径或耗时较长时，可以选择基于优先级排队调节解决策略。首先为各穿梭车规划好最优路径，然后根据每台穿梭车的路径预测穿梭车之间是否会发生冲突，如果存在冲突则调整穿梭车的路径来避免碰撞。

在整个调度系统中，穿梭车是资源使用者，行走巷道、货位巷道、升降机和充电站均是资源，每一个资源在一定时间内只能由一辆穿梭车使用，穿梭车使用资源的过程通过基于优先级的交通规则法进行调度，根据资源使用时间及建立的优先级来决定避让规则，对穿梭车进行路径规划，或者排队等待，避免路径冲突和死锁情况的出现。

基于任务优先级的交通管控策略如下描述：

为了优化管理多个穿梭车在巷道中的通行问题，对车辆经过的栅格地图路径以调度系统的时钟为基准建立一个时间窗表，该时间表的作用就是判断穿梭车对冲突栅格资源的占用时间。每一个在执行任务的穿梭车均有一个时间窗表，该时间表描述了每个资源的占用情况，即经过每个栅格的到达时间和离开时间。以执行第一个任务的穿梭车规划的路径和建立的时间窗表为基础，为后续穿梭车逐个规划路径并建立时间窗表。若新规划的路径与前面已规划好的路径没有冲突，或路径冲突但时间没有重叠，则表示路径规划是可行的；若新规划的路径有冲突并且时间有重叠，需要重新规划路径，重复上述过程，直到不存在冲突或时间重叠。如果不能规划出最短路径，或重新规划的路径用时比排队等待用时还长，则暂停对该任务的执行，排队等待。

针对穿梭车交通管控冲突类型，对应的具体调度控制方法如下：

（1）相向冲突有三种情况，即在货位巷道上的冲突、在行走巷道上的冲突和在出入库口、升降机位（包括进出升降机前的一个栅格）的冲突。货位巷道或行走巷道上的冲突发生时，根据设定的优先级决定低优先级的穿梭车采取规避冲突路径规划策略，也就是低优先级的穿梭车视高优先级穿梭车所规划的路径均为占用，低优先级的穿梭车路径规划避开所有占用路径。如果在入库口或升降机位的冲突发生时，低优先级穿梭车需等待其它穿梭车释放入库口或升降机位置资源，再进行路径规划（任务排队等待执行）；如果在出库口或升降机位的冲突发生时，因空载穿梭车（此时可视为高优先级）物理上已占据资源，所以载货穿梭车（此时可视为低优先级）需等待其它穿梭车释放出库口或升降机位置资源，再进行路径规划（任务排队等待执行）。相向冲突三种情况下的路径规划，如图4所示。

图4 相向冲突的调度

（2）追赶冲突有两种情况（假定空载车辆速度大于载货车辆），前车减速（包括静止）追赶和空载车辆追赶载货车辆。因为在路径规划时，即根据时间窗控制进行无冲突或根据优先级排队等待原则规避，追赶冲突只有在前车故障时发生，后车采取停车等待或重新进行路径规划继续执行任务。

（3）路口冲突有四种情况，两辆车在路口冲突后的路径不重叠、两辆车在路口冲突后的路径重叠、两辆车在路口冲突后有一方行驶到对方之前的位置，以及两辆车在路口冲突后相互行驶到对方之前的位置（锁死冲突），如图5所示。前三种情况在路径规划时，均可根据时间窗控制或根据优先级排队等待进行规避。

图5 路口冲突的调度

（4）对于上述（3）中方法无法解决的第四种问题（锁死冲突），需要根据任务优先级给低优先级车辆附加一个临时任务，行驶到起始位置附近进行避让（附加任务不能与其它穿梭车路径产生新的冲突），并释放之前占用的资源，到达新位置后再重新规划路。

（5）对于穿梭车运行过程中发生故障或受到外界干扰而中断任务执行的情况，其它与任务中断穿梭车路径有交叉的穿梭车在行驶到故障点附近后，保持安全距离暂停等待。如果能够短时间内恢复，则由当前穿梭车按原路径继续执行任务；否则应取消当前穿梭车的任务，由系统调度其它空闲小车接管任务，并更新受影响的穿梭车时间窗信息。

综合上述多种情况来看，采用基于优先级的排队等待和重新规划路径两种策略，均能解决路径冲突和穿梭车运行过程中发生故障的问题。一是低优先级的穿梭车在冲突时排队等待高优先级的穿梭车通过并释放资源，再继续执行；二是重新规划穿梭车路径继续执行当前任务，或由其它穿梭车接管任务。

3.软件系统设计

穿梭车调度管理系统的总体设计以“软件平台思想”为指导，将系统设计为一套支持穿梭车调度从路径规划、流程设计、系统仿真到系统实施全过程的整体解决方案。上位控制系统根据从其它系统接收到的出入库指令，统筹调度穿梭车车辆，将任务分配给合适的小车。小车在智能交通管理控制下，沿规定的路线自动高效地完成搬运任务，并可及时调度小车进行充电、维护保养等。

穿梭车调度系统软件主要由信息通讯、状态监控、设备管理、故障处理、任务管理及调度规划、系统日志管理等模块组成。

图6 软件结构示意图

信息通讯模块，按照拟定的通讯协议通过以太网或无线网络实现与业务系统、穿梭车、升降机、充电站的实时通讯。状态监控模块，主要实现对穿梭车、升降机、充电站等相关设备运行状态、接受的任务工单状态、下达的调度工单状态和选择的调度策略状态的实时显示。设备管理模块，主要实现对接入调度系统的穿梭车、升降机、充电站等设备的参数设定以及货架中货位信息的设定。故障处理模块，主要实现对穿梭车、升降机和充电站上报的故障信息进行故障类型判断，依据故障处理应急方案下达任务中止、重新调度及上报故障等命令。任务管理及调度规划模块，主要实现将业务系统下达的任务分解为调度系统可解算的子任务，规划穿梭车行走路径，动态调度穿梭车及升降机执行任务，具备多穿梭车交通管理及避碰的能力，还有穿梭车充电管理。系统日志管理模块，主要实现对调度系统的操作内容、操作时间及设备状态记录到数据库，具备断电恢复能力。

4.虚拟仿真

多层穿梭车存储系统地图模型和调度模型建立后，还需要建立离线虚拟仿真系统。根据穿梭车运行参数、出入库任务和系统能力需求，模拟真实系统运行情况，通过对系统出入库能力、设备使用效率等仿真结果对比分析，发现系统运行过程中可能存在的瓶颈问题，并找出在系统能力需求下的最佳穿梭车配置数量。为了保证数据接口的一致性，便于程序模拟调试，系统采用PLC仿真器的方式模拟穿梭车运行状态，PLC仿真器可手动或自动模拟更改穿梭车的数据。穿梭车调度系统可以手动或自动模拟添加任务，同时通过数据接口读写PLC仿真器的实时数据，结合地图数据对系统进行模拟仿真。

四、结束语

本文针对密集式存储穿梭车调度问题，通过将多层三维空间货架进行栅格化处理，利用A*算法和时间窗原理进行穿梭车路径求解，能很好地解决穿梭车执行任务过程中的路径规划和无冲突交通管控问题，为系统的实际应用提供基础技术支撑，对类似系统的应用具有较高参考价值。