基于节约里程法的回收路径优化

陈楚欣

(太原科技大学 交通与物流学院，山西 太原 030024)

1 引言

近年来，废弃物的不断增多，使得回收物流成为人们关注的焦点。于冬梅提出了由垃圾产生源头进行分类的垃圾分类回收模式，运用GBRT模型进行垃圾量的预测，采用免疫算法进行湿垃圾中转中心的选址，并运用遗传-模拟退火算法进行路径优化。李倩茜等针对村镇生活垃圾中转站的选址问题，建立多目标规划模型，并利用遗传算法进行求解，达到了成本最小、环境负效应最低的目标。孙芬芬,羊英以上海市为例，构建了废弃手机的回收物流网络模型，并对该模型进行了灵敏度分析。

现有研究大多集中于构建回收物流网络模型以及回收站的选址问题，而回收物流的路径问题有待研究。文章参考正向物流中配送路径优化方法对回收路径进行优化。蔺士文等通过建立VRP模型，运用节约里程法进行配送路线的优化，并进行碳排放和运耗油成本分析验证了节约里程法的可行性。郭圆圆,李静宜通过构建RFM模型对客户进行分类，运用节约里程法优化果品同城配送方案，提高了服务水平。宋赛凤等运用节约里程法优化某大型水果超市物流中心向其10个分店配送的路线，并用聚类分析改进复杂配送网络模型，保证该方法的高效性和便利性。

针对回收物流的特点，拟采用节约里程法进行回收路径的优化。文章以太原市万柏林区某回收转运站为研究对象，先将其周边100个小区进行分类，应用SPSS软件中K均值聚类分析方法将其分为9个小区群，并对这9个小区群的回收路线进行实例分析，验证了节约里程法在回收物流的路径优化中的可行性。

2 理论依据

2.1 节约里程法

节约里程法是启发式算法的一种，用来优化配送路线问题。其运算依据是三角形两边之和大于第三边，将两个以上往返里程合并为回路，直到达到一辆车的装载和运距限制时，再对下一辆汽车的配送路线进行优化。利用节约里程法确定配送路线时，需要综合考虑以下三个方面的因素：配送方的配送能力、配送中心与客户之间的距离以及客户与客户之间的距离。在此基础上制定使配送车辆的总周转量达到或接近最小的配送方案以实现节约的目的。因此，本方法需要满足以下3个前提：①配送的是同一种或相类似的货物；②各个用户的地理位置及需求量已知；③配送方有足够的配送能力。

除上述之外，还需要满足3个条件：①方案能满足所有用户的时间要求；②配载量不超过车辆的载重；③每辆车每天的总运行时间及里程数满足规定的要求。

其基本原理如下：为配送中心，，表示客户。到和的距离为0和0，客户和之间的距离为。配送中心的配送方案只有两种：一种是由配送中心向客户和分别配送；另一种是配送中心先向()配送，再由()向()配送。

图1 节约里程法

(1)方案一的配送路线如图中(b)所示，为:

→→→→

(1)

配送距离为:

=2+2

(2)

(2)方案二的配送路线如图中(c)所示，为:

→→→

(3)

配送距离为:

=++

(4)

若不考虑其他因素的影响，两种方案的里程之差(如式5)即为里程节约量。

=+-

(5)

2.2 K均值聚类分析

聚类是指将相似的事件聚合在一起。聚类分析属于描述性数据挖掘，是划分类别的过程，且所要划分的类是未知的。而K均值聚类分析是一种基于样本均值的计算方法，在聚类的过程中通过计算类中各对象的属性均值，作为类的中心点。对象和类的距离是该对象和类中心点的距离。对组内对象的调整是通过计算最小方差的方法，即最终目标是生成总体方差最小的K个类。聚类的步骤如下：

(1)从N个样本对象中，任意选定k个对象作为k个类中的初始对象。

(2)从剩余N-k个样本对象中任意选择一个对象，计算其和K个类的相似度(距离)，并将其归并到相似度最高的类中。

(3)重新计算已归并的各对象和k个类之间的相似度，根据相似度调整并归类。

(4)重复步骤(2)直至所有对象归并到k个类中。

2.3 实例分析

文章选取了太原市万柏林区某回收转运站附近100个小区为研究对象，验证该模型的有效性。首先根据实地调查，收集100个小区的回收次数和回收量。其次对小区进行聚类分析，将100个小区分为9个小区群。目前由转运站直接派车每天定时向每个小区进行清运。转运站备有两种厢式货车：1.5～2T和4～6T的厢式货车，均为电动车，由于电量限制，其最大行驶里程分别为20km和50km。现有回收模式为，回收司机分别对每个小区进行回收作业，回收作业完成后遂返回回收转运站。根据实地调查，该种回收方式下常常导致汽车空载。因此需要对回收路径进行优化。回收时司机将废弃物品统一装入编织袋进行打包，所以可视为相似物品。详细的优化步骤如下。

(1)文章记录了回收转运站周边100个小区最近一个月的回收次数和回收量，并对其进行规范化处理，处理公式为:

并应用SPSS软件中的K均值聚类分析将其分为9个小区群，如表1所示。

表1 小区群细分结果

鉴于其位置的复杂性，将其进行微调，并将9个小区群进行编号，每个小区群包含的小区个数及其日均清运量等具体内容如表2所示。

表2 9个小区群具体内容

(2)回收转运站P和9个小区群的地理位置及其之间的距离(连线上的数字，单位：km)和其日均清运量(括号中的数字，单位：kg)如图2所示。

图2 转运站与9个小区的位置关系及日清运量

(3)根据上述数据，计算回收转运站P到各个小区群以及各小区群之间的最短距离，如表3所示。

表3 任意两点之间的最短距离

(4)利用节约里程公式(见式5)计算出各小区的节约里程数并进行降序排列，得到节约里程排序表，如表4所示。

表4 节约里程数排序

根据上述节约里程排序表，首先将节约里程数最大为17的小区节点C、D连接起来，形成回路P-C-D-P，此时回路总运量2.8t，总运距21km，均小于汽车载重和运距的限制。其次将节约里程数第二为11的小区节点B、C连接起来，形成回路P-B-C-D-P，此时回路总运量4.9t，总运距22km，仍均小于汽车载重和运距的限制。最后将节约里程数第三为10的小区节点A、B连接起来，形成回路P-A-B-C-D-P，此时回路总运量5.52t，总运距30km，此时运距达到最大，得到优化后的第一条清运路线，同时把涉及A、B、C、D这四个小区节点的路线删除掉。重复上述步骤，最终形成3条清运路线，如表5所示。

表5 仓储中心运输路线情况

优化路线前，回收转运站每天需要派出7辆1.5～2t的车和2辆4～6t的车，总行驶里程为136km。优化后，需要2辆4～6t的车和1辆1.5～2t的车，总行驶里程为77km，共节省59km的行驶里程。通过优化，不仅大大减少了汽车的空载率，而且减少了汽车的总行驶里程，提高了清运效率。

3 结论

回收物流在现代物流中占据不可忽视的一环。文章采用SPSS软件中的K均值聚类分析将回收转运站附近100个小区分为9个小区群，通过节约里程法为回收物流的回收路径问题提供了新的解决思路，并且通过实例分析，验证了其可行性。但是随着AI智能技术、物联网技术的不断发展，回收柜逐渐走进了众小区。回收柜的便利等优势不断改变着人们的观念，当人们更愿意选择回收机处理废旧物品之后，回收物流的新问题将会随之出现，如何在繁杂的回收节点中选择最优的回收路线，也是今后研究的方向。