基于模拟退火算法的双目标优化模型在垃圾收集路径规划中的应用研究

摘要：文章针对城市垃圾车的“距离-时间”双目标优化问题，提出了一种基于模拟退火算法和线性加权法的优化模型，旨在同时优化最短行驶距离和最短运输时间。首先，该研究综合考虑了站点间的距离、运输时间、装载时间、倾倒时间和排队时间等多种因素，构建了双目标优化规划模型。其次，选择模拟退火算法进行求解，采用Metropolis准则和退火过程，以有效突破局部最优解。最终，通过调控退火温度等参数，确保了算法的有效性与效率。结果显示，该模型能够显著优化垃圾车的总行程和运输时间，为城市垃圾处理系统的规划与调度提供了坚实的理论基础。

关键词：模拟退火算法；线性加权法；双目标优化

中图分类号：TP311 文献标识码：A

文章编号：1009-3044（2025）02-0023-03 开放科学（资源服务） 标识码（OSID） ：

0 引言

随着城市化进程的加快，垃圾处理已成为城市管理的关键环节。垃圾车收集路径规划问题引起了大量中外学者的关注。明勇等人[1]提出了一种基于改进混合蛙跳和GIS的路径规划设计，其收敛速度和寻优能力非常突出。闫芳等人[2]则将动态模型分解为一系列静态模型，通过粒子群规划来进行路径规划设计，考虑的因素包括碳排放、车辆装载能力及二次污染等，较为全面。Nuortio等人[3]的主要贡献在于提出了GVNT元启发式的概念解模型及其成功的实际应用，包括为大型实际路由问题设计高效求解方法的若干实现指南。

在垃圾收集和运输过程中，提高车辆运行效率、降低运行成本已成为亟待解决的问题。垃圾车的运行不仅与站点之间的距离有关，还受到转运时间、装载时间、倾倒时间和排队时间等多种因素的影响。模拟退火法[4-7]作为一种启发式搜索方法，其跳出局部最优解的能力在解决复杂模拟问题时表现出了显著的性能。基于此，本文讨论了在停车场与处理站唯一的情况下，垃圾车“距离-时间”双目标优化的数学模型，旨在通过模拟退火算法找到同时满足时间最短和距离最短的解。

为了建立一个全面、准确的数学模型，本文首先明确了站间距离和转运时间等基本变量，并在此基础上构建了车辆总运行距离和总时间的计算公式。与以往研究不同，本文采用线性加权法[8]将双目标问题转化为单一目标进行优化，并通过数据标准化方法，使不同的距离和时间度量得以在同一尺度上进行比较。此外，通过参数控制，确保算法在有限时间内收敛至最优解。研究成果不仅有助于优化垃圾收集和运输过程，还为其他类似的双目标优化问题提供了有效的解决思路。

2 双目标优化模型建立与求解

2.1 基于路程与时间双目标最优的规划模型

在停车场与处理站唯一的情况下，构建了双目标最优距离-时间数学模型。通过模拟分解等方法，将多个影响因素转化为一个简单因素，最终得到满足时间和距离最优的解。

2.1.1 模型建立

车辆行驶的总距离：

D = Σdij，i = 1，...，13 （1）

式中：D 代表总距离，dij 代表站点i到站点j 之间的距离，包括停车场、收集站和处置站之间的距离，以及其他站点之间的连接距离。

垃圾车在每个收集点翻转垃圾所需的时间：

tf = 120 × [ K ] i ＼2 （2）

式中：tf 代表翻桶所用时间，Ki 代表第i 个收集点的站点垃圾桶数量。

处理站最多同时容纳 4 辆车倾倒，故存在以下约束方程：

tf = 90 + Qi，Sci gt; 4 （3）

式中： Sci 为垃圾处理站此时汽车总数， Q 为车辆等待前面汽车的时间。

Q = 900 - Sc （i - 4），i ≥ 5 （4）

车辆站点运行此征收时间：

tp = ts + tf + tr （5）

式中：tp 代表站点花费的总时间；ts 代表站点花费的启停时间；tr代表补偿时间。

每辆车的总运行时间为：

tBa = tdj +Σln （t ） p + tij + tis + tx + tsd （6）

式中：Ba 为汽车的编号；tdj 为停车调查到收集点的时间；tij 为第i 站到第j 站所需时间；tx 为垃圾车卸载时间；

车辆执行任务最长时间：

T = max{t } Ba ，a = 1，2，...，13 （7）

式中：T代表实际行驶总时长。

将总路程与时间的关系归一化，将数据归一化为：

时间-距离双目标建模：

min（0.8L* + 0.2T*） （10）

2.2 模型求解

2.2.1 模拟退火算法（SA）

