一般来说, 自动化立体仓库货物货位 (slotting) 是由货物编码和储位编码联合组成, 货物编码和货物唯一对应且固定, 不会随着货物的移动而变化;而货物和其所处的储位编码是唯一对应但非固定, 随着货物的移动, 其对应的储位也会变化, 因而货物的货位也是变化的。在自动化立体仓库中, 以医药为例, 药品种类繁多, 批量小, 由于季节性和流感病等因素以及仓库中药品种类的增减会导致原有的药品摆放位置不再合适而需要货位优化 (slotting optimization) 。货位优化是因为各类变化因素而需动态再配置仓库货物货位, 使货位布局合理, 实现拣货效率提高和仓库操作成本降低为目的。货位优化主要发生两个时间点:一个是仓库盘点时发现货物摆放存在不合理的情形, 如药品种类增加或减少;二是由于外部因素, 如季节性疾病或某种突发性疾病爆发, 导致医药品出入库频率发生变化而需要重新进行储位分配。

国外研究有:Malmborg[1]提供了在不同的货位分配原则下分析空间需求和取货效率之间的折衷的工具;Thonemann[2]提出在随机环境中应用周转率和分类进行库位分配的方法;Moon等[3]比较了采用不同存储 (分类存储或随机存储) 策略进行储位再分配时的设备利用率;Heragu等[4]提出了用启发式算法对不同的货物存储方式找到适当的货位分配策略, 解决功能区规模与产品配置;Koster等[5]梳理了手工拣选作业流程设计与控制的决策方案, 包括布局设计、存储分配方法, 路由方法, 订单配料和分区等;Kim等[6]提出了基于模拟退火的货位问题模型与算法求解。

国内研究有:周奇才等[7]提出立体仓库运行控制的优化准则与优化控制数学模型, 提出堆垛机出入库系统货箱运行的优化控制程序等;肖建等[8]根据物料相关性及用料频率, 建立了检修备品库货位分配的多目标优化数学模型, 用蚁群算法求解了该NPC问题;俞雷霖等[9]提出了一种求解自动化立体仓库货位分配与优化的混合禁忌搜索算法, 实现堆垛机对所有出入库零件的操作运行距离之和最短;马永杰等[10]提出了基于随机存储策略的库区和货位分配以及堆垛机行驶时间为优化控制目标的多目标函数;罗健[11]提出了基于离散粒子群算法的货位优化方法, 提高自动小车存取系统的存取效率, 方便货位管理;陈璐等[12]提出了自动化立体仓库中物料动态储位分配优化问题的整数规划建模, 设计了一个两阶段的启发式算法, 利用禁忌搜索算法求解。

从上面的文献综述可以看出, 目前关于货位优化的研究存在普遍性的问题是:自动化立体仓库货位与储位的特性研究没有有效区分, 货位移动前后动态优化模型建立分析缺乏。本文针对这些问题, 通过对自动化立体仓库进行货位移动动态优化建模研究, 将货物的货位融合货位编码和储位编码两者信息、将货物移动前后的相关数据作不同时间参数标记, 并考虑货物出入库效率高等因素。

传统的储位存储策略主要有四种:定位存储、随机存储、分类存储、分类随机存储。如医药自动化立体仓库通常采取分类存取的方式, 将存储区分为常温区、冷藏区、特殊药品区等, 然后在各个区域按一定原则进行储位的分配。仓库货位优化一般需要遵循以下原则:

(1) 一般货品的放置应该遵循先近后远、先下后上, 重物在下、轻物在上的原则, 以保证货物的就近入出库和货架的稳定。

(2) 分巷道存放。当仓库中有多个巷道时, 同种货物要分散在不同的巷道。

(3) 相关性产品放在一起。相关的货物有时需要同时存取, 为降低存取成本, 可根据产品的特性将货物分成族, 将同族产品摆放在相近的储位中。

在自动化立体仓库中, 货位优化的原则与传统的原则有一些不同, 以医药为例, 区别主要如下:

