基于改进K-means聚类方法的新零售物流配送路径优化

陈婵丽，钟映竑

（广东工业大学 管理学院，广东 广州 510520）

1 引言

自2016年起，新零售概念越来越为人们所熟悉。随着时代的发展，企业通过物流使得线上线下融合，互相补充实现共同发展。各企业为适应新零售时代的要求，进行了一系列战略布局和合作，企业可通过共同平台实现合作共赢。新零售时代的到来，使得消费者可以通过各种渠道进行购物，而用户的购物体验成为重中之重。物流配送路径问题一直是物流领域的研究重点，然而目前的多数物流配送模式仍不适应新零售时代的特点，传统的物流配送路径方法的研究仍停留在适应于传统的零售方式，并未将线上线下很好地融合以获取良好的购物体验。为了适应新零售时代，如何对物流配送进行优化，融合线上线下，减少物流配送路程以提升用户体验度是本文的研究重点。本文假设新零售各实体店面可实现协同合作，各实体店面具有一定的库存量且可以作为配送中心，从末端实体店物流配送路径角度出发，对新零售各实体店物流配送路径优化方法进行研究。

2 研究背景

2.1 新零售背景

近年来，人们越发重视购物体验，线上已无法满足人们日益增长的体验式消费，购物体验始终不及线下。传统的线下供应链体系必须通过更高效的互联网技术实现转型提效。2016年，马云指出，“纯电商和纯零售都将结束。线上线下通过物流达到融合的新零售即将引领未来的商业模式”[1]。同年《国务院办公厅关于推动实体零售创新转型的意见》也明确了实体零售企业创新转型的9项主要任务，定调实体零售转型[2]。从近几年开始，各企业为适应新零售制定了一系列的战略布局和投资合作。阿里巴巴先后通过投资入股联华超市、新华都和三江购物、高鑫零售和百联集团达成战略合作，构建创新型跨界超市。与此同时，腾讯也加快了新零售的步伐，与家乐福、沃尔玛达成战略合作伙伴关系，并投资永辉超市、京东。新零售背景下，生鲜社区店及各杂货店B2B应运而生，如永辉超市和中百集团旗下邻里生鲜及京东旗下钱大妈。阿里巴巴成立了多家盒马鲜生，盒马鲜生既是超市也是配送中心，更是仓储中心，是对线下超市全面重构的新零售业态。腾讯和京东联手构建无人超市和京东到家，腾讯三轮投资每日优鲜便利购，线上到家服务占据主要地位[3]。

新零售的核心在于推动线上线下的高度协同，达成战略合作的末端实体店面可通过充分的库存共享和快速的物流服务不断提升客户体验度和满意度。连接线上与线下两者的关键点在于物流配送，物流配送行业不但要求所有货物能及时送达，而且也要求尽可能降低整个运输成本，所以物流配送车辆路径优化问题是亟待解决的关键问题。传统的优化方法搜索时间较长，且不适应新零售企业合作共赢模式，难以找出最优路径，并且不同实体店对同一客户点的配送路径重复率高，造成配送成本高，效率低。为适应时代发展，提高车辆路径优化率，如何利用新零售下各实体店面可协同配送的特点改进末端实体店物流配送路径方法，使线上线下融合，最大程度地提升用户体验，增加销量，降低企业物流配送成本，成为迫切需要解决的关键问题。

2.2 新零售模式下的传统配送方法

2.2.1 TSP问题描述。本文对末端物流的物流配送策略进行优化，主要研究问题是TSP（traveling salesman problem）旅行商问题。这是一个非常经典的NP完全问题[4]，可描述为：已知n个城市相互之间的距离矢量，旅行商配送对象（通常是物流配送车辆）开始会选择其中的某一个城市作为初始站，从初始站开始出发去遍历访问其他的所有城市一次，每个城市仅访问一次，最后回到初始站，TSP问题就是如何规划旅行商使其所走的路线最短。简单地说，就是寻找n个城市的最短遍历路径，或者通过算法搜索自然子集X={C1,C2,…,Cn}(X的元素表示对n个城市的编号)的一个符合最短路径条件的排列π(X)={D1,D2,…,Dn}，使Td取最小值，其中d(Di,Di+1)表示城市Ci到城市Ci+1的距离。

