自动仓库三叉堆垛机拣选作业的优化

王军郝岩柱张楠/文

自动仓库三叉堆垛机拣选作业的优化

王军1郝岩柱2张楠2/文

自动化立体仓库的广泛应用要求计算机化的控制算法去支持其调度和拣选决策。本文针对一个三叉堆垛机拣选顺序的问题进行研究，涉及一个三叉堆垛机存取操作，目标是通过算法计算，最大限度地减少堆垛机完成拣选任务单所需的时间。实践证明，研究堆垛机拣选作业优化问题对自动化立体仓库工作效率的提高具有重要意义。本文所研究的算法已经成功应用到上海烟草集团有限责任公司天津卷烟厂项目中。

自动化立体库、堆垛机、拣选作业优化、节约算法

一、引言

自动化立体仓库得到越来越广泛的应用，主要原因在于它可靠性高且人为干预少，不仅能实现计算机智能管理，减少重复操作，还能避免一些有危险的人工操作，具有很大的经济优势。自动化立体仓库的应用极大的提高了生产与配送效率，但同样也存在一些难以解决的问题。如，每个项目中的货位排序调度，为堆垛机产生拣选任务列表，以及管理规划问题，都是自动化立体仓库优化作业的目标。

在这当中，如何解决路径优化问题是进一步提高自动化立体仓库效率的关键，也是主要难题。本文通过节约算法对TSP问题求解来解决堆垛机拣选优化问题，即解决在立体仓库中三叉堆垛机配三叉货物用时最短所对应的三个货位路径。

二、系统概述

上海烟草集团有限责任公司天津卷烟厂自动化立体仓库分为托盘区与料箱区：托盘库由2个巷道组成，共4排×25列×18层=1800个货位；料箱库由4个巷道组成，共8排×48列×62层=23808个货位，每个货位一只料箱。检定系统每日检定15000只单相表，每日入库20000只新表，因此采用三叉堆垛机来提高出入库效率。

货架采用牛腿货架，每台堆垛机可以对它的两侧货架进行取放货操作。货位长度为1000毫米，高度为400毫米，并且所有的货位都是相同的。堆垛机可在水平方向上和垂直方向上同时运动，且其加减速是线性的，行走最大速度为180米/分，升降最大速度为60米/分。

图1 ：天津卷烟厂的堆垛机系统

图2 ：天津卷烟厂的输送系统

三、 堆垛机拣选优化算法

检定出库流程：仓储系统接收生产系统下达的检定计划。当生产系统下达计划（检定单元）启动命令、检定单元批次要料信号及要料数量，仓储系统自动分配出库货位生成搬运任务，由堆垛机、上层输送机将指定货位的料箱搬运至主输送线上，经固定条码1识读校验检定料箱。校验失败的料箱输送到异常处理工位，等待人工处理；正确的料箱输送至检定车间入口经固定条码2进行分拣，再自动输送到检定单元暂存区。

堆垛机拣选作业优化指：在检定出库时调度系统调用优化算法对搬运任务重新排序，使三叉堆垛机取三个非连续货位所用时间最短，从而提高工作效率。堆垛机拣选作业流程如图3所示。

从图3可以把堆垛机的拣选作业调度归纳成如下问题：设有3个拣选任务，即有3个货位点等待堆垛机到达，堆垛机从出/入库站台处出发，分别到达3个货位点，且每个货位点只去1次，最后回到初始位置，求堆垛机运行时间最短。

这一问题类似于旅行商问题(TSP)。旅行商问题一般可描述为：1名旅行商从1个城市出发，访遍n个城市1次且仅1次后返回原出发城市，求总距离最短的巡回路径。现在，将TSP问题应用到堆垛机拣选作业控制系统上，即寻找1条巡回路径T=(t1,t2, ,tn)，使得下列目标函数最小：

图3 ：堆垛机拣选作业流程

通过上面目标函数可以看出，其解的搜索空间随着拣选货位数n的增加而增大，因此我们采用节约算法对其求解。

TSP问题求解：任意2个拣选货位点之间的距离：货位点以(x,y)表示，其中x为列，y为层，将2个货位点i(x1,y1)和j(x2,y2)的运行时间表示为。初始位置坐标为(1,1)，用点0表示。设堆垛机从初始位置出发执行一批任务，这批任务包含3个拣选货位，分别为(10,6)，(25,26)，(40,16)。执行完任务后，堆垛机回到初始位置(1,1)。将上述3个货位分别用1、2、3代表。

在堆垛机执行拣选作业时，假设堆垛机在水平方向上和垂直方向上都是以恒高速运行，其制动和起动过程忽略不计。

将上述货位(10,6)，(25,26)，(40,16)，以及行走最大速度为180米/分（3000毫米/秒），升降最大速度为60米/分（1000毫米/秒），货位长度为1000毫米，高度为400毫米，代入上述公式即可得如下数据：

拣选货位相对初始位置的运行时间坐标为(3S,2S)，(8S,10S)，(13S,6S)。表1为两货位间运行时间表。

表1 ：任意两货位间运行时间

四、运行结果

由于节约算法结构清晰，程序易读，而且正确性容易得到验证。本文通过C语言进行程序设计，并把该算法成功应用到堆垛机拣选作业系统中，程序运行结果如下：

从程序运行结果中，我们可以得出最优解为 (8S,10S)，(13S,6S)，(3S,2S)，即堆垛机最优路径为从初始位置0到2号货位，再到3号货位，到1号货位，最后返回到初始位置0处。最短时间为28秒。而通过表1组合排列法我们知道3个货位共有6条路径，分别为0-1-2-3-0、0-1-3-2-0、0-2-1-3-0、0-2-3-1-0、0-3-1-2-0、0-3-2-1-0，用时分别为：

3+8+5+13=29秒；

3+10+5+10=28秒；

10+8+10+13=41秒；

10+5+10+3=28秒；

13+10+8+10=41秒；

13+5+8+3=29秒；

由此可见运行时间最大路径之一为(8S,10S)，(3S,2S)，(13S,6S)， 最长时间为41秒。通过比较我们发现一个三叉堆垛机一次拣选配货过程就可以节约13秒。

五、 结论

在本文中，我们基于节约算法对TSP问题进行求解来解决自动化立体仓库中堆垛机拣选作业问题。该算法是通过C程序编写的，它能快速计算出堆垛机最短运行时间相应的路径。实验和工程应用表明：用TSP问题去解决自动化立体仓库中堆垛机拣选作业问题是完全可行的，该应用能有效提高自动化立体仓库堆垛机拣选作业的工作效率。

作者单位：1.上海烟草集团有限责任公司天津卷烟厂；2.沈阳新松机器人自动化股份有限公司