自动化立体仓库是物流和生产中的基础装备, 具有存储量大、占地空间小、自动化程度高等优点, 通常由高层货架组成, 它的应用在一定程度上提高了仓库 (或仓储环节) 的作业效率和水平。自动化立体仓库的货架有固定式和旋转式两种, 并以前者居多。但无论哪种货架, 为了从立体仓库的货架中取出货物, 必须进行拣选。尤其是对固定式货架, 拣选作业更是对应自动化立体仓库的调度的核心。固定式货架拣选必须设定拣选路径。因此拣选路径的优化不但影响货物存取作业效率, 也决定了拣选环节堆垛机的能耗。为此人们越来越重视对拣选路径调度的优化。尤其是随着生产往即时化方向发展, 及基于时间的竞争趋势下, 无论是生产和服务的节拍都不断提高, 这对自动化立体仓库的拣货速度提出了更高要求。比如电子商务行业的拣货速度决定了订单、配送的履约服务水平, 已经成为重要的竞争手段, 面向生产流水线的立体仓库拣货决定了对生产线节拍的支持水平。

立体仓库货架拣选货物的路径优化本质上是路径规划问题, 所以对其拣选过程的优化也通常将其转化为路径优化问题来解决, 如将其视为旅行商问题来解决[1], Sarker等提出了一种基于控制和调度系统立体仓库优化拣选的混合智能方法[2]。以这种思路, 国内外围绕固定式货架立体仓库的拣选问题进行了大量研究, 提出和应用了一系列优化方法和算法。包括有分支定界法[2]、遗传算法[3]、粒子群算法[4]、禁忌搜索算法、模拟退火算法。由于各种算法求解复杂度和耗费时间有差异, 为了提高工程实用性, 围绕求解效率和优化程度, 不同学者又提出了新优化思路或进行了一系列改进和算法优化。如方彦军等采用最大最小蚁群算法改进基本蚁群算法过早陷入局部最优的缺陷, 并用于自动化立体仓库拣选作业优化问题取得较好效果[5];田国会等采用了一种结合Ho Pfield网络模型的遗传算法, 该算法利用了遗传算法的全局寻优特性和Hopfield/Tank神经网络的局部快速搜索能力, 获得了全局优化的拣选作业路径[3]。靳萌[6]等提出了一种结合动态规划方法的启发式搜索算法生成拣选路径;该方法调和了动态规划空间开销大与启发式搜索时间开销大的矛盾, 有效解决了多穿越巷道布局下的拣选路径规划问题, 算法有效节约了计算机空间资源。

这些算法各有千秋, 但随着改进, 越来越复杂, 需要复杂的编程实现才能应用, 不适合普通工人和简单的实验仿真、教学中应用。

Trans CAD是美国Caliper公司设计研发的一款基于GIS (Geographic Information System) 的交通规划软件, 目前它得到许多国家和地区广泛的应用。其简单易学, 具有强大的绘图功能和编辑功能[7]。Trans CAD软件具有强大的规划功能, 内置路径优化算法, 能实现路径规划优化, 可用于寻找交通路径、道路的需求量的预测和分析, 物流中心和仓库的选址规划等。近年也有少数几个研究将其应用到了立体仓库货架拣选作业路径优化问题中[8], 但对立体仓库简化过多, 与实际立体仓库模型差异较大;且限于模拟, 而不是直接利用其进行路径规划。

鉴于此, 本文研究了通过Trans CAD的路径优化功能对固定式货架自动化立体仓库 (为表述简单, 简称为“立体仓库”) 的拣货路径优化的应用方法。通过将立体仓库的货位和路径信息直接转化为Trans CAD地图, 然后利用Trans CAD路径规划功能, 实现了自动化立体仓库的拣货路径的优化。提高了立体仓库的拣货路径规划的和拣选效率, 减少了能耗, 节约成本。从而可以提高对订单的响应速度和企业的竞争力。

固定式货架自动化立体仓库主要由固定式货架 (构成货位) 、巷道堆垛机、输送系统、出入库工作台、控制系统 (包含中央控制计算机) 等构成。拣选作业时, 仓库管理员根据货物的出入库需求, 将出入库货物信息输入到中央计算机中, 中央计算机将拣选的作业任务的任务单传送给控制系统, 控制系统再传输给执行系统, 巷道堆垛机根据执行系统的相关执行指令到货架上的相应的货位点进行货物的存取作业 (具体存取也可由人完成) , 在存取作业完成后, 并回到出入库工作台。通常每次要进行一系列货位拣选任务, 因此涉及路径问题。路径不但决定了路径的长短, 也决定了所耗费的时间、能耗。因此, 对拣选路径优化也对应的有路径最短和时间最短[4]两类目标。拣选的路径距离可通过式 (1) 来表示, 对应的行驶时间可通过式 (2) 来表示。