本文研究的物流配送路径问题类似这类TSP问题。假定已知的多个互不协同的配送中心（实体店面如超市、便利店等）的位置和其在一个特定城市区域各自的需求量，其中物流配送车辆有最大的配送范围限制（默认为3km），且每一个配送中心有且只有一辆物流配送车辆。在满足目标函数最小和多个约束条件的前提下要求每一个配送车辆从各自的配送中心出发，把货物分别送到各自的配送目标位置，每个配送目标位置有且只有一辆物流配送小车进行一次配送，完成所有配送货物的配送任务后从最后一个配送目标位置返回至配送中心。整个过程中最关键的问题就是配送路线的优化和如何有效地分配配送资源，对区域内的所有配送需求进行配送，使总体的配送路径最短。

2.2.2 新零售模式下传统配送问题。目前，绝大多数的物流配送有很成熟的配送策略和方案。通常都是结合各类智能算法，如遗传算法、启发式算法[5]、粒子群算法[6]和模拟退火算法[7]等，针对特定的场景和特征进行对应的改造，从而提高物流配送效率。石红国等[8]提出使用Hopfield神经网络与归约结合求解大规模TSP，通过提取原TSP较优解间的公共边以缩小规模，再利用原神经网络得到较优解后将TSP还原并求较优解。苑光明等[9]针对路径规划中收敛速度慢的问题对遗传算法引入了拐弯因素，改进传统的精英保留策略以提高AGV运行效率。Doerr B等[10]研究优化时间如何依赖于参数的选择，提出(1+(λ，λ))遗传算法(GA)，得到如何静态与动态地选择种群大小、变异概率和变异偏差的结果。刘二辉等[11]通过改进遗传算法和灰狼优化算法引导小车路径规划，可用于求解复杂静态环境中的移动机器人路径规划问题。Gong D W等[12]利用遗传算法对区间优化问题进行研究，提出一种解决区间多目标优化问题的方法[6]。

然而，在末端物流的现实配送场景中，很多物流配送中心（各类实体店面比如超市、便利店等）的配送效率并不是特别高效。通常在某一个特定的物流配送区域范围内，多个不同的物流配送中心有着相同的配送点，如果没有一个统一的配送平台对这些物流配送中心进行综合管理和分配，那么这些配送中心只能配送各自范围内的配送点。这样在同一个物流配送区域内，同一个目标配送点（比如小区）可能会由多个不同的配送中心负责配送。这类情况在现实生活中非常常见。图1采用seaborn对广州市天河区的几个实际配送实体店面及其配送点进行了模拟仿真。从图中圆圈中的点可以看到，对于B实体店和H实体店，它们的位置不同，但是各自有一个订单在同一个配送点。根据传统的配送模式，B实体店和H实体店必须同时分配两个配送车辆到同一个配送地点，造成浪费。如何结合协同配送和重聚类的方式重组这些配送资源，是一个值得研究的问题。

随着新零售时代的来临，用户体验度成为最重要的提升指标。对于用户来说，不仅要求线上预订要快，更要求线下配送与线上同步。线下的配送效率是影响新零售发展的一个核心因素，如何快速响应用户的配送需求，成为目前亟待解决的关键问题。

图1 不同实体店重复配送目标示范图

3 用遗传算法改进的K-means聚类方法

针对新零售模式下传统物流配送存在的问题，本文提出了一种新型的混合聚类算法。通过改造K-means聚类，结合遗传算法求解TSP问题进行重聚类。配送点重聚类时，配送中心采用了共同配送的新模式来提高响应度，并且对其中存在的重复配送点进行了合并优化。共同配送后可以使配送中心具有更大的配送范围，从而提高了物流配送效率，实现了新零售的快速配送。本文提出的新型混合聚类算法主要有以下贡献：

（1）相比较于其他传统的遗传算法，本文提出的混合聚类算法可以通过协同配送和TSP最短路径重聚类的方式来提高区域物流的整体配送效率，通过对同区域内不同配送中心的模拟仿真，基于Tensor-Flow机器学习平台[13]、改进K-means算法和遗传算法对所有配送需求点进行重聚类，更加合理和高效地重组了物流配送资源，提高了物流配送效率。

（2）对于实际中存在的重复配送点问题，通过协同配送优化的方式，对这类配送需求点进行了合并优化，用同一个配送资源（如外卖人员）匹配不同配送中心的多个重复配送点的配送需求，优化这部分物流配送成本，从而提高了整体的配送响应度。

4 物流配送的数学模型求解算法描述

4.1 遗传算法

