基于多蚁群算法的低碳车辆路径研究

Research on Low-Carbon Vehicle Routing Using a Multi-Ant Colony Algorithm

摘要: 本文针对软时间窗约束下的低碳车辆路径优化问题，构建了以最小化车辆使用数量和总成本为目标的数学模型，包括燃油成本、碳排放成本及时间窗违约成本。本文采用多蚁群系统(MACS)求解这一NP‑hard问题，通过多蚁群协同搜索并引入Cross exchange局部搜索算子，增强了算法的全局探索与局部开发能力。基于实际案例的数值实验表明，该算法能有效减少车辆数、缩短行驶距离并降低总成本，验证了其在求解低碳、准时配送路径问题中的可行性与有效性，为物流企业践行低碳运营提供了决策参考。

Abstract: This paper addresses the vehicle routing optimization problem with soft time window constraints and low-carbon objectives, and develops a mathematical model aiming to minimize the number of vehicles used and the total cost—including fuel cost, carbon emission cost, and time window violation cost. A multi-ant colony system (MACS) is adopted to solve this NP-hard problem. The approach employs multiple ant colonies to conduct cooperative search and introduces a Cross exchange local search operator, which enhances the algorithm’s global exploration and local exploitation capabilities. Numerical experiments based on a real-world case demonstrate that the proposed algorithm can effectively reduce the number of vehicles, shorten travel distance, and lower the total cost, verifying its feasibility and effectiveness in solving low-carbon and on-time delivery routing problems. The study provides a decision-making reference for logistics enterprises to implement low-carbon operations.

1. 引言

在全球气候变化应对体系逐步深化的进程中，实现经济发展与碳减排的协同已成为各国政策制定的重要导向。中国于第七十五届联合国大会上正式宣布了“双碳”战略目标，承诺在2030年前实现碳达峰、2060年前实现碳中和，这为国内相关产业的低碳转型提供了明确的时间表与路径指引。物流运输作为能源消耗的重要部门，其碳排放约占全球总量的14%，因而在构建绿色低碳供应链中具有显著减排潜力。

低碳车辆路径规划作为经典VRP的延伸，在模型构建中纳入碳排放指标，旨在通过系统优化行驶路径，在满足运输需求的同时降低全程碳足迹，进而达成运营成本与环境效益的平衡[1]。

近年来，学者开始关注电动汽车路径优化(EVRP)中的碳排放问题。Zhang等[2]以最小化CO2排放为目标构建模型，但未兼顾经济效益。为平衡环境与经济因素，部分研究将碳排放转化为经济成本。YanLi等[3]通过碳税与分时电价优化城市物流配送，采用蚁群算法并进行实际案例模拟。Juvvala等[4]建立成本最小化模型，包括路线、车辆固定、排放及区域进入费用，采用改进蚁群优化(MACO)，结果显示购置补贴与区域进入费对电动车推广关键。Foroutan等[5]研究异质车队绿色路径与调度，结合逆向物流和加权提前/延迟成本，实现双目标最小化。

在协同能源策略方面，梁海峰等[6]将碳排放纳入电动汽车与光伏调度，通过遗传算法优化“绿电”收费与补贴方案，可提升光伏协同效能并增加负荷聚合商收益。曹仁伟等[7]构建包含运输、制冷、货损及碳排放成本的生鲜配送优化模型，结合改进K-means与蚁群算法求解，结果显示电动车在总成本和碳排放上均优于燃油车。杨芳等[8]引入货损因素优化冷链配送，验证了降低成本与碳排放的有效性。李文翔等[9]通过碳交易机制替代补贴，建立新能源汽车市场化激励模型，为“后补贴时代”提供政策参考。

从配送服务实践来看，客户时间窗约束的引入进一步增加了问题的现实复杂性。其中，软时间窗因允许在时间窗范围外提供服务并施加相应惩罚，较之硬时间窗更贴合实际商业场景中的弹性调度需求[10] [11]。因此，研究同时融合低碳目标与软时间窗约束的车辆路径问题，对于企业提升服务满意度与履行环境责任具有重要意义。

本文聚焦于软时间窗约束下的低碳车辆路径优化问题，构建以使用车辆数最小与总成本最低为目标的路径规划模型。该问题在计算复杂度上属于NP-hard问题[12]，通常需借助智能优化算法进行近似求解。本研究通过设计相应求解策略，旨在为物流企业开展低碳、准时配送提供决策支持，也为“双碳”目标在物流领域的落实提供方法参考。

