0 引言

车辆路径问题最早由Dantzig等^[1]提出，受到了学者们的广泛关注，并产生了许多关于车辆路径优化问题研究的变体，例如具有容量限制的车辆路径优化问题^[2-3]、考虑时间窗的车辆路径优化问题^[4-5]、动态车辆路径问题^[6-7]等。随着环境问题的日益突出，一些学者开始研究绿色车辆路径问题，通过不同的路径优化策略来减少能源消耗和碳排放。

Jabir等^[8]首次将二氧化碳排放量纳入车辆路径问题模型中，并成功解决了成本和碳减排目标之间的矛盾，抑制了经济成本的上升。Wu等^[9]在构建模型时考虑了碳排放量和经济成本，有效提高了垃圾收运的经济性与时效性。Qiao等^[10]综合考虑碳排放量、经济成本和惩罚成本，最终得到经济、环境和社会效益相平衡的收运解决方案。Dayanara等^[11]以垃圾收运次数、时间窗、碳排放为约束，构建了带垃圾转运中心的路径优化模型。Liu等^[12]考虑不同类型车辆协作进行垃圾收运并建立了优化模型，以达到将经济成本和碳排放量降至最低的目标。Li等^[13]全面考虑车辆的固定成本、提前和延迟的惩罚成本、燃料成本及车速、负载和道路坡度对燃料消耗的影响，开发了一种带有可变邻域搜索的混合遗传算法求解。周双牛等^[14]考虑车辆载重对碳排放量的影响，建立了以最短路径和极小化碳排放量为目标的绿色垃圾收运路径优化模型并验证了该模型的鲁棒性。王瑞等^[15]建立了以运输距离、油耗和碳排放相结合的多目标垃圾收运模型，并证明了该算法的有效性和实用性。陆徐龙^[16]以经济成本和碳排放成本最小为优化目标构建了数学模型，以满足垃圾收运低碳需求。李四兰等^[17]建立了以总成本最低为目标函数的冷链物流多温共配路径优化模型，以实现低碳收运。

车辆路径问题的求解算法主要分为精确算法和启发式算法2类。目前应用最为广泛的算法是启发式算法，主要包括遗传算法、蚁群算法、模拟退火算法等。韩孟宜^[18]将遗传算法与节约算法、大规模邻域搜索算法相结合，设计了一种混合遗传算法对模型进行求解。刘洁等^[19]设计了一种聚类蚁群算法对成都市生活垃圾收运路线优化进行求解。王晨頔^[20]建立了带时间窗的多目标优化模型，使用粒子群算法进行编程求解，得到不同模式下收运车辆的调度方案。赵今越等^[21]以最小化运输成本和车辆固定成本为目标建立了数学模型，并提出了一种改进蚁群算法求解模型，通过实例验证了模型的正确性及算法的有效性与优化能力。夏小云等^[22]提出了一种遗传蚁群融合算法求解大容量约束的车辆路径问题，并证明了该算法的优越性。

现有针对绿色车辆路径问题的研究中，很少综合考虑车辆固定成本、运输成本和碳排放成本及车辆容量与时间窗约束对运输成本的影响。对于这类问题的求解算法，蚁群算法具有较强的鲁棒性，但仍存在容易陷入局部最优的问题。本研究以湖州某地垃圾收运实例为研究对象，综合考虑配置车辆数、车辆行驶里程、车辆碳排放3个因素，构建绿色低碳的垃圾收运车辆调度与路径优化模型，并设计改进蚁群算法求解，寻找最优收运方案。

1 问题描述与基本假设

已知某环卫基地有垃圾收运车辆集合S和垃圾收集点集合N，面向绿色低碳的收运车辆调度与路径优化问题可以描述为：在垃圾分类收集的基础上，不同类型垃圾的收运车辆分别从环卫基地出发，到达各垃圾收集点。在满足车辆载重约束和时间窗约束的条件下，将垃圾收集并运送到环卫基地，最后将垃圾按照其类别分别集中运往不同的处理设施厂进行处理。在此基础上，构建以车辆固定成本、行驶成本和碳排放成本综合最优为目标的垃圾收运车辆调度与路径优化模型。考虑到实际应用中车辆调度与路径优化的复杂性及可求解性，为保证模型可行，将问题抽象化以构建数学模型，提出以下假设以简化问题：

