基于K-means聚类的生鲜自提柜选址及配送方案优化

徐昊源，缪鸿志

（大连海事大学 交通运输工程学院，辽宁 大连 116081）

0 引言

生鲜电商逐渐成为人们获取生活物资的新渠道，尤其是为了应对突如其来的新冠肺炎疫情，电商平台、商超线上应用、社区微信团购等“云买菜”方式已成为大部分居民的首选。生鲜产品具有易腐特点，其末端配送对时效性和存储条件相对较为严格。为了保持新鲜度，在城市社区纷纷设立了生鲜自提柜，自提柜选址不仅影响到消费者取货的便利性，也影响商家末端配送的效率与成本。

生鲜自提柜选址起源于配送中心的选址。Bortolini，等[1]提出三目标线性规划模型进行生鲜自提点的选址，考虑了典型的生鲜分配约束，即生鲜质量、市场需求和生产能力的约束；Katiyar，等[2]在考虑配送时间窗的基础上，采用改进的蜂群算法进行生鲜自提柜选址，有效减少了生鲜品损耗；HOLMBERG，等[3]开发了一种PI算法，通过生鲜自提点的选址与共享，极大限度地减少了生鲜品浪费；Drezner，等[4]考虑从配送中心到销售点的运输成本以及销售点的库存成本，构建了易腐产品的配送中心选址模型；黄雨珊，等[5]基于深圳市盒马鲜生、菜鸟驿站及相关设施兴趣面（Area Of Interest，AOI）、兴趣点（Point Of Interest，POI）数据，综合运用空间分析、定量统计等方法，探究了社区化新零售与物流终端自提点代表之间的对接基础与可行性路径；李炜勤，等[6]采用改进的二进制教与学优化算法求解了最优选址和容量决策；王文川[7]构建了末端共同配送自提点选址-路径问题模型，并采用两阶段启发式算法进行了求解。K-means聚类方法具有收敛速度快、调参量小等优点，适用于以城市小区为数据点的结果簇密集选址。从研究现状来看，基于Kmeans聚类的生鲜自提柜选址方法还不多见。

考虑到影响生鲜产品配送的因素比较复杂，不能仅仅基于运输时间或距离指标进行决策，本文考虑新鲜度损耗因素，分析生鲜产品从商家到消费者的全链条运输成本，运用K-means聚类算法建立以交通小区为选址依据的自提柜选址模型，并结合自提柜设置的建设与运营成本，从总成本最优的角度对选址点进行筛选。

1 生鲜品末端配送影响因素分析

生鲜产品与其他产品的不同之处就在于生鲜产品具有新鲜度，且其新鲜度会在运输和储存的过程中受到温度和时间等因素的影响而发生变化。由于本文假设生鲜产品在生鲜自提柜中储存的时间不长，消费者会尽快将其取走，因此认为在自提柜的储存过程中不会造成生鲜产品新鲜度的损耗，只考虑运输过程中由温度和运输问题引起的新鲜度的下降。

整个配送路线为三级配送网络，配送流程为生鲜车辆从配送中心出发，前往生鲜自提柜放置点进行卸货后返回，居民从生鲜自提点提货后返回居民小区。在此运输链中，影响自提柜选址的主要因素有：

（1）需求分布差异。不同城市的经济状态不同，相同城市不同区域的经济状态也有所差异，导致生鲜产品需求量存在差异。因此，生鲜自提柜的建设需要结合实际需求情况进行最终决策，以保证满足多种用户的不同需求。

（2）交通条件。自提柜应在尽可能靠近需求点的同时还具有交通便利的条件，保证配送的同时使用户的取货过程更加方便、快捷，满足庞大的车流量和人流量的交通往来需求。

（3）自然环境条件。由于生鲜自提柜需安装在公共区域，以便所有用户进行自助取货，安装位置多处于室外，因此选址应考虑到自然环境的损害，不能选择在风口位置，也要尽量使其有所遮挡，减少暴风雨和日晒导致的隐患和损毁。

2 成本分析

2.1 生鲜品的新鲜度损耗成本