式中D表示总路线距离, T表示拣选时堆垛机行驶总时间, n为拣选需要经过的所有经过的包含工作在在内的货位点的数量 (由单次的拣选任务单决定) , ki表示拣选需要经过第i个货位点, 其中第1个点为工作台。d (ki, ki+1) 表示经过货位点ki, ki+1堆垛机行驶的距离, t (ki, ki+1) 为对应的行驶时间, ty (ki, ki+1) , tz (ki, ki+1) 分别表示堆垛机在两货位点间水平和垂直方向的行驶时间, vy、vz为堆垛机的水平和垂直方向的匀速行驶速度, L、H分别代表货架的单位宽度、高度, yki、zki为第i个货位点的y、z坐标。

Trans CAD有强大的路径规划功能, 可以在路线网络中得到任意起点到终点的最短路径或最优路径, 但都基于其内置地图和生成的网络来实现的。因此, 如果要应用Trans CAD来进行立体仓库的拣选路径优化, 涉及两个层次性问题: (1) 自动化立体仓库在Trans CAD中的表达, 即必须将立体仓库的定位信息转化表示为Trans CAD的地图信息; (2) 拣选优化问题的表达。将立体仓库的拣选路径问题转化Trans CAD的路径规划问题。显然, 第 (1) 个问题的解决是第 (2) 问题解决的基础。以下只阐述要点, 涉及的Trans CAD的一些通用操作, 如增加属性字段等, 可参考文献[7]。

立体仓库由一系列货架构成的货位 (或货格) 组成, 根据其构成原理, 对拣选的调度寻址, 每个货位点位置信息实际上包含货位所处的巷道、层和列信息, 则可用 (x, y, z) 三维坐标来表示, 对应代表货位在第x巷道第y列第z层的位置, 但Trans CAD的规划使用的位置坐标是二维的。为此, 可如下转换:以x坐标将立体仓库分层, 称为货位点层, 层号为x坐标, 这样立体仓库就可以直接转化为多个层次的二维库位组合, 然后将立体仓库的货位点位置的 (y, z) 坐直接转为Trans CAD的坐标 (即实现一一对应) 。为了实现以上转化, 需要在Trans CAD中新的二维立体仓库货位点增加属性来区分其本身的层次, 以表示原先的x坐标。这样就可以的将自动化立体仓库的三维坐标转换为Trans CAD中的二维坐标, 完成了立体仓库在Trans CAD的地图信息表达, 为后期路线规划奠定基础。主要操作步骤如下:

(1) 建立立体仓库货位点的平面示意图。可使用常用的CAD绘图软件来完成。绘制时, 按前面的立体货位按巷道分割的思路, 分巷道绘制二维平面图, 保持其x、y、z坐标相对位置、间距与立体仓库中的一致, 如 (1, 1, 1) 与 (1, 1, 2) 为z方向相邻的货位, 在二维地图上也应相邻。图1为在Auto CAD中绘制的两条巷道的自动化立体仓库货架的平面表达图形, 粗实线标出的为巷道分界线。完成后, 将其保存为dxf格式。

图1 货架货格平面示意图   下载原图

(2) 导入到Trans CAD中。将以上的dxf格式文件导入到Trans CAD中, 并检查网络的连通性 (使用Check Line Layer Connectivity命令) , 修改错误未连通的节点, 必须修改到保证图中的任意相邻点的网络连通, 因为Trans CAD将根据网络的连通性来确定路径, 不保证任意相邻点连通, 则表达的路径将与实际的立体仓库拣选有区别, 因为实际的立体仓库任意两个相邻货位是相通的。

(3) 为Trans CAD中的货位添加坐标。在Trans CAD中激活建立的货位点层, 修改点的属性 (Modify Table) , 增加记录x、y、z坐标属性的字段, 为理解简单, 可命名为巷道号、y坐标, z坐标。并用原先立体仓库的坐标对应填充。填充后的结果如图2示意。图中当x为负时, 表示在x巷道左侧货架;当x为正表示在x巷道的右侧货架。

图2 Trans CAD中的货位点坐标示意   下载原图

