基于关联性分析的智能仓库货位优化研究

曾敏刚 张俊杰 陈伟贤

摘  要：订单分拣是仓储作业中很重要的一个环节，而智能仓库拣选中货架的位置处于动态变化中，因此进行合理的货位布局尤为重要。为有效解决智能仓库货位分配问题，提出了在仓库中设置关联货物储存区的策略，进而给出了基于关联性分析的货位优化方案，即先根据历史出库订单数据進行关联性分析以进行储位布局，以实现机器人搬运货架次数最少的目标;同时考虑COI指数等因素进行建模确定货架布局，以实现机器人搬运路径最短的目标。最后，通过算例分析，验证了基于关联分析的货位优化方案的有效性。

关键词：货位优化;关联规则;Apriori算法;智能仓库

中图分类号：F253    文献标识码：A

Abstract： Orders sorting is an important part of warehousing operations， the position of shelves is in dynamic change in intelligent warehouse， so it is particularly important to carry out reasonable location layout. The strategy of setting up associated cargo storage area in warehouse is proposed so as to realize the optimization of storage location in intelligent warehouse. Then， a new optimization solution of storage location is put forward： first， the correlation analysis is carried out according to the historical outgoing order data to carry out the layout of storage space， so as to achieve the goal of minimizing the number of cargo sorties carried by robots. At the same time， the factors included COI index are taken into the model to realize the shelf layout in order to achieve the goal of the shortest moving path of the robot. Finally， the effectiveness of the location optimization scheme based on correlation analysis is verified by an example.

Key words： storage allocation; association rules; apriori algorithm; intelligent warehouse

0  引  言

电商仓储，正在经历半人工、半自动化向以机器人智能物流系统为主的仓库自动化转变，实现无人智慧化布局、数字化运营和自动化作业。智能仓库主要包括四大系统：（1）存储系统，主要由不同类型的货架组成，限高2.5米;（2）输送系统，主要由AGV机器人组成;（3）分拣系统，主要由拣货台、输送装置和自动识别系统等组成;（4）控制系统，主要由自动控制系统和中央计算机管理系统组成。拣货作业时间一般约占全部作业时间的40%以上，拣选成本一般占全部运营成本的65%以上[1]，所以货位布局的优化对提高分拣效率尤为重要。

目前国内外学者对货位优化的研究主要集中在3个方面：（1）货位优化模型：①以货架稳定性、拣货时间或拣货距离为优化目标：文献[2-5]以货架稳定性最高和堆垛机运行时间最短建立多目标模型，张贵军等[6]提出了精英多策略的货位分配方法;杨玮等[7]基于多色集合理论对货位分区建立多目标模型;肖建等[8-9]根据物料的确定相关性和统计相关性这两个概念，建立了以拣货人员距离最短的多目标优化数学模型，但所研究的相关性，仅限于物料需求的相关性，例如加强螺栓与防松螺母这样的物料组合;文献[10-11]以传统仓库为例，提出了SKUs相关性的概念，设计了“SKUs对”位置交换策略以提高效率。②以仓库利用率、成本和能耗为优化目标：Simon Brezovnik等[12]考虑提高仓库空间利用率和降低库存成本两个目标建立优化模型;Muppant等[13]建立了整数规划数学模型;Quintanilla等[14]基于随机存储策略，提出了最大化仓库空间利用率的货位调整方法;张思建等[15]以出入库总能耗及存取效率为目标建立模型;ELSAYED E A[16]提出基于迭代搜索的定位储存模型，以租用存储空间的方式最优化仓储容量;András Kovác[17]针对货物循环进出的情况，建立了循环周期最短和工作强度最低的货位分配模型。③RGV行驶时间为优化目标：刘万强等[18]建立了RGV小车行程时间的通用计算模型，通过更改不同的参数来对应计算不同工况下RGV车的行程时间。④货架搬运次数为优化目标：Nils Boysen等以亚马逊仓库Kiva系统为例，建立了以货架搬运次数最小化为目标的混合整数规划模型，用于求解最佳拣选订单的批次和顺序以及货架分配方案[19]。（2）货位仿真和编程实现：赵金萍等[20]对自动化立体仓库的叉车、堆垛机和货架均进行了优化，Flexsim软件仿真结果表明操作台的利用率提高了10%～15%;张仰森等[21]以某集团公司立体仓库管理系统为例，提出了一个多角度计算的级联式的货位优化分配算法及其编程实现。（3）货位布局方式和存储策略：文献[22-23]研究了不同的仓储设施布局方式对货位分配的影响，文献[24-26]研究了Fishbone布局方式对AGV小车的行驶路径的影响;文献[27-28]基于聚类方法，提出了现货物分类优化管理的策略;QUINTANILLA S等[29]将货位分配问题类比于着色问题，采用定位存储策略最小化存储空间。