(1) 各垃圾收集点、环卫基地等节点地理位置及其之间的距离已知。(2)各垃圾收集点的垃圾产生量在期望值范围内，不超过容量限制。(3)在收运工作时间窗、车辆最大载重约束、车辆行驶距离的范围内，垃圾收运车辆可任意行驶至多个节点。(4)收运车辆在垃圾收集点的装车作业时间固定且已知。(5)收运车辆的配置成本和单位距离运输成本固定且已知。(6)收运车辆行驶速度固定，且在工作时间内路况良好。(7)单个收运车辆只能服务1条回路。

2 模型构建

本研究构建的优化模型需要实现在作业时间窗约束、车辆载重约束和车辆行驶速度约束下车辆成本和二氧化碳排放成本最少。基于此，针对影响生活垃圾分类收运决策的目标和约束条件进行分析，以收运车辆调度与路径规划作为研究对象，采用VRP相关知识建立数学优化模型，具体模型如下：

(1)

(2)

式中，x_ijk和y_jk为0-1整数决策变量，其中，i和j为任一收集点；k为任一车辆。

目标函数：

(3)

该目标函数表示运营总成本最小化，由车辆固定成本、运输成本和碳排放成本构成。式中，N为垃圾收集点集合；K为车辆集合；d_ij为收集点i, j之间的距离；y_0jk为车辆k从集中点出发到达收集点j收运; c_k为车辆k的单位距离运输成本；f_k为车辆k的固定成本；F_e为单位距离碳排放量；δ为碳排放系数。

约束条件为：

(4)

(5)

式(4)和(5)表示每个垃圾收集点只能由1辆车进行作业且每条回路只能作业1次。

(6)

式(6)表示子回路消除约束。式中S为车辆访问收集点集合。

(7)

式(7)表示流量平衡约束，即进入某垃圾收集点和车辆数等于从该垃圾收集点离开的车辆数。

(8)

式(8)表示垃圾收运车辆均从车辆集中点出发。

(9)

式(9)表示垃圾收运车辆从车辆集中点出发，完成收运工作后必须返回车辆集中点。

(10)

式(10)表示车辆载重约束，即每辆车收运垃圾量不能超过该车最大载重量。式中，q_i为收集点i的垃圾量；Q为车辆最大载重量。

(11)

式(11)表示垃圾收运工作时间窗约束。式中，[S₁, S₂]为垃圾收运时间窗；w_ik为车辆k到达收集点i的时间。

(12)

式(12)表示任一垃圾收集点作业时间须在规定时间内完成。式中，[a_i, b_i]为收集点i的工作时间窗。

垃圾车辆的总运营成本包括车辆固定成本和行驶过程中的运输成本。

车辆固定成本包括车辆购置成本、车辆维护成本、车辆保险费用、工作人员工资4部分。垃圾收运车辆的使用年限约为10 a，其中车辆购置成本按照10 a使用期限分摊至每天，每辆垃圾收运车辆配备2名司机。对于可变成本，以燃油费作为计算依据。综上，每辆垃圾收运车辆的固定成本和运输成本为：

(13)

式中，f_k为每辆车的固定使用成本; f_p为车辆购置成本; f_m为车辆维护成本; f_w为车辆保险费用; f_i为工作人员工资成本。

(14)

式中，c_k为垃圾收运车辆的运输成本；d_k为车辆行驶直线距离；c_f为每公里燃油费。需要注意的是，本研究通过设置非直线系数α描述车辆行驶过程中的实际距离。非直线系数是指路段起讫点间的实际交通距离与两点间空间直线距离之比，棋盘式路网的非直线系数一般为1.2~1.5。根据湖州市实际路网分布特征，将非直线系数设置为1.4。

车辆碳排放量与燃油消耗量和燃油类型直接相关，为了更加准确地测算车辆行驶过程中的碳排放量，引入碳排放系数，并采用转化法直接将车辆燃油消耗量与相对应的碳排放系数相乘，将燃油消耗量转化为碳排量。通过分析，采用线性关系进行油耗和二氧化碳排放量之间的转换，计算式为：

(15)