遗传算法（genetic algorithm，GA）是模拟生物在自然环境中的遗传和进化过程而形成的一种全局优化搜索算法[14]。目前有很多种通过遗传算法求解TSP问题的优化算法的方案，但对于实际场景中具有不同配送资源的独立实体门店来说，传统的遗传算法求取最短路径的策略比较乏力。从整体的物流配送效率来看，由于不同实体店面在同一个区域内需要各自配送货物，所以在相同范围的同一个物流区域内，这种算法求取出来的并不是整体的最优解。

遗传算法求取TSP的主要计算步骤如下：

（1）编码。选择实际问题参数集，即对n个配送目标点的TSP问题进行染色体的分段编码，其中每一段为对应配送目标点的编号；

（2）种群初始化。完成染色体编码后产生一个初始种群作为初始化对象；

（3）定义适应度函数。设{k1,k2,…,kn}为染色体种群，其中Dkikj表示配送目标点ki到配送目标点kj的距离，则适应度函数为:

其中，fitness表示刚好从配送中心k1出发，遍历n-1个配送目标点后再返回到配送中心的距离的倒数。因此适应度函数应当选择尽可能大的染色体目标，适应度值越大的染色体越优质，反之亦然；

（4）选择操作。从原种群中选择染色体个体到新种群中，个体被选中的概率与适应度值相关，适应度值越大，则概率越大；

（5）交叉操作。采用部分映射杂交法，确定交叉操作的父代染色体个体；

（6）变异操作。采用随机选取两个点并互换位置的方式，产生两个[1,n]范围内的随机整数p1和p2，确定位置后互换；

（7）计算路线长度。若迭代未结束，继续执行（4）-（6）步，直到迭代结束。

4.2 共同配送模式下基于遗传算法改进的K-means聚类方法

K-means算法最早在1967年由Macqueen提出，K-means在聚类算法中最简单、最高效。其核心思想是，由用户指定k个初始质心以作为聚类的类别，重复迭代直至算法收敛[15]。本文对K-means聚类算法进行针对性的改造，对其中的集合分簇和收敛规则进行修改。集合分簇开始之前，将当前所有的目标配送地点作为输入数据集。与其他K-means方法的不同之处在于，本文的整体输入数据集是不会发生变化的。收敛规则为：除了以欧几里德的中心距离平方和之外，利用上述的遗传算法求取TSP的距离，对每一个分簇中的所有数据对象与当前的聚类中心进行路径求和，当迭代次数达到阈值或中心距离平方和与路径求和不再变化时，结束聚类过程。整个混合聚类算法的步骤如下：

（1）根据配送中心点选择聚类中心分簇。设k为聚类中心数目，xi表示第i个目标对象，K-means算法以k为参数，将具有n个目标对象的集合D={x1,x2,…,xn}分为k个簇C={C1,C2,…,Ck}。本文采用实际配送中心的数量作为k参数，将实际物流区域中的多个配送中心作为初始化的聚类中心T={t1,t2,…,tk}；在整个集合的重聚类过程中，配送中心的位置不会发生改变。

（2）初始化分簇。当完成聚类中心的初始化后，就对簇进行初始化，对集合D中的n个目标对象，计算xi(i=1,2,…,n)到中心向量tj(j=1,2,…,k)的欧几里德距离dij，将dij中最小的值对应的xi标记为相应的簇类，直到D集合中所有的对象被标记完成；算出每个聚类簇的所有欧几里德距离的平方和Oj(j=1,2,…,k)，作为收敛条件。

（3）分簇后的最短路径求和。对于j=1,2,…,k的所有Cj中的目标对象，通过遗传算法求得簇内的最短路径rm(m=1,2,…,k)，并将所有簇内求出的最短路径求和，得Sm(m=1,2,…,k)，作为收敛条件，并计算出首个收敛条件Esum1=Oj+Sm。

（4）重聚类。对于j=1,2,…,k的所有Cj中的最长欧几里德距离的向量xm(m=1,2,…,k)，计算xm到其他k-1个聚类中心向量tj(j=1,2,…,k-1)的欧几里德距离，将最小值重新随机分配到其余的聚类中心；分配后重新计算所有簇中的Oj和Sm的求和结果Esum2作为判断条件，若Esum2＜Esum1，则使用该重聚类的结果；否则重新使用重聚类之前的结果；

（5）重复（3）和（4），直到Esum=Om+Sm(m=1,2,…,k)的结果不再变小或当前的迭代次数达到最大迭代次数的阈值时停止重聚类。

