基于智能垃圾箱回收阈值的回收车辆路径问题

文/孟亚雷

本文针对智能回收车辆路径问题，考虑了智能垃圾箱回收阈值对回收公司运营成本的影响，构建了回收公司运营成本最小化的优化模型，并运用PSO粒子群算法进行车辆路径优化，并结合实例对模型和算法的有效性进行了验证。结果表明，回收公司通过确定合理的垃圾箱回收阈值进行车辆优化调度，可以有效降低回收运营成本，进而为智慧城市回收物流网络建设提供了理论借鉴。

1.问题描述

随着城镇化进程的加快与居民消费水平的提高，居民生活垃圾与日俱增，“垃圾围城”现象普遍存在，并成为新一轮城镇化发展的制约因素[1]。近年来，国家大力推动城市环卫系统与再生资源系统的两网融合，以减少资源消耗，降低环境污染。一种基于物联网技术的智能垃圾箱应运而生[2]。智能垃圾箱可以实施监测箱体内废弃物的填充状态，当达到一定的阈值后，回收公司派遣车辆进行清理。而不同的回收阈值将导致待清理的智能垃圾箱数量与废弃物回收量有所差异，对车辆调度与路径优化提出了更高的要求[3]。在车辆数量一定的情况下，为了提高回收效率并节约回收运输成本，需要综合考虑垃圾箱回收阈值对车辆调度的影响，进行合理的回收车辆路径优化问题研究。图1展示了基于智能垃圾箱回收阈值的回收车辆路径优化前后对比。

图1 基于智能垃圾箱回收阈值的回收车辆路径优化前后对比

由图1可知，图1（a）表示传统回收路径下，回收公司统一清理服务范围内的智能垃圾箱，由于部分垃圾箱内废弃物数量较少，回收公司派遣车辆进行清理，使得回收效率低下，且回收网络中存在长距离运输与交叉运输等现象，增加了回收运输成本。图1（b）表示基于智能垃圾箱回收阈值的回收路径，回收公司预先设定合理的回收阈值，当智能垃圾箱内废弃物填充状态达到回收阈值后，回收公司派遣车辆进行回收，并结合智能垃圾箱的分布情况与达到回收阈值的时间进行合理的路径优化，节约了废弃物运输成本，并提高了回收效率。

2.模型建立

基于智能垃圾箱回收阈值的回收车辆路径问题可表示为G=（N0，A）的无向图，N0为图中所有回收节点的集合，包括垃圾箱N与回收公司0，A为图中任意节点间弧的集合，xijv为0-1变量，当车辆v由节点i行驶至节点j时，xijv=1，否则，xijv=0。Uv为车辆v服务的智能垃圾箱的集合，V为所有车辆的集合，Dij为回收节点i与回收节点j之间的距离，fv为单位距离油价，o为回

收公司预先设定的回收阈值，mj表示智能垃圾箱的容量，qv表示车辆容量，L为车辆行驶最大距离，Q为回收公司处理能力，|Uv|为车辆v服务的智能垃圾箱的数量，[ej，lj]为智能垃圾箱回收时间窗，ajv为车辆到达节点j的时间，div为车辆离开节点i的时间，tijv为车辆由节点i行驶至节点j的运输时间，λe为车辆早于垃圾箱时间窗到达回收点的单位时间惩罚成本，λd为车辆晚于垃圾箱时间窗到达回收点的单位时间惩罚成本，kv为车辆租赁成本，δv为车辆维修成本，ρ 为回收品固定处理成本，σ 为回收品变动处理成本，wjv为车辆在节点j的等待时间，W 为无穷大常数。本文以回收公司运营成本最小化为目标，建立基于智能垃圾箱回收阈值的回收路径优化模型，如式（1）所示。

式（4）表示任一智能垃圾箱只能由一辆车进行服务，式（5）为流量守恒约束，式（6）为车辆容量约束，式（7）为车辆行驶距离约束，式（8）为回收公司处理能力约束，式（9）表示消除了车辆行驶子回路，式（10）-式（12）为车辆到达垃圾箱所处回收点的时间约束，式（13）为变量约束。

3.PSO粒子群算法

车辆路径问题是由Dantzig和Ramser于1959年首次提出，属于典型的NP-hard问题，学者们倾向于采用启发式算法进行求解。PSO粒子群算法是模拟鸟类捕食行为的一种智能优化算法，经常被用于求解路径优化问题[4]。粒子群算法搜索过程中，每一个粒子都表示一个优化解，拥有速度和位置两个属性。其中，离子飞行速度根据粒子搜索过程中的最优解（局部最优）和种群搜索过程中的最优解（全局最优）进行动态调整。粒子速度与位置更新公式如下所示。