参考1889年阿仑尼乌斯（Arrhenius）提出的阿仑尼乌斯方程（反应速度与温度呈指数关系）描述新鲜度的损耗过程[8]。假设生鲜产品的新鲜度损失表示为运输时间的指数关系式。用生鲜产品新鲜度函数来表示生鲜产品的新鲜度随运输时长的变化规律，见式（1）。

θ为生鲜产品在配送过程中发生的变质率，取0.008。当运输时间t=0时，φt=1表示生鲜产品在配送初始时间新鲜度为1。φt是关于t的单调递减函数，即φt随t的增加而减少，与生鲜产品的新鲜度随运输时长增加而减少的实际情况相符合。

由上述新鲜度函数可以得到，生鲜产品从配送中心m经生鲜自提柜备选点i，最终到需求点j的过程中消耗的总时长为：

其中，r为城市交通拥堵系数，假设在交通顺畅时进行配送，取t=1.2；dmi为区域配送中心m到生鲜自提柜i的距离；dij为生鲜自提柜i到小区需求点j的距离；v1为生鲜配送车辆在城市内的平均行驶速度，交通顺畅时取8.8m/s；v2为消费者取货后的平均步行速度，取1.3m/s。

新鲜度为φt=(1-θ)t，则生鲜产品的新鲜度在此过程中下降了1-φt，生鲜产品变质损耗成本可表示为μ(1-φt)cijdmij。根据上文的变质损耗成本分析，可得到损耗成本的表达式为：

其中，μ为生鲜产品单位损耗成本，取0.5元/(t·km)；cij为小区j消费者从生鲜自提柜i取出的生鲜产品数量；dmij为配送中心m到生鲜自提柜i再到小区需求点j的总距离。

2.2 配送成本

配送运输成本是指生鲜产品由配送中心运输到自提点的过程中所消耗的运输费用，是运输量、距离、单位费率的乘积。配送成本表示如下：

其中,cmi为从配送中心m到自提点i的货物运输量；dmi为配送中心m到自提点i的距离；a为运输货物单位费率，取0.5元/（t*km）；式（7）、式（8）表示每一个生鲜自提点只由一个配送中心进行配送。

2.3 建设与运营成本

建设成本指生鲜自提柜在选址建设中产生的不可变的成本，主要包含生鲜自提柜的购买成本、安置生鲜自提柜时的相关设施成本、安装的人工成本以及所处位置的土地租赁成本等。由于本文涉及的区域较小，因此将此部分成本设置为一个固定值。运营成本也可以说是可变成本，主要指生鲜产品在流通过程中（如短期储存以及装卸搬运过程）投入的人力物力成本。

建设与运营成本可表示为：

其中fi为生鲜自提柜的年单位建设成本，取7 500元/（套*年）；n为流通过程中单位运营成本，取5元/t；cij为小区j消费者从生鲜自提柜i取出的生鲜产品数量。

3 基于K-means聚类的生鲜自提柜选址

3.1 K-means聚类

MacQueen首次提出了K均值聚类算法，它属于非监督学习的硬聚类算法，通过迭代寻找最优聚类。聚类的一个核心问题就是如何合理地定义相似性度量函数。在此采用应用较为普遍的欧氏距离来度量样本间的距离。点x=(x1，x2，...，xn),y=(y1，y2，...，yn)之间的相似度见式（13）。

3.2 “手肘”法确定聚类中心个数

本文中，聚类中心个数对应着自提柜的数目。“手肘”法[9]的判断指标是误差平方和，随着聚类数K的增大，样本划分会更加精细，每个簇的聚合度会逐渐提高，误差平方和SSE会逐渐变小。当聚类数K＜Kbest时，随着K的增大SSE的下降幅度会较大；当K＞Kbest时，随着K的增大每个簇的聚合度趋向于稳定，SSE的下降幅度会更加平稳，此时“肘部”对应的位置即为最佳聚类数K=Kbest。

式（14）中，Sk为第k簇，j为Sk的样本点，ik为Sk的质心，即Sk中所有样本的均值。

