刘旺盛, 马国旺, 江雨瑶, 曾艳

(集美大学航海学院， 厦门 361021)

随着电子商务产业的兴起与企业发展的需要，现代仓库由传统的少品种小批次的拣选向大批次多品种拣选发展，这种变化使企业对货物周转的需求愈来愈高，因此，传统少出/入口仓库布局很难满足企业实际生产活动的需要，而多出/入口仓库能够有效地提高作业拣选速度、减少单一出/入口工作量等优点，成为更多企业的选择。

在仓储作业中，拣选作业成本占仓储总运营成本的65%以上。合理的货位指派规则在降低拣选距离的同时，更能显著地提高人力效率从而降低企业成本。因此，探究多出/入口仓库的环境下货位指派策略具有重要的实践意义。

货位优化问题被证明是 NP(nondeterministic polynomially)难题，早期相关问题研究考虑条件大多较为单一。近年来，随着大数据技术的提出以及数据挖掘的应用[1-2]，货位优化问题的研究从基于货品频率、货品类别与货位关系的研究转向从历史订单中发掘货品之间关联度、货品属性与仓库实际相结合的研究。Lee[3]最早于1992年提出货品之间的关联性的概念，他认为货品关联度可表示为货品同时出现在一张订单上的频率。而后,许多学者在考虑关联度的基础上,不断地拓展与延伸，采用不同方法对货位优化问题开展研究。

部分学者尝试将货品相关性与其他因素考虑起来构建货品优化模型，如Qiu 等[4]基于货品关联度，根据实际优化情况设计了一种基于耗时规则的货位编号规则。Ning等[5]同样在考虑货品相关性的基础上，将货架稳定性、交货时间等因素纳入模型构建。Yang 等[6]针对医药物流中心布局不合理导致效率低下的问题，提出了品类间和品类内两阶段优化方法。Wu 等[7]结合预测订单请求，采用货品相关度构建了一个多目标优化模型来解决仓库空间分配问题。Yang等[8]考虑了货架稳定性、货品相关性构建模型。除此之外，在模型求解方面， Wang等[9]针对货架稳定性、货品相关性等因素构建模型，并采用改进遗传算法进行求解。周亚云等[10]采用谱聚类算法对货品关联规则聚类问题进行求解。

不同仓库布局适合的货位优化方法也不一样。从以往研究来看，大多数学者均以单一出入口仓库为研究对象，而目前仓库的流动性高，大多数仓库为了方便货物的进出，设计为多出入口、一边进一边出模式，现有的货位优化方法显然不适用。因此，现针对这种仓库布局提出了以相关性进行聚类的货位优化策略。该策略基于峰值聚类算法以货品关联度最大为优化目标对货品进行关联聚类，并根据多出/入口仓库的实际情况对货位布局进行优化与调整。最后，通过实例数据与企业现行随机存储策略进行对比，验证本文方法的有效性与稳健性。

1 多出/入口仓库简介

多出/入口仓库布局如图1所示，有X排货架，每个货架上有多个储位可供存储。每个入口对应一个出口，两者是一一对应的，称为一个组对，一共有多少这样的组对，称为出/入口组对数。每当订单下达时，拣选员需要按照订单所列货品进行判断，根据订单上首位货品所在巷道对应的入口进入，然后按照订单货品顺序依次拣选货品，当订单中所有货品均拣选完毕后，从巷道所属最近出口离开。

图1 多出/入口仓库平面布局例图Fig.1 Multi-exit/entrance warehouse layout

2 货品优化模型及求解

2.1 模型假设

为了结合实际，突出研究主要问题，现有如下假设。

(1)订单已经完成分拆与合并，拣货员按照订单分拣，每次只拣选一张订单。每个货位只能存储一种货品，且不考虑货品体积、质量、数量的影响。

(2)货品到出/入口的距离为存放货品的中心到出/入口的距离。

(3)拣选路径按照订单所列货品依次拣选，订单上相邻货品拣选路径遵循最短原则，不考虑拥堵情况。

(4)货位数量可以满足所有待优化货品存储需求。

2.2 货位优化模型构建

2.2.1 相似度

本文研究中货品之间关联性是根据不同货品是否同时出现在同一订单中[11]，出现在相同订单内次数越多，其货品之间关联程度越高。两两货品相关程度计算公式为

(1)

式(1)中：i、j为货品编号，i、j∈{1,2,…,m}；Cij为货品i、j之间的关联性指数；Pi为包含货品i的订单数目；Pj为包含货品j的订单数目；Pij为同时包含货品i、j的订单数目。

当Cij=0，表示货品i、j不存在关联性，即订单集中没有订单同时包含货品i、j；当Cij=1，表示两者存在完全关联关系，即订单集中货品i、j总是能够同时被分配到同一个订单中。同时Cij=Cji总存在对称性。且Cij取值范围为[0,1],其值越接近于1，货品i、j被分配到同一个货品聚合类可能性越大。

