基于K—Means聚类算法的配送中心物流成本分析

摘要：文章提出了一种基于聚类算法的配送中心选址问题。针对复杂的配送中心选址问题，利用聚类算法中的K—means算法解决配送中心选址问题，该算法的实证中解决了125个配送点的配送中心寻优问题，而且在选择配送中心时充分考虑客户的需求和各地实际情况（各地的消费能力、地理位置以及交通等），通过定量分析和定性分析结合的方式，建立起了二级配送网络。实证结果表明，该配送网络具有实际应用价值并具有良好的经济效果。

关键词：聚类算法；物流成本；配送中心

中图分类号：F252.14 文献标识码：A

配送中心作为供应链的关键组成部分，一直受到企业界和学术界的重视。配送中心对供应链的影响主要来自于两个方面：一是配送中心本身操作效率，二是配送中心地址的选择。对于物流配送中心选址问题，对不同的模型要求，传统的研究方法主要有整数规划法、图上作业法[1]、重心法[2]、鲍莫尔一沃尔夫法（Baumol—Wolfe）[3]、运输规划法、仿真方法等。前人已经提出许多基于精确值的选址方法，利用数学规划方法[4，5]确定最理想的地址， Tompkins和White[6]用偏好理论将所有主观因素两两比较从而为主观因素赋予了权重值。Spohrer和Kmak[7]提出了一种权重因素分析方法将定量的数据和定性的评价值结合在一起，用以从多个备选项中选择合适的地址。Stevenson[8]提出了一种选择最好地址的价值量分析方法。国内学者对于配送中心选址研究也取得了一定的成就，提出了一些配送中心选址的新方法。西南交通大学的刘海燕、李宗平、叶怀珍[9]的论文《物流配送中心选址模型》利用的是混合整数规划法，长沙交通学院的陈曦、傅明[10]的论文《GIS环境下的物流配送中心选址模型与算法研究》采用的是基本遗传算法，张培林，魏巧云[11]的论文《物流配送中心选址模型及其启发式算法》中采用的是启发式方法，马正元，黄斌[12]的论文《Hopfield人工神经网络在物流配送中心选址优化中的应用》中应用的是神经网络，此外，还有的采用模拟退火算法，模糊控制方法等。

1 K—means聚类算法原理

2 模型建立

本章采用基于K—means聚类的基本原理，划分一级配送中心及其区域，需要根据需求点的地理位置进行聚类，这样的目的是为了确定销售区域后，在每个销售区域建立相应的配送中心，取代点对点配送，从而达到降低配送成本的目的。

5 实 证

国内某汽车制造企业（为方便计算，生产和发运地假设为哈尔滨市）的销售物流业务，旺季情况：每年11月至次年2月为旺季运输，是正常运输运力需求的200%；每年5～7月为淡季运输，是正常运输运力需求的50%；其他为正常运输；运费标准：每辆商品车的运费为1 200元，即1 200元/辆；订单周期：假设为2周一次。企业生产ABCD四种车型，只有A车型不能通过铁路运输方式，其他都可以通过公路、铁路、水路三种方式运输。具体数据如下：

（1）所选城市分布图

所选城市分布的原则是选择具有代表性的二级城市，这些二级城市能覆盖全省且消费能力较高。从全国所有省市中选取了125个城市作为二级城市，由图1可以看出，这些城市基本上能覆盖整个中国。

根据以上的求解步骤，采用matlab编程对模型求解，求解结果表明当选择配送中心个数为17个的时候，所得到的总的运输距离最小，整个配送距离如图2所示，由图可知该求解步骤可以很好地解决K—means聚类方法中的初始聚类中心个数难以确定的缺点，通过变化初始聚类中心的个数，可以得到不同聚类中心个数下的配送里程，从中找出一个最优的配送方案。

（2）物流成本计算

仓储成本假设[15]：计算仓库面积=车辆占地面积×宽裕系数，本问题中宽裕系数取1.2；人员配备：每100平方米配备一个人员，其工资水平假定每人年薪2万元；仓库维护费用：每平方米年维护费用为15元；保险费用：仓库存货价值

×0.2%；汽车损失费（仓储导致的汽车价值损失）：仓库存货价值×0.3%。

运输成本假定：汽油费用：卡车每公里汽油费1.1元；汽车修理费：运输专用汽车价值的8%；汽车保险费：运输中车辆的价值×0.3%；汽车折旧费：年折旧率10%；司机费用：每车配备两司机，其工资水平每个司机年薪2.5万元。

按照上述条件计算后的点对点的运输方式成本：

327 307 222元；按照优化后的配送中心配送方式的运输成本：235 030 995元；成本节约28.19%，可知，该配送方案经济可行。

6 对基于K—means算法优化过程的深入探讨

在优化的过程中，由于初始的中心点是随机生成的，这样在聚类的过程中就有可能使聚类的结果受到初始随机选定的中心的影响而过早地收敛于次优解。所以针对这个问题在本文中通过让程序迭代足够多次的方法来减小这方面的误差，如图4所示，这是当聚类数为17时的求解过程跟踪曲线，从中可以看到，在迭代的过程中解的大小有着随机分布的特征，但是当迭代足够多的次数时，就可以找到一个相当最优的解（此算例在第959次迭代时找到相对最优解），这也说明本文中所使用的方法在实际中是有效的，而且与遗传算法等相比相对经济了一些。

7 结 论

（1）通过以上成本计算可知，该方法是切实可行的并且能节约成本；

（2）和传统的配送中心选址问题相比，将智能算法引入可以更好地解决节点较多的配送中心选址问题；

（3）在采用聚类算法的过程中，首先通过配送距离最短的寻优方法得到配送中心个数，然后再对配送中心进行区域划分，更好地解决了K—means算法不能初始聚类中心个数问题；

（4）当然，该算法存在纬度问题，当问题随着配送中心个数增多是，其时间复杂度和空间复杂度呈指数级增长。

参考文献：

[1] 杨海荣. 现代物流系统与管理[M]. 北京：北京邮电大学出版社，2003：1—81.