生活垃圾收运路径优化研究

文/陈欢欢 朱虹宇

基于生活垃圾量剧增、城市建成区范围不断扩展、生活垃圾终端处理设施不断外移、收运系统模式重新调整等问题，构建以最小化运输成本和碳排放成本为目标的生活垃圾收运路径优化模型，并通过重构解空间设计了一种改进回溯搜索算法对模型展开求解。最后，通过与遗传算法和模拟退火算法相比，改进回溯搜索算法能获得更高质量的解，收运路径方案的收运距离最短，在生活垃圾收运路径优化中能得到一个较好的应用。

1.引言

近年来，随着中国经济社会的发展和城镇人口的增多，使城市生活垃圾的产生量也随之增加，2021年我国城市生活垃圾产生量约2.49亿吨，清运压力仍不容小觑。国家统计局数据显示，生活垃圾的收集和运输的物资消耗占整个垃圾处理系统的70%～80%[1]。同时，为顺应公益、垃圾分类回收以及低碳环保等政策要求，合理的生活垃圾收运方案能有效地缩短收运距离为企业降本增效、降低碳排放量减少环境污染，故对生活垃圾收运路径进行优化，具有重要的现实意义。生活垃圾收运路径优化问题属于一般车辆路径问题，国内外学者对该问题已展开了深入研究。张玉州等[2]以最小车辆运输费用为目标构建了多回收站垃圾收运问题模型，引入合作协同算法，并结合改进聚类算法和混合遗传算法对模型展开求解，证明了所提算法在降低复杂垃圾收运问题时，具有良好的性能；赵今越等[3]针对带硬时间窗的垃圾收运路径问题，以最小化运输成本和车辆固定成本为目标建立了数学模型，并提出一种以改进蚁群算法为外部框架，混沌电磁场优化算法为内部模块的新型混合蚁群算法对城市生活垃圾分类收运问题进行求解；Alshraideh等[4]通过遗传算法和约定居民服务水平的概率约束方法研究了随机需求下带时间窗的周期性医疗废弃物收运路径问题；Lu等[5]提出了一个基于信息通信技术的智能将垃圾分类收集系统抽象为一个双目标数学模型优化垃圾收集问题的编程模型，证实了所提出的多目标混合算法遗传算法具有较好的优化效果，能有效地解决多个废物处理中心、废物转运站和废物桶的废物管理问题；Akhtar等[6]提出了一种改进的有容量车辆路径问题回溯搜索算法，该算法基于容量车辆路径问题模型与智能箱的概念，提供了最佳的垃圾收集路径，能有效降低收运经济成本和收运过程中的环境负效应。目前国内外针对生活垃圾收运路径优化的研究已有一定的基础。从现有研究来看，虽然部分学者考虑了碳排放等环境指标，但较少研究实际清运过程中车辆实时载重对碳排放量的影响，且在相关求解算法的选取上，目前大多数学者多用元启发式算法中较为常见的算法对问题展开求解，对于回溯搜索算法的研究应用较少。综上所述，本文以最小化运输成本和碳排放成本为目标构建生活垃圾收运路径优化模型，运用回溯搜索算法对该问题展开求解，并通过重构解空间优化回溯搜索算法，从而保证算法与问题的适配性，最终获取最优的生活垃圾收运路径方案，为相关企业降本增效。

2.模型构建

2.1 问题描述及符号说明

一辆或多辆垃圾收运车从车场出发，对区域内的所有垃圾收集点展开清运，当垃圾收运车满载或完成路径内最后一个垃圾收集点的清运工作后，垃圾收运车返回至车场卸载垃圾，重复上述过程，直至完成所有垃圾收集点的清运。根据问题描述，对本文的模型假设如下：1）垃圾收集点和车场的位置已知；2）各垃圾收集点的垃圾量已知且固定；3）垃圾收运车单一且车辆载重固定。模型所涉及的相关参数及定义如下：W，表示生活垃圾收集点的集合；Z，表示垃圾收运车的集合；Q，垃圾收运车的最大载重量；dij，表示节点i，j间的距离；P，表示单位油价；pe，表示单位碳排放成本；qi，表示生活垃圾收集点的垃圾量；Qc，表示收运车单位燃料消耗产生的碳排放量；fij，表示节点i，j间垃圾收运车的单位距离油耗；xijk，表示当垃圾收集点i到垃圾收集点j由车辆清运，xijk=1，否则；xijk=0，yik表示当垃圾收集点i由车辆k清运，yik=1，否则yik=0。

2.2 数学模型

本文以运输成本和碳排放成本最小为目标，其中燃油消耗通过“负载估计法”计算得出[7]，即

其中，ρe为车辆空载时的单位距离油耗，ρf为车辆满载时的单位距离油耗。

式（5）表示每个垃圾收集点被清运一次且只能由一辆车进行清运；式（6）表示进出平衡约束；式（7）表示每条收运路径上的餐厨垃圾总量不得大于垃圾收运车的最大载重；式（8）表示消除子回路，其中J为车辆k的收运垃圾点集合；式（9）表示决策变量间的逻辑关系；式（10）保证每辆车都从车场出发；式（11）和式（12）表示变量的取值约束。

3.算法设计

回溯搜索算法是一种新颖而强大的进化算法，该算法只有一个控制参数。相较于其他元启发式算法而言，该算法结构简单，有效、快速，能够轻松适应不同的优化问题，全局优化能力强。因此，本文选取回溯搜索算法对问题展开求解。由于回溯搜索算法主要用于求解连续空间的优化问题，而本文生活垃圾收运路径优化问题属于非连续空间的组合优化问题，故，需要对回溯搜索算法加以改进，重构解空间。具体的改进回溯搜索算法流程如下：