(1) 相似的药品可以摆放在一起。相似药品是指医药性质属于同类但不同厂家、不同品名的药品。但在自动化立体仓库中, 由于采用的是条形码技术或射频识别技术, 用堆垛机进行存取, 不会产生混淆现象, 凭借这些强大的信息系统的支撑, 相似的药品可以摆放在一起。

(2) 药品的摆放可以不考虑重量。由于药品的重量较轻且没有较大区别, 因而在摆放的过程中可以不考虑重量。

(3) 药品移动的距离最短。在货位优化的过程中, 为使效率提高, 堆垛机运行成本降低, 应尽量使药品移动的距离最短, 所花时间最少。

本文假定, 在仓储管理系统中, 一个货物包含有货物编码, 储位编码和货位三条信息。

储位为仓库中货格, 储位编码方法有区段式编码、品项群式编码、地址式编码三种方式。本文对储位的编码采用地址式编码方法。首先将仓库模拟成一个立方体, 里面的货架按排有规律的摆放。储位编码按储位在仓库货架中所属的排、层、格, 从前到后、从下到上、从右到左按数字1、2、3等进行编码。如010203表示第一排货架第二层的第三个货格上的医药品。

货物编码和货物是唯一对应且固定的, 且不会随着货物的移动而变化。货物编码方法较多, 主要有流水编码法、分组编码法、数字分段法、实际意义编码法等。本文对医药品的编码采用实际意义编码法, 其编码包含的信息包括货物的名称、重量、尺寸等信息。此外由于本文将所有医药品按族进行了分类, 因而货物编码所包含的信息中还包括货物所属的族。在实际操作中, 该货物编码可表现为货物的条形码或电子标签。

本文将货物的货位定义成由其所处的储位编码和该货物编码联合组成, 是随着货物所处的储位的变化而变化的。每个货物的货位信息包括货物此时所处的储位编码及该货物所处的族。如0102031表示存储在仓库第一排货架第二层的第三个货格上的医药品, 该医药品所处的族为第1族。

为了将研究问题简化, 便于研究, 本文提出了如下假设:

(1) 储位与货品的存放尺度相适应。

(2) 假设货品进行分类存放, 每个货格中只放一种货物。

(3) 假设货位优化前后位于同一个货格上的所有货物仍处在同一个货格上。

(4) 假设货格长宽高尺寸相同。

(5) 假设堆垛机和传输带都为匀速运动。

(6) 医药品从货架到传送带的时间忽略不计。

(7) 假设货物移动过程中即使货物是在同一货架上移动, 也要先移动到该货架y=0和z=0处后再移动到优化后位置。

在自动化立体仓库中, 需要定期或不定期的进行货位优化, 本文引入参数t来表示仓库进行货位优化的次数, 第t次时间相应参数可以进行历史数据的查询和保存。需要指出的是, 第t次进行货位优化时引入的初始数据并不等同于第t-1次进行货位优化时优化后的数据结果, 还包括这两次货位优化的中间时间段由于货位整理, 货物出入库等原因引起的信息的变化, 这就要求在仓储管理过程中, 当仓储状况发生变化时需要及时将变化信息录入计算机系统, 方便下次进行货位优化。

(xtytzt) ———第t次货位优化后医药品在货架上所处储位的储位编码;

(xt-1yt-1zt-1) ———第t次货位优化前医药品货位优化前所处储位的储位编码;

(A, B, C) ———分别表示货架在x向、y向、z向上货格的最大编号, 即x、y、z的最大值;

l———货格长宽高的长度;

h———每排货架之间的距离;

vx———传输带的运输速度;

vy———堆垛机在纵方向的移动速度;

vz———堆垛机在垂直方向移动速度;

nt———t时间货位优化时将所有产品分为n族;

i———表示第i族药品;

j———表示第i族第j个药品;

t———表示进行货位优化时间t;

dt———第t次货位优化时所有n族药品类内离散距离和为d;

mt———第t次货位优化时第i族药品的坐标均值;

dijt———第t次货位优化时第i族内第j个药品到mi的距离;

kit———第t次货位优化时第i族药品的个数;

Mt———第t次货位优化时全部n族药品的均值坐标;

