基于K均值聚类算法的生鲜运输路径优化模型
时间：2022-12-08 09:10:04 来源：雅意学习网 本文已影响 人 
周蓉蓉 陈 栋 刘思远
（1.南京国家现代农业产业科技创新中心，南京 211800；
2.国家农业信息化工程技术研究中心，北京 100097；
3.智慧农业技术集成与应用创新农业农村部重点实验室，南京 211800；
4.广西大学计算机与电子信息学院，南宁 530004）
近年来，随着生活水平的提高，人们对生鲜农产品的需求不断增加，我国的生鲜市场规模不断扩大，对生鲜的冷链配送服务要求日益增加；
由于冷链配送受交通状况与配送地分散程度的影响较大，尤其在一线城市普遍面临着生鲜配送成本高、配送订单分散的问题。目前，我国大型生鲜供应企业每日的货物配送仍旧需要人工根据配送地址对配送车辆进行调度安排，耗费的人力时间成本较高，而且无法保证配送成本的最优化。如今随着物流技术[1]的快速发展，生鲜冷链配送的调度、路径选择正向智能化方向发展。基于以上背景，通过引入车辆路径问题（Vehicle Routing Problem，VRP）[2]求解方法，研究生鲜冷链配送路径优化算法，对提高物流效率，降低成本具有重要意义。
冷链物流路径优化问题(Vehicle routing problem,VRP)于1959年提出后[2],成为运筹学与组合优化领域的热点问题，而生鲜农产品物流作为冷链物流分支，也受到了学界的极大关注。生鲜农产品物流涵盖包装、装卸、运输、储存、加工和配送等多个环节，涉及从农业生产到销售终端，跨越不同行业及不同企业，参与主体多元、组织化程度不一，从业人员专业能力和知识水平参差不齐，加上农产品运输成本、储存加工保鲜成本、流通中介费用等层层叠加，导致物流成本上升。在物流成本占比中，粮食类农产品为40%左右，蔬菜、水果等生鲜农产品超过60%[3]。国内冷链物流近些年取得了高速发展[4]，但仍然存在冷链物流流通率较低、地区发展不均衡、冷链物流体制不健全，以及第三方物流发展缓慢等问题。当前，国内冷链物流网络优化主要包括配送中心选址和配送路径优化两个问题，对于冷链物流配送中心选址问题的研究，需要考虑的不确定变量较多，因此研究的范围也比较广泛，主要研究的还是被选择的配送中心点与辐射半径的距离之间的约束、用户需求量与配送中心点之间的约束等问题，采用的方法也较多，包括采用启发式算法[5]、混合算法[6]、元启发式算法[7]、模拟退火算法[8]、禁忌搜索算法[9]、蜂群算法[10]等现代智能优化算法。冷链物流配送路径优化问题的研究目前主要考虑对不同成本因子的约束研究，包括配送过程中的运输成本、时间窗约束下的惩罚成本、货损成本等，有的也考虑了碳排放成本[11-15]，王芳等对带时间窗的多目标蔬菜运输配送路径优化进行了研究[16],吴亮然等提出了基于车辆配送线路的区域协同配送方法[17],赵志学考虑拥堵区域的多车型绿色车辆路径问题优化[14],杜琛等将客户满意度和最小损耗加入了目标函数，对冷链配送路径优化问题进行了求解[18]，以上研究为本研究提供了求解参考。
综上所述，当前的冷链物流车辆路径优化问题多以变化不同优化因子作为研究目标函数，从而得出一种或多种约束因子的车辆路径优化模型。但针对大城市内配送目的地分布范围广的场景，比如针对城市生鲜配送较为鲜见。陈栋等对跨省雏鸡配送场景提出了订单分群的求解方法[1]，为解决大城市生鲜配送路径优化问题提供研究思路。本研究通过引入K 均值聚类算法，根据配送目的地位置进行配送单元划分，并以配送距离和货物损耗最小、车辆使用数较少为目标函数，构建生鲜配送路径优化模型，并使用改进的遗传算法进行求解，以北京某生鲜农产品供应商实际配送车辆数据进行模型验证。在此基础上设计研发了适用于城市生鲜农产品配送的车辆路径优化服务系统，实现了生鲜配送车辆调度优化等功能。
2.1 问题描述
北京某生鲜农产品企业每天负责北京各大商超的生鲜果蔬配送，配送的目的地跨越北京全市，地理位置跨度较大，每天需要针对不同配送需求进行车辆配送安排，并尽可能减少车辆所走的路程，同时需要满足客户的时间要求。本研究根据实际场景，对研究范围进行约束如下：①此企业只有一个配送中心，每天所有生鲜果蔬货物由此配送中心统一配送；
②配送所使用的冷链车辆的型号、载重量、体积都相同；
③配送的客户目的地的位置固定，且每天的需求量一定；
④配送安排尽可能达到路程最短，使用的配送车辆数量尽可能少。
2.2 模型构建
基于以上问题的描述，构建生鲜农产品配送路径优化目标函数，目标函数的约束条件为配送总里程、车辆数、时间窗约束条件，其数学表达如下。
一是确保每条路径上各客户的货物需求量之和不超过配送车辆的载重量：
二是确保每条配送路径的长度不超过配送车辆一次配送的最大行驶距离：
三是确保每条路径上的客户数不超过总客户数：
四是确保每个客户都得到配送服务：
五是确保每条路径的客户的组成：
六是限制每个客户仅能有一台配送车辆送货，当第k 辆车服务的客户数≥1 时，说明该台车参加了配送，则取sign(nk)=1，当第k辆车服务的客户数＜1时,，表示未使用该台车辆，则取sign(nk)=0。表达如下：
在本研究中，对于时间惩罚函数默认为一个常数，此参数不在本次研究中作为动态约束条件，为下一步深入研究做预留。
3.1 求解流程
针对生鲜农产品配送问题，本研究设计了两种求解流程，一种是直接对所有配送订单进行整体路径优化求解，如图1 所示。①鲜配送订单数据预处理，提取出订单中订单编号、地址（经纬度）与订单的需求量、客户配送时间等信息；
②将全部生鲜配送订单信息与车辆信息作为参数输入到遗传算法中，按照优化目标函数，匹配相应的配送车辆，经过算法的复制—交叉—变异等迭代操作，最终选择表现最好的结果输出。
图1 整体优化流程图Fig.1 Overall optimization flow chart
另一种采用根据订单目的地位置先进行聚类，然后分组进行路径优化求解，如图2所示。
图2 基于聚类的优化求解流程图Fig.2 Optimization flow chart based on clustering
①对生鲜配送订单数据预处理，提取出订单中订单编号、地址（经纬度）与订单的需求量、客户配送时间要求等信息；
②根据配送目的地的经纬度信息，采用基于位置的K均值的聚类方法，对生鲜配送订单进行聚类划分小组，形成多个订单配送单元。③将划分好的订单配送单元中的配送信息作为算法参数进行输入，调度优化算法基于遗传算法对每个订单配送单元的配送信息按照目标函数进行求解，最终选择表现最好的结果输出。④将对每个订单配送单元优化的结果进行合并后输出。
3.2 配送目的地聚类方法
在3.1 小节中，采用根据订单目的地位置先进行聚类，然后分组进行路径优化求解。本研究采用K均值聚类算法根据配送订单目的地经纬度进行配送订单位置聚类。K 均值聚类算法是一种非层次聚类算法，在最小误差的基础上将数据划分了特定的类，类间利用距离作为相似度指标，两个向量之间的距离越小，其相似度就越高[1]。其算法求解过程中，关键是确定K 的值，本研究使用肘部法与轮廓系数确定K的值。
本研究选用了北京某生鲜供应企业的209 个真实订单数据，其订单的位置散点分布如图3所示。
图3 订单位置散点图Fig.3 Order Position Scatter Chart
通过肘部法确定聚类K（最终的簇数）值，如图4所示。取不同K值的平均畸变程度曲线，曲线曲率最高的K值范围在8～15之间。
图4 K均值聚类肘部法则平均畸变曲线Fig.4 K-means clustering elbow rule average distortion curve
通过轮廓系数法确定K（最终的簇数）值，如图5所示。由此确定K=10，系数最大。
图5 K取不同值对应的聚类效果图Fig.5 Clustering effect with different K values
3.3 遗传算法求解过程
通过对遗传算法进行改进，实现对生鲜农产品配送路径优化的求解，结合实际生鲜果蔬订单配送路径优化问题，确定问题求解的具体流程如下。
算法参数与数据初始化，对种群规模Population-Size、交叉概率Pc、变异概率Pm、进化代数GenerationNum 以及惩罚函数Pw 等参数进行初始化设置，提取生鲜农产品配送订单中的订单编号、订单经纬度、订单的货物需求量等数据。②初始化种群，对种群个体进行编码，生成对应规模的种群矩阵。③计算种群中每个个体的目标函数值，根据目标函数值确定每个个体的适应度，选取适应度最优的个体保留。④对种群中的个体进行交叉、变异操作，生成新的种群。⑤重复③—④步，直到满足进化代数。⑥将适应度最优（适应度值最小）的个体作为最优解输出。
4.1 数据的初始化及求解过程
本研究选用北京某生鲜供应商的209 条配送订单数据作为样本数据。数据项包含订单编号、客户姓名、配送时间、最后达到时间、地址、经度、纬度、农产品数量、农产品重量、农产品体积、出货仓库编号、出货仓库名称、客户是否为VIP。筛选订单编号、经度、纬度、农产品重量、农产品体积、出货仓库地址数据项作为求解数据，数据概要如图6所示。
图6 实验数据概要图Fig.6 Schematic diagram of experimental data
求解过程如下：
（1）种群初始化：以配送订单的顺序作为一个种群的个体，即一个染色体。
（2）种群描述矩阵：生成一个矩阵，一行代表种群中一个个体，列代表客户订单编号。矩阵如下所示：
（3）结合实际情况，对配送车辆进行数字化描述，规定只有一种类型的车辆，载重为8吨、容积为50立方米；
车辆数量满足当日订单数。
（4）求解：①数据初始化。②初始化种群生成。③计算种群适应度：fitness-个体路径的总里程，取倒数fitness=1/evaluation;一般适应度越大越好，在总里程中约束中是越小越好，故在此去倒数。④计算种群中各个个体的累计概率:
按照交叉概率Pc 使用OX交叉法对种群进行交叉；
按照变异概率Pm 对种群中个体进行变异。⑦判断种群的代数是否达到设置数。不满足则重复执行③-⑦；
满足则输出最优的个体，求解结束。
（5）对遗传算法参数进行设置：种群数量为200个，交叉概率为0.5，变异概率为0.05，迭代次数为10000 次。经过以上求解步骤，得到适应度曲线，如图7所示，在种群迭代进化5000次后，趋于平缓。
4.2 求解结果比较与分析
基于以上求解步骤，分别对整体路径优化求解结果和经聚类后的路径优化求解，如图8 所示，未聚类与聚类的配送区分明显，使用聚类的方法对配送订单分布更清晰。
图8 配送订单聚类前后效果对比图Fig.8 Comparison of the effect before and after the clustering of delivery orders
如表1 所示。对比两种方式的求解结果，配送优化总里程和车辆使用数量，由表中可以看出，未经聚类的优化里程平均3753.01Km，使用车辆数平均32辆；
经聚类的优化里程平均2105.4Km，使用车辆数平均辆34 辆；
在车辆使用数量相差不大情况下，配送运行总里程大幅度降低。结果显示使用聚类的方式具有合理性。
表1 不同算法求解算例计算结果Table 1 Calculation results of examples solved by diferent algorithms
4.3 模型应用
本研究通过基于以上研究，设计研发了适用于城市生鲜农产品配送的车辆路径优化服务系统，实现了生鲜配送车辆调度优化等功能，为生鲜供应企业减低配送成本，提升企业效率提供了科技支撑。系统采用B/S架构，将模型打包成服务，提供API调用接口的形式来为生鲜供应企业服务。系统功能运行流程如图9所示。
图9 配送路径优化服务流程Fig.9 Optimizing service progress
系统的服务API接口与应用实例如图10所示。
图10 系统服务实例Fig.10 System running instance
本研究针对生鲜农产品城市配送场景，针对其配送订单分散，配送成本高，配送路线选择人工依赖性强的问题，提出了基于K均值聚类算法的生鲜运输路径优化模型，通过引入K 均值聚类算法，实现了根据配送目的地位置的配送单元划分，并以配送距离和货物损耗最小、车辆使用数量较少的情况做为目标函数，构建生鲜配送路径优化模型，模型使用改进的遗传算法进行求解。通过对北京某生鲜供应企业实际的配送订单的数据分析与求解，分别对未聚类与聚类情况下的求解结果进行对比，结果显示配送目的地不进行聚类情况下配送的里程平均为3753.01 公里，使用的车辆数量平均为32 辆；
在对配送目的地进行聚类情况下配送的里程平均为2105.4公里，使用过的车辆数量平均为34 辆；
在使用车辆数量增幅不多的条件下对配送目的地聚类分组后模型让配送总里程比未进行聚类分组的情况降低了43.9%。通过对城市生鲜农产品配送的车辆路径优化服务系统的设计与研发实现了生鲜配送车辆调度优化服务功能，为生鲜供应企业降低配送成本和提升企业效率提供了技术支撑。
本研究对大城市范围的生鲜配送路径优化问题中的订单位置聚类问题进行了深入的研究，其优化的约束条件只考虑了配送总里程与配送车辆，在下一步研究中，将对配送时间窗、碳排放等约束条件以及考虑不同聚类算法的使用对优化结果影响性进行研究。
猜你喜欢 冷链聚类种群 山西省发现刺五加种群分布今日农业(2022年15期)2022-09-20一种傅里叶域海量数据高速谱聚类方法北京航空航天大学学报(2022年8期)2022-08-31中国冷链物流：应对冬奥的技术大考科技创新与品牌(2022年4期)2022-05-08国务院办公厅印发 《“十四五”冷链物流发展规划》农村百事通(2022年2期)2022-03-11基于数据降维与聚类的车联网数据分析应用汽车实用技术(2022年4期)2022-03-07基于模糊聚类和支持向量回归的成绩预测华东师范大学学报（自然科学版）(2019年5期)2019-11-11重庆市冷链物流共同配送模式的研究智富时代(2019年4期)2019-06-01重庆市冷链物流共同配送模式的研究智富时代(2019年4期)2019-06-01由种群增长率反向分析种群数量的变化中学生物学(2018年8期)2018-03-01种群增长率与增长速率的区别中学生物学(2008年6期)2008-08-29
