应用聚类分析实现物流配送网络的优化

开篇：润墨网以专业的文秘视角，为您筛选了一篇应用聚类分析实现物流配送网络的优化范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

[摘 要] 研究了物流配送网络的优化问题，通过对配送货物采用聚类预处理，增加了系统处理实际问题的规模，提高了配送网络的优化性能。测试结果表明该方法有效地降低了配送的成本，提高了效率。

[关键词] 物流 配送网络 聚类分析

一、引言

配送是物流系统中一个直接与消费者相连的重要环节，优化配送网络，进行合理的物流配送是实现运输规模经济、节省运输费用的重要手段。物流配送网络实际上由多个不同的网络组成，每个网络都服务于特定的目标，但每个网路又不是孤立进行运作的。确切地说，在不同的运输网络之间存在极大的重叠和冗余。因此通过配送网络的优化，消除这些冗余是降低配送成本的有效手段。聚类分析又称群分析，它是研究(样品或指标)分类问题的一种统计分析方法。采用聚类分析的方法，可极大地提高优化的性能，增加所处理业务的规模。

二、聚类基本理论

“物以类聚，人以群分”，在自然科学和社会科学中，存在着大量的分类问题。所谓类，通俗地说，就是指相似元素的集合。聚类分析起源于分类学，随着人类科学技术的发展，对分类的要求越来越高，仅凭经验和专业知识难以确切地进行分类，于是数学工具逐渐地被引用到了分类学中，形成了数值分类学，之后又将多元分析的技术引入到数值分类学形成了聚类分析。

假设一个要进行聚类分析的数据集包括n个对象，这些对象可以是人、房屋、货物等。基于内存的聚类算法通常都采用差异矩阵[1]的数据结构。

差异矩阵是一个对象-对象结构。它存放所有n个对象彼此之间所形成的差异。它一般采用n×n矩阵表示，如式(1)所示。

其中，d(i, j)表示对象i和对象j之间的差异(或不相似性程度)。通常d(i, j)为一个非负数，当对象i和对象j非常相似或彼此“接近”时，该值接近0，该数值越大，就表示对象i和对象j越不相似。由于有d(i,j) = d(j,i)且d(i, i) = 0，因此就有式（1)所示的矩阵。

所采用的测量单位可能会对聚类分析产生影响。例如：将测量单位(对于高度属性)从英尺变为米，或(对于重量属性)从英磅变为千克，都会导致不同的聚类结果。通常采用一个较小的单位表示一个属性会使得属性的取值范围变大，因此对聚类结构就有较大的影响。为帮助避免对属性测量单位的依赖，就需对数据进行标准化。所谓标准化测量就是给所有属性相同的权值。这一做法在没有任何背景知识的情况下是非常有用的。而在一些应用中，用户会有意识地赋予某些属性更大权值以突出其重要性。例如:在对货物进行聚类分析时，可能就会给时间属性赋予更大的权值。

为了实现标准化测量，一种方法就是将初始侧量值转换为单位变量。给定一个属性(变量)f，可以利用以下计算公式对其进行标准化：

(1)计算绝对偏差均值S

其中，x1f，x2f，…… xnf是变量f的n个测量值，mf为变量f的均值，也就是

