基于图论的聚类算法在订单分批问题中的应用

吴天行，郭 键

（北京物资学院，北京 101149）

基于图论的聚类算法在订单分批问题中的应用

吴天行，郭 键

（北京物资学院，北京 101149）

首先阐述了传统的基于相似巷道的订单分批模型的原理，然后根据图论和聚类分析的相关原理，建立了基于图论的聚类算法订单分批模型，最后通过一个实际的算例，以最小拣选路径为目标函数，分别对未分批订单、基于巷道相似性分批的订单和基于图论的聚类算法分批的订单结果进行了比较，从而论证了该算法的有效性。

拣选作业；订单分批；图论；聚类分析

1 引言

物流拣选作业是按照客户的需求，将一种或多种存储货物取出重新组合整理并安放在特定位置的一系列的作业活动，该活动涵盖了拆包和再次包装。合理的拣选作业可以极大地提高物流活动的运作效率[1]。在拣选作业中，订单分批策略一直以来都备受研究者的关注。国外学者Van den berg就提出进行订单分批对降低拣选路径长度和人力物力的消耗具有重要作用。而国内学者李诗珍也认为，对减少拣货作业总时间影响最大的活动就是分批策略[2]。

在订单分批问题中，采用聚类分析的方法对订单进行分批是目前比较常用的方法，该方法的主要原理是通过一系列的相关准则，将符合这一准则的相关订单合并成为一类订单，其主要目的是减小订单拣选的总路径，提高订单拣选效率，从而降低总拣选成本。

订单分批中常以相似度作为分批准则，订单相似度也就是订单之间的相似性。相似度主要划分为两大类，即特征向量和相似系数。在特征向量中，常作为划分依据的主要有储位特征向量和坐标特征向量。而在相似系数中，常用的划分依据主要有储位相似系数、面积相似系数和巷道相似系数[3]。目前应用最为广泛的就是基于巷道相似系数的订单分批策略。

2 基于巷道相似系数的订单分批策略

利用聚类分析法进行订单分批作业的核心就是确定两个订单之间的相似程度，根据相似程度来判断是否将这两个订单合成一批进行拣选。订单间的巷道相似度是进行订单是否合成一批常用的指标，即依据两个订单所具有的相同巷道数的多少进行度量。

两个订单间所拥有共同巷道数比例的公式为:

其中Sij为巷道相似系数，Ci和Cj表示订单i和j中商品分布的巷道集合。

根据上述巷道相似系数的公式，可以建立基于聚类算法的订单分批数学模型。设：

式（2）是在形成批量的订单中, 同一批中的两两订单相似系数之和最大。式（3）表示一个订单只允许在一批中完成。式（4）表示只有在第j批订单已经存在的情况下，订单i才可以分批到j批中[4]。式（5）、式（6）表示每批订单所含有的品类数总的重量和容积不可以超过拣货车的载重量和容积。

该算法的本质仍然属于节约算法，核心依然是确定最小的订单拣选路径，从而提高物流拣选效率。不同点是分批时的依据由原本的最大节约量改为巷道的最大相似系数。该算法的基本思想简述如下：

（1）计算出所有的两两订单间的相似系数Sij。

（2）将计算出的相似系数按照从大到小的顺序排列。

（3）将最大的相似系数的订单合成为一批，如果有多个相似系数相同的订单，则选择订单中品类最多的订单合成为一批，并且判断是否满足约束条件，如不满足则转至步骤（5）。

（4）将已经合成的订单作为新产生的订单，对新的订单重新计算巷道相似系数进行分批。

（5）将最后仍没有分批的订单作为单独订单自成一批，停止。

3 基于图论的订单分批策略

3.1 图论的相关概念

图论是一门应用广泛且内容丰富的学科，该学科可以追溯至柯尼斯堡七桥问题[5]。图论中的图是由多个给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某些特殊关系，用点代表事物，用连接两点的线表示相应两个事物间具有的这种关系[6]。

图的数学含义是指一个有序的三元组(V(G),E(G), ψG)，其中V(G)为非空的顶点集，E(G)为不与V(G)相交的边集，而ψG是关联函数，使得G的每一条边都对应于G的无序顶点对uv(未必互异)，简记为图G=(V(G),E(G))或G=(V,E)[7]。

各结点之间存在的相近关系可以用K近邻有向图来加以描述。K近邻有向图是指有向图G=（V，E），结合点集为V={v1，v2,…,vn}，边集合为E={e1,e2,…,en}，ei=＜vp, vq＞，vp，vq∈V，i=1，2，…，m，其中ei存在当且仅当vp是vq的近邻，ei的方向为vp起始点指向vq的终止点。

在K近邻有向图G=（V，E）中，如果对V中的任意两个结点vp和vq同时存在边epq=＜vp,vq＞和eqp=＜vq,vp＞，即为结点vq和vp互为近邻，则称vq和vp为K互邻居。