3.3 生鲜自提柜选址的算法实现

算法分为两部分，第一部分为根据小区的位置与需求量，结合K-means聚类法确定最佳的自提柜选址；由于配送中心数量有限，第二部分采用贪心算法筛选出各个自提柜对应的最佳配送中心，具体步骤如下：

步骤1：在所有M个小区中选取s个居民小区作为自提柜的设置点，即作为初始聚类中心；

步骤2：测算各个小区用户至聚类中心（自提点）的欧式距离，并根据各个小区的生鲜产品需求量计算新鲜度损耗成本，按照成本最小的准则将各个小区分到距离他们最近的聚类中心（自提点）所对应的类；

步骤3：以每组中每个小区为备选聚类中心（备选自提点）重新计算本组的新鲜度损耗成本，将每组最小总成本所对应的备选聚类中心作为新一代聚类中心（自提点）；

步骤4：重复步骤2与步骤3，直到聚类中心（自提点）不再变化或者达到最大迭代次数；

步骤5：计算每个配送中心送货到自提点的运输成本与生鲜度损耗成本之和，根据贪心算法选取成本和最小值对应的配送中心作为自提点的供货方。

4 案例分析

4.1 基础数据

本文以长春市南关区及其周边部分区域为研究对象，选取其中三个超市作为生鲜配送中心，周边31个小区作为生鲜产品的需求点，所有需求点同时作为生鲜自提柜安置的备选点，都有摆放生鲜自提柜的可行性，通过高德地图获取配送中心与小区需求点的地理坐标，区域配送中心位置信息见表1，居民小区及配送中心的位置如图1所示。

图1 生鲜产品需求点及配送中心位置

表1 区域配送中心位置信息表

考虑到各需求点居民楼分布情况不同，因此采用重心法计算各个小区的中心，将其作为自提点的备选位置。并且基于对实际道路情况的考虑，以高德地图的路径搜索结果为准进行测距，分别计算配送中心到各居民小区需求点的路径距离以及各居民小区之间的步行距离。

根据各个小区的人口规模，选取一定比例的人群作为生鲜自提柜的使用人群，同时考虑自提柜的最大容积等约束，根据实地调查估算各个需求点的年生鲜需求数量（单位：t/年），见表2。

表2 各需求点的年需求量

4.2 聚类结果分析

本文使用总误差平方和SSE度量聚类质量。显然随着簇数K值的增大，SSE的值会逐渐减小。当K值小于实际簇数时，SSE下降趋势明显，随着K值接近最优簇数，SSE下降的趋势逐渐变缓慢。因此，本文以SSE递减趋势开始明显变缓作为聚类结束的判断条件。由图2可知，K＞5时，下降趋势明显变缓。最后结合成本分析确定最佳分类数。

图2 SSE的变化趋势图

上述聚类分析结果以新鲜度损耗成本与配送成本为依据，没有考虑到生鲜自提柜的建设与运营成本。因此，考虑自提柜的建设与运营成本，分别对比聚类数为5与6时两种聚类结果下的成本，结果见表3。

表3 成本对比表

由对比可知，聚类数为6时，总成本最低，各生鲜超市、生鲜自提柜与需求点的对应关系见表4，自提柜的选址示意图如图3所示。

图3 生鲜自提柜选址方案图

按照上述条件计算，优化之前点对点运输的总成本为30.539 6万元，按照表4设置生鲜自提柜，优化后总成本为18.709 5万元，成本节约38.74%。由此可知，该配送方案经济可行。

表4 配送中心-自提柜-小区对应关系表

5 结语

随着生鲜市场的不断扩大，线上购买线下收货的方式获得了消费者的认可，为了满足消费者需求，生鲜自提柜应运而生。本文以新鲜度为依据，基于Kmeans聚类算法对自提点进行选址优化，并进行了算例验证，从需求点中进行生鲜自提柜选址，兼顾了经济效益和社会效益。本文仍然存在着不足，如各小区的生鲜需求量预测不够精确，没有考虑到自提柜的数量及容量限制等，将会在下一步研究中加以分析。