2.2.2 货品聚类优化模型

一个组对数对应一个货品聚类，令货品聚类数等于出/入口组对数n。为了让分拣员行走距离尽可能短，需要将相关性高的货品尽量聚到一个类，放置在同一个货架群组；相关性低货品分配到不同聚类中，分别放置在不同货架群组，并且将相关度大的货品尽可能靠近放置，因此目标函数为两两货品之间的相关度值乘以距离。

(2)

(3)

(4)

(5)

式(2)中：e为货位编号且e∈{1,2,…,M}；g为聚合类编号且g∈{1,2,…,G}；dij为分配货位后货品i,j之间距离，通常采用曼哈顿距离进行计算。

式(3)表示每种货品只能指派到一个货品聚合类中；式(4)表示每种货品只能指派到一个货位中；式(5)表示决策变量取值约束;Xig为若将货品i指派到聚合类g，则为1，否则为0；Yie为若将货品i指派到货位e，则为1，否则为0。

2.3 模型求解

聚类分析是通过将数据对象集合划分成为不同聚合簇的过程，每个聚合簇内数据间彼此具有相关性[12]。本文将根据目标函数，设计有效地智能聚类算法进行问题求解。首先，从客户历史订单数据入手，挖掘货品之间相关度并求出N维货品相关度矩阵，然后，基于货品相关度矩阵利用多维标度分析算法对矩阵进行数据处理。以出/入口数量作为货品聚类簇数目，并采用密度峰值聚类算法进行聚类并输出聚类结果集，最后基于聚类后结果集求解模型并进行货位分配。

2.3.1 多维标度分析算法

多维标度分析算法是以数据点之间距离为标准，将高纬度坐标投影到低纬度坐标的一种数据处理方法[13]。它与其他数据处理算法最大不同在于，在处理过程中，MDS算法要求数据点之间相对距离(在本文中为货品之间相关度)变化最小。本文中要处理数据是货品相关度矩阵，它与多维空间中距离矩阵在矩阵形式上表现一致，因此，以货品之间的相关度代替传统数据点之间的距离,采用MDS算法对相关度矩阵进行数据处理。该算法基本流程如下。

输出：低维矩阵Z。

(1)对输入订单数据集预处理得到两两货品同时订购矩阵P并生成相关度矩阵W,W∈Rm×m。

(2)构建等效方程Cij=‖zi-zj‖，zi,zj∈Z,Cij∈W。

(3)令B=ZTZ，B∈Rm×m,其中B为降维后样本内积矩阵，求解实对称矩阵B,B=UΛUT。

(4)对矩阵B做特征值分解。

2.3.2 基于峰值聚类下货品关联挖掘算法

在实际中，多出/入口仓库往往具有规模大、存储货品数量多、种类丰富等特点。所以在进行数据处理和分析时需要面对大量数据，而传统聚类算法在求解时往往需要多次循环往复的迭代。本文选取DPC算法进行求解能有效地解决上述问题，同时该算法具有直观发现聚类中心、处理不同形状数据集等优点[14]。

DPC算法基于一种假设[15]：对于一个货品集，聚类中心被一些低局部相关度的货品包围，而且这些低局部相关度货品与其他有高局部相关度货品间相关度值都比较小。这对聚类中心的选取提出两大要求，首先能够成为聚类中心货品具有较大的局部相关度，其次与其他局部相关度较大货品相关性较小。因此，在DPC算法中，主要需要计算局部相关度和相对最小相关度两个变量。

数据对象xi的局部相关度ρi计算公式为

(6)

lc=dis(MP)

(7)

式中：lij为MDS处理后货品之间相关度大小；lc为截断相关度；dis为货品集中所有货品间相关度按照升序排列后相关度序列；M为货品间相关度值的总数目；P为百分比，通常取2%[16]。

相对最小相关度δi，定义为

(8)

即为在局部相关度高于货品i所有货品中，与货品i最小相关度。

计算出所有货品的局部相关度ρi与相对最小相关度δi后，即可根据ρi与δi的关系在决策图中观察出聚类中心和确定聚类簇数。对于某些在决策图中关系不明显，不易观察对象。可通过式(9)将决策值γi进行降序排列，从前往后选取需要聚类中心即可。

γi=ρiδi

(9)

基于DPC算法总流程如下。

输入：低维矩阵Z。

输出：货品聚合类结果集A={a1,a2,…,ag}。

(1)计算矩阵,且令lij=lji,i

(2)确定截断相关度lc。

(3)计算货品集中每个货品ρi与δi。

(4)借助式(9)确定需要聚类中心。

(5)对剩余货品进行聚类操作。

(6)返回最终聚类结果集A。

2.3.3 存储区域优化

