陈先宇

(重庆交通大学，重庆 南岸 400074)

优良的仓储配置可以促使企业灵活且高效地组织所经营的商品，提高企业商品周转效率，因此，如何进行仓储配置的优化是当前生产、零售，以及物流企业所面临的一个重要问题.例如，企业生产出的商品往往需要暂时放置在自己的仓库中，然后再选择合适的时机将这些商品按照类别、配送数量、目的地等信息进行配送，所以，如何利用企业日常经营过程中产生的历史配送信息对库存进行合理的优化配置成为提高商品周转和配送效率的一个重要途径.

在零售行业中，顾客在购买某种商品后往往会再次购买与该商品相关的其他商品，例如在超市中，顾客购买了大米和白面之后，可能会再购买食用油等生活用品，因此，合理的商品布局不仅能够方便顾客选取相关商品，也能促使顾客将某些模糊或潜在的购买需求转换为实际购买行为，从而可以大幅度地提高商品出售率.

同样道理，在物流企业的日常经营过程中涉及到了大量的物资周转，这些物资需要暂存在企业的仓库中，而不同类型商品的配送周期不同，因此，只有优化物流企业的仓储配置才能提高仓储利用率，以及配送产品的周转速度，进而提高企业经济效益.

目前，有关仓储配置的建模与优化问题已经成为研究热点，并取得了一系列的研究成果.例如，文献[1]中采用Petri网对物流仓储系统建模，并利用ShowFlow物流仿真软件对仓储系统进行了仿真分析.文献[2]研究了物联网环境下智能物流仓储系统构建方法.文献[3]对基于库存成本最优化的配送中心选址问题进行了研究，建立了配送系统年总成本最优化模型,并给出配送中心选址方案.文献[4]中基于RFID和遗传算法研究了实时炸药仓储优化问题，文中利用RFID技术实时获取炸药仓库信息，提出了炸药仓库的库位分区策略，通过对炸药仓储的工作特点及要求分析，建立了炸药仓储的优化数学模型，并运用遗传算法求解模型的优化解.

本文采用数据挖掘的方法研究仓储配置优化问题，从企业的历史交易获取企业产品的优化组织与存放方案.在经典的面向关联规则的数据挖掘算法-Apriori算法基础上，利用企业日常经营中的数据，挖掘和分析企业产品之间的内在流动和周转关联关系，进而实现企业产品的仓储优化配置.

1 关联规则与数据挖掘

数据挖掘技术帮助用户从大量的数据库或文件数据中发现并提取出用户感兴趣的数据.基于关联规则的数据信息抽取是一种有效的数据挖掘方法[5-6]，面向关联规则的数据挖掘处理算法从数据记录或者数据对象中获取数据项之间的关联性，而这些关联性预示了数据项之间的数据依赖，因此，依据这些关联性可以从一些数据对象的信息推测和预见未来的一些数据信息.下面介绍几个与关联规则相关的定义，这些定义是进行面向关联规则的数据挖掘的基础.

定义1(关联规则)

对于m个不同项所构成的集合I={i1,i2,i3,…,im}，D为一个事务数据库，具有唯一标示符的D中每个事务T为I中一组项对应的集合，即T⊂I.若X⊂I∧X⊂T,则T包含X.将蕴含式X⟹Y称为关联规则，其中X⊂I∧Y⊂I∧X⊂Y=Ø.

定义2(支持度)

项目集X在事务D中的支持度定义为包含X的事务在D中所占有的百分比，即Support(X/D)=αX/|D|*100%，其中αX为包含X的事务数目.若支持度Support(X)大于给定的最小支持度阈值，则称其为频繁项集，否则称其为非平凡项集.

定义3(置信度)

关联规则X⟹Y是指D中包含有X的事务同时包含Y事务的百分比，记为Confidence=Support(X∪Y)/Support(X)*100%.

定义4(强/弱关联规则)

在进行数据挖掘时给定最小支持度和置信度分别为minsup与minconf，若Support(X⟹Y)>=minsup∧Confidence(X⟹Y)>=minconf，则称X⟹Y强关联规则，否则称其为弱关联规则.

面向关联规则的数据挖掘算法的实现过程主要分为以下两步：①求解频繁项目集，即寻找所有的支持度不小于给定minsup的项目集.②求解关联规则，即在获取的每一个最大频繁项目集中寻找置信度不小于给定minconf的关联规则.

2 基于Apriori算法优化仓储配置

仓储配置的优化需要从大量的历史交易数据中挖掘对货物存储位置有帮助的信息.通常情况下，企业仓库中的不同类型的商品在出货或者配送时存在一定的联系，例如，某些类型的货物通常安排在一起进行配送，所以，这些货品在进行存储时如果安排在相邻的存储位置则可以大幅度提高出货或者配送效率.从第2节的定义中可以得知，关联规则可以刻画两个事务之间的支持度和置信度，因此，基于关联规则的数据挖掘技术非常适合应用到仓储配置的优化过程中.

在面向关联规则的数据挖掘过程中，Apriori算法是一个经典的挖掘算法，该算法通过逐层搜索的方式求解频繁项集，再从这些频繁项集中求解强关联规则.下面首先介绍Apriori算法，然后在该算法的基础上给出仓储配置优化算法.

2.1 Apriori算法

基于“任何频繁项集的所有子集一定是频繁项集”这一属性，Apriori算法引入修剪策略，通过搜索候选项集的方式产生频繁项集，其核心算法描述如算法1所示[7]：