K聚类图是为了区分K互邻居和K非互邻居而建立起来的，具体含义是指图G，=(V，E，)，结点集合为V={v1，v2，…,vn}，边集合为∈V，i=1，2，…，m，其中e，i存在当且仅当vp是vq的近邻。通过以上的定义可知K聚类图是一个无方向的图，在K聚类图中所有连同的子图都是K互邻居。

3.2 基于图论的订单分批算法

基于图论的订单分批算法又名N-M算法，该算法的主要原理是首先分析数据中的对象,根据分析寻找所有对象的K近邻，根据K近邻相互关联性构造K近邻有向图，最后再通过K近邻有向图中的K互邻居关系建立K聚类图，发现数据中的自然聚类，从而对订单进行分批[8]。该算法的具体执行步骤如下：

（1）建立K近邻有向图。假设需要分批的订单里包含n个商品品项，各个商品品项可以表示为如下所示的商品各品项之间的距离矩阵D。

其中d(i,j)为品项i和品项j之间的距离，满足d(i,j)≥0，d(i,j)=d(j,i)且d(i,i)=0。

得到品项的距离矩阵之后对距离矩阵进行搜索，基于搜索结果建立K近邻有向图。同时将K近邻有向图表示为邻接矩阵的形式，矩阵的元素可以表示为A_G(i, j)。

（2）建立K聚类图。K聚类图是由多个K互邻居的点对构成的，K互邻居的点对相互连结就形成了K互邻居关系子图，当子图中相互连结的点仅有一个时，该子图就变为孤立点，利用K聚类图可以将数据很好的进行聚类[9]。为了方便计算与存储，可以将K聚类图表示为邻接矩阵的形式，并且记为A_CG，A_CG的元素可以表示为A_CG(i,j)。邻接矩阵的构造如下所示：

（3）遍历K聚类图，形成聚类。对K聚类图进行遍历，在进行遍历时应使用广度优先搜索算法进行遍历，利用广度优先搜索算法的基本步骤如下所示：

①∀v∈V(G)标号l(v)=0，令l=0。

②当所有标号为l时，与顶点u相关联的边的端点都已经标号时，则停止；否则把与顶点u相关联的边的端点编号编为l+1，并记录这些边，令l=l+1，转至②。

（4）根据聚类的结果按照分批规则进行分批。在对K聚类图进行遍历后，可以自然形成关于订单商品品项的自然聚类，根据实际问题可以按照如下的分批规则将订单进行适当的分批与调整，使得其符合实际的订单分批要求。

③将已合成的订单批次剔除原订单后，对剩余未分批的订单重新进行聚类，直至分批完成。

4 算例验证

4.1 算例的基本信息

为了验证基于图论的订单分批算法的科学性与有效性，下面将以一个实际的订单分批的例子对该算法进行验证。该订单分批的例子将会分别使用未分批的订单方法、基于相似性的订单分批算法和基于图论的订单分批算法对订单进行分批，并对分批结果进行比较和验证。

为了便于比较和分析，订单分批的例子取自于文献[10]中的算例，其仓库货物平面图如图1所示。

图1 仓库货物平面图

由图1可知该仓库是一个由15排货架和7条巷道组成的，左下角是仓库的出入口。现在已知每一排货架有15个存储单位，每一个单位的长度和宽度都为1，巷道的宽度为1。

现有7个需要拣取的订单，详细数据见表1。

表1 拣选订单信息表

订单拣选的要求是在满足拣选车重量和体积的要求下，如何使拣选的订单总距离最小。

4.2 未分批的订单拣选距离

本次算例验证的拣货路径策略采取混合策略，即通过选取穿越策略、返回策略、中点策略、最大间隙策略等使拣货路径最短[11]。不对订单进行分批只需要将备选的7个订单的总的路程计算出来，并对每个订单体积和重量是否符合拣选车的要求进行验证，具体过程见表2。

表2 未分批订单拣选距离表

4.3 基于巷道相似性的订单分批拣选距离

利用巷道相似系数对订单进行分批，首先要使用式（1）得到巷道的相似系数，经过计算可以得到巷道相似系数见表3。

表3 巷道相似系数表

根据表3可知，将订单4与订单6合成一批作为新的订单，其余的再次计算巷道相似性。由此可以得到新的巷道系数见表4。

表4 新的巷道系数表

由表4可知，应该将订单3与订单5合成为一批，其余的订单再次计算巷道的相似系数。

继续按照上述的方式进行计算，最后可以得到最终的订单分批结果，见表5。

表5 最终订单分批表

根据已经得到的订单分批可以计算出基于巷道相似系数的订单分批的拣选距离为81+77+98+85=341。

4.4 基于图论的订单分批拣选距离

使用基于图论的订单分批算法首先应该根据式（8）计算出各订单内商品品项的距离矩阵D1，为了方便说明与计算，现在将原图转化为按照商品品项标号排序的仓库平面图，如图2所示。

图2 商品品项仓库布局平面图

由图2可知，需要分批的7个订单一共有25个商品品项，这些商品分别由1到25分别标号，以此计算出这7个订单商品品项的距离矩阵D1。

