基于车辆路径优化的城市垃圾分类运输调度模型研究

A Vehicle Routing Optimization Model for Urban Waste Classification Transportation Scheduling

摘要: 随着城市垃圾分类政策的全面推进，高效、低碳的垃圾收运系统成为城市管理的关键。本文构建了一个融合车辆路径优化、中转站选址与碳排放控制的综合优化模型，对垃圾分类运输系统进行系统分析。首先，将垃圾收集问题抽象为带容量约束的车辆路径问题，建立单类型车辆路径优化模型。其次，考虑四类垃圾由专用车辆运输，构建多类型车辆路径优化模型。最后，引入中转站选址、时间窗与碳排放因素，建立带时间窗的多类型车辆路径优化模型。针对模型规模大、变量耦合度高的特点，设计了两阶段求解算法：首先利用自适应大邻域搜索算法确定中转站选址及收集点分配，再采用并行蚁群算法优化多类车辆路径。研究结果表明，该模型能有效降低运输距离与系统总成本，提升垃圾分类运输系统运行效率，为城市垃圾分类运输调度提供理论依据与决策支持。

Abstract: With the comprehensive implementation of municipal waste classification policies, the development of an efficient and low-carbon waste collection and transportation system has become a critical challenge in urban management. This paper constructs an integrated optimization model that incorporates vehicle routing optimization, transfer station siting, and carbon emission control to systematically analyze urban waste-sorted transportation systems. Initially, the waste collection problem is abstracted as a capacitated vehicle routing problem, leading to the formulation of a single-type vehicle routing optimization model. Subsequently, considering that four types of waste are transported by dedicated vehicles, a multi-type vehicle routing optimization model is developed. Finally, factors such as transfer station location, time windows, and transportation-related carbon emissions are incorporated to establish a comprehensive multi-type vehicle routing optimization model with time windows. Given the large-scale nature of the model and the high degree of variable coupling, a two-phase solution algorithm is designed. The first phase employs an adaptive large neighborhood search algorithm to determine transfer station locations and collection point allocations, while the second phase utilizes a parallel ant colony optimization algorithm to optimize transportation routes for multiple vehicle types. The results demonstrate that the proposed model effectively reduces transportation distance and total system costs while improving the overall operational efficiency of waste-sorted transportation systems, providing theoretical foundations and decision-making support for urban waste classification transportation scheduling.

1. 问题描述与分析

1.1. 问题的背景

随着我国城市化进程加快和居民生活水平提升，城市生活垃圾产生量持续增长，已逼近各地处理能力上限，现有垃圾管理体系面临严峻挑战。当前垃圾分类依赖居民按标识投放，由工作人员分类收集、运输至处理设施。然而，垃圾运输受车辆容量与载重、中转站运营时间与处理上限、运输成本及碳排放控制等多重因素制约。因此，亟需综合考虑垃圾产生量与类型、收运点与处理厂间距离、车辆性能、行驶时间及碳排放等条件，对运输路径与调度方案进行优化，以降低总行驶距离、运输成本和中转站建设投入，实现高效、低碳、经济的垃圾分类收运体系，助力城市可持续发展与环境治理。

1.2. 问题的提出

在城市垃圾分类运输过程中，各收集点会产生不同类型的垃圾，不同类别垃圾需由对应的专用车辆进行运输。该城市有30个垃圾分类收集点，其坐标及四类垃圾量见表1，其中处理厂为坐标原点。同时车辆在运输过程中受到载重量、容积及运输成本等因素的限制，且车辆每日行驶时间也存在一定约束，见表2。此外，为提高运输效率，可在城市中若干候选位置设置垃圾中转站，将收集点垃圾先运输至中转站，再统一转运至最终处理厂，中转站候选位置及参数见表3。

为提高城市垃圾分类运输系统的运行效率，需要综合考虑垃圾收集点的空间分布、不同类别垃圾产生量、运输车辆类型、中转站布局等因素，对垃圾运输与调度过程进行系统优化。

Table 1. Waste distribution at classification collection points

表1. 垃圾分类收集点的垃圾分布

收集点编号	$x_i$ (km)	$y_i$ (km)	厨余垃圾$w_{i,1}$ (吨)	可回收物$w_{i,2}$ (吨)	有害垃圾$w_{i,3}$ (吨)	其他垃圾$w_{i,4}$ (吨)
1	12	8	0.72	0.12	0.06	0.3
2	5	15	1.38	0.23	0.05	0.64
3	20	30	1.08	0.18	0.04	0.5
4	25	10	1.55	0.31	0.06	1.18
5	35	22	1.62	0.27	0.05	0.76
6	18	5	1.76	0.384	0.096	0.96
7	30	35	0.77	0.168	0.042	0.42
8	10	25	1.02	0.238	0.068	0.374
9	22	18	1.32	0.176	0.044	0.66
10	38	15	1.45	0.3	0.075	0.675
11	5	8	1.35	0.27	0.108	0.972
12	15	32	1.87	0.51	0.068	0.952
13	28	5	2.58	0.516	0.129	1.075
14	30	12	1.134	0.21	0.063	0.693
15	10	10	0.78	0.13	0.065	0.325
16	20	20	0.768	0.192	0.08	0.56
17	35	30	0.72	0.27	0.09	0.72
18	8	22	1.595	0.348	0.087	0.87
19	25	25	1.5	0.36	0.09	1.05
20	32	8	1.08	0.18	0.09	0.45
21	15	5	0.912	0.19	0.038	0.76
22	28	20	0.9	0.195	0.075	0.33
23	38	25	0.99	0.27	0.072	0.468
24	10	30	1.44	0.24	0.048	0.672
25	20	10	1.74	0.319	0.116	0.725
26	30	18	1.17	0.39	0.13	0.91
27	5	25	1.7	0.34	0.17	1.19
28	18	30	2.64	0.66	0.044	1.056
29	35	10	0.864	0.216	0.072	0.648
30	22	35	0.986	0.204	0.085	0.425