(2)计算标准化测量(Z -分值）

其中，绝对偏差均值sf要比标准差σf更为鲁棒(对含有噪声数据而言)。在计算绝对偏差均值时，对均值的偏差|xnf-mf|没有进行平方运算，因此异常数据作用被降低。

一种有效的聚类分析计算方法是基于密度的算法(Density-based Methods），它与其它方法的一个根本区别是:它基于密度而非基于各种各样的距离。这样就能克服基于距离的算法只能发现“类圆形”聚类的缺点。这个方法的指导思想就是:只要一个区域中点的密度大过某个阈值，就把它加到与之相近的聚类中去。代表算法有:OBSCAN算法、OPTICS算法、OENCLUE算法等。

三、配送网络的优化

配送网络的底层结构由下述五个主要元素构成:

1.Facility(设施)

配送网络中的站点(一般是物理的)。在网络中，站点代表了货物集中或分发的地点。例如，在邮政配送网中，它们可以是加工及分发站，调度中心，航空邮件中心和散件中心。

2.Delivery(一次投递的货物)

Facility之间配送的项目。在网络中，Delivery代表了在特定时间窗(即，从货物准备好到要求送达目的站之间的时间段)之内、从起点到终点、有一定体积和重量、要运送的货物。不同类型的Delivery可能代表了，从起点到终点、有不同的服务标准的货物(例如，从北京到上海的特快专递)。

Delivery按是否可分开配送可以分成可分Delivery和不可分Delivery。可分的Delivery是可以被分成不同部分进行配送的。相反，不可分Delivery不能分成不同部分进行配送。

3.Batch(班次)

配送网络中时间固定，经过的站点固定的运送货物的路线。一个Batch的定义包括Batch的各个方面:运输工具的容量或载重能力，Batch的类型(航空，公路，铁路等)，Batch的工作日(一周里面哪天或哪些天有出发的安排)，到达和离开每个中间站点的时间(用时分秒表示，不牵扯日期)，签订一个班次的费用和提前解除班次合约的费用。

4.Leg(班次的一段)

Leg连接相邻的两个Facility，Batch由一系列Leg组成。Leg的定义包括：从属的Batch，Leg起点，Leg终点，离开Leg起点和到达Leg终点的时刻(用时分秒表示，不牵扯日期)，Leg开始离Batch开始的天数，容量或载重能力，可变运输成本(单位体积或重量的运输成本)等属性。当然，在一个Batch中，前一个Leg的终点要和后一个Leg的起点相同。

5.TriP(行程)

真正意义上用于移动货物的途径(路线)。Trip的构成形式是多样的，我们既可以把一个Batch看成是一个Trip来配送Delivery，也可以取一个Batch的若干Leg作为配送Delivery的Trip，还能使用多个Batch的Leg作为Trip，只要它能在规定时间内把Delivery从起点运送到终点。Trip是为了方便建模而构建的一个虚拟的概念，配送网络优化系统运行的时候，先使用搜索技术把每个Delivery的所有可行配选Trip找出来，再进行建模。

费用由Leg可变费用(可变运输费用)，Trip迟到惩罚费用，Batch固定费用和Batch提前解约费用构成。优化的目标就是满足“指派约束”和“容量和载重能力约束”的情况下，使总费用最小。

由于物流配送网络的Facility既能作为起点，也能作为终点，因此每个Facility可能既集中货物也分发货物。相应地，一个Batch可能同时需要搜集和分发货物。假设将要优化的物流配送网络已经签订了一些班次。即优化的目标是判断哪些班次继续留用，那些班次应该提前解除合同。

在模型优化之前，必须把原始数据转化成标准的数据格式输入模型。这个步骤包含分析数据和清理数据;依照特定的内容、结构和格式的要求准备好输入数据文件。在预处理时，对数据进行彻底的检查。数据的错误、矛盾之处都得到更正。预处理过程中，最重要的一步就是进行聚类预处理。

在货物数量庞大的配送网络中，如果把每单货物都看成一个Delivery(即把每单货物都当成一个Delivery变量加入模型中)，模型的求解过程将耗费相当长的时间。所以在模型进行求解之前，我们可以使用一些成熟的聚类分析方法，把权重属性值比较接近的货物聚合成一个Delivery，从而减少模型的计算复杂度。模型的解在接近最优解的情况下，能极大地缩短计算时间。所谓权重属性，就是用来权衡货物是否能合成一个Delivery所参考的重要的属性。

在实际中，一种较好的方法是采用基于密度的DBSCAN(Density-based Spatial Clustering of Application with Noise)聚类算法对货物进行聚类。该算法通过不断生长出足够高的密度区域来进行聚类，它能从含有噪声的空间数据库中发现任意形状的聚类。

由于要把时间和类型都类似的货物进行聚类，所以选用货物的类型、货物就绪时间和要求送达时间等属性为聚类的权重属性。属性和算法都确定好了之后，可编写Java程序实现DBSCAN聚类算法。输入不同的货物数，输出聚合好的Delivery。通过每个Delivery可以查询到每个原始的货物。见表1：

使用Java程序编制配送网络的优化系统，系统主要由以下几个部分构成：搜索行程、构建CPLEX模型、使用CPLEX进行优化。将表1的数据输入该优化系统，得到测试结果见表2：

在近似于实际问题规模(120个站点，300个班次，502段，10000个配送货单)的时候，可以看出，优化系统还是可在一分钟左右完成计算。

四、结论

通过比较测试结果可以发现，使用优化系统的总花费要比传统方法少20%，极大地降低了配送的成本。证明通过聚类分析对配送货物进行预处理可有效提高配送网络的优化性能。

参考文献:

[1]Ian.H.Wjtten，EibeFrank，Data Mining：Pratical Machine Learning Tools and Techniques.Seeond Edition[M]. Elsevier Ine.2005

[2]韩家炜 堪博著 范 明 孟小峰 译:数据挖掘：概念与技术(原书第二版)[M].机械 工业出版社.2007.03

[3]施建年:物流配送[M].北京:人民交通出版社,2003