在DPC算法聚类结束后，根据生成的聚类结果返回货品聚合类内货品相关性坐标，然后根据类内相关性坐标计算货品聚合类相关性坐标均值Mg,最后计算不同聚合类相关性坐标均值距离dg，并根据距离的大小决定存储区域的分配位置。具体流程如图2所示。

图2 存储区域优化流程图Fig.2 Flow chart of storage area optimization

2.3.4 货位优化模型求解

通过对式(1)计算得出货品相关性矩阵，并以MDS算法对矩阵进行维度处理，再通过DPC算法将相关性高的货品聚成一类，将存储区域与货品聚合类一一匹配，使相关性高的货品尽可能被分配到同一存储区域。模型求解具体流程如图3所示。

图3 模型求解流程图Fig.3 Flow chart of model solving

3 算例求解及结果分析

3.1 算例说明

通过实地调研方式，获得H企业A仓库2018年4—5月订单数据集，其中包括订单编号、货品种类、货品位置等数据。由于企业数据需要保密处理，所以订单编号及货品种类均采用数字替代。A仓库中共有8排货架，对原始订单数据集进行处理清洗后保留2 076张有效订单，包含842种货品。订单数据如表 1所示。

表1 订单数据表Table 1 Table of order data

3.2 货品两两相关性分析

通过Python2.7编程软件对订单隶属数据进行分析根据式(1)计算货品两两相关性表，如表2所示。

表2 货品两两相关性表Table 2 Table of goods correlation

3.3 数据处理

从货品相关性表得出货品相关性矩阵为n维矩阵，聚类算法无法直接进行处理。采用MDS算法对货品相关性矩阵进行处理以获得二维相关性坐标。处理后数据如表3所示。

表3 数据处理表Table 3 Table of data processing

3.4 数据聚类处理

通过MDS算法对货品相关性进行数据处理后，再利用峰值聚类算法进行聚类。本文聚类簇选择根据出/入口数量，H公司A仓库中共有4个出/入口8排货架，因此聚类簇选择应为4。聚类结果如表4所示。

表4 聚类结果表Table 4 Table of clustering results

3.5 基于密度峰值算法下模型求解

3.5.1 货位区域优化

H公司原有货位分配策略为随机策略，想要货品尽可能均匀分配到仓库，达到作业均衡化目的，但在实际应用中与理想效果相差甚远。在原始仓库布局的基础上，不改变货架位置。通过DPC算法依据货品相关性将货品划分为4个聚合类。使高相关性货品聚合类在存储区域位置上尽可能的接近。优化货品存储区域示例图，如图4所示。

图4 优化货品存储区域图Fig.4 Optimized goods storage area map

3.5.2 存储策略比较

根据货品存储区域分配结果，使用Python2.7编程软件基于实例数据分别计算本文存储优化与随机存储这两种储位优化策略下跨区域平均订单拣选距离，结果如表5所示。

表5 基于不同优化策略跨区域平均拣选距离比较表Table 5 Table of average pick distance comparison

跨区域平均拣选距离是指平均一个拣选员拣选不同存储区域需行走路径，通常用总拣选距离除以订单数量。

3.6 灵敏度分析

为了避免实验结果的偶然性，本文模拟生成几个其他规模的算例，计算并比较本文存储优化策略与随机存储优化策略结果，优化存储策略表如表6所示。

由表6可知，跨区域平均拣选距离大小与货品种类数量存在一定关系，因此本文基于密度峰值聚类算法下探究不同货品种类数量与跨区域平均拣选距离关系。并对其进行灵敏度分析，灵敏度分析图如图5所示。

表6 优化策略比较表Table 6 Comparison of optimization strategies

由图5可见货品种类数量与跨区域平均拣选距离存在着正相关性。但随着货品种类数量增加，其跨区域平均拣选距离增长趋于平缓。这与实际情况相符，当货品种类数量增加时，将高相关性的货品聚成一类放在同一存储区域进行存取，能有效减少拣选距离，提高拣选员工作效率。

图5 灵敏度分析图Fig.5 Sensitivity analysis diagram

4 结论

基于物流仓库发展趋势出发，针对多出/入口仓库布局下对货位优化问题进行了研究，分别设计了多维标度分析算法与峰值聚类算法进行聚类分析，然后进行组内和组间货位分配。本文有如下创新之处。

(1)设计了多维标度分析算法可以直接解决企业数据与聚类模型需要数据之间不兼容问题。

(2)采用密度峰值聚类算法，将高相关度货品存放在同一存储区域，减少了拣选员经历巷道数量，提升了仓库作业效率。

(3)根据多出/入口仓库布局情况来确定货品聚类簇数，并根据实际情况进行调整，利用货品相关性来达到订单拣选距离最小目的。

通过实际案例验证，本文策略比随机策略平均优化24.56%。本文设计模型与策略为解决多出/入口仓库货位优化问题提供了有效地决策方法，显著提高了仓库运作效率，降低了企业的仓储运作成本。