张磊1 王璐1 王晋冰1 张杰2 李致远2 林辉轮3
1 贵州省贵阳市烟草物流配送中心 贵州贵阳 550000
2 西南交通大学交通运输与物流学院 四川成都 611756
3 西华大学法学院 四川成都 610036
摘要：本文基于烟草公司卷烟配送问题中一系列大数据相关处理问题：配送对象数量庞大、分布不均匀、客户订单总量大但大小不均，提出了K-means聚类算法，进行配送点区域划分，将复杂的卷烟配送问题转换为传统的车辆路径问题。
关键词：卷烟配送;大数据;K-means聚类算法
ABSTRACT：Based on a series of big data related processing problems in cigarette distribution problems of tobacco companies, such as large number of distribution objects, uneven distribution, and large but uneven size of customer orders, this paper proposes k-means clustering algorithm, divides distribution point regions, and converts complex cigarette distribution problems into traditional vehicle routing problems.
KEYWORDS:cigarette distribution; big data; k-means clustering algorithm
1 引言
客户对应的配送点数目庞大、配送点位置分布不均匀、客户订单大小不同且总量巨大，这些都是烟草公司在烟草配送时面对的问题。随着我国烟草行业业务进一步扩展，诸如此类与大数据处理相关等的问题也会越来越多，如果不能对其进行有效处理，则会产生运力浪费和配送成本过高等问题。对于复杂的烟草公司卷烟配送问题，只有先解决了其中涉及的大数据相关的问题，才能采用传统VRP模型进行卷烟配送路径优化。本文以贵州省烟草公司贵阳市公司为例，首先对贵阳市公司的客户信息进行一系列处理，再对建立的客户对应配送点分布图进行区域划分，最后求得最优配送路径。
2基于大数据的卷烟配送问题描述与算法
2.1问题描述
卷烟配送问题相较于传统的车辆路径问题（VRP），其难点在于：对象信息量、数量巨大且分布不均匀。因此，烟草公司进行卷烟配送时，首先应该对客户信息进行处理，并将结果进行可视化处理，在此基础上，才能使用传统算法进行配送路径求解。本文提出使用K-means聚类算法进行配送区域划分，将对象分布划分为不同区域，并以划分之后的区域作为研究对象。这样就实现了复杂卷烟配送问题向传统的车辆路径问题的转换。最后，本文以贵阳公司所属范围的花溪区为算例，进行了实例分析。
2.2 K-means聚类算法
K-means聚类算法的基本思想是:按照数据间的距离大小，将数据集划分为K个簇，输人聚类数目K之后,首先从数据集中随机选取k个样本点作为初始聚类中心，然后计算各个样本点分别到K个初始聚类中心的距离，将样本按照距离最小原则归类，形成K个簇，再计算各个簇的平均值得到新的聚类中心，不断重复上述过程，直到聚类中心不再发生变化或者迭代次数达到设定的值之后，算法结束。
.png)
3 计算过程
3.1对客户位置信息和订单信息进行集中处理
首先收集所有客户的位置信息（经纬度），并基于此进行区域划分结果见图1。接着，通过客户订单信息，进行客户需求量汇总，结果见图2。然后合并客户订单和位置信息，合并结果见图3。然后针对某一个区域，采用K-means聚类算法将距离相近的客户“打包”为不同的配送域，并计算使用正半矢公式计算出每个配送域的中心位置，结果见图4。
.png)
在此基础上，对所得的客户对应配送点区域划分和配送域划分结果进行可视化处理，分别见图5和图6。
.png)
最后根据可视化结果，以各个配送域为对象，先计算出每个配送区内各个配送域间的最优配送路径，进而得出贵州省烟草公司贵阳市公司整个所属范围的最优配送路径。
3.2算例
以贵阳市烟草公司所属配送区域花溪区为例，使用传统遗传算法计算该区域内所有配送域间最优配送路径，并将求得的最优配送路径与原有的配送路径进行对比。（图7为求得的最优配送路径，图8为原有配送路径。）本文方法求得的最优配送路径长度为145km，原有路径长度为301km,因此节约了大量的运输能力和运输成本。
.png)
4 结论与分析
通过花溪区算例，证明了本文使用的方法不仅仅高效，所得结果效果也较好，对烟草公司卷烟配送问题提供了解决途径。同时，本文提出的K-means聚类算法，也为之后的烟草公司卷烟配送面临的大数据相关问题提供了思路。
在进行区域划分时，由于K-means聚类分析不能有效处理配送点分布不均匀、不能有效区分配送区域邻接区域等问题。因此，在进行区域划分时，可根据客户配送点所在区或街道进行手动分。这样能有效处理区域间邻接处有障碍阻隔（如围墙等）、同一个区域内部配送点分布不均匀程度较大等问题，以便于在对区域继续进行细分，使用K-means聚类算法将其划分为不同配送域时的计算效果与结果精度。
参考文献
[1]齐佳婷.城市农产品冷链物流配送车辆路径问题研究[D].浙江理工大学，2016.
[2]周辉仁，唐万生，王海龙.基于差分进化算法的多旅行商问题优化[J].系统工程理论与实践，2010,30(8):1471-1476.
[3]郎茂祥.配送车辆优化调度模型与算法[M].北京:电子工业出版社,2009:146-202.
[4]巩现勇，方圆.居民地聚类分析算法适应性对比研究[D].信息工程大学.2020.
[5]王子龙，李进.基于距离和权重改进的K-means算法[D].空军工程大学.2020.
[6]胡红春.烟草物流配送车辆线路优化研究与应用[J]物流技术,2012(21):214-217.
[7]付依良,李萌,程强等.烟草物流配送网络综合优化模型与方法[J]中外企家,2013(31):205-215.
作者简介：张磊（1983.3-）男，汉族，贵州六盘水人，硕士，研究方向：物流管理，信息系统管理。
项目基金：2020年贵州省烟草公司贵州市公司科技项目《基于大数据的卷烟物流库存与配送系统优化研究》。