孙浩文 张唯嘉

摘要：近年来，垃圾分类成为社会关注的热点，而垃圾分类运输路径优化是其核心问题之一。本文介绍了垃圾分类运输路径优化问题的常见目标、约束与求解算法;最后展望了研究前景与方向。

关键词：垃圾分类;车辆路径优化;文献综述

引言

目前，我国的垃圾分类尚且处于初级阶段，很多地区只注重前端分类，在收运和处理时仍然是混合的，使得分类的实际效果大大降低。中端分类收运又是垃圾分类流程中最重要、费用最高的环节。因此，研究垃圾分类运输路径的优化非常重要，能有效降低成本，提高垃圾收运效率。

1数学模型

最小成本是垃圾分类运输最常见的目标[2]。根据研究重点的不同，在运输模型中添加不同的约束。

（1）容量约束。在收集路线问题中，车辆的容量通常是有限的。

（2）需求约束。确保至少有一辆收集车经过每个有需求的节点或弧线。    （3）一般性网络约束。比如文献[3]引入质量平衡约束，确保出发地与目的地的总流量相等。

（4）时间窗约束。时间窗对客户服务时间进行限制。通过在交通密度低的时期为每个客户指定一个时间窗口解决了交通拥堵问题。

（5）环境约束。考虑增加环境负担的约束。Chang[4]等将噪声控制、交通拥堵和空气污染控制约束纳入模型。

（6）司机午休。Bhat[5]引入司机午休时间，将员工的休息纳入考虑范围。

（7）紧凑性。路线紧凑度描述了路线重叠度。紧凑的路线成本更低，对于收集路径规划者和司机来说也更清晰。可以通过计算不同路线之间的交叉次数来衡量路线紧凑度。

总结来看，除了容量约束、需求约束等常规约束外，越来越多的学者开始将工人休息、环境约束等人文关怀方面的约束纳入考虑。

2 求解方法

从本质上讲，垃圾收集是一个车辆路径问题（VRP）。给定一组停靠点的单辆车辆的路线通常简化为旅行商问题 （TSP） 或中国邮递员问题 （CPP）。 TSP和有容量约束的CPP都属于 NP-hard 问题，没有完美的方法可以解决这类问题。

常见的精确优化方法有分支定界法和割平面法等。此外，元启发式算法是最主要的解决垃圾分类运输问题的方法。元启发式包括禁忌搜索、遗传算法、蚁群优化算法和模拟退火算法等[6][7]。禁忌搜索是除局部搜索外，经常使用的元启发式算法。通过禁忌表，可以对最近访问过的解决方案进行短期记忆，防止循环或陷入局部最优。文献[6]提出了一种使用不同类型邻域的局部搜索算法，后来又将禁忌搜索用于垃圾收集路径的优化，实验得出结论：与局部搜索算法相比，禁忌机制的引入有显著的改进。遗传算法试图通过模拟自然进化来寻找潜在的解决方案，通过交叉、变异、继承和选择等遗传算子来更新解。蚁群优化算法通过模拟蚂蚁寻找食物的行为，蚂蚁四处觅食时会产生信息素踪迹。这条路径被其他蚂蚁用来确定最短路径。最短路径的信息素轨迹会更强，因为通过这条路径返回蚁群的蚂蚁会比选择更长路径的蚂蚁更快地刷新信息素轨迹。较高的信息素水平会导致更多的蚂蚁选择短路径，最终找到最短路径。与其他模型相比，蚁群算法更容易实现运输路径的求解。文献[7]利用模拟退火算法比较了分类单仓运输和分类多仓运输的成本和运输效率，并提出了垃圾分类运输的建议。

除了元启发式，构造启发式也是常出现的优化算法。构造算法根据一些构造规则来确定一个路线，但不改进路线。每次选择离当前节点最近的作为下一个要访问的节点。在实践中，构造启发式常与元启发式相结合，用构造启发式的候选解决方案作为元启发式解决方案的起点。

3 结语

近年来，学界对垃圾分类的关注度在逐年提高。未来，可能会使用新技术驱动对有效的收集路线的研究。例如，使用GIS 计算垃圾收集路线的累积海拔增益，此信息可用于设计具有较小累积海拔增益的路线以节省燃料。再比如，现代 GPS 系统提供道路拥堵的实时更新。此外，环境问题在垃圾收集路线和管理中的重要性或将继续增加。

致谢

感谢2021年度上海理工大学第一批科研项目课程（13900010）对本文研究工作的资助。

参考文献

[1]BELIEN J， BOECK L D， ACKERE J V. Municipal Solid Waste Collection and Management Problems： A Literature Review[J]. Transportation Science，2014，48（1）：78-102.

[2]宋薇，劉建国，聂永丰.城市生活垃圾收运路线优化研究[J].环境卫生工程，2008（01）：11-12+15.

[3]Huang GH， Sae-Lim N， Liu L， Chen Z （2001） An interval-parameter fuzzy-stochastic programming approach for municipal solid waste management and planning. Environ. Modeling Assessment 6：271–283.

[4]Chang N-B， Wang SF （1996） Solid waste management system analysis by multi-objective mixed integer programming model. J. Environ. Management 48：17–43.

[5]Bhat VN （1996） A model for the optimal allocation of trucks for solid waste management. Waste Management Res. 14：87–96.

[6]Bianchessi N， Righini G （2005） Heuristic algorithms for the vehicle routing problem with simultaneous pick-up and delivery. Comput. Oper. Res. 34：578–594.

[7]牟能冶，程驰尧，蒋尔伟，田沛翎.基于多车型多行程的城市生活垃圾分类运输路径优化[J/OL].安全与环境学报：1-13[2021-12-22].https：//doi.org/10.13637/j.issn.1009-6094.2021.0527.