Table 2. Parameters of four types of transport vehicles

表2. 四类运输车辆参数

垃圾类型	载重$Q_k$ (吨)	容积$V_k$ (m^3)	距离成本$C_k$ (元/km)	碳排放系数${\alpha }_k$ (kg/km)	碳排放系数${\beta }_k$ (kg/吨)
厨余垃圾	8	20	2.5	0.8	0.3
可回收物	6	25	2	0.6	0.2
有害垃圾	3	10	5	1.2	0.5
其他垃圾	10	18	1.8	0.7	0.25

Table 3. Transfer station candidate locations and parameters

表3. 中转站候选位置及参数

中转站编号	$x_i$ (km)	$y_i$ (km)	建设成本$T_j$ (万元)	时间窗口$\left[a_f,b_f\right]$ (小时)	存储容量$S_k$ (吨)
31	15	15	50	[6, 18]	[20, 15, 5, 30]
32	25	25	60	[8, 16]	[25, 20, 6, 35]
33	35	15	45	[10, 14]	[18, 12, 4, 25]
34	10	25	55	[7, 17]	[22, 18, 5, 32]
35	20	30	58	[9, 15]	[24, 22, 7, 38]

1.3. 问题的分析

城市垃圾分类运输系统的优化调度问题需要综合考虑垃圾收集点的位置与垃圾产生量、不同类型垃圾运输车辆的参数约束以及中转站的选址等多种因素。因此，该问题属于具有多重约束条件的复杂组合优化问题。为降低问题求解难度并逐步逼近实际应用场景，本文采用分阶段建模与逐层扩展的分析思路对该问题进行研究。

第一阶段：单类型车辆路径优化。首先考虑最基础的情形，假设仅使用一种通用运输车辆即可完成所有垃圾的收集与运输任务。在该假设下，问题可抽象为一个单目标优化问题，其本质为经典的带容量约束的车辆路径问题(Capacitated Vehicle Routing Problem, CVRP) [1]。以所有车辆的总行驶距离最小为目标函数，同时结合车辆载重容量限制及收集点垃圾量构建容量约束和路径连续性约束等条件，从而建立单一车辆类型车辆路径模型(Single-Type CVRP, STCVRP)，为后续复杂模型的构建提供理论基础。

第二阶段：多类型专用车辆协同调度路径优化。考虑四类垃圾(厨余垃圾、可回收物、有害垃圾及其他垃圾)必须由专用运输车辆分别收运，可将原问题分解为四个并行的CVRP子问题，构建多类型车辆路径优化模型(Multi-Type CVRP, MTCVRP)，并将目标函数扩展为最小化四类垃圾运输车辆的总运行成本或总行驶距离。

第三阶段：融合中转站选址、时间窗与碳排放的综合路径优化。在第二阶段模型的基础上还需要考虑中转站的选址问题。中转站具有作业时间限制，因此车辆到达中转站必须满足相应的时间窗约束。与此同时，车辆碳排放量通常与车辆载重和行驶距离呈正相关关系。因此，在确定运输路径后，还需通过合理规划车辆行驶顺序，降低整体碳排放水平。基于上述因素，本文构建了带时间窗多类型车辆路径优化模型(Transfer Station-CVRP with Time Windows, TCVRPTW)，其优化目标为最小化每日运输成本与中转站建设成本之和，并兼顾运输效率与环境效益。

鉴于该综合优化问题具有规模大、变量多、约束复杂且耦合性强等特点，传统精确算法难以在合理时间内获得高质量解。因此，本文设计了一种两阶段启发式求解算法。在第一阶段，采用自适应大邻域搜索算法(Adaptive Large Neighborhood Search, ALNS) [2]对中转站选址及垃圾收集点分配问题进行优化，以获得较优的中转站选址与服务区域划分；在第二阶段，在已确定的中转站网络结构下，对每类垃圾运输任务分别采用蚁群算法(Ant Colony Optimization, ACO) [3]进行车辆路径优化，以提高求解效率并获得较优的运输路径方案。

2. 问题假设

1) 运输车速度恒定；

2) 装卸垃圾的时间被忽略；

3) 节点距离走直线，任意两个节点相通，没有交通堵塞；

4) 车辆数量充足；

5) 该城区每天的垃圾运输需求、交通情况稳定不变；

6) 在有中转站的情况下，运输车需要先将垃圾收集点的垃圾暂存中转站；

7) 垃圾容重符合实际情况；

8) 不要求运输车必须先到中转站再前往垃圾收集点。

3. 模型的建立与求解

3.1. 模型的建立

3.1.1. STCVRP模型的建立

首先，考虑单类型车辆路径优化，即城区拥有1个垃圾收集厂和$n$ 个厨余垃圾垃圾收集点，而专用车辆有最大载重$Q$ 和最大容积$V$ 。所以，建模过程中需要引入二元决策变量以表示路径选择，同时为实现如消除子环的约束，还需引入连续变量，所以采用混合整数规划(MIP) [4]来进行建模。