Metropolis算法是退火过程的核心，旨在避免陷入局部最优解。1953年，Metropolis提出了重要性采样法。具体而言，Metropolis准则中，新解是否被接受取决于其优劣关系：若新解优于当前解，则直接接受；若新解劣于当前解，则以由温度决定的概率接受当前解。温度越高，接受概率越大；温度越低，接受概率越小[9]。

基于当前状态x （n）和某一指标（如梯度下降或能量） ，状态更新为 x （n + 1），系统能量由 E （n）变为E（n + 1）。定义系统由x （n + 1）转移至x （n + 1）的接受概率P如下：

如果系统的能量降低，则新状态的接受概率为1；如果系统的能量增加，则根据设定的概率P 进行处理：生成一个在区间[0，1]内均匀分布的随机数ε，若ε 大于P，接受这种状态转移；否则，拒绝该转移。接着进行下一步，重复上述过程。概率P 的大小与能量变化量和温度T之间的关系有关，如图1所示。

2.2.2 模拟退火参数调整

模拟退火算法以Metropolis算法为基础，但在不调整参数的情况下使用该算法可能会导致优化搜索速度过慢。为确保算法在合理的时间范围内达到稳定状态，必须谨慎设置控制其稳定的参数。在上述公式中，可调参数用T表示。若T设置过高，退火过程将过快，可能导致在局部最优解时过早终止；反之，如果T设置过低，计算时间将会增加。在实践中，退火温标被用来调节退火过程，最初T值较大，随着退火过程的进行，T值逐渐降低。

1） 起始温度越高，得到高效率的解决方案的概率就会越高，当然所需要的时间周期也就越长。因而起始温度 T（0） 应该选得足够高，以便接受所有的转移状态。

2） 指数式下降是退火速率中最便捷的下降方式：

T （n） = λT （n），n = 1，2，3，... （12）

式中：λ 为一个介于0.8到0.99之间的正数。对于每个温度，都需要进行符合条件的转移尝试。指数下降的稳定速率相对较慢，其他的下降方式如下：

3） 最终温度。退火过程的完成可以定义为在若干次更新迭代中没有新状态可供更新，或未达到预先设定的条件阈值。

2.2.3 模拟退火的步骤

目标函数、解空间和初始解三个部分是模拟退火算法的基本组成部分，图2详细展示了其算法流程[10]。

初始化：设定起始温度T，初始解状态为S，以及每个温度值对应的迭代次数L；

对k=1，…，L执行第（3）至第（6）步；

生成新解S'；

计算增量 ΔT = C （S'） - C （S），其中 C（S）为代价函数；

如果ΔT lt; 0，则接受S'作为新的当前解；否则，以概率exp （-Δ T／T"） 接受S'作为新的当前解；

当满足停止条件时，输出当前解作为最优解，程序结束。停止条件通常是在连续若干个新解未被接受时，算法停止；当T 逐渐减小至0时，返回第2步。

模拟退火算法产生的新解和接受解的步骤如下：

首先，在现有解的基础上，利用生成函数在解空间中构建一个新的解。为了简化后续的计算和验证过程，并缩短算法的执行时间，通常会采用一些简单的变换方法来生成新的解决方案。需要强调的是，所采用的变换方法将决定当前方案的基本结构，从而影响收敛稳定方案的选择。其次，计算新方案所带来的目标函数差异。由于目标函数的差异仅受到调整部分的影响，因此在进行计算时，采用增量计算法的优先级最高。在绝大多数情况下，这种方法是计算目标函数差异的最有效方式。

再次是考虑新解的可接受性来进行判断，接受的标准是其依据。其中，最常用的接受标准是Metropo⁃lis准则：当ΔT 小于0时，接受S'作为新的当前解S；如果ΔT≥0，则以概率exp （-Δ T／T"） 来决定是否接受S'作为新的当前解S。

最后，如果新方案被接受，则用新方案替代当前方案。接着，执行当前方案中与新方案生成时间相对应的转换部分，并调整目标函数值，从而完成一次迭代，进入下一轮试验。如果新方案被拒绝，则继续基于原有的当前方案进行下一轮求解。模拟退火算法不受初始值的影响，所得到的解与起始状态S（即算法迭代的起始点） 无关。该算法具有渐进回收性，理论上证明其以1的概率回收到整体最优解。此外，模拟退火算法还具备并行处理的能力[11-13]。

2.2.4 算法求解流程

采用MATLAB语言编写程序，对上述内容进行模拟退火算法优化，仿真过程中所需的控制参数设计如下：

1） 解空间。在解空间中所有固定的起始点及最终点的循环排列集合可用S 表示，得到D = {（π1，π2，...，π72）|π1 = 1，（π2，π3，...，π70 ）{1，2，...，70}} 的 循环排列，π71 = 71，π72 = 72。 其中，每一个循环排列表示70个收集点的回收路径。

