考虑排队时间的城市生活垃圾收运路径优化研究

文/朱虹宇 陈欢欢

随着城市现代化水平的提高，城市生活垃圾的数量呈现逐年增长的趋势，同时对于垃圾收运的效率也提出了巨大的要求。在垃圾收运过程中，车辆在中转站的排队等待时间占比较多，会影响到垃圾收运的整体效率，因此考虑排队时间的生活垃圾收运问题显得十分重要。基于当前的研究现状，本文考虑车辆在中转站的排队等待时间，以垃圾收运成本和车辆等待时间最小为目标函数，建立数学模型，并用模拟退火算法对该问题进行求解，验证本文模型的可行性。

1.引言

城市生活垃圾数量的增加给垃圾处理带来了极大挑战，研究垃圾收运路径优化问题，制定经济高效的城市生活垃圾收运方案显得尤为重要[1]。车辆在中转站的排队等待时间会影响到整个垃圾收运系统的运行效率，进而影响垃圾收运成本，因此考虑排队等待时间的城市生活垃圾收运问题十分重要。

2.问题描述

垃圾收运路径问题可以描述为：中转站有足够多的车辆完成垃圾收运，车辆从中转站出发，到各个垃圾收集点进行垃圾收运，车辆容量有限制，当达到车辆最大装载能力后返回中转站排队卸载垃圾，然后车辆继续返回之前没有被服务到的垃圾收集点进行服务，直到所有的垃圾收集点都被服务。然后车辆继续返回未被服务的垃圾收集点，继续上述工作，直到对所有的垃圾收集点都完成收运，车辆返回中转。建立模型以收运成本和等待时间最小为目标，合理安排收运路线。

3.模型建立

本文模型的参数说明如下：N为所有点的集合，Nc为垃圾收集点集合，N0表示中转站，xiju为0-1变量，当车辆u由节点i行驶至节j点时，xiju=1，否则，xiju=0。yiu为0-1变量，当车辆u访问节点i时，yiu=1，否则yiu=0。U为车辆集合，qu为车辆u的最大载重量，Vu为车辆u的行驶速度，gi为收集点i的垃圾量，C1、C2为车辆的固定成本和单位距离行驶成本，dij为两个设施点间的距离，tij表示车辆从节i点到节点j的行驶时间，tiu为u车对垃圾收集点i的服务时间，Tu为u车在中转站的等待时间，hu为u车在中转站的平均作业时间，wiu为u车到达垃圾收集点i的时间，wou为u车到达垃圾中转站的时间，β 为所有设施点不满足时间窗约束的惩罚成本。[Ai，Bi]为收集点i的期望时间窗。本文以垃圾收运成本和等待时间最小为目标建立模型。

obj1：运输距离产生的成本、固定成本、时间窗惩罚成本

模型中，（4）表示每个垃圾收集点只有一辆车进行服务；（5）表示每个垃圾收集点均需被服务，且只被服务一次；（6）表示车辆容量约束；（7）表示流量平衡；（8）表示每辆车从中转站出发，完成垃圾收集后又回到中转站。对双目标函数进行归一化处理[2]：

4.模拟退火算法

1953年Metropolis最早提出模拟退火算法的思想，Kirkptrick在1983年将模拟退火算法应用在解决组合优化的问题中[3]。模拟退火算法是一种依据固体退火原理，模拟加热熔化金属退火过程的智能算法，其以一定的概率选择劣质解，全局搜索能力强，并且不容易陷入局部最优，算法步骤如下：Step1：设置模型参数；Step2：随机生成初始解S；Step3：对解进行解码；Step4：计算目标函数；Step5：对当前解进行领域搜索，产生新解Snew；Step6：计算Δf=f（Snew）-f（S）；Step7：按Metropolis准则接受新解；若Δf＜0，接受新解，若Δf≥0，则以的概率接受新解；Step8：若满足终止条件，则输出最优解，否则退火T=T0*q，并返回步骤5。

5.算例分析

现以重庆市南岸区的垃圾收运路线优化为例进行分析，选取49个垃圾收集点和1个垃圾中转站，收运车辆的最大载重量为6吨，速度为35km/h，运输成本为3元/km，启动成本为400元/天。结合现有的相关文献[4，5]对本文进行参数设置：初始温度设置为T0=1000，降温速率设置为0.95，迭代次数为maxgen=1000，每个温度下的迭代次数设置为Lk=200。

从表2可以看出，本文模型的排队时间最低为0.0436小时，与不考虑排队时间的模型运行结果相比，排队时间减少了8.656小时，其最大改进幅度为99.5%。本文模型的车辆排队时间占比最小为0.27%，不考虑排队时间的模型计算出来的车辆排队时间占比为60.7%，排队时间占比明显减少，说明车辆的利用率有所提高。综合上述分析，本文模型能够有效减少排队时间和车辆工作时间，降低排队时间在整个垃圾收运过程所占比例，提高车辆工作效率，进而提高中转站整体的运行效率。

表2 结果对比分析

6.结论

本文对生活垃圾收运路径问题进行研究，重点考虑了车辆在中转站的排队时间，以最小化垃圾收运成本和排队时间为目标建立了数学模型，数值算例结果表明，本文所设计的考虑排队时间模型能更好的降低车辆排队时间。由于垃圾收运车在中转站的等待时间减少，进而使车辆资源和人力资源发挥最大效益，进一步提高垃圾清运效率，为解决垃圾收运的实际问题提供了更多的理论和决策支持，因此考虑排队时间的垃圾收运模型更具有现实意义和实用价值。