根据距离矩阵D1以及式（9）以及式（10），可以得到K聚类图的邻接矩阵，这里由于点分布是随机的，所以K的取值为5。由此可以得到K=5时的邻接矩阵D2。

根据得到的K聚类图的邻接矩阵进行遍历，遍历的方法采用广度优先搜索算法，并利用MATLAB软件进行求解。

广度优先搜索算法求解的结果见表6。

表6 求解结果表

根据求解结果可以将表6转化为按照订单分批的形式，见表7。

表7 原始订单分批

由于实际情况订单不允许被拆分，因此需要根据订单分批规则重新进行分批。根据订单分批规则①可以将订单3、订单6和订单7分成一批，新分批的订单编号位1。根据分批规则②可以将订单1与订单2合为一批，新分批的订单编号为2。其余未分批的订单有订单4与订单5，将其重新使用N-M算法进行分批，可以得到表8未分批订单的商品距离。

表8 未分批订单商品距离

根据表8可以得到K聚类图邻接矩阵D3。

对矩阵D3使用广度优先搜索算法，当K值为3时，可以得到商品品项的分批，即为第1批：1；第2批：2,3,4；第3批：5。根据以上信息可以得到订单4与订单5以商品品项为单位的分批，见表9。

表9 订单4与订单5分批情况

根据实际情况订单不允许被拆分，因此根据订单分批规则可以将订单4与订单5合为一批订单。

由此可以得到最后的订单分批结果见表10。

表10 订单分批结果

根据订单分批的结果可以计算出订单分批后的总路程为107+125+52=284。

4.5 结论及分析

根据以上的计算可以得到利用N-M算法进行订单分批的结果最优为284。其次是使用巷道相似性的分批算法为341，最差的是不对订单进行分批的结果为471。因此可以清楚的看到，对订单进行分批对于拣选距离的优化有着重要的作用，而在订单分批方法中，基于图论的订单分批算法相较于传统的基于巷道相似性的订单分批算法有着一定的优越性，在实际的订单分批中应当考虑使用该种算法。

由两种订单分批算法的原理分析可以得知，基于巷道相似性的订单分批算法是从整体上来进行订单分批的，该算法是根据相同的巷道内拣选距离一般较短这一原理进行分批，而基于图论的订单分批算法是从每一个订单品项的角度出发寻找最短路径，该算法是直接求出订单商品品项之间的最短拣选路径再对订单进行分批的。由此来看基于图论的订单分批方法可以更精确的找到订单之间的最短路径，从而更有效地进行订单分批。

由于N-M算法引入了K互邻居和K聚类图的概念，根据K互邻居确定的订单分批不需要依据其他的划分批次的方法，可以减少因为划分概念不清造成的聚类错误，同时计算中的K值也更适合使用者从底层到高层进行参数的设定。

[1]徐强.基于电子标签的配送中心分拣系统的研究与设计[D].武汉:武汉理工大学，2008.

[2]曹雪丽.人工拣选作业中订单分批处理研究综述[J].物流技术,2012,(9).

[3]王雪飞.基于分层加权的多边形图形匹配[J].工程图学学报, 2002,(2).

[4]李诗珍.配送中心拣货作业优化设计与控制研究[D].成都:西南交通大学,2008.

[5]刘斌.有源网络“有向根树法”的研究及应用[D].天津:河北工业大学,2007.

[6]任媛.关于图控制理论的若干问题研究[D].通辽:内蒙古民族大学,2013.

[7]张新.图论在集合论中的应用[D].济南:山东大学,2005.

[8]应德全.一种基于图论的聚类算法 NeiMu[J].计算机工程与应用,2009,(3).

[9]应晓敏.面向Internet个性化服务的用户建模技术研究[D].长沙:国防科学技术大学,2003.

[10]李诗珍.基于聚类分析的订单分批拣货模型及启发式算法[J].统计与决策,2008,(12).

[11]杨华荣.配送中心拣货路径信息采集与处理研究[D].长沙:中南大学,2011.

Application of Graph Theory Based Clustering Algorithm in Order Batching Problem

Wu Tianxing,Guo Jian
(Beijing Wuzi University,Beijing 101149,China)

In this paper,we first elaborated on the working principle of the order batching model based on the traditional channel similarity principle,then according to the graph theory and clustering analysis,built the order batching model using the graph theory based clustering algorithm,and at the end,through an empirical numerical example,compared the order batching result based on channel similarity and based on the clustering algorithm,thus demonstrating the validity of the algorithm developed in this paper.

picking activity;ordering batching;graph theory;clustering analysis

F224;F252.21

A

1005-152X(2017)08-0112-05

2017-07-03

北京市属高等学校青年拔尖人才培育计划项目（CIT&TCD201504052）；北京物资学院青年运河学者资助项目；北京物资学院国家级科研项目培训基金项目

吴天行（1990-），男，河北人，硕士研究生，研究方向：算法与模型优化。

doi∶10.3969/j.issn.1005-152X.2017.08.026