综上可知，（1）国内外学者研究对象集中于自动化立体仓库，对智能仓库的货位优化问题研究甚少，而“货到人”拣选方式中货架位置是动态变化的，传统优化方法并不适用于智能仓库分拣的工作场景;（2）研究方法主要集中于建立数学模型，目标多为拣货时间、货架稳定性和空間利用率等，考虑因素集中于周转率，而对货物相关性研究甚少;（3）部分学者虽从相关方面进行了研究，但相关性分析算法的有效性较弱，并未从数据挖掘方面进行拓展。因此本文针对智能机器人“货到人”拣选工作特点，综合考虑了货物相关性和货物COI指数等因素，结合数据挖掘的Apriori算法，提出了基于关联性分析的货位优化方案。

1   问题描述

1.1  问题提出与基本假设

智能仓库自动化应用的主要一个方面便是“货到人”拣选，工作模式为：当订单开始处理后，系统发出指令，AGV智能机器人从储存区将整个货架搬运至拣货工作台，拣选人员只需根据显示屏和播种墙电子标签的提示，从指定货位拣取相应数量的商品放入订单箱即可。“货到人”这一拣选方式，给货物存储与货物拣选之间的动静结合带来了新的问题：（1）如何在一个货架上摆放多张订单的货物？（2）电商仓库中存储的货物批量大、种类多，如何挖掘出货物之间的关联性？（3）如何布局货位，使得AGV机器人搬运货架路径最短？

根据如上描述，将本文进行货位优化所作假设总结如下：

（1）存放的货物种类已知;

（2）每种货物的周转率和体积已知，即COI指数已知;

（3）货架上每个储位只摆放同一种货物，储位单元格长宽高为定值;

（4）智能仓库采用单端出入库方式;

（5）存取货物耗费的时间忽略不计，仅考虑货物拣选时间。

1.2  模型建立

1.2.1  符号说明

模型所需符号及说明见表1所示。

1.2.2  建立模型

（1）AGV搬运货架次数最少

AGV每次从存储区搬出的货架上要尽可能包含多张订单的货物，即关联性高的货品的位置尽可能紧邻。为此通过关联性分析将货物分成不同的类别，使得同类货物尽可能集中放置，而不同类货物则尽可能分散。

①同类货物内部的分散度

定义各类货品的中心位置为该类货品内所有货物向量坐标的均值：

a=∑x，y，z，w                                           （1）

每类货品的类内分散度定义为此类货品中每种货物到中心位置的距离之和：

d=∑                      （2）

则所有货物的类内分散度为：

d=∑d                                                  （3）

②不同类货物之间的分散度

定义所有货品的中心位置为各类货品中心位置的向量坐标的均值：

A=∑a                                                （4）

定义不同货品间的类间分散度为各类货品中心位置到所有货物中心位置的距离之和：

D=∑a-A                                             （5）

考虑到让关联度高的货物尽可能放在一起，故类内分散度要最小，而关联性很低的货物则要均匀地分散到仓库中且离仓库入口距离最小，故类间分散度最大，且A=最小。

故目标函数为：

maxF=                                              （6）

（2）AGV搬运货架行走路径最短

在考虑货架的布局时，引进货物COI指数[30-31]，综合考虑货物周转率和体积两个因素，使得COI指数小的货物尽可能靠近出库口，减少AGV搬运距离。

该目标函数为：

minF=∑∑∑∑C·L                                      （7）

约束条件为：

①货位界限约束

x≤x≤x    y≤y≤y    z≤z≤z    w≤w≤w                             （8）

②容量约束

∑∑∑∑Q≤∑∑∑∑V                              （9）

2  模型求解

2.1  算法思路

电商仓库中存储的货物种类繁多且数量庞大，然而相互之间存在关联性的货物却不多，故本文提出关联货物存储区的策略，只将关联性很高的少部分货物存放至该区域，在该区域内按照上文建立模型进行货位布局。