经过以上三个步骤就把立体仓库的货位信息在Trans CAD中转换为了地图信息, 简称立体仓库地图。立体仓库地图的每一个点代表原立体仓库中的一个货位, 但相邻两货位之间的距离都被抽象为了1, 实际信息在2.1.2中表达。

在确定自动化立体仓库的货位点之后, 还要根据实际, 表达巷道堆垛机的出发点以及巷道堆垛机的拣选运行速度以及在货位之间的运行时间。一般地, 在自动化立体仓库中都选择同一类型的巷道堆垛机, 其在货架间的巷道中行走时, 设其先进行水平方向的移动, 然后再进行垂直方向的运动。为简化, 忽视负载对堆垛机运行速度的影响。表达方法如下:

(1) 根据立体仓库的层数和前面的转换原理, 得到堆垛机的出发点坐标, 如, 设第一巷道堆垛机出发坐标为 (0, 1) , 第二巷道堆垛机的出发坐标为 (0, 11) , 如只有1个堆垛机则出发点相同, 优化时每次额外增加巷道的运行时间和距离即可。根据坐标, 在得到的Trans CAD立体仓库地图中对应点, 并将其单独保存为地理文件。即通过点击Trans CAD中的TOOLS-Export输出, 具体可参见Trans CAD的使用说明书。

(2) 将以上保存的堆垛机的地理信息以新图层的方式添加到原立体仓库地图文件中, 可添加不同样式 (style) 标记来区分。如图3所示为添加堆垛机位置的立体仓库地图示意图。

图3 添加堆垛机位置的立体仓库地图   下载原图

(3) 添加堆垛机运行速度等属性。激活立体仓库地图线层, 修改其属性, 增加数据字段分别用于存储堆垛机水平和垂直方向两货位间的距离 (由于任何两货位间都是连通的, 该距离实际对应单位货格的距离长与高, 如果H与L都不是1, 即与2.1.1中货位坐标抽象的距离有差异, 则需要添加字段, 并通过H、L、现有“Length”字段间的公式转换存储为实际距离) 、运行速度、单位货格的行驶时间, 并根据实际堆垛机的运行速度转化后填充数据, 对应的单位货格的行驶时间为L/vy或H/vz.如图4为添加的实例片段, 设定H=L=1 m, 已知巷道堆垛机在水平方向上的速度为vy=2 m/s, 垂直方向上的速度为vz=1m/s, 则水平方向的单位时间距离0.5 s, 垂直方向的单位时间距离为1 s, 图中添加“speed”和“time distance”两个新字段分别存储水平方向的速度和单位货格的行驶时间, 为后面优化做好了参数定义准备。

图4 添加堆垛机运行时间属性片段   下载原图

在Trans CAD完整表达自动化立体仓库之后, 就具备了可利用Trans CAD中技术特征和功能进行路径求解的条件, 但仍需要确定拣选路径规划的路线网络、具体的拣选任务货物点和优化目标等。

将自动化立体仓库货架的拣选近似看成是旅行商问题。即堆垛机从出入库台出发, 历经所有需要经过的n个货位点拣选后, 最后返回到出入库台的过程, 为此寻找总拣选作业距离最短或总作业时间最短的路径。Trans CAD提供了两种方法来解决最短路径问题:使用”shortest path”工具箱和创建最短路径矩阵, 本处使用前者提高操作和实验交互性。该工具只需要指定起点和终点, 就可自动得到最短路径。主要步骤主要如下:

(1) 激活立体仓库货架地图的线层, 创建网络 (Create Network) 。选中所有字段, 主要应包括2.1.2中创建的两货位间的距离、运行速度、单位货格的行驶时间等字段, 如图4的“speed”、“time distance”字段;如果前面两货位间的距离用新字段表示, 此时创建网络对话中的“Read Length from”输入应选择对应字段 (默认为“Length”字段) , 如图5所示。并将创建的网络文件设为当前激活的网络。

图5 创建网络   下载原图

(2) 利用Trans CAD寻找最短路径。执行“Networks/Paths-Shortest Path”, 打开“Shortest Path Toolbox”工具箱, 按拣选货位在立体仓库地图上选中要经过的点 (即货位) , 并确定起点和终点。分别设定最小目标为距离 (Length) 和时间 (即设定的单位货格的行驶时间字段, 示例中为“time distance”) , 则可分别得到最短拣选回路和时间最短的拣选回路。如图6所示。

图6 求取拣选路径方法   下载原图

以下通过拣选实例分析基于Trans CAD的立体仓库拣选路径优化的方法, 并分析效果。实验内容包括: (1) 基于总作业路线距离最短的单巷道拣选作业路径的优化; (2) 基于总作业时间最短的多巷道拣选作业路径的优化。