Dt———第N次货位优化时所有药品到n族药品中心M的离散度和;

Lt———第t次货位优化时所有药品均值坐标到出库口的距离;

pij———仓库中第i族第j个医药品的周转率。

为了方便货架上货格的表示, 将自动化立体仓库模拟成一个立方体, 建立如图1坐标体系。

医药品在出库的过程中先通过堆垛机走y方向和z方向, 然后到传输带上完成x方向的运输。位于同一个货格上的药品看做一个整体。模型的建立过程如下:

(1) 目标函数F1

储位分配中第一条原则是要提高出入库效率, 降低出入库距离, 实现就近入库。在货位优化中, 对储位进行重新分配, 目标之一就是实现货物的就近出库, 使出库频率高的货物摆放在离库口近的地方。就近出库, 即使货物在出库过程中总移动时间最短。第t次货位优化时将药品分成nt族, 第i族药品有kit (i=1, 2, 3, 4, …, n) 个, 每个医药品所在储位为 (xtytzt) , 在三维空间内表现为 (xijt, yijt, zijt) , 用模型表示如下:

图1 模拟仓库立体坐标图  下载原图

该目标函数中, 频率越高的医药品, 其运行时间就应该越短, 从而使总运行时间最短。考虑到货架与货架之间存在间隔, 运输带在x轴方向的单位运行距离为l+h。

(2) 目标函数F2

对于相似的医药品, 最好能够摆放在一起, 这样能直观掌握同类药品的数量与出入库变化, 便于管理。将相似药品摆放在一起, 即使相似药品之间的距离和最小。

计算类内离散度。定义第t次货位优化时第j族药品的坐标均值为:

计算类间离散度。全部nt族药品的均值坐标为Mt, 则:

定义所有药品类中心到n族药品中心Mt的离散度和的值为每类药品的中心mit到Mt的距离和, 则:

因为药品种类繁多, 很多药品都具有相似性, 为把相似的药品放在一起, 并尽量使所有药品均匀分散在仓库中并离出库口最近, 则应使类内离散度尽量小, 类间离散度尽量大, 并使均值坐标点M离出库口距离最短。则得到第二个目标函数:

(3) 目标函数F3

货位优化是一个对储位进行重新调整的过程, 货物的重新摆放就涉及到货物的搬运, 为节约时间和成本, 需要使搬运的时间和移动距离最短。由计算机统计资料可得知某药品目前在货架上的储位编码为 (xij (t-1) yij (t-1) zij (t-1) ) , 倒库之后, 该药品移动到的储位编码为 (xijtyijtzijt) , 要使移动距离最短, 则有第三个目标函数:

由公式1, 6, 7及相关约束条件, 得到自动化立体仓库货位优化的目标函数如下:

遗传算法需要一个标量的适应度信息才能进行计算, 对于多目标问题, 就需要根据多个目标来确定个体的适应值。目前, 国内外的适应值分配机制方法有如下一些:权重法、目标规划法、goal attainment法、constraint法、Goldberg等提出的基于Pareto非劣解概念的方法和non-generational遗传算法等。本文采用权重法。

利用遗传算法求解, 为方便进行轮盘赌选择, 适应度函数最好为求最大值函数, 因而将目标函数转化如下:

本文使用Matlab软件, 采用适合求解多目标优化问题的遗传算法来解决该货位优化问题。编码过程主要包括初始化、求适应度、选择、交叉、变异等几个步骤。其主要步骤介绍如下:

(1) 在计算机系统中, 每个货物的信息包含货物编码、其所处的储位编码和货位号等。由于货位优化是一个动态的过程, 其求解过程涉及出入库过程及堆垛机等运输设备的运行距离的计算, 因而需要一个能动态反应货物移动过程的数据作为数据来源。此外。模型的构建还涉及货物所处的族, 因而本文选择货物的货位作为求解模型的初始数据来源。

