多模式混动电车路径优化：时间窗约束下的联合调度与能耗控制模型
一 研究背景与问题提出
1.1 研究背景
近年来，全球碳达峰和碳中和目标的提出使得交通运输部门减排备受关注。交通运输约占全球温室气体排放的 15%。电动化被认为是实现零碳运输的重要手段。纯电动汽车（EV）具有低能耗、零排放等优点，但行驶里程有限、充电时间长等问题限制了其在物流行业的应用。混合动力电动汽车（HEV）能够在内燃机与电机之间切换，兼顾燃油车的续航与电动车的环保优势。
在车辆路径优化领域，绿色车辆路径问题（G‑VRP）逐渐成为研究热点，其目标是在满足客户需求和时间窗约束的前提下减少能耗和碳排放。现有研究大多针对传统车辆路径问题(VRP)或纯电动车辆路径问题(EVRP)，很少考虑混合动力车辆的多模式运行特性。此外，客户时间窗在现代物流环境中十分重要，不仅影响配送效率，也增加了路径规划的难度。
1.2 问题定义与挑战
本文提出了“多模式混合动力电动汽车路径问题(含时间窗)”（Multi‑Mode Hybrid Electric Vehicle Routing Problem with Time Windows，MM‑HEVRPTW）。该问题在传统VRPTW的基础上增加了以下特性：
多模式运行 – HEV 在每一条道路弧上可以选择四种运行模式：燃油模式(M1)、电动模式(M2)、充电模式(M3)和增压模式(M4)。不同模式的能耗和行驶时间不同；燃油模式成本最高但对电池无影响，电动模式能耗最低但行驶时间最长，充电模式由内燃机驱动并向电池充电，增压模式同时使用内燃机和电机以提供短时间的快速行驶。
时间窗约束 – 每位客户具有最早到达时间 和最晚离开时间 ，车辆可以提前到达并等待，但必须在时间窗内完成服务。
电池动态 – 车辆电池状态随行驶和充电而变化，各模式的充放电速率不同；电动和增压模式消耗电量，充电模式增加电量，燃油模式电量保持不变。
不可预知的组合复杂度 – 多模式选择、时间窗与电池三类约束共同作用，使得模型组合空间急剧扩大，进一步加剧了求解难度，该问题属于 NP-hard。
本问题在城市配送、城际干线运输和绿色供应链中具有重要应用价值：HEV 可在拥堵或低排放区域使用电动/充电模式，在高速路段使用燃油或增压模式；合理选择模式有助于减少总成本和排放。
图 1 展示了MM‑HEVRPTW的示例：仓库0、七个客户以及四种运行模式路径。燃油模式用实线表示，充电模式用长虚线，电动模式用点划线，增压模式用点线。
1.3 主要贡献
论文指出，现有文献尚缺乏同时考虑多模式和客户时间窗的 HEV 路由模型，因此提出了以下创新：
混合整数线性规划模型 – 构建了第一个考虑多模式和时间窗的 HEV 路由模型，整合了电池状态、时间窗和货物容量等约束。
改进的自适应大规模邻域搜索(ALNS)算法 – 提出新的客户移除数策略、动态随机插入算子和 3‑mode‑change(3‑MC)局部搜索算子，并在搜索过程中引入半随机变量邻域下降(SRVND)与不可行惩罚机制，以提高求解质量和速度。
性能验证 – 通过与 CPLEX 和现有领先算法比较，证明了所提 ALNS 在求解质量和计算时间上的优势。灵敏度分析表明多模式显著降低成本，电池放电速率的提升比充电速率的提升对成本下降作用更大。
二 模型建立与符号定义
2.1 符号约定
集合：
– 顶点集合，包括客户集合和仓库 0； – 车辆（HEV）集合； – 运行模式集合 ，分别代表燃油、电动、充电和增压。 参数：
– 车辆在模式 下从顶点 到 的行驶成本； – 模式 下弧 的行驶时间； – 客户 的需求； – 车辆货物容量； – 电池最大容量； – 模式 的充/放电率（燃油模式为 0，充电模式为正，电动和增压模式为负）； – 客户 的服务时间窗； – 客户 的服务时长； – 车辆最大行驶时间。 决策变量：
– 当 HEV 从顶点 到 行驶时取 1； – 当 HEV 在弧 选择模式 时取 1； – 客户 的服务开始时间； – HEV 到达客户 （）时的电池电量 – HEV 回到仓库时的电池电量
2.2 模型目标与约束
为了同时规划车辆路径和运行模式，模型旨在最小化总行驶成本。其数学模型如下。
目标函数：
约束条件：
客户唯一服务约束：每个客户只被服务一次。
流平衡约束：除仓库外，车辆进入某个顶点必须离开该顶点。
车辆使用约束：每辆车的出发次数至多为一次。
载重约束：车辆所运货物总量不超过容量。
模式选择约束：当弧 被车辆 行驶时，必须且只能选择一种运行模式。
最大行驶时间约束：
服务开始时间与时间窗约束：
时间衔接与子回路消除约束：使用大数 消除子回路，实现时间顺序。
电池初始与容量限制：仓库电量初始化为 0，且车辆在任意顶点的电量不能超过最大容量。
电池动态更新 – 若车辆在弧 采用模式 ，则电池电量按对应充/放电率更新：
图 2 显示了解的表示方法：每条路线由仓库和依次访问的客户组成，每条弧关联一个运行模式，算法在插入或删除客户时同时调整模式。
三 改进的自适应大规模邻域搜索算法
MM‑HEVRPTW 的求解难度很高，传统混合整数求解器只能解决小规模问题。文中基于 Ropke 和 Pisinger 提出的 ALNS 框架设计了改进算法。其核心思想是通过毁坏‑修复策略和自适应算子选择机制在解空间中跳出局部最优，并结合局部搜索进一步改进解。
3.1 算法总体框架
初始解 – 以燃油模式为主，通过“最便宜插入”(cheapest insertion)启发式构建可行解。首先根据客户时间窗结束时间排序，若结束时间相同则比较开始时间，再比较需求量，优先插入关键客户，尽量减少时间窗违约。
毁坏与修复 – 每次迭代选择一个移除算子和一个插入算子；先移除若干客户，再按照插入算子将其重新插入，获得新解。通过模拟退火准则接受一定劣质解以跳出局部最优。
局部搜索（SRVND） – 在修复后的解上执行半随机变量邻域下降，将 reinsertion、2‑opt、swap 等局部操作与 3‑MC 模式变换结合，进一步改进解。
接受准则与随机化参数 – 采用模拟退火策略决定是否接受新解；同时通过调整随机化参数与移除客户数范围控制搜索强度，避免过早收敛。
3.2 客户移除数策略
传统 ALNS 中移除客户数固定，难以兼顾多样性与效率。文中引入动态移除数策略，根据当前最优解的改进情况和迭代次数调整移除的客户数量。如果新解改善最优解，则移除数设置为最小值，使扰动较小；若长时间无法改善，则增大移除数以加大扰动，帮助跳出局部最优。
3.3 移除算子
作者设计了六种毁坏算子，包括：
Shaw 移除 – 优先删除在距离、需求、时间窗等特征上相似的客户，以产生结构差异较大的解。 最差成本移除/最差距离移除/最差时间移除 – 按照移除后成本或行驶距离减少最多的客户优先删除。 历史移除 – 比较客户当前位置与历史最佳位置成本的差异，大差异客户优先删除，促进多样性。 随机移除 – 随机选取客户，避免过度贪心。
图 3 展示了在 ALNS 中移除和插入客户的示例：首先从第 2 条路线中删除客户 6 及其模式，再插入到第 1 条路线中客户 2 与 3 之间。
3.4 插入算子
为修复部分，引入四种插入算子：
贪心插入 – 每次选择成本增量最小的客户插入。 后悔插入 (Regret‑2) – 计算客户在不同插入位置的成本差异，优先插入“后悔值”最大的客户。 随机插入 – 随机选择客户插入成本最小的位置。 动态随机插入 – 文中提出的新算子，随机选取客户后在一组候选位置中随机选择插入，候选集按成本升序排列并由参数 控制随机程度；随着连续迭代无改进， 逐渐减小，增强随机性，帮助搜索跳出局部最优。
3.5 局部搜索与 3‑MC 算子
局部搜索采用半随机变量邻域下降 (SRVND)，包含以下算子：
Reinsertion、2‑opt、Swap – 分别对应重新插入、两弧替换和交换客户位置的经典邻域结构。 3‑MC 模式变换 – 针对多模式特性设计，随机选取三条弧，评估26种燃油、电动、充电模式组合，再将最佳组合中的每一种模式替换为增压模式生成额外的 3 种组合，共 29 种组合；选择成本最小的方案。
由于 3‑MC 搜索耗时较长，仅在 RVND 结束后调用一次。此外，为减少计算量，在 reinsertion、2‑opt 和 swap 操作中新产生的弧只考虑充电和电动两种模式，而将燃油和增压模式留给 3‑MC 算子评估。
图 4 给出了局部搜索中 reinsertion、2‑opt 和 swap 操作的示例，它们在单条路线内重新排列客户顺序，以寻找更优的路径和模式组合。
3.6 不可行惩罚与接受准则
为了处理因时间窗或电池约束引起的不可行解，作者设计了惩罚机制：在成本函数中加入不可行度乘以惩罚系数；惩罚系数随搜索动态调整，使算法能够在可行解和不可行解之间探索并逐步收敛。此外，采用模拟退火准则决定是否接受劣解，使搜索过程具有适度的随机性和跳跃性。
四 数值实验与结果分析
4.1 实例生成与参数设置
实验基于 HEV‑TSPTW 数据集扩展而成。原数据集包含不同车辆数、客户数和地理布局的216 个实例。为了生成 MM‑HEVRPTW 实例，作者随机生成客户需求（10–40 单位），设置车辆数为2～5辆，容量为150，电池容量为16.8 kWh，电池充电与放电速率分别为 12 kW/h 和 48 kW/h。同一弧在不同模式下的成本和时间根据 HEV‑TSPTW 数据集估算：燃油模式成本系数为100%，电动模式20%，充电模式110%，增压模式120%，行驶时间顺序为增压 < 燃油 < 充电 < 电动。
ALNS 的参数通过预实验调优。对最大移除数 和最大迭代数 分别测试多个取值，结果表明 、 能在解质量和计算时间之间取得良好平衡。其他参数如 等参考了文献并结合实验调整。
4.2 算子有效性分析
论文比较了不同移除和插入算子组合在20 客户实例上的性能。结果显示，采用最差成本移除结合动态随机插入的配置在平均成本和计算时间上表现最好。Shaw 移除和随机移除的性能与最差成本移除相近，但计算时间略高；最差时间移除效果最差。在插入算子中，动态随机插入和随机插入优于贪心插入和后悔插入，说明适度的随机性有助于搜索跳出局部最优。
进一步的实验表明，引入新的移除数策略和 3‑MC 算子后，算法能获得更好的解；半随机局部搜索比仅使用 RVND 能进一步降低成本。
4.3 算法比较与敏感性分析
4.3.1 算法比较
将所提 ALNS 与 CPLEX、混合遗传搜索(HGS)在不同规模实例上比较。对8 或10 客户的小规模实例，ALNS 在短时间内即可找到与 CPLEX 相同甚至更优的解，而 CPLEX 的求解时间远高于 ALNS。在20 和50 客户的中、大规模实例上，CPLEX 无法在 1 小时内求得最优解，而 ALNS 平均几分钟即可获得高质量解，且明显优于 HGS。
4.3.2 多模式优势分析
作者比较了多模式和单模式（仅燃油或仅电动）情况下的解。结果表明，多模式能显著减少成本，因为车辆可以在特定路段使用成本低的模式，在需要赶时间时切换为增压模式。
4.3.3 电池充放电率敏感性
文中调整电池充电速率和放电速率的比值，考察对成本的影响。图 5 显示，当充电率/放电率比值从 1:3.5 增大至 1:1 时，提升电池放电率（即减小放电时间）比提升充电率对成本下降效果更显著，说明提高电池放电功率更值得关注。表 14 进一步列出了不同实例的百分比变化。
图 5 显示了调整电池充电/放电率对平均解成本的影响。曲线表明，当放电率提升时，成本下降更快；同时提升充放电率也能降低成本，但效果介于前两者之间。
五 结论与启示
本文在绿色车辆路径研究领域提出了多模式混合动力车辆路径问题(含时间窗)。通过构建混合整数线性模型，明确了路线规划、时间窗、电池状态和模式选择之间的复杂耦合关系，并给出了严格的约束体系。针对模型复杂性，文章设计了改进的自适应大规模邻域搜索算法，融合多种毁坏与修复算子、半随机局部搜索、3‑MC 模式变换以及惩罚机制等，显著提升了求解效率。
数值实验表明，所提算法在小规模实例上能快速获得最优解，在中、大规模实例上明显优于 CPLEX 和当前领先算法，验证了其有效性和稳定性。利用多模式运行能有效降低成本；在电池技术改进方面，提高电池放电速率比提升充电速率更能降低运输成本。
实践启示：
模式策略优化 – 物流企业应根据路段特点和时间要求灵活切换 HEV 运行模式，充分利用电动模式的低成本和增压模式的时间优势。
电池技术发展 – 汽车制造商在改进混合动力车辆时可优先提升电池放电速率，以便在需要快速行驶时提供更大电功率，减少总行驶成本。
算法应用 – 所提 ALNS 框架具有通用性，可扩展到考虑多仓库、混合车队或随机需求的复杂路由问题。未来还可以考虑非线性充电、车辆电池老化、交通拥堵和天气等随机因素，以提升模型现实性。
总体而言，MM‑HEVRPTW 为绿色物流提供了新的建模和优化思路，具有广阔的理论和应用前景。
文章须知
推文编辑：单子叶
责任编辑：张仁义
原文链接：https://doi.org/10.1016/j.tre.2025.103976