设一自动化立体仓库有固定货架8排, 每排固定货架有10层30列, 总共2 400个货位, 平面示意图如图7所示。货架中货格的宽度 (L) 、高度 (H) 都为1 m.每条巷道都有一台堆垛机, 每一排的货架都有一个出入库台。其第1、2两条巷道的货位信息、存放货物信息如表1所示, 其中的货位号编号格式为“H巷道号-层号-列位置”, 如H1-01-02表示在第一巷道的第一层第二列位置。现有两张下架作业单, 分别如表2、表3所示。已知巷道堆垛机在巷道的轨道上水平方向的运行速度为Vy=2 m/s, 垂直方向上的升降速度为Vz=1 m/s, 巷道堆垛机货叉平均存货或取货的时间为8 s, 自动化立体仓库每日平均订单量为400个。假定货箱足够大, 每次能将每个巷道的任务一次拣完, 巷道堆垛机都以整托的方式进行货物的存取作业, 其水平方向单位距离能耗为10个单位, 垂直方向单位距离耗为15个单位。

图7 仓库平面示意图   下载原图

表1 货位及库存信息表     下载原表

表2 下架作业单1     下载原表

表3 下架作业单2     下载原表

按前面的思路, 在Trans CAD建立案例中立体仓库的Trans CAD地图模型。为了便于分析和计算, 只建立仓库第一巷道和第二巷道的货架地图, 如图2所示。

已知表2下架作业单1都是在第二巷道的货架的货格上。普通拣选作业方式为从远离巷道堆垛机出入库台开始从右往左依次开始拣选, 下架作业单1拣选的路径如图8所示。

图8 下架作业单1普通拣选作业路径   下载原图

由图8中知, 该方式下拣选总作业距离为56 m, 水平方向距离30 m, 垂直方向距离26 m, 总行走时间41 s, 货叉存货或取货的单位时间为8 s, 则总作业时间为121 s.

应用Trans CAD对其进行优化, 同样根据表1信息在地图上选中要经过的点, 并确定起点和终点, 以距离最短为目标, 得到下架作业单1的最短拣选回路如图9所示。

图9 拣选路径及拣选结果   下载原图

由图9可知, 优化后的总作业距离为52 m, 减少4 m.其中水平方向距离30 m, 垂直方向距离22, 下架作业单1优化前和优化后的分析比较表4所示。

表4 下架作业单1实验结果比较     下载原表

表3下架作业单2包括在第一巷道和第二巷道的货架货格上, 普通的拣选作业方式为从远离巷道堆垛机出入库台开始从右往左依次开始拣选, 拣选的路径如图10所示。

由图10中得, 总作业距离为89 m, 其中水平方向距离48 m, 垂直方向距离41 m, 拣选作业的行走时间62 s, 巷道堆垛机总共经过9个货位点, 同时巷道堆垛机还把货物放货在出库台, 则总共11个点, 则多巷道传统拣选的总作业时间为150 s.

图1 0 拣货单2的普通拣选路径   下载原图

对下架作业单2的货架拣选路径进行优化, 求解总作业时间最短的拣选路径。根据表2分别在第一、二巷道选中要经过的点, 并确定起点和终点, 和在“shortest path”工具箱选择时间为优化目标, 显示的最短拣选回路和拣选结果如图11所示。

图1 1 拣货单2的最短时间拣选优化路径   下载原图

从图11计算出优化拣选水平距离为48 m, 垂直方向为36 m, 基于Trans CAD的多巷道拣选作业的总作业时间为131 s.下架作业单2优化前后的分析比较如表5所示。

表5 下架作业单2实验结果比较     下载原表

立体仓库作为物流的先进装备应用越来越广泛, 但面对日益增长的拣选需求, 节约时间、路线和能耗成为企业关注的问题。本文应用Trans CAD的路线规划功能, 基于位置信息和立体仓库的作业原理, 将立体仓库通过转换降为二维图形信息, 并导入到Trans CAD生成为地理信息, 从而可以利用Trans CAD的路线规划功能。转化中涉及立体仓库货位点表达, 堆垛机表达和拣选问题表达3个主要问题。一旦建立模型后, 就可以快速获取每次的优化拣选路径。论文的方法为立体高层货架简单直观优化拣选路径和进行拣选优化实验、仿真提供了一种新的选择, 也拓展了Trans CAD的应用。该方法已经成功用到了《物流运筹学》等的优化教学实验中。