蚁群算法(Ant Colony Optimization, ACO)是一种受自然界蚂蚁群体觅食过程启发的元启发式算法，由意大利学者Dorigo及其合作者在20世纪90年代早期首次系统提出[13]，广泛应用于各类组合优化问题的求解。经典蚁群算法主要依赖信息素的正反馈机制引导搜索，这一机制虽能加速收敛，但也可能导致算法过早陷入局部最优。为此，研究者常通过融入变异算子来增强解的多样性，进而提高算法的搜索效率。

针对带软时间窗的车辆路径问题(VRPSTW)，学者们基于蚁群优化算法提出了多种改进策略。例如，研究[14]将大规模邻域搜索技术应用于VRPSTW的求解；文献[15]则在模型中引入软时间窗约束，并结合萤火虫算法对蚁群算法进行混合优化，以提升解的质量。此外，文献[16]通过融合2-opt局部搜索算子来增强蚁群算法的邻域搜索能力，虽取得一定优化效果，但仍存在解空间探索范围有限的问题。Xiang X提出ACO-CD，通过维持客户覆盖多样性提升DVRP求解效果[17]；Ebadinezhad S提出DEACO，结合参数自适应与聚类策略，提高收敛速度和搜索精度[18]。Elcock J设计ACO-RNK，将信息素更新与优先级启发式结合，用于任务调度，性能优于HEFT和MGACO [19]。Wang Y针对无人机MEC系统提出双目标bi-ACO，引入异构蚁群，实现路径规划与任务卸载优化[20]。Sun H提出EPIACO，应急路径规划中采用多种改进机制，显著缩短路径并加快收敛，为实际疏散提供支持[21]。

为克服上述局限，本文提出一种改进的多蚁群系统(MACS)，通过嵌入Cross exchange局部搜索算子，进一步加强对解空间的深度探索与开发。在数据集上的实验表明，该改进策略能有效降低路径总行驶距离与所需车辆数目，显著提升了算法在复杂VRPSTW实例中的综合求解性能。

2. 问题阐释与数学建模

2.1. 问题阐释

鉴于实际运营环境中，企业往往基于成本效益原因而倾向于采用集中式配送策略[22]，本研究聚焦于单一配送中心场景下的车辆路径优化命题。为构建切实可行的理论框架，本文提出如下基本假定：

关于配送中心：系统中存在唯一的配送枢纽节点，所有运输车辆自该节点启程执行配送任务，任务完成后必须返回原点形成闭环路径。

关于运输车队：在满足全部配送需求的前提下，追求车辆调度数量的最小化；各车辆的实际装载量需同时满足两项约束——既要涵盖其服务路径上所有客户的累计需求，又不得突破车辆自身的额定载重上限；车队在满载油箱状态下从配送枢纽出发，其续航能力足以支撑整个配送回路的行驶需求；车队配置采用统一标准。

关于需求节点：遵循每个客户只由一辆车配送服务的原则；每个客户节点的货物需求量、期望送达时间窗口及服务耗时等参数均为已知确定量。

2.2. 参数符号定义

本研究采用以下数学符号表示系统要素：

集合定义：$N=\left\{0,1,2,\cdots ,n\right\}$ 表示节点集(其中节点0特指配送中心，其余为客户点)；$K=\left\{1,2,\dots ,k\right\}$ 表示可调度车辆集合。

能耗参数：$r_0$ 与$r_1$ 分别表示车辆空载及满载工况下的单位距离燃油消耗率。

容量指标：$Q$ 表示车辆额定最大载重；$Q_{ij}$ 表示车辆由节点$i$ 驶向节点$j$ 时的实时载重量。

需求与距离：$q_i$ 表示客户$i$ 的货物需求量；$d_{ij}$ 表示节点$i$ 与节点$j$ 之间的空间距离。

成本参数：$c$ 为燃油单价；$FE$ 表示单位燃油的碳排放因子；$CT$ 为碳税税率；$f_k$ 表示车辆单位里程的固定运营成本。

时间窗参数：$\left[S_j,E_j\right]$ 表示客户$j$ 的可接受服务时间区间；$a_1$ 与$a_2$ 分别为提前到达与延迟到达的惩罚权重系数；$t_j$ 表示车辆实际抵达客户$j$ 的时刻。