3.1 编码与解码

根据回溯搜索算法求解问题的适配性，重构解空间。采用非负整数编码的方式表示解空间，生活垃圾收集节点为1，2，3，…，n，车场编码为0，假设现有8个生活垃圾收集点，其编码为1～8，车场为0，种群中每个个体表示收运车对生活垃圾收集节点的清运顺序，再根据目标函数和约束条件对个体进行解码，获取车辆的实际清运路径，如图1所示。第一辆车从车场出发，对生活垃圾收集节点2、5、1清运完成后，返回车场。第二辆车从车场出发，对生活垃圾收集节点6、4、5、8、7、3清运完成后，返回车场。重复以上操作，直至完成所有生活垃圾收集节点的清运工作。

图1 编码解码示意图

3.2 构建初始种群

改进回溯搜索算法的种群由当前种群P和历史种群HisP构成，首先对P和HisP初始化。初始种群采用随机选择法和最邻近法相结合的方法构建。首先以车场为起点，随机选择一个生活垃圾收集点连接车场，再依据当前收运车剩余装载容量、当前垃圾收集点与剩余未被清运的生活垃圾收集点间的距离从剩余未被清运的收集点中选择一节点加入当前路径中，直至当前路径不存在可行插入节点时，新增一条初始路径。选择新的路径，重复上述步骤，直至所有节点均在路径中，产生初始配送方案，组成初始种群。

3.3 选择Ⅰ

首先随机生成两个数a和b，其中a～U（0，1），b～U（0，1），并基于式（13）进行历史种群的选择，然后通过随机排列准则打乱历史种群中个体的顺序，生成最终历史种群。

其中，:=表示前者随后者更新。

3.4 变异和交叉

改进回溯搜索算法通过变异和交叉获得试验种群T，T 的初始形态由变异产生，为了获得T，首先通过式（14）进行变异：mutant=P+F·（HisP-P）（14）

其中，F是控制参数，控制搜索方向矩阵（HisP-P）的幅度，F=d·rndn，rndn～N（0，1），d为问题维数。

其次，在交叉策略中引入映射矩阵，具体如下：随机生成均匀分布的随机数a和b，取值范围为0～1，如果a＜b，那么对于当前种群中的每个个体，计算要映射的元素数量：将种群中每个个体的元素数乘以混合率和0～1范围内的随机数，从而计算出需要映射的元素数。再根据需要映射的元素数，分别将映射数组中的前几个数设为0，其余则设为1。如果a≥b，则只有一个元素被映射为0，其余则设为1，被映射为0的元素的位置由每个个体的元素数乘以0～1范围内的随机数所得值确定。

则可表示为：

此时，T中可能存在非可行解，若存在非可行解，则试验种群中的个体随机选取可行域范围内的一个值替代。

3.5 选择Ⅱ

通过下式对种群进行更新：

其中，DistTn，d和DistPn，d分别表示T和P中个体的适应度值。如果当P中的个体最优解优于当前改进回溯搜索算法获得的全局最优解，则改进回溯搜索算法获得的全局最优解随当代种群中的个体最优解更新。

4.算例分析

改进回溯搜索算法程序在MatlabR2017a下完成，种群数目为30，个体长度等于生活垃圾收集点数与垃圾收运车辆数之和减1，混合率mixrate为0.8，最大迭代次数为100。

4.1 算例背景信息

重庆市是中国面积最大的十个城市之一，其中重庆主城区是全市的政治、经济、文化、交通、金融中心。2021年末，主城区城镇人口高达967.58万人，常住人口高达1038.99万人，GDP为10927.63亿元，占全市GDP总量的39.17%。人口和经济水平的增长使重庆主城区生活垃圾量也随之增加，致使现有生活垃圾收运系统不再适应重庆主城区的快速发展，迫切需要对现有垃圾收运系统进行调整。对此，本文进行生活垃圾收运路径优化研究，改善垃圾收运系统中的前端收集系统的现状，优化生活垃圾收运系统。

4.2 实例信息

通过调研，本文随机选取主城区的20个垃圾收集点、1个垃圾处理厂为研究对象展开生活垃圾收运路径优化研究。模型中涉及的相关参数设定为：垃圾收运车的最大载重为2000kg、单位油价为7元/kg、单位碳排放成本为0.025元/kg、单位燃料消耗产生的碳排放量为2.67kg/L、空载时的单位距离油耗为0.165L/km、满载时的单位距离油耗为0.377L/km。

4.3 结果分析

为了验证本文所提算法的有效性，在获取最终收运方案前，本文分别运用改进回溯搜索算法、遗传算法以及模拟退火算法独立运行10次实例算例，并选取最优解的收运距离为对比指标进行结果对比，结果如表1所示：

表1 算法有效性分析结果对比

从表1可以看出，本文所提算法求解到的最优收运方案总收运距离为177.8223km，分别比遗传算法和模拟退火算法所获得的最优解降低了21.44%、8.71%，证明本文所提算法具有良好的性能，可较好地解决生活垃圾收运路径优化问题。

运用改进回溯搜索算法对上述实例进行计算，得到餐厨垃圾收运最优路径如表2所示：

表2 生活垃圾收运路径方案

5.结论

本文针对生活垃圾收运路径优化问题，构建了一个以最小化运输成本和碳排放成本为目标的生活垃圾收运路径优化模型，并通过重构解空间设计了一个改进回溯搜索算法对模型展开求解。相较于遗传算法和模拟退火算法，本文所提算法分别使收运距离降低了21.44%和8.71%，说明本文所提算法具有良好的计算表现性，能较好地求解生活垃圾收运路径优化问题。