式中，E_c为每公里二氧化碳排放量; δ为二氧化碳排放系数; F_e为每公里油耗量。

为使碳排放量考虑到目标函数总成本中，通过企业缴纳的碳税衡量碳排放成本。垃圾收运车辆收运时产生的碳排放成本的计算公式如下：

(16)

式中，E为碳排放成本; C_m为每单位碳排放的碳税。

3 改进蚁群算法

为在规定时间内求解垃圾收运最优方案，设计了改进蚁群算法对模型求解，首先改进算法的状态转移方式和信息素更新方式。然后，通过构建最大最小蚁群算法解决算法容易陷入局部最优的问题。最后，在算法中嵌入2-opt局部搜索算法对路径节点进行调整，并进行早熟收敛判断。求解算法具体步骤如下。

(1) 状态转移方式

本研究首先针对基本蚁群算法的状态转移方式进行改进。在蚁群算法中，蚂蚁根据每条路径上的信息素浓度进行寻优，即蚂蚁根据信息素η从节点i转移到节点j。因此，为保证每个垃圾收集点都能够被选择和搜索，本研究综合考虑了收运工作时间窗约束和车辆载重约束条件，对状态转移方式进行改进，式(17)显示了状态转移概率的计算方式。

(17)

式中，n为所有垃圾收集点结合；τ_ij为路径(i, j)上的信息素浓度；α(α≥0)为信息素启发因子；β(β≥0)为期望启发因子；λ(λ≥0)为收运车辆载重因子；τ_in为蚂蚁从收集点i到下一步可能会选择的收集点n的路径上的信息素浓度；η_in为路径(i, n)上的能见度; k_in为车辆到达下一步可能会选择的收集点n的载重率; p为在区间[0, 1]内的随机数；p₀为固定值，其取值范围为(0, 1)；η_ij为路径(i, j)上的能见度，即从收集点i到j的启发程度；k_ij为收运车辆的载重率。

通过上述公式可以发现，当垃圾收集点i到j之间的信息素浓度τ_ij越大，且距离d_ij越短，车辆的载重率k_ij越高时，蚂蚁选择路径(i, j)的概率也就越大。

(2) 信息素更新方式

在蚂蚁进行新路线探索的过程中，会在其经过的路径上释放信息素，同时信息素也会随时间挥发。一般在蚂蚁构造出路径之后，会对残留的信息素进行更新。通过在可行路径及目标函数最小路径上增添额外信息素的方式对信息素进行更新，更新方式为：

(18)

式中，ρ为信息素挥发因子；1-ρ为信息素残留因子；当路径(i, j)为可行路径或目标函数最小路径时，在路径(i, j)上添加额外信息素Δτ_ij^k或Δτ_ij^*。

(3) 最大最小蚁群算法

通过引入最大最小蚁群算法解决算法过早收敛的问题，即蚂蚁形成路径后，每条路径上的信息素浓度均存在最大值和最小值，将每次更新后的信息素浓度保持在[τ_min, τ_max]区间范围内，从而防止路径间的信息素浓度差距过大。最小信息素浓度可增加对最优解进行探索的可能性，而最大信息素浓度可保证经验对于蚂蚁的启发性。最大最小蚁群算法的公式为：

(19)

(4) 过早收敛判断

将蚁群中单个蚂蚁的聚集程度和解在进行多次迭代后是否趋于平稳，作为判断算法是否过早收敛的依据。针对蚁群中单个蚂蚁的聚集程度，用式(20)表示为：

(20)

式中，σ²为蚁群适应度方差；f_i为第i个蚂蚁的适应度值；f_avg为蚁群平均适应度值。通过对f进行不断取值限制σ²的大小。当σ²小于最小适应度方差σ_min²时，种群个体被认为产生聚集，算法陷入过早收敛，因此要进一步对所求解进行优化。

(5) 解的进一步优化

在蚁群算法中嵌入2-opt算法以进一步解决蚁群算法容易陷入局部最优的问题。2-opt算法属于一种局部搜索算法，其原理是通过对交换解的2条边对其进行更新，直至求得最优解。针对本研究构建的垃圾收运车辆调度与路径优化模型，首先通过计算求得初始解，然后针对初始解中的2条路径进行交换，重新计算运营成本和路径长度，判断新路径是否满足约束条件并改善目标函数，由此得到更高质量的解。通过此流程进行解的进一步优化，直至求得最优收运方案。