(2) 编程采用的是十进制编码。种群为一个矩阵, 每行为一条染色体, 染色体中每四个数字代表一个货物的相关信息, 分别表示该货物所在位置的行、列、排和所属的族。如染色体[1 4 6 1 2 5 3 2 4 5 6 3……], 其中 (1, 4, 6, 1) 表示该货物所在储位为 (1, 4, 6) , 并且该货物属于第1类。

(3) 求解适应度函数采用权重法。由于该问题为多目标优化问题, 且无法判断区分各目标的重要程度, 因而采用权重法, 通过给各目标函数分配不同的权重来寻求最优解。

(4) 选择采用轮盘赌选择法。轮盘赌选择是从染色体群体中选择一些成员的方法。在本文中, 将各目标函数分配权重后, 以其加权和在总和中所占的比重作为选择标准进行选择, 加权和越大的种群被选择的概率越大。

(5) 变异采用均匀变异算子。本文采用适合实数编码的均匀变异算子进行变异, 即用符合货物在某方向上坐标值范围内的均匀分布的随机数, 以变异概率来替代某染色体上的原有基因[10]。本文选择的变异概率为0.001, 交叉概率为0.8。

(6) 终止准则。由于本文模型适应度的阀值难以确定, 设置终止准则为:当适应度值在连续两代取值之差的绝对值小于等于10-3时, 运行终止。此策略简单易行, 易于控制, 不易陷入死循环, 且易于得到全局最优解。

本文选择虚拟一个自动化立体仓库来对模型进行验证。设该自动化立体仓库有20行20排20列, 所有货物分为3类。虚拟一组数据, 该数据包含50个货物的初始货位、出入库频率及所属族等信息。

评价货物摆放情况是否合理, 主要从是否满足三个目标函数来判别:货物是否都摆放在离出库口较近的储位上;相关性货物是否都摆放在一起;货位优化过程中货物的移动距离是否较小, 即F3值是否较大。此外还可通过适应度函数值是否达到一个较大数值来判断。

输入该组初始数据, 通过仿真得出优化前货物的摆放情况如下, 这时t=0, 货物分配杂乱分散, 布局不合理, 如图2, 仓库的综合性能较差。

为获得最优的结果, 通过输入不同的目标函数的权重值来获得不同的货位优化结果, 从中选择最优的一组结果作为最优决策方案。分配权重的思路为先平均分配权重值, 再分析输出结果, 找出三个目标函数中实现度最差的目标函数并适当提高其权重所占比例, 重复此操作, 逐渐寻得最优解。

当三目标函数的权重按W= (0.3, 0.6, 0.1) 分配时, 得到货位优化后的分布图如图3, 这时货物分布情况良好, 货物基本都摆放在仓库出入口处, 且都按族分配, 此时, F3的取值为1.4326, 取值相对较大, 表明货位优化过程中货物的移动距离较短。此时t=1, 适应度函数的取值为266.0525。该决策方案得到了较理想的结果。

图2 优化前货位分布图  下载原图

图3 优化后货位分布图  下载原图

为检验模型的时间维度, 假设第一次货位优化后, 仓库中有部分货物出库, 部分药品出入库频率发生变化, 且新增了一类药品。以新的初始数据作为输入数据, 得出优化后的货物分布图如图4。

图4 第二次货位优化后货物分布图  下载原图

此时, W= (0.2, 0.5, 0.3) , 货物基本都摆放在仓库出入口处, 且都按族分配, F3的取值为3.5153, 取值相对较大, 表明货位优化过程中货物的移动距离较短。此时t=2, 适应度函数的取值为399.4236。该决策方案得到了较理想的结果。

对优化前后货物分布情况进行比较, 可以发现经过优化, 货物的摆放更加规范, 表明遗传算法能有效解决该问题。

本文有效界定了自动化立体仓库货物货位的内涵与标定, 在考虑货物移动前后的相关数据能有效记录的前提下, 以医药为例, 构建了自动化立体仓库货物出入库效率高, 相似货物摆放一起, 货物移动距离最短三个因素的基于时间的货物货位优化多目标模型, 通过对算例采取遗传算法的结果显示本文方法对立库货位优化有效可行, 数据记录能有效进入仓储自动管理环节。