随着我国经济和现代制造业的发展,仓储管理在现代生产、流通中的地位越来越高,仓储管理成本在总投资成本的占比越来越高[1]。仓库物资的出库入库以及整理工作若采用传统的利用叉车、堆垛机等工具搬运货物的方式来完成,不但工人的劳动强度高而且工作效率很低,已经越来越难以满足现代仓储管理的需求。

利用现代通信技术、计算机技术、传感器技术和自动化控制等技术的全自动立体化仓库的出现,仓储管理进入一个新的阶段。AGV(Automated Guided Vehicle)自动引导车是全自动立体化仓库的重要组成部分,若AGV配备装卸装置即可构成自动引导搬运车。自动引导搬运车通过自动引导装置,可按照路径规划的最佳路径行驶,配合装有RFID电子标签的托盘,在仓库内按要求搬运送各项物资,实现物资装卸与搬运全过程自动化。自动引导搬运车自动化程度高,行驶路径可以根据仓储货位的要求而灵活改变,柔性好。自动引导搬运车的应用,大大减轻了工人的劳动强度,对提高仓储管理工作效率,降低管理成本具有重大意义。

自动引导搬运车在无人驾驶情况下将物资安全运送至指定位置,必须进行路径规划。所谓路径规划是指在具有障碍物的环境中,按照一定的评价标准,寻找一条从起始状态到目标状态的无碰撞路径,其本身是机器人学和人工智能的一个重要课题[2]。路径规划在仓储管理中,主要目标是在最短路径将物资输送到指定位置。最短路径问题是图论研究中的一个经典算法问题,常用的路径算法有:Dijkstra算法、A*算法、SPFA算法等。Dijkstra 算法作为一种经典的最短路径搜索算法,广泛应用于物流管理的路径规划、车辆导航等领域。

Dijkstra算法是由荷兰计算机科学家E.W.Dijkstra在1959年提出的一种求解最短路径的方法,该算法采用了贪心算法模式,解决了有向图中单个源点到其他顶点的最短路径问题,其基本思想是:首先求出长度最短的一条最短路径,然后参照它求出长度次短的一条最短路径,依次类推,直到从顶点v到其他所有顶点的最短路径全部求出来为止[3]。

若V是有向图D的顶点集合,S是已经求出的最短路径的终点集合,d[i]存放从顶点v0到顶点vi的最短路径长度(若两定点中没有边则为∞),E[k][i]中存放边(vi,vk)上的权值。

Dijkstra算法的基本过程为:

初始时,S中只有一个源点,假设为v0,则第一条最短路径(v0,vk)为:

d[k]=min{ d[i]| vi∈V-v0 }

将求得的最短路径的终点存入S,则下一条最短路径的长度为:

d[k]=min{ d[i]| vi∈V-S }

每次求出一条最短路径后,将最短路径的终点存入S,然后对所有vi∈V-S,修改d[i]

d[i]=min{ d[i],d[k]+ E[k][i]}

当算法结束时,d[i]中储存的便是从出发顶点到目的顶点的最短路径。

为了建立路径规划数学模型,首先需要对仓储空间进行了简化,将三维空间投影到俯视平面,形成平面内的路径规划问题。简化后再将各个工位点作为顶点进行编号,编号时每个工位对应一个顶点,自动引导搬运车需要搬运物资时,首先根据工位点找到该物资所在的货架号,再根据其偏移位置从工位点移动到正对存放该物资位置,最后根据存放位置编号确定物资存放在货架的那一层。在仓库入口处安装有RFID读写器,带有RFID电子标签的托盘进出仓库时该读写器自动对电子标签进行读取,待管理员确定后自动存入仓库管理系统的数据库之中,仓库环境地图如图1所示。

图1 顶点编号   下载原图

按照各顶点之间距离确定权值,形成带权有向图,如图2所示。

图2 带权有向图   下载原图

表示为邻接矩阵为:

根据Dijkstra算法,首先通过邻接矩阵的第1行求出从顶点1到其他各顶点的最短路径的初步结果,然后逐行求出所有的最短路径,得到从入口1到各个工位点路径为:

表1 从入口到各工位最短路径 导出到EXCEL

在整理仓库物资时,若需要在不同货架之间移动物资,只要在仓库管理系统中选择要进行移动物资,由管理系统自动提取物资移动的起点和终点的工位号进行计算,并将得到的规划路径和货物信息一并发送至自动引导搬运车。如果货架位置发生了变化,只要更改邻接矩阵即可。

通过Dijkstra算法对自动引导搬运车进行路径规划,自动引导搬运车按照路径规划的最佳路径行驶,配合RFID电子标签,实现数据的自动化采集,优化验收入库、出库核实、库存盘点等业务过程,提高信息核对速度,消除事务处理中的人工操作,减少无效劳动,提高工作效率,降低运营成本。