4 实例结果对比与分析

以浙江湖州某地垃圾收运为研究对象，在垃圾收集点进行空间聚类处理的基础上，安排垃圾收运车辆调度方案。通过对比分析目前垃圾收运实际应用方案、聚类情况下改进蚁群算法、遗传算法、粒子群算法和未聚类情况下改进蚁群算法的优化方案，以车辆固定成本、运输成本和碳排放成本均最小为目标，确定车辆最优垃圾收运路径的方案。

4.1 垃圾收集点空间聚类

分析处理2021年1月至2021年3月湖州某地63个小区98个垃圾收集点不同类型垃圾每日垃圾量的24 984条数据，420条垃圾收集站点信息和经纬度坐标数据，2021年12月14日湖州市垃圾收运车辆作业时的65 499条有效GPS轨迹数据，包括收运车辆的经纬度坐标、位置、速度、时间和状态等。通过空间聚类，将98个垃圾收集点划分为5个子区域(如图 1所示)，可同时安排多辆收运车在不同区域工作，能够有效减少垃圾收运时间和收运路程，提高效率、降低成本。

4.2 收运车辆调度优化方案

通过上述设计的基于改进蚁群算法的求解步骤对模型进行求解，迭代200次后得到最优收运方案，并结合QGIS对收运路线进行一体可视化操作，迭代曲线和最优收运路径如图 2和图 3所示。其中，车辆行驶总距离为98.86 km，总成本为2 488.91元，车辆配置数量为5辆。

各区域具体收运顺序如表 3所示。由表 3可知，A~E区域的垃圾收运工作由编号1~5的5辆车来完成。综合考虑收运成本、行驶距离和作业时间等因素，安排1号车首先完成A区域8个垃圾收集点的收运工作并回到环卫基地，再从环卫基地出发，完成E区域的收运工作。C区域需3号和4号车同时工作，才能在规定的工作时间内完成收运。

根据湖州市实际车辆轨迹数据分析结果可知，目前垃圾收运实际应用方案的总行驶距离为132.34 km，未聚类情况下基于改进蚁群算法求解得到的收运方案车辆总行驶距离为111.75 km，遗传算法收运方案的总行驶距离为108.81 km，粒子群算法收运方案的总行驶距离为110.04 km，改进蚁群算法收运方案的总行驶距离为98.86 km。每种方案具体使用车辆数和行驶距离对比如图 4所示。可以看出，在满足车辆容量约束和工作时间窗约束的前提下，基于改进蚁群算法的收运路径优化方案在车辆配置和行驶距离上均优于其他算法。

垃圾收运方案各成本对比如图 5所示。

目前垃圾收运实际应用方案的车辆固定成本、运输成本和碳排放成本分别为3 428.64，463.19，113.81元；未聚类情况下基于改进蚁群算法求解得到的收运方案的车辆固定成本、运输成本和碳排放成本分别为2 571.48，391.13，96.11元；遗传算法收运方案、粒子群算法收运方案和改进蚁群算法收运方案的固定成本均为2 142.9元，运输成本分别为380.84，385.84，346.01元，碳排放成本分别为93.58，94.81，85.02元。

综上所述，基于空间动态聚类的改进蚁群算法得到的垃圾收运方案最优，总成本最低，为2 573.93元。

5 结论

(1) 基于绿色低碳的垃圾收运车辆调度与路径优化问题，积极响应“碳中和”政策，将碳排放量折算成碳排放成本，综合考虑企业经济效益和环境效益，构建了面向绿色低碳的垃圾收运车辆调度与路径优化模型，并设计了改进蚁群算法求解所建立的模型。

(2) 为验证模型与算法的有效性和实用性，基于湖州市某地生活垃圾收运实例，利用不同算法求解了最优收运方案并进行了对比分析。结果表明：本研究提出的改进蚁群算法能求解模型，且与实际应用方案相比具有更优的经济与环境效益；与其他算法求解结果相比，改进蚁群算法求解速度更快，方案更优；构建的考虑碳排放的模型能在降低总成本的基础上减少收运流程的碳排放污染，有效提升企业社会经济效益。