5 实验结果与分析

5.1 实验数据

实验数据均采集实际的城市坐标点。以广州市天河区内的10个实体店面坐标作为实验数据（如图2所示），同时根据“美团”和“饿了么”两个平台的爬虫数据，获得附近居民住宅区的实际位置作为物流配送的目标点。根据百度地图提供的定位功能，将这些居民住宅区对应的坐标数据作为配送目标点的坐标。由于是实际的GPS设备获取的经纬度坐标，而在计算路径时要用米制坐标，因此通过百度提供的坐标转换服务API将经纬度坐标转换为对应的米制坐标。为便于描述与展示，我们只对其中的物流配送中心的数据信息做展示，见表1。

图2 天河区10个配送中心的分布图

5.2 实验环境准备

本文需要通过图形计算来精确模拟整个物流配送过程，因此选择了谷歌公司提供的Tensorflow作为实验平台。Tensorflow是Google提供的一个基于数据流编程的库，目前被广泛使用于各类机器学习和科学计算的编程实现方案中，它提供了一系列高效的基础组件和各类API，可以为本文的实验提供非常强大的功能支撑。

表1 各个配送中心之间的位置坐标和配送需求量

实验环境方面，使用的是腾讯云服务器的Linux系统，发行版采用了Ubuntu，内核版本为Linux（4.15.0）；通过安装python、pip等必要的基础IDE和第三方库Tensorflow，为计算提供基础条件。实验环境的系统信息见表2。在进行混合聚类算法的聚类计算过程中，需要使用python编程调用相关的程序接口来启动画图，需要Tensorflow的图形计算，还需要其他第三方库的支持，因此在实验系统Linux上面还要安装Seaborn等必要的第三方库。

表2 实验环境的系统信息

5.3 实验结果

图3是传统遗传算法求取各个配送中心所遍历的路径，图4是采用基于协同配送的混合聚类算法后的配送路径。从图3可以看出，每一个配送中心负责配送各自的物流需求，其中有一些配送目标点与其他配送中心的配送目标点重复，不同的配送中心对相同的目标点进行重复配送。由图3可知，在相同配送范围内，每一个配送中心都要遍历比较冗长的配送路径，区域内的整体配送过程也比较复杂和冗长。从图4可以看出，基于协同配送混合聚类算法重聚分配后的路径相比图3而言，物流配送中心的配送路径明显得到优化。对于每个配送中心都通过重聚类，优先分配距离较近的配送目标点；并且对存在的重复配送目标点的配送需求进行合并优化，优先将合并后的配送需求分配给最近的配送中心负责。通过重聚类和协同分配后，在同样区域内有效的减少物流配送路径，同时可满足大量的配送需求。

图3 传统遗传算法物流配送路径

图4 基于改进K-means聚类方法的物流配送路径

图5是对每一个配送中心在聚类前与聚类后通过遗传算法遍历所有配送点的物流配送路径统计情况，更直观地证明了本文提出的混合聚类算法的有效性。横坐标表示采集于真实地理位置的实体店面，也是配送中心；纵坐标表示配送中心分别通过传统遗传算法、共同配送模式基于遗传算法改进的K-means聚类方法求得最短路径后物流车辆的行驶路程（单位：m）。在同一个物流区域内，使用改进混合聚类方法后，大多数配送中心的行驶路程都得到优化。

从表3可以看出，整个物流区域的物流车辆行驶总路程在聚类后比聚类前减少了39.89%。值得注意的是，由于需要优先分配就近的配送需求目标点，在重聚类过程中会出现部分配送中心的配送路程要比之前大，但是区域内总体的配送路程得到明显的改善，这符合协同配送的出发点，同时也能提高区域内整体配送效率。

图5 TSP和改进后的混合聚类算法配送路程的比较

表3 实验数据结果比较

6 结语

在新零售背景下，从末端物流配送路径的角度出发，本文建立了车辆配送路径最优化的数学模型，提出了一种用遗传算法改进的K-means聚类方法。本文采用广州市天河区实际数据，通过Tensorflow软件仿真实验进行验证。实验结果证明，和传统遗传算法相比，本文提出的用遗传算法改进的K-means聚类方法在复杂的区域物流内可减少39.89%的配送路程。该算法解决了重复配送路径问题，并且优化了物流配送路径，提高了配送效率，从而改善了服务质量和用户体验度。