货物关联性反映的是两种货物或者多种货物之间相关程度的强弱，而COI指数则是某种货物的周转率与体积之比，是货物本身特有的“属性”。二者无法统一度量，此外关联性程度高的货物可能COI指数很低，故本文在求解上未采用将多目标转化为单目标的解法，而是采用两阶段优化求解，算法思路如图1所示。

货品关联性分析旨在通过分析历史已处理的订单数据，根据货品间的关联性结果确定储位布局，货架布局方案则通过建模求解。

2.2  货位布局求解

2.2.1  关联规则简介

关联规则（Association Rule）是在数据库和数据挖掘领域中广泛研究的一种重要模型[32]，可数学化描述为：设I

=i，i，i，…是一個项目集合，D是事务型数据库，其中的每个事务T都由一个唯一的标识符TID进行区分，即D

=T，T，T，…，每个事务Ti=1，2，3，…对应I上的一个子集。事物数据库D如表2所示。

设项集X、Y是项目集合I中的一个集合，满足X？哿T，Y？哿T，X？奂I，Y？奂I，且X∩Y=？覫。用X→Y表示关联规则，相关关系的强度由支持度（Support）和置信度（Confidence）来评价。其中SupportX→Y=PX∪Y，ConfidenceX→Y=PY|X。

为了挖掘有意义的关联规则，需要设定两个阈值：最小支持度MinSup（Min Support）和最小置信度MinCon（Min Confidence），将同时满足MinSup和MinCon的规则称为强关联规则[33]。

2.2.2  Apriori算法简介

在众多挖掘关联规则的算法中，Apriori算法为布尔关联规则挖掘频繁项集的经典算法，并得到了广泛应用。Apriori算法的求解步骤为逐层搜索迭代，即利用k-项集来产生k+1-项集：首先扫描数据库找出频繁1项集，记为L1，然后对L1做连接操作生成C2，扫描数据库从C2中选出频繁2-项集即L2;不断如此循环下去直到无法发现更多的频繁k-项集为止[34]。

Apriori算法挖掘关联规则主要可分为4个步骤，如图2所示。

2.2.3  货位布局方案

采用Apriori算法对历史订单进行分析，可挖掘出关联性高的频繁项目集，储位布局时需将关联性高的货物尽可能摆放在同一个货架上，应遵循以下规则：（1）将关联规则根据置信度大小排序，置信度高的关联规则所包含的货物优先布局;（2）相互独立的关联规则所包含的货物应放置在不同货架上;（3）存在交叉关系的关联规则里所包含的货物，应根据储位数量进行合理放置，例如关联规则A→B和E→B存在交叉，则所涉及的ABE这3种货物统一放在一个货架上;（4）若多个关联规则均包含某种货物，且该货物已经布局完成，则将关联规则里包含的剩余所有货物放在同一个货架上，例如关联规则F→A、G→A和H→A均包含货物A，且A布局已经完成，则将剩余的货物FGH放置在同一货架上。

储位布局只确定了哪些货物组合到同一个货架上，实现了AGV搬运货架次数最少的目标;而AGV搬运路径最短目标的实现，则需在储位布局的基础上，将COI指数低的货物分配到离出库口最近的位置上，可通过Lingo进行模型求解。综合储位、货架布局方案得到最终的货位优化方案。

3   算例分析

3.1  数据收集与关联性挖掘

假设仓库当前共存储50种货物，已经出库了100张订单，订单数据如表3所示：

设定MinSup=0.2，MinCon=0.75，根据Apriori算法求解步骤，并按照置信度大小对其进行排序，最终筛选出的二项频繁项目集的强关联规则如表4所示：

置信度越高表示两者之间的关联性越高，储位布局时两者的位置应尽可能的紧邻。

3.2  货位布局方案

假设一个货架共有3个储位，每个货位只放一种货物，且每个货位的容量无限大。仓库布局如图3所示，其中括号内数字表示该货架到出库口的距离。

根据这100张历史订单分析得到的关联性结果，按照储位布局规则依次考虑货物间的位置，得到储位初步布局图如图4所示。

为简化计算：（1）以货物周转频率代替COI指数;（2）因为同一货架上的放置货物已经固定，故可取3种货物周转率的加权平均值作为货架的周转率。