算法1Apriori处理流程.

Apriori(D,Lm)

{L1=FindFreq1_Itemsets(D,minsup);

For(m=2;Lm-1!=;m++)

{Cm=aprior_gen(Lm-1);

For∀xD

{Cx=subset(Cx,x);

For ∀c∈Cxc.count++;}

Lm={c∈Cm| c.count>=minsup};

}

对给定的最小支持度minsup，FindFreq1_Itemsets(D,minsup)遍历一次数据库D，求解所有频繁项目集，Lm为大型的m项目集的集合；aprior_gen()用来产生新的候选集，subset(Cx,t)用来求解Cx中被x所包含的项目集.

2.2 仓储配置优化算法

假设当前有n种货物需要进行存储，分别记为G1,G2,…,Gn，有关这n种货物的配送记录存放在数据库D中，当前具有k个库存位置，现需要求解一个优化的库存配置结构，则算法求解过程如下：

(1)调用Apriori算法，得到m条强关联规则，记为GZi，(1<=i<=m)，其中规则的形式为:Gp⟹Gq,spq=v1i,cpq=v2i，其中1<=p,q<=n,spq,cpq分别为Gp⟹Gq的支持度和置信度.

(2)令P(Gp,Gq)=(cpq+cqp)/2，则P(Gp,Gq)表示货品Gp与Gq在一起存放的概率，令表示Gp与Gq存放距离.

(3)利用K-中心点算法将G1,G2,…,Gn聚类为k个簇，则每个簇中的货品对应一个库存位置.K-中心点算法[8-9]最初在给定的数据集合中随机选择k个对象作为最终形成的k个簇的中心点，再按照数据对象之间的距离推算公式计算剩余数据对象到中心点之间的距离，并按照距离的大小值将这些数据对象分配给k个中心点，从而得到最初的k个簇.

然后再次随机选取一个不是中心点的数据对象，计算这个数据对象代替其他某个数据对象的总代价，如果代价为负，则用该数据对象替换原有数据对象，否则不予以替换.循环执行上面的过程，直至得到的k个簇中的中心点不再变化为止，下面给出仓储优化配置算法的类C描述.

算法2仓储优化配置算法

Optimize_Storage(Goods Gn,int k){

Apriori(D,Lm);

For i=1 to k

{ select g∈Gn randomly;gc[i].centroid=g;}

Let CC={ gc[i].centroid }, GC={gc[i]}, 1<=i<=k;

Flag=True;

While (flag){

{ minSim=1, maxSim=0;

for each good g {Gn-CC}

{for i=1 to k

{TempSim=Distance (g, gc[i].centroid);

if (TempSim< minSim) { minSim=TempSim; t=i;} }

gc[t].g=gc[t].g∪{r};

if (TempSim>gc[t].maxsim) gc[t].maxsim=TempSim;

gc[t].num++;}

Select an gp∈{Gn-CC} randomly;

for i=1 to k

{ for each g rc[i].g

{ TotalSim1= Distance (g,gc[i].centroid); TotalSim2= Distance (g, gp);}

Cost=TotalSim1-TotalSim2;

if (Cost<0) {gc[i].centroid= gp; flag=true; break;}

else Flag=flase; }

}

Return GC;

}

3 应用举例

某蔬菜种植中心种植了若干种蔬菜，该中心建有物流配送中心，在进行蔬菜配送前需要将上述蔬菜采摘后放入仓库中存放.仓库建有4个存储分库，现有若干条历史交易记录，现要求以历史交易数据为数据源进行分析，求解一个优化的仓库配置方案.

表1为交易数据表，为了叙述简单，仅仅选取其中20条记录，蔬菜的名称使用符号来替代，分别为：黄瓜(A1)、西红柿(A2)、辣椒(A3)、萝卜(A4)、白菜(A5)、茄子(A6)、西兰花(A7)、蘑菇(A8)、胶瓜(A9)、甘蓝(A10)、韭菜(A11)、菠菜(A12).

表1 历史交易数据表

采用上述算法求解的各项关联规则(Ai⟹Aj，即购买蔬菜Ai同时购买了Aj)之间的置信度如表2所示，表中的数据单位为百分比.

表2 置信度数据表

在表2的基础上，采取公式Distance(Gp,Gq)=100*(1-P(Gp,Gq))计算两种蔬菜之间的购买距离，然后采用K-中心点聚类算法，将聚类的个数设置为4，编程求解聚类结果为：{A3,A8,A10,A5},{A1,A7,A9,A2},{A4,A6}和{A11,A12}.由上述聚类结果可以得知4个仓库分别存放{辣椒、蘑菇、甘蓝、白菜}，{黄瓜、西兰花、胶瓜、西红柿}，{萝卜、茄子}，{韭菜、菠菜}.

4 结束语

本文通过对企业库存的历史交易记录进行信息抽取，利用面向关联规则的数据挖掘方法获取库存商品之间的关联关系，计算商品之间的置信度，然后将置信度转化为存储距离，并利用K-中心点算法将存储商品进行聚类，从而得出了优化后的仓储组织结构.

文中给出了相关算法的求解过程及其类C语言描述，并将该算法应用到一个具体的实例，说明如何对仓储进行优化，下一步的研究工作是由K-中心点算法的数据结构，构建更加合理和高效的商品购买距离计算公式，从而进一步优化所求得的仓储配置方案.