已知收集点坐标$\left(x_i,y_i\right)$ 、垃圾产生量$w_i$ 和最大载重$Q$ 。为了表示路径和节点方便，还需定义路径索引为$v\in R$ ，处理厂和垃圾收集点索引集合$N=\left\{0,1,\cdots ,n\right\}$ ，为0时表示的是处理厂。

为了计算厨余垃圾专用车辆的总运输路程，定义一个二元决策变量来表示车辆运输的第$v$ 条路径是否从收集点$i$ 行驶到$j$ ，如下

$A_{v,i,j}\in \left\{0,1\right\}v\in R,i\in N,j\in N,i\ne j$ (1)

定义收集点$\left(i,j\right)$ 之间的距离为

$d_{i,j}=\sqrt{{\left(x_i-x_j\right)}^2+{\left(y_i-y_j\right)}^2}$ (2)

其中$x$ 和$y$ 为收集点的坐标值，通过式(1)和式(2)计算出目标函数，如下

$\min {\displaystyle {\sum }_{v\in R}{\displaystyle {\sum }_{i\in N}{\displaystyle {\sum }_{j\in N}{d}_{i,j}\cdot A_{v,i,j}}}}i\ne j$ (3)

在满足目标的同时，这个运输方案还需要满足下列约束条件。

收集点需求满足约束：

首先，每个垃圾收集点都需要被规划在内，否则收集垃圾的需求未被满足。其次，如果多次到达同一个收集点会产生重复行驶距离，导致总距离增加，违背优化目标。则需要满足下式：

${\displaystyle {\sum }_{v\in R}{\displaystyle {\sum }_{j\in N}{A}_{v,i,j}}}=1\forall i\in N/\left\{0\right\}$ (4)

载重约束：

已知运输车辆有最大载重$Q$ ，那么方案中的每条路径的垃圾收集总量不能超过这个载重限制。则需要满足下式：

${\displaystyle {\sum }_{i\in N/\left\{0\right\}}{\displaystyle {\sum }_{j\in N}{w}_i\cdot A_{v,i,j}}}\le Q\forall v\in R$ . (5)

最大容积约束：

已知运输车辆有最大容积$V$ ，那么方案中的每条路径的垃圾收集总量不能超过这个容积限制。定义垃圾的密度为$\rho$ ，则需要满足下式：

${\displaystyle {\sum }_{i\in N/\left\{0\right\}}{\displaystyle {\sum }_{j\in N}\frac{w_i\cdot A_{v,i,j}}{\rho }}}\le V\forall v\in R$ (6)

路线约束：

每条路径的起点与终点都需要为处理厂，即使得每条路径都要包含节点0。则满足：