根据3.3节中建立的模型进行求解，得到新的货架布局如图5所示。

4  结  论

本文针对传统研究的不足，对智能仓库的货位布局进行研究，通过算例分析，得到以下结论：（1）针对智能机器人“货到人”拣选货架位置动态变化的工作模式，提出了设置关联货物储存区的策略，进而给出了基于关联性分析的货位优化方案;（2）通过关联分析确定储位布局，实现了机器人搬运货架次数最少的目标;考虑COI指数建立模型求解货架布局实现了机器人搬运路径最短的目标;（3）引入了数据挖掘中Apriori算法来分析货物之间的相关性，提高了算法的有效性。

研究方法和货位布局方案对企业现有的仓库拣选工作具有重要的指导意义。本文在方案求解上采用分阶段优化方法，未来可考虑全局优化，并考虑订单组合和货位容量的限制，以得到更优的货位布局方案。

参考文献：

[1]  RENDE K， THO L D， KEES J R. Design and control of warehouse order picking： A literature review[J]. European Journal of Operation Research， 2006，182（2）：481-501.

[2] 鄂晓征，祖巧红，曹萌萌. 基于遗传算法的汽车零件自动化仓储货位优化[J]. 系统仿真学报，2013，25（3）：430-435，444.

[3] 侯忠，郑国华. 基于遗传算法的汽车零配件仓库货位优化研究[J]. 铁道科学与工程学报，2016，13（11）：2305-2312.

[4] 李鹏飞，马航. 基于病毒协同遗传算法的自动化立体仓库货位优化模型[J]. 中国管理科学，2017，25（5）：70-77.

[5] 赵雪峰，贠超，胡江. 自动化仓储系统不规则货位优化问题研究[J]. 计算机工程与应用，2012，48（24）：222-225，230.

[6] 张贵军，姚俊，周晓根，等. 基于精英多策略的货位分配优化方法[J]. 計算机科学，2018，45（1）：273-279.

[7] 杨玮，傅卫平，王雯，等. 基于多色集合和粒子群算法的立体仓库货位分配优化[J]. 机械科学与技术，2012，31（4）：648

-651，655.

[8] 肖建，郑力. 检修备品库的货位优化模型[J]. 清华大学学报（自然科学版），2008（11）：1883-1886.

[9] 肖建，郑立. 考虑需求相关性的多巷道仓库货位分配问题[J]. 计算机集成制造系统，2008，14（12）：2447-2451.

[10] 李英德. 波次分区拣货时装箱与货位指派问题协同优化的模型与算法[J]. 系统工程理论与实践，2013，33（5）：1269-1276.

[11] 李英德，鲁建厦，潘国强. 穿越策略下考虑相关性的货位优化方法[J]. 浙江大学学报（工学版），2012，46（8）：1424-1430.

[12]  Simon Brezovnik， Janez Gotlih， Jo？觩e Balic， et al. Optimization of an Automated Storage and Retrieval Systems by Swarm Intelligence[J]. Procedia Engineering， 2015，100：1309-1318.

[13]  Venkata Reddy Muppani （Muppant）， Gajendra Kumar Adil. Efficient formation of storage classes for warehouse storage location assignment： A simulated annealing approach[J]. Omega， 2007，36（4）：609-618.

[14]  QUINTANILLA S， ？魨NGELES P？魨， BALLEST？魨N F， et al. Heuristic Algorithms for a Storage Location Assignment Problem in a Chaotic Warehouse[J]. Engineering Optimization， 2014，47（10）：1405-1422.

[15] 张思建，方彦军，贺瑶，等. 基于模拟退火算法的AVS/RS多批货箱入库货位优化[J]. 武汉大学学报（工学版），2016，49（2）：315-320.

[16]  ELSAYED E A. Optimization of Warehouse Storage Capacity under a Dedicated Storage Policy[J]. International Journal of Production Research， 2005，43（9）：1785-1805.

[17]  Andr？觍s Kov？觍cs. Optimizing the storage assignment in a warehouse served by milkrun logistics[J]. International Journal of Production Economics， 2009，133（1）：312-318.

[18] 刘万强，周亚勤，杨建国，等. 新型棋盘格密集仓库的出入库货位分配优化[J]. 东华大学学报（自然科学（下转第37页）