2） 目标函数。目标函数（或称代价函数）为车辆所有的路径长度。要求：

进行一次迭代由三个步骤组成。

3） 新解的产生。假设上一步迭代的解为：

π1... πu - 1πuπu + 1... πv - 1πvπv + 1... πu - 1πuπu + 1... π72

①2交换法。选择任意两个序号u和v，将它们之间的顺序交换，使整体变为逆序，此时得到的新路径为：

π1... πu - 1πvπv - 1... πu + 1πuπv + 1... π102

②3变换法。选择任意的序号u、v 和w，将u 与v之间的路径插入到w 之后，得到的新路径为：

π1... πu - 1πv + 1... πwπu... πvπw + 1... π102

4） 代价函数差。根据第一步，此时路径差可用下述公式表示：

Δf = （dπu - 1，πv ） + dπu，πv + 1 - （dπu - 1，πu ） + dv，πv + 1 （16）

5） 接受准则：

如果f lt; 0，则接受新的路径；否则，以概率exp （-Δf ／T） 来决定是否接受新的路径。具体操作是生成一个在[0，1]区间内均匀分布的随机数rand，如果rand小于exp （-Δf ／T），则进行降温。降温时使用选定的降温系数α，新的温度T将被设定为αT（其中T为上一步迭代的温度） ，这里选择α = 0.997。

6） 结束条件：判断整个退火过程是否完成，可以通过预先设定的停止温度e = 0.01°来判断。如果T 小于e，流程结束，输出结果。

2.3 模型求解结果

利用双目标规划与模拟退火算法（SA） 的优化结果如表1所示。

所有车辆全部完成时间为6 805秒。

3 结论

本文聚焦于垃圾车在停车场与处理站唯一情境下的“距离-时间”双目标最优规划问题。通过构建数学模型，综合考虑站间距离、运输时间、本征时间、倾倒时间及排队时间等多个关键因素，采用模拟退火算法，将双目标优化问题转化为单一目标，并经过数据归一化处理，实现时间与路程的综合权衡。研究结果表明，合理规划可使垃圾车实现“时间-距离”最优解，显著提升垃圾处理效率，对城市垃圾处理系统的优化设计具有重要指导意义。该研究具有极强的实践性，能够应用于实际的垃圾收集车辆路径规划中，提高效率，降低成本，减少污染，具有显著的社会效益。在后续研究中，结合更多先进学习算法，并考虑更多现实因素，例如车辆容量限制、交通流量等，有望进一步完善模型，提高模型的实用性。

参考文献：

[1] 明勇，王华军.基于改进混合蛙跳和GIS的城市垃圾车回收路径优化设计[J]. 计算机测量与控制，2014，22（12）：4054-4057.

[2] 闫芳，邓德萍，柴福良.基于智能垃圾桶的垃圾分类动态收运路径优化问题研究[J].计算机应用研究，2022，39（12）：3620-3625.

[3] NUORTIO T，KYTÖJOKI J，NISKA H，et al.Improved route plan⁃ning and scheduling of waste collection and transport[J].ExpertSystems with Applications，2006，30（2）：223-232.

[4] 刘婧.基于改进模拟退火算法的船舶物流配送中心选址研究[J].舰船科学技术，2020，42（16）：199-201.

[5] 冉昊杰，王宏智.基于改进模拟退火算法的生鲜农产品配送中心选址[J].计算机与现代化，2022（10）：36-40.

[6] 于琪，张静.融合模拟退火参数的自适应遗传算法求解柔性作业车间调度问题[J].电脑与信息技术，2024，32（3）：12-16.

[7] 任小强.基于遗传和模拟退火算法的电动汽车充电调度策略研究[J].兰州职业技术学院学报，2024，40（3）：73-77.

[8] 连燕.基于加权和的多目标优化法在小流域治理中的研究[J].云南水力发电，2022，38（8）：66-70.

[9] 张广智，赵晨，涂奇催，等.基于量子退火Metropolis-Hastings 算法的叠前随机反演[J].石油地球物理勘探，2018，53（1）：153-160.

[10] 陈科胜，鲜思东，郭鹏.求解旅行商问题的自适应升温模拟退火算法[J].控制理论与应用，2021，38（2）：245-254.

[11] 罗渝东.基于改进模拟退火算法的台北市路划构建方法研究[J].时空信息学报，2024，31（2）：240-247.

[12] 孟浩德，吴征天，吴闻笛，等.基于改进模拟退火算法的灭火小车多目标路径规划[J]. 计算机与数字工程，2024，52（2）：394-398.

[13] 朱昱颖，金秋.基于模拟退火算法的电动汽车电池配送路径优化[J].科技与创新，2024（3）：31-33，37.

【通联编辑：张薇】