$\{\begin{array}{l}{\displaystyle {\sum }_{j\in N}{A}_{v,0,j}}=1\forall v\in R\hfill \\ {\displaystyle {\sum }_{i\in N}{A}_{v,i,0}}=1\forall v\in R\hfill \end{array}$ (7)

同时，还需要保证路径的连续性，即对于每个垃圾收集点，进入该点的路径数等于离开该点的路径数。则需要满足下式：

${\displaystyle {\sum }_{i\in N}{A}_{v,i,h}}-{\displaystyle {\sum }_{j\in N}{A}_{v,h,j}}=0\forall h\in N/\left\{0\right\},\forall v\in R$ (8)

其中，$h$ 也是收集点的索引。

时间约束：

由于垃圾处理厂的工作时间为6点到18点，假设方案中每条路径都安排一辆车，那么需要满足每条路径的用时要在工作时间范围内。则须满足下式：

$\frac{{{\displaystyle \sum }}_{i\in N}{{\displaystyle \sum }}_{j\in N}{d}_{i,j}\cdot A_{v,i,j}}{40}\le 12\forall v\in R$ (9)

子回路消除约束：

为了防止每条路径出现不包含收集厂的闭合回路，选择采用MTZ约束[5]来消除子回路[6]。定义一个辅助决策变量$B_{v,i}$ ，满足$\forall i\in N,B_{v,i}\ge 0$ ，得到下式：

$B_{v,i}-B_{v,j}+\left(n+1\right)A_{v,i,j}\le n\forall i,j\in N,i\ne j,\forall v\in R$ (10)

综上所述，本模型采用了混合整数规划，定义了二元决策变量$A_{v,i,j}$ 和辅助决策变量$B_{v,i}$ ，建立了STCVRP模型，如式(11)所示，其中$i\ne j\ne h$ 。

$\{\begin{array}{l}\min {\displaystyle {\sum }_{v\in R}{\displaystyle {\sum }_{i\in N}{\displaystyle {\sum }_{j\in N}{d}_{i,j}\cdot A_{v,i,j}}}}\\ s.t.\{\begin{array}{l}{{\displaystyle \sum }}_{v\in R}{{\displaystyle \sum }}_{j\in N}{A}_{v,i,j}=1\forall i\in N/\left\{0\right\}\\ {{\displaystyle \sum }}_{i\in N/\left\{0\right\}}{{\displaystyle \sum }}_{j\in N}{w}_i\cdot A_{v,i,j}\le Q\forall v\in R\\ {{\displaystyle \sum }}_{i\in N/\left\{0\right\}}{{\displaystyle \sum }}_{j\in N}\frac{w_i\cdot A_{v,i,j}}{\rho }\le V\forall v\in R\\ \{\begin{array}{l}{\displaystyle {\sum }_{j\in N}{A}_{v,0,j}}=1\forall v\in R\hfill \\ {\displaystyle {\sum }_{i\in N}{A}_{v,i,0}}=1\forall v\in R\hfill \end{array}\\ {\displaystyle {\sum }_{i\in N}{A}_{v,i,h}}-{\displaystyle {\sum }_{j\in N}{A}_{v,h,j}}=0\forall h\in N/\left\{0\right\},\forall v\in R\\ \frac{{{\displaystyle \sum }}_{i\in N}{{\displaystyle \sum }}_{j\in N}{d}_{i,j}\cdot A_{v,i,j}}{40}\le 12\forall v\in R\\ B_{v,i}-B_{v,j}+\left(n+1\right)A_{v,i,j}\le n\forall i,j\in N,\forall v\in R\end{array}\end{array}$ (11)

3.1.2. MTCVRP模型的建立

相较于3.1.1节仅考虑单一车辆类型的情形，实际垃圾分类运输需分别处理厨余垃圾、可回收物、有害垃圾和其他垃圾四类，且各类垃圾须由专用运输车辆独立收运。由于不同车型互不兼容，四类运输任务在逻辑上相互独立，仅共享道路网络，因此可将原问题分解为四个并行的单类型带容量约束的车辆路径问题(STCVRP)。在此基础上，通过整合四类车辆的优化结果，构建多车型带容量约束的车辆路径问题(MTCVRP)模型，在满足各自容量与服务约束的前提下，协同优化整体运输方案，以最小化系统总运输成本。

每类车辆的载重限制$Q_k$ ，容积限制$V_k$ 和单位距离运输成本$C_k$ 不同，其中$k\in K=\left\{1,2,3,4\right\}$ 分别对应上述四种垃圾类型。定义二元决策变量来表示第$k$ 种车辆运输的第$v$ 条路径是否从收集点$i$ 行驶到$j$ ，如下

$A_{v,i,j}^k\in \left\{0,1\right\}k\in K,v\in R^k,i\in N,j\in N,i\ne j$ (12)

其中$R^k$ 是第$k$ 种车辆路径索引的集合。目标函数为

$\min {\displaystyle {\sum }_{k\in K}{\displaystyle {\sum }_{v\in R^k}{\displaystyle {\sum }_{i\in N}{\displaystyle {\sum }_{j\in N}{C}_k\cdot d_{i,j}\cdot A_{v,i,j}^k}}}}i\ne j$ (13)

这个模型的约束条件只需要将式(4)~式(10)扩展到每种车辆类型的路径都满足即可。综上，得到MTCVRP模型，如式(14)所示，其中$i\ne j\ne h$ 。

$\{\begin{array}{l}\min {\displaystyle {\sum }_{k\in K}{\displaystyle {\sum }_{v\in M^k}{\displaystyle {\sum }_{i\in N}{\displaystyle {\sum }_{j\in N}{C}_k\cdot d_{i,j}\cdot A_{v,i,j}^k}}}}\\ s.t.\{\begin{array}{l}{{\displaystyle \sum }}_{v\in R^k}{{\displaystyle \sum }}_{j\in N}{A}_{v,i,j}^k \forall i\in N/\left\{0\right\}\\ {{\displaystyle \sum }}_{i\in N/\left\{0\right\}}{{\displaystyle \sum }}_{j\in N}{w}_{i,k}\cdot A_{v,i,j}^k\le Q_k \forall v\in R^k\\ {{\displaystyle \sum }}_{i\in N/\left\{0\right\}}{{\displaystyle \sum }}_{j\in N}\frac{w_{i,k}\cdot A_{v,i,j}^k}{{\rho }_k}\le V_k \forall v\in R^k\\ \{\begin{array}{c}{\displaystyle {\sum }_{j\in N}{A}_{v,0,j}^k}=1\forall v\in R^k\\ {\displaystyle {\sum }_{i\in N}{A}_{v,i,0}^k}=1\forall v\in R^k\end{array}\forall k\in K\\ {\displaystyle {\sum }_{i\in N}{A}_{v,i,h}^k}-{\displaystyle {\sum }_{j\in N}{A}_{v,h,j}^k}=0\forall h\in N/\left\{0\right\},\forall v\in R^k\\ \frac{{{\displaystyle \sum }}_{i\in N}{{\displaystyle \sum }}_{j\in N}{d}_{i,j}\cdot A_{v,h,j}^k}{40}\le 12\forall v\in R^k\\ B_{v,i}^k-B_{v,j}^k+\left(n+1\right)A_{v,i,j}^k\le n\forall i,j\in N,\forall v\in R^k\end{array}\end{array}$ (14)

其中为了得到每种垃圾的密度${\rho }_k$ ，本文参考文献[7]中的相关数据并对数据进行简化处理，将各类垃圾最大值的平均值作为最大容重，以典型值的平均值为平均容重，并对最大容重和平均容重两种情况进行处理与分析。处理完的数据如表4所示。

Table 4. Waste bulk density for four types

表4. 四种类型垃圾容重

垃圾类别	最大容重(t/m^3)	平均容重(t/m^3)
厨余垃圾	0.48	0.29
可回收物	0.21	0.1245
有害垃圾	0.6467	0.3848
其他垃圾	1.25	0.74

3.1.3. TCVRPTW模型的建立

在MTCVRP模型的基础上，进一步考虑中转站的选址与收集点分配问题。同时，为响应绿色运输需求，还需兼顾运输过程中的碳排放问题。模型的主要目标设定为最小化每日运输成本与中转站建设成本之和。为了简化模型结构，碳排放量不作为直接优化目标，而作为路径优化完成后的评价与调整指标，用于在多个可行方案中选择更为低碳的运输路径。已知有$m$ 个中转站候选，则定义其索引为$f\in F=\left(n,n+1,\cdots ,n+m\right)$ 。

中转站可对各类垃圾进行临时存储，意味着在路径中中转站可以作为起点或终点。这样运输过程被分为了两层运输结构，第一层运输指的是从各个收集点到中转站(或者直接到处理厂)，第二层运输指的是从中转站到处理厂，相当于中转站对应的支线运输，和处理厂对应的主线运输。这两层运输情况不同。因此，需要分别定义两个二元决策变量$A_{v,i,j}^{1k}$ 表示第一层运输中第$k$ 种车辆运输的第$v$ 条路径是否从收集点$i$ 行驶到$j$ 和$A_{v,f,g}^{2k}$ 表示第二层运输中第$k$ 种车辆运输的第$v$ 条路径是否从中转站$f$ 行驶到$g$ 。为了计算中转站运输成本，再定义$E_f$ 表示中转站$f$ 是否被建设，则目标函数可以表示如下：

$\min {\displaystyle {\sum }_{f\in F}\frac{T_f}{3650}{E}_f}+{\displaystyle {\sum }_{k\in K}{\displaystyle {\sum }_v{\displaystyle {\sum }_{i\in N\cup F}{\displaystyle {\sum }_{j\in N\cup F}{C}_k\cdot d_{i,j}\cdot A_{v,i,j}^{1k}}}}}+{\displaystyle {\sum }_{k\in K}{\displaystyle {\sum }_v{\displaystyle {\sum }_{f\in F\cup \left\{0\right\}}{\displaystyle {\sum }_{g\in F\cup \left\{0\right\}}{C}_k\cdot d_{f,g}\cdot A_{v,f,g}^{2k}}}}}$ (15)

其中$T_f$ 为中转站建设成本，使用期限为10年。在满足目标的同时，还需要满足以下约束条件。

中转站选址约束：

每个收集点的第$k$ 类垃圾只能被分配给一个垃圾中转站或者直接运往处理厂，定义二元决策变量$D_{i,f}^k$ 表示第$i$ 个收集点的第$k$ 类垃圾是否被分配给中转站$f$ ，$D_{i,0}^k$ 表示为第$i$ 个收集点的第$k$ 类垃圾是否直接运往处理厂，它们需要满足下式。

${\displaystyle {\sum }_{f\in F\cup \left\{0\right\}}{D}_{i,f}^k}=1\forall i\in N/\left\{0\right\}$ (16)

对不同垃圾而言，被分配给中转站$f$ 的对应收集点的垃圾量不能超过其存储容量$S_{k,f}$ ，则需要满足下式：

${\displaystyle {\sum }_{i\in N/\left\{0\right\}}{w}_{i,k}\cdot D_{i,f}^k}\le S_{k,f}\cdot E_f$ (17)

还需要保障每个收集点被分配到建设的中转站：

$D_{i,f}^k\le E_f$ (18)

中转站时间窗约束：

中转站$f$ 仅在时间窗口$\left[a_f,b_f\right]$ 允许车辆停靠，定义一个时间窗[8]辅助变量$Z_{v,f}^k$ ，对于两层运输结构，需要分别满足下面的约束。

$\{\begin{array}{l}{Z}_{v,f}^k+\frac{d_{f,j}}{40}-G\left(1-A_{v,f,j}^{1k}\right)\le Z_{v,j}^k\forall k\in K,\forall f\in F,\forall j\in N\cup F\hfill \\ G\ge b_f-a_f+\frac{d_{f,j}}{40}\hfill \\ a_f\le Z_{v,f}^k\le b_f\hfill \end{array}$ (19)

$\{\begin{array}{l}{Z}_{v,f}^k+\frac{d_{f,g}}{40}-G\left(1-A_{v,f,g}^{2k}\right)\le Z_{v,g}^k\forall k\in K,\forall f\in f,\forall g\in \left\{0\right\}\cup F\hfill \\ G\ge b_f-a_f+\frac{d_{f,g}}{40}\hfill \\ a_f\le Z_{v,f}^k\le b_f\hfill \end{array}$ (20)

接着就要在这个二层运输结构上，考虑MTCVRP模型的约束。

收集点需求满足约束：

${\displaystyle {\sum }_v{\displaystyle {\sum }_{j\in N\cup F}{A}_{v,i,j}^{1k}}}=1\forall i\in N/\left\{0\right\},\forall k\in K$ (21)

最大载重容积约束：

其中需要定义$w_{v,f,g}^{2k}$ 为第二层运输中第$k$ 种车辆运输的第$v$ 条路径从中转站$f$ 运走的垃圾量：

$\{\begin{array}{l}\begin{array}{c}{{\displaystyle \sum }}_{i\in N/\left\{0\right\}}{{\displaystyle \sum }}_{j\in N\cup F}{w}_{i,k}\cdot A_{v,i,j}^{1k}\le Q_k \\ {{\displaystyle \sum }}_{i\in N/\left\{0\right\}}{{\displaystyle \sum }}_{j\in N\cup F}\frac{w_{i,k}\cdot A_{v,i,j}^{1k}}{{\rho }_k}\le V_k \end{array}\hfill \\ \begin{array}{c}{{\displaystyle \sum }}_{f\in F}{{\displaystyle \sum }}_{g\in \left\{0\right\}\cup F}{w}_{v,f,g}^{2k}\cdot A_{v,f,g}^{2k}\le Q_k \\ {{\displaystyle \sum }}_{f\in F}{{\displaystyle \sum }}_{g\in \left\{0\right\}\cup F}\frac{w_{v,f,g}^{2k}\cdot A_{v,f,g}^{1k}}{{\rho }_k}\le Q_k \end{array}\hfill \end{array}\forall v$ (22)

满足载重的前提下，需要保证从中转站运走的垃圾量与运入的垃圾量持平，则需要满足下式：

${\displaystyle {\sum }_{i\in N/\left\{0\right\}}{\displaystyle {\sum }_v{w}_{i,k}\cdot A_{v,i,f}^{1k}}}={\displaystyle {\sum }_v{\displaystyle {\sum }_{g\in \left\{0\right\}\cup F}{w}_{v,f,g}^{2k}\cdot A_{v,f,g}^{2k}}}\le Q_k$ (23)

路线约束：

即起点终点为中转站或处理厂，以及路线的连续性，分别满足下式。

$\{\begin{array}{l}{\displaystyle {\sum }_{j\in N\cup F}{A}_{v,0,j}^{1k}}+{\displaystyle {\sum }_{j\in N\cup F}{\displaystyle {\sum }_{f\in F}{A}_{v,f,j}^{1k}}}=1\hfill \\ {\displaystyle {\sum }_{i\in N\cup F}{A}_{v,i,0}^{1k}}+{\displaystyle {\sum }_{i\in N\cup F}{\displaystyle {\sum }_{f\in F}{A}_{v,i,f}^{1k}}}=1\hfill \\ {\displaystyle {\sum }_{g\in \left\{0\right\}\cup F}{A}_{v,0,g}^{2k}}={\displaystyle {\sum }_{f\in \left\{0\right\}\cup F}{A}_{v,f,0}^{2k}}=1\hfill \end{array}\forall v$ (24)

$\{\begin{array}{l}{\displaystyle {\sum }_{i\in N\cup F}{A}_{v,i,h}^{1k}}-{\displaystyle {\sum }_{j\in N\cup F}{A}_{v,h,j}^{1k}}=0\forall h\in N/\left\{0\right\}\hfill \\ {\displaystyle {\sum }_{f\in F}{A}_{v,f,\overline{h}}^{2k}}-{\displaystyle {\sum }_{g\in F}{A}_{v,\overline{h},g}^{2k}}=0\forall \overline{h}\in F\hfill \end{array}\forall v$ (25)

处理厂时间约束：

$\{\begin{array}{l}\frac{{{\displaystyle \sum }}_{i\in N\cup F}{{\displaystyle \sum }}_{j\in N\cup F}{d}_{i,j}\cdot A_{v,i,j}^{1k}}{40}\le 12\forall v|A_{v,i,0}^{1k}=1\hfill \\ \frac{{{\displaystyle \sum }}_{f\in F\cup \left\{0\right\}}{{\displaystyle \sum }}_{g\in F\cup \left\{0\right\}}{d}_{f,g}\cdot A_{v,f,g}^{2k}}{40}\le 12\forall v\hfill \end{array}\forall k\in K$ (26)

子回路消除约束：

$\{\begin{array}{l}{B}_{v,i}^k-B_{v,j}^k+\left({\displaystyle {\sum }_{i\in N}{D}_{i,f}^k}+1\right)A_{v,i,j}^{1k}\le {\displaystyle {\sum }_{i\in N}{D}_{i,f}^k}\hfill \\ B_{v,f}^k-B_{v,g}^k+\left(m+1\right)A_{v,f,g}^{2k}\le m\hfill \end{array}\forall i,j,f,v$ (27)

综上所述，本问题的TCVRPTW模型已经建立完成。

3.2. TCVRPTW模型的求解

3.2.1. 两阶段算法的设计

针对TCVRPTW，选择采用自适应大领域搜索(ALNS)为基础框架，设计两阶段算法如图1所示。

Figure 1. Two-phase algorithm for solving the TCVRPTW model

图1. 二阶段算法求解TCVRPTW模型

1) 中转站选址与收集点分配

对TCVRPTW模型进行两阶段的求解，第一阶段需要完成中转站选址与收集点分配问题，简化中转站成本进行估算，考虑选址会产生的建设成本和拟产生的与其对应收集点的距离成本：

${\displaystyle {\sum }_{f\in F}{T}_f{E}_f}+{\displaystyle {\sum }_{k\in K}{\displaystyle {\sum }_{i\in N∕\left\{0\right\}}{\displaystyle {\sum }_{f\in F}{C}_k\cdot d_{i,f}\cdot D_{i,f}^k}}}$ (28)

在满足容量等约束条件的前提下，旨在最小化总成本，获得一个局部最优的中转站选址与收集点分配方案，为后续路径优化提供高质量初始结构。为此，本文采用ALNS算法进行求解[2]。

算法从一个初始可行解出发，在严格满足中转站容量约束的条件下，通过迭代执行“破坏–修复”操作对当前解进行扰动与重构。破坏阶段设计了三类算子以增强解空间的探索能力：随机移除算子均匀移除若干收集点；最差移除算子移除对目标函数贡献最差(即单位分配成本最高)的节点；Shaw邻域移除算子则基于收集点间的空间距离与垃圾类型相似性，移除结构上相近的点集，促进区域重组。修复阶段采用贪心插入与后悔值插入(Regret-k)策略，将被移除的节点重新分配至满足容量约束的中转站，优先选择能最小化成本增量或具有较高机会成本的分配方案。为提升搜索效率，算法引入自适应算子选择机制：在长度为50的滚动窗口内，根据各算子对解质量的贡献动态评分——若生成新全局最优解得5分，仅改进当前解得3分，否则得1分；算子被选概率正比于其累计得分，从而自动赋予高效算子更高权重。此外，为避免早熟收敛，算法嵌入模拟退火接受准则，允许以概率$P=\exp \left(-\frac{\Delta Z}{T}\right)$ 接受劣解，其中$\Delta Z$ 为成本增量，温度$T$ 随迭代次数指数衰减，实现从全局探索到局部开发的平滑过渡。

2) 路径优化

第二阶段，在确定的中转站与收集点分配基础上，为两层运输结构优化路径，分为多个MTCVRP子模型利用并行算法来求解，并在其中考虑中转站时间窗约束。最后，再根据碳排放量尽可能小的原则来决定车辆的行驶方向，定义$H_{v,i,j}^{1k}$ 为第一层运输中第$k$ 种车辆运输的第$v$ 条路径从收集点$i$ 行驶到$j$ 的载重、$H_{v,f,g}^{2k}$ 为第一层运输中第$k$ 种车辆运输的第$v$ 条路径从收集点$f$ 行驶到$g$ 的载重。得到碳排放量的成本为：

$E={\displaystyle \sum }_{k\in K}{\displaystyle \sum }_v{\displaystyle \sum }_{i\in N\cup F}{\displaystyle \sum }_{j\in N\cup F}\left(d_{i,j}\cdot {\alpha }_k+{\beta }_k\cdot H_{v,i,j}^{1k}\right)+{\displaystyle \sum }_{k\in K}{\displaystyle \sum }_v{\displaystyle \sum }_{f\in F\cup \left\{0\right\}}{\displaystyle \sum }_{g\in F\cup \left\{0\right\}}\left(d_{f,g}\cdot {\alpha }_k+{\beta }_k\cdot H_{v,f,g}^{2k}\right)$ (29)

为求解上述MTCVRP模型，采用多群体主从并行蚁群算法。该方法采用主从架构，由主进程协调四个子种群，每个子种群分别负责一类垃圾的路径优化。在各子种群内部，蚂蚁依据信息素浓度${\tau }_{ij}$ 与启

发式信息${\eta }_{ij}=\frac{1}{d_{ij}}$ 构建可行路径，其状态转移概率定义为：

$P_{ij}^k=\frac{{\tau }_{ij}^{\alpha }\cdot {\eta }_{ij}^{\beta }}{{{\displaystyle \sum }}_{l\in {\Omega }_i^k}{\tau }_{ij}^{\alpha }\cdot {\eta }_{ij}^{\beta }},{\eta }_{ij}=\frac{1}{d_{ij}}$ (30)

其中${\Omega }_i^k$ 表明蚂蚁$k$ 在节点$i$ 处满足载重、容积及时间窗约束的可行邻域。若插入新节点将导致任一约束被违反，则车辆立即返回所属中转站并重新出发，从而确保所生成路径的可行性。信息素更新采用“挥发–强化”机制：

${\tau }_{ij}\leftarrow \left(1-\rho \right){\tau }_{ij}+\frac{Q}{Z_{\text{best}}}+\frac{Q}{Z_{\text{global}}}$ (31)

其中$\rho$ 为信息素挥发率，$Q$ 为常数，${\text{Z}}_{\text{best}}$ 和$Z_{\text{global}}$ 分别为当前最优解与全局最优解的目标函数值。在并行执行过程中，各子种群独立进行搜索，并在每代迭代结束后将局部最优解上传至主进程；主进程统一更新全局信息素矩阵，并将其广播至各子种群，实现跨种群的信息共享与协同进化。该机制在提高计算效率的同时，有效增强了解空间的探索能力，从而获得高质量的路径优化结果。

两阶段的求解互相影响。第一阶段确定了中转站选址和分配，这直接决定了第二阶段需要解决的MTCVRP子问题规模与结构。同时为避免第一阶段的“局部最优”导致整体解效果差，第二阶段的求解结果需要反作用于第一阶段，具体为可以将第二阶段计算出的实际每日成本，作为第一阶段评估中转站选址方案的依据；当第二阶段难以迭代出最优路径的时候，需要重回第一阶段进行中转站的选址和分配。

3.2.2. TCVRPTW模型的结果

通过所建立的TCVRPTW模型及两阶段算法，利用MATLAB软件编程按序完成对中转站选址以及该选址下的车辆运输路径优化。如图2所示，通过两阶段算法，添加表3中5个中转站候选点的位置及相关参数，根据综合模型最终确定1个中转站，即中转站32号，并根据中转站分配对应的收集点。

Figure 2. Transfer station selection and collection point allocation

图2. 中转站选取及收集点分配

第一阶段确定好中转站之后，通过规划中转站对应的收集点与其之间的运输路径分别最小化四类垃圾的总运输成本。从图3可以看出，厨余垃圾等4类垃圾随着迭代次数的增加，各垃圾的成本都有所下降。这说明本文的算法及求解思路是可行且有效的。

Figure 3. Changes in transport costs for four types of waste

图3. 四类垃圾运输成本变化

从图4中可以看出，在选中一个中转站情况下，厨余垃圾通过7次运输将各收集点的垃圾运至中转站，再由中转站运回处理厂；可回收物经2次运输将垃圾送到中转站再运至处理厂；有害垃圾仅需1次即可完成各收集点垃圾运输工作；其他垃圾分3次将所有收集点的垃圾依次送至中转站并统一送回处理厂。而各类垃圾的路线选择及载重、运输时间和安排见表5。其中，车辆1负责将厨余垃圾运至中转站，车辆2、3负责将厨余垃圾转运至处理厂；车辆4负责将可回收物运至中转站并最后送至处理厂；车辆5负责将有害垃圾先运至中转站，结束后送至处理厂；车辆6负责将其他垃圾从收集点运至中转站，并统一送至处理厂进行处理。

Figure 4. Transport and storage routes for four types of waste

图4. 四类垃圾运输及存储路线

Table 5. Route selection and related data for four types of waste

表5. 四类垃圾路线选择及相关数据

垃圾类别	路径编号	路线	载重(t)	时间(h)	车辆分配	车辆用时(h)
厨余垃圾	1-1	0→19→16→9→4→25→32	6.878	1.875	1	8.675
	1-2	32→12→24→8→18→27→32	7.625	1.25	1
	1-3	32→22→26→5→23→17→7→30→32	7.156	1.25	1
	1-5	32→2→11→15→1→21→6→32	6.902	1.625	1
	1-6	32→14→20→13→29→10→32	7.108	1.35	1
	1-7	32→3→28→32	3.72	0.45	1
	1-8	32→0	5	0.875	1
	1-9	0→32→0	5	1.75	2	7
	1-10	0→32→0	5	1.75	2
	1-11	0→32→0	5	1.75	2
	1-12	0→32→0	5	1.75	2
	1-13	0→32→0	5	1.75	3	5.25
	1-14	0→32→0	5	1.75	3
	1-15	0→32→0	4.389	1.75	3
可回收物	2-1	0→19→16→9→25→4→13→6→21→1→15→11→2→18→27→8→24→12→28→3→30→32	5.917	3.6	4	7.85
	2-2	32→22→26→14→20→29→10→5→23→17→7→32	2.469	1.625	4
	2-3	32→0	6	0.875	4
	2-4	0→32→0	2.386	1.75	4
有害垃圾	3-1	0→19→22→26→14→4→13→20→29→10→5→23→17→7→30→3→28→12→24→8→27→18→2→11→15→1→21→6→25→9→16→32	2.305	4.8	5	4.61
	3-2	32→0	2.305	0.875	5
其他垃圾	4-1	0→19→22→26→14→4→13→20→29→10→5→23→17→7→30→32	9.804	2.975	6	9.9
	4-2	32→16→9→25→6→21→1→15→11→2→18→27→8→24→12→32	9.96	2.1	6
	4-3	32→3→28→32	1.556	0.45	6
	4-4	32→0	10	0.875	6
	4-5	0→32→0	10	1.75	6
	4-5	0→32→0	1.32	1.75	6
每日总成本(元)		4043.3
碳排放量(kg)		2479.826

3.2.3. 二阶段算法优势机理分析

相较于传统遗传算法(GA)，该算法在问题结构适配性、搜索自适应性及收敛可靠性方面具有显著优势。

首先，在问题结构适配性方面。求解TCVRPTW模型本质上是选址与路径耦合的双层组合优化问题。若用传统GA，需将两类不同变量硬塞进一条染色体，编码复杂且容易产生不可行解[9]。而本文算法分两步处理：ALNS负责选址与分配，ACO专注路径优化，更契合问题结构，减少无效搜索。

其次，在搜索自适应性方面。传统GA使用固定的交叉和变异概率，无法根据搜索进展自动调整，容易在早期陷入局部最优或后期失去多样性[10]。而ALNS能根据算子历史表现动态选择操作[11]，ACO则通过信息素自动强化好路径[12]，整个过程无需人工调参，适应性更强。

最后，在收敛可靠性方面。GA因强选择机制常过早收敛到次优解[13]。本文算法引入模拟退火的接受准则，允许偶尔接受较差解以跳出局部最优，同时用精英信息素保留优质路径，兼顾探索与开发[14]。

4. 总结

本文针对城市垃圾分类运输系统中的路径规划与调度问题，构建了一个融合车辆路径优化、中转站选址与碳排放控制的综合优化模型。首先，在不区分垃圾类型的基础上，将垃圾收集问题抽象为带容量约束的车辆路径问题，建立单类型车辆路径优化模型(STCVRP)，为后续复杂模型奠定基础。随后，考虑实际垃圾分类运输需求，将厨余垃圾、可回收物、有害垃圾和其他垃圾分别由专用车辆运输，构建多类型车辆路径优化模型(MTCVRP)，并分析不同车辆参数对运输路径及成本的影响。最后，在前述模型基础上进一步引入中转站选址、时间窗约束以及运输碳排放因素，建立了带时间窗的多类型车辆路径优化模型(TCVRPTW)。

针对该模型，本文设计了两阶段求解算法。第一阶段基于自适应大邻域搜索(ALNS)确定中转站选址及收集点分配方案；第二阶段在确定的中转站网络下，利用并行蚁群算法对不同垃圾类型车辆的运输路径进行优化。通过MATLAB编程求解，得到最优中转站选址方案为设置32号中转站，并据此规划了四类垃圾的运输路径。结果表明，在引入中转站后，垃圾运输系统能够有效减少运输距离，提高车辆利用效率，同时降低整体运输成本。模型计算得到每日总运输成本为4043.3元，碳排放量为2479.826 kg，验证了所提出模型与算法的可行性与有效性。

总体来看，本文构建的综合优化模型能够较为真实地反映城市垃圾分类运输系统的运行机制，通过合理的中转站布局与路径优化，可以有效降低运输成本与碳排放，为城市垃圾分类运输系统的规划与调度提供了理论依据和技术参考。未来可在以下方面进一步拓展：考虑非对称路网及交通限制以提升模型现实性；引入实时交通数据实现动态优化；将碳排放纳入多目标函数进行协同优化，并结合启发式策略提升大规模问题的求解效率。