式（14）为粒子速度更新公式，式（15）为粒子位置更新公式。式（14）与式（15）中n=1，2，3，...，N；N表示种群中粒子的个数；表示表示粒子的惯性权重，是0-1之间的随机数；vn，i表示在第i代搜索过程中粒子n的速度；c1与c2表示学习因子，一般c1=c2=2，r1与r2表示0-1之间的随机数；pbest表示粒子搜索过程中的最优解（局部最优），gbest表示种群搜索过程中的最优解（全局最优）；xn，i表示粒子在第i代搜索过程中的位置。粒子群算法具体实施步骤如表1所示。

表1 粒子群算法步骤

4.实例分析

以智能回收公司A与其服务范围内100个智能垃圾箱为例，研究基于智能垃圾箱回收阈值的回收路径优化问题。为了提高回收效率，提高智能回收服务水平，回收公司A需要预先设置合理的回收阈值o，并运用PSO粒子群算法进行合理的车辆调度。根据已有文献[5，6]与多次实验计算基础上，本文的算法参数设置为：种群规模popsize=100，算法最大迭代次数i_max=200，回收阈值o=80%，智能垃圾箱容量mj=50kg，回收车辆容量qv=500kg，单位距离油价fv=0.8元，回收公司处理能力Q=10000kg，单位时间惩罚成本λe=15，λd=20，车辆租赁成本kv=100元，车辆维修成本元δv=50，回收品固定处理成本ρ=1000元，回收品变动处理成本σ=0.15元。以回收公司运营成本最小化为目标，结合智能垃圾箱回收阈值对车辆路径进行优化，基于智能垃圾箱回收阈值的回收路径优化前后各项指标对比如表2所示。

表2 基于智能垃圾箱回收阈值的回收路径优化对比

由表可知，经过回收路径优化后，回收公司运营成本有效降低了33.80%，车辆使用数降低了3辆。其中，违反时间窗惩罚成本降低了78.39%，车辆租赁成本与维修成本均降低了37.50%，运输成本降低了36.94%。此外，为了进一步确定合理的回收阈值，本文探讨了不同回收阈值下满足回收条件的垃圾箱数量、回收品数量、车辆使用数与回收公司运营成本的变化情况，如表3所示。

表3 不同回收阈值下指标对比

由表可知，随着回收阈值由100%降低到70%，需要服务的智能垃圾箱数量逐渐增多，有32个增加值70个，收集到的回收品数量由1600kg增加值2569kg，回收车辆使用数由4辆增加值6辆。此外，本文通过对比不同回收阈值下回收车辆的平均装载率来确定最优的回收阈值。不同回收阈值下回收车辆的平均装载率、车辆使用数与回收公司运营成本的对比图如图2所示。

图2 不同回收阈值下指标对比

由表3和图2可知，当回收阈值为80%时，车辆平均装载率达到最大值，为90.60%，回收公司运营成本达到了最小值，为3491元；相比于回收阈值分别为100%、95%、90%和70%的场景，运营成本分别降低了23.76%、13.14%、11.87%和9.87%。综上所述，回收公司预先确定回收阈值为80%时，可以获得最低的运营成本。

5.结论

本文研究了基于智能垃圾箱回收阈值的回收车辆路径问题，考虑了当回收公司预先确定合理的回收阈值进行回收服务时运营成本的变化情况，建立了回收公司运营成本最小化的成本模型，并运用PSO粒子群算法进行求解。以智能回收公司A为例，对其服务范围内智能垃圾箱的回收路径进行优化，并对模型与算法的有效性进行了验证。研究结果表明，经过回收路径优化后，回收公司运营成本有效降低了33.80%，车辆使用数降低了3辆。不同回收阈值下优化目标的对比结果表明，相比与回收阈值为100%、95%、90%和70%的场景，回收公司预先确定80%为回收阈值时，车辆平均装载率最高，为90.60%，回收公司运营成本最低，为3491元。本文丰富了智能回收优化调度理论，为研究逆向物流车辆路径问题提供了新的研究思路，进而为智慧城市回收网络优化建设提供了方法借鉴。

引用出处

[1]林晶晶,毛雅婧,林宗平.“互联网+再生资源回收”模式推进机制的三方演化博弈研究[J].生态经济,2022,38(03):202-209.

[2]丁梦思,王琰,潘可可,陈学进,李桂荣.智能识别分类垃圾箱的认识与设计[J].科技创新与应用,2022,12(14):78-81.

[3]Hannan,M.A.,Akhtar,M.,Begum,R.A.,et al.Capacitated vehicle-routing problem model for scheduled solid waste collection and route optimization using PSO algorithm[J].Waste Management,2018,71:31-41.

[4]杨景明,穆晓伟,车海军,呼子宇,侯宇浩.多策略改进的多目标粒子群优化算法[J].控制与决策,2017,32(03):435-442.

[5]卿东升,邓巧玲,李建军,刘帅,刘鑫,曾素平.基于粒子群算法的满载需求可拆分车辆路径规划[J].控制与决策,2021,36(06):1397-1406.

[6]郭森,秦贵和,张晋东,于赫,卢政宇,于佳欣.多目标车辆路径问题的粒子群优化算法研究[J].西安交通大学学报,2016,50(09):97-104.