决策变量：$x_{ijk}$ 为二元变量(车辆$k$ 执行弧段$i\to j$ 时取1，否则为0)；${\gamma }_{ik}$ 为服务指派变量(车辆$k$ 服务客户$i$ 时取1，否则为0)；${\gamma }_k$ 为车辆启用变量(车辆$k$ 被使用则取1，否则为0)。

2.3. 数学模型构建

2.3.1. 运输成本建模

车辆运输成本由两个核心部分构成：燃油消耗成本与车辆启用的固定成本。

借鉴负荷估算理论框架，当车辆承载货物质量为$M(M\in \left[0,Q\right]$ 时，其单位距离的燃油消耗函数可表述为：

$\rho \left(M\right)=r_0+\frac{r_1-r_0}{Q}M$ (1)

车队完成全部配送任务所产生的燃油总成本可量化为：

$C_{11}=c{\displaystyle \sum }_{k=1}^K{\displaystyle \sum }_{i=0}^N{\displaystyle \sum }_{j=0}^N{x}_{ijk}\rho \left(Q_{ij}\right)d_{ij}$ (2)

考虑到车辆固定成本与行驶里程呈线性关系，该部分成本计算如下：

$C_{12}=f_k{\displaystyle \sum }_{k=1}^K{\displaystyle \sum }_{i=0}^N{\displaystyle \sum }_{j=0}^N{x}_{ijk}{d}_{ij}$ (3)

2.3.2. 碳排放成本建模

依据Hoen等学者[23]的实证研究结论，碳排放量与燃油消耗量存在显著正相关性，碳排放成本可表达为：

$C_2=FE\ast CT{\displaystyle \sum }_{k=1}^K{\displaystyle \sum }_{i=0}^N{\displaystyle \sum }_{j=0}^N{x}_{ijk}\rho \left(Q_{ij}\right)d_{ij}$ (4)

2.3.3. 时间窗违约成本建模

配送企业与客户通常会商定特定的服务时间窗$[S_j|E_j]$ 。当车辆在该时间区间之外到达时，虽然配送服务仍会正常执行，但企业需承担相应的违约惩罚成本。其成本函数可表达为：

$C_3=a_1{\displaystyle \sum }_{j=1}^N\max \left\{\left(S_j-t_j\right),0\right\}+a_2{\displaystyle \sum }_{j=1}^N\max \left\{\left(t_j-E_j\right),0\right\}$ (5)

2.3.4. 综合优化模型

综合上述分析，本文构建的融合碳排放约束与时间窗约束的车辆路径优化模型。

系统目标分为两层，第一层是满足车辆数量最小，第二层是系统总成本最小化，分别为(6)和(7)：

$\min T_1={\displaystyle \sum _{k=1}^K{\gamma }_k}$ (6)

$\min T_2=C_{11}+C_{12}+C_2+C_3$ (7)

模型需满足以下约束条件：

${\displaystyle \sum _{i=0}^N{q}_i{\gamma }_{ik}}\le Q,k\in \left\{1,2,\cdots ,K\right\}$ (8)

${\displaystyle \sum _{k=0}^K{\gamma }_{ik}}=1,i\in \left\{1,2,\cdots ,n\right\}$ (9)

${\displaystyle \sum _{j=0}^n{\displaystyle \sum _{k=1}^K{x}_{ijk}}}={\displaystyle \sum _{k=1}^K{\gamma }_{ik}},i\in \left\{1,2,\cdots ,n\right\}$ (10)

${\displaystyle \sum _{i=0}^n{\displaystyle \sum _{k=1}^K{x}_{ijk}}}={\displaystyle \sum _{k=1}^K{\gamma }_{jk}},j\in \left\{1,2,\cdots ,n\right\}$ (11)

${\displaystyle \sum _{i=1}^n{x}_{i0k}}=1,k\in \left\{1,2,\cdots ,K\right\}$ (12)

${\displaystyle \sum _{i=1}^n{x}_{i0k}}=1,k\in \left\{1,2,\cdots ,K\right\}$ (13)

${\displaystyle \sum _{i=0}^N{\displaystyle \sum _{j=1}^N{x}_{ijk}}}\le M\ast y_k,k\in K$ (14)

其中，约束式(8)确保各车辆的配载量不超过其容量上限；约束式(9)保证网络中每个客户节点均获得服务；约束式(10)~(11)共同实现客户节点与服务车辆的一对一映射关系；约束式(12)~(13)强制要求所有车辆必须从配送中心出发并最终返回，形成完整的配送回路；(14)表示只有当车辆被启用时才启用决策变量；M为足够大的正数。

3. 求解方法设计

3.1. 蚁群系统

本节介绍并阐述应用于旅行商问题(TSP)的原始蚁群系统(ACS)。实际上，MACS-VRPTW的提出正是为了解决需要同时最小化车辆数量与行驶时间的带时间窗车辆路径问题(VRPTW)。该多目标优化通过两个基于ACS的人工蚁群协作实现。

ACS的目标是寻找最短回路。该算法中，$m$ 只蚂蚁并行构建路径($m$ 为参数)。每只蚂蚁被随机分配至起始节点，并需构建一个完整回路作为解。回路的构建以节点为单位逐步推进：每只蚂蚁迭代添加新节点直至所有节点均被访问。当蚂蚁$k$ 位于节点$i$ 时，会在可行节点集$N_i^k$ (即尚未访问的节点集合)中按轮盘赌的概率规则选择下一个节点$j$ 。构建回路使用的轮盘赌概率选择规则如公式(15)所示：

$P_{ij}=\{\begin{array}{cc}\frac{{\tau }_{ij}\ast {\left[{\eta }_{ij}\right]}^{\beta }}{{{\displaystyle \sum }}_{l\int N_i^k}{\tau }_{ij}\ast {\left[{\eta }_{ij}\right]}^{\beta }}& if j\int N_i^k\\ 0& otherwise\end{array}$ (15)

此处$\beta$ 为参数，用于衡量启发式值的相对重要性，而$q_0\left(0\le q_0\le 1\right)$ 则决定了利用策略与探索策略的相对权重——$q_0$ 值越小，采用公式(15)所述概率规则的可能性越高；吸引度${\eta }_{ij}$ 为弧$\left(i,j\right)$ 长度的倒数，为静态启发式值，不发生改变。

在每轮迭代中，所有蚂蚁完成解构造后，会通过局部搜索对当前解进行优化，并采用迄今获得的全局最优解更新信息素轨迹。该过程循环执行，直至满足预设终止条件：达到最大解生成数量、超过限定计算时间或连续若干代未出现改进解。

蚁群系统采用双重信息素更新机制：局部更新在解构造过程中实时降低当前访问边的信息素浓度以促进探索；全局更新则在每轮迭代后仅通过全局最优解强化其包含的边，以此实现对优质解邻域的集中搜索。全局更新规则表示为：

${\tau }_{ij}=\left(1-\rho \right)\ast {\tau }_{ij}+\rho /J_{\Psi }^{gb}$ (16)

其中$\rho \left(0\le \rho \le 1\right)$ 为参数，而$J_{\Psi }^{gb}$ 表示自计算开始以来由蚂蚁生成的最短路径$J_{\Psi }^{gb}$ 的长度。该全局更新流程在每个循环结束时执行，即每次构建阶段完成后均会应用。${\Psi }^{VEI}$ 与${\Psi }^{TIME}$ 局部更新的执行方式如下：当蚂蚁从节点$i$ 移动至节点$j$ 时，弧段$\left(i,j\right)$ 上的信息素轨迹量将根据公式(17)迭代：

${\tau }_{ij}=\left(1-\rho \right)\ast {\tau }_{ij}+\rho /{\tau }_0$ (17)

其中${\tau }_0$ 表示轨迹的初始值。研究发现，将该参数设定为${\tau }_0=1|\left(n*J_{\Psi }^h\right)$ 是较优的取值，此处$J_{\Psi }^h$ 为最近邻启发式方法所得初始解的长度，$n$ 为节点数量。

3.2. 多蚁群系统

Gamhardella、Taillard和Agazzi提出了一种多蚁群系统(Multiple Ant Colony System, MACS)，用于求解带时间窗的车辆路径问题(VRPTW) [24]。在文献[24]中，该方法由两个蚁群系统协同组成：第一个蚁群系统(ACS_VEI)以最小化车辆使用数量为优化目标，第二个蚁群系统(ACS_TIME)则在车辆数量约束下进一步优化行驶成本。两个蚁群系统分别维护独立的信息素轨迹，通过共享全局最优解对信息素进行更新，从而实现协同搜索。

Figure 1. Flowchart of the multi-ant colony algorithm

图1. 多蚁群算法流程图

在MACS框架下，ACS_VEI和ACS_TIME均采用new_active_ant算法逐步构建可行解，其解构建流程如图1所示。具体而言，每只蚂蚁从随机选取的配送中心出发，在满足车辆容量约束和客户时间窗约束的前提下，逐步选择下一个服务节点。由尚未访问的客户节点与配送中心共同构成当前的可用节点集合。位于节点$i$ 的蚂蚁通过轮盘赌机制选择下一个访问节点$j$ 。

节点选择过程中，引入吸引度函数${\eta }_{ij}$ 作为启发式信息，其计算综合考虑了节点$i$ 与节点$j$ 之间的行驶时间$t_{ij}$ 、节点$j$ 对应的时间窗区间$\left[S_j,E_j\right]$ ，以及节点$j$ 在当前解构建过程中未被成功插入路径的累计次数$I{N}_j$ 。其中，$I{N}_j$ 用于刻画节点$j$ 的插入难度，引导蚂蚁在解构建阶段优先考虑历史上较难插入的节点，以提高路径延展性并减少车辆启用数量。当ACS_TIME调用new_active_ant算法时，由于车辆数量已基本确定，不再引入节点插入难度因素，因此将$I{N}_j$ 相关参数设为0。

在完成可行路径构建后，MACS中的new_active_ant算法进一步引入Cross exchange变异操作对解进行局部搜索，以增强解的多样性并避免算法过早陷入局部最优。其基本思想为：从两条路径中分别选取两对边，记为$\left(a,b),(c,d\right)$ 与$\left(e,f),(g,h\right)$ ，将上述的边断开并重新交叉组合，在保持节点$b$ 与$c$ 、节点$f$ 与$g$ 之间访问顺序不变的条件下生成新的路径结构，其示意如图2所示。

Figure 2. Cross exchange operator

图2. Cross exchange算子

在实施变异操作前，首先将new_active_ant生成的初始解去除路径中的配送中心节点(0)，得到连续的客户访问序列；变异操作完成后，再根据时间窗与载重约束将配送中心节点重新插入相应位置，从而构造出满足约束条件的可执行路径。局部搜索阶段结束后，将新生成的$$ l$$个候选解与原有的$$ k$$个解进行比较，依据总成本从中选取表现最优的$$ k$$个解进入下一次迭代，最终得到满足时间窗及相关约束条件的高质量解。

4. 数值实验

本文基于数值实验来验证算法效率，使用一个包含100个客户节点的实际案例数据集进行测试，实验相关参数如表1所示。

Table 1. Relevant problem parameters

表1. 相关问题参数

参数名称	参数值	参数名称	参数值
空载燃油消耗率(L/km)	0.07	碳税(元/吨)	30
满载燃油消耗率(L/km)	0.17	早到惩罚系数(元/h)	10
最大载重量(kg)	100	晚到惩罚系数(元/h)	20
燃油价格(元/L)	6	信息素权重	1
行驶速度(km/h)	30	启发因子权重	2
距离固定成本(元/km)	3	信息素挥发率	0.1
燃油碳排放参数(g/L)	2.621	种群规模	10

从多蚁群系统算法的仿真实验结果来看，在同时考虑碳排放成本与时间窗惩罚的车辆路径优化问题中，算法表现出了显著的优化效果。与初始解相比，优化后所需车辆数由21辆减少至10辆，降幅约为52.4%；总距离从2210.8 km缩短至856.4 km，降低约61.3%；总成本则由9764.8元下降至4231.2元，节约幅度达56.7%。上述结果表明，多蚁群系统算法在求解带时间窗的低碳车辆路径优化问题上具有较好的综合优化能力。

5. 总结

本文研究了软时间窗与碳排放约束下的车辆路径优化问题，构建了以最小化车辆数与总成本为目标的数学模型，并采用了多蚁群系统算法进行求解。算法通过多蚁群协同并引入Cross exchange局部搜索算子，增强了搜索能力。

在一个实际算例上的实验表明，该算法能有效减少车辆使用、缩短行驶距离并降低总成本。与初始解相比，车辆数从21辆降至10辆，总成本从9764.8元降至4231.2元，验证了算法在求解该复杂问题上的有效性，为物流企业实施低碳、准时配送提供了决策支持。

未来研究可考虑从以下角度进一步拓展：其一，探讨多类型车型的配送优化，以更好匹配多元化的低碳物流场景需求；其二，融入动态时间窗约束，增强模型应对需求时变的响应能力；其三，研发更为高效的求解策略，用于处理更为复杂的实际决策问题。