考虑电池寿命的实时电动汽车路径规划与充电优化（Real-Time Electric Vehicle Routing and Charging Optimization with Battery Life Consideration）

《Internet of Things》：Real-Time Electric Vehicle Routing and Charging Optimization with Battery Life Consideration

　　

摘要：向电动化出行的转型给车辆路径规划和能量管理带来了前所未有的挑战，特别是在实时运行约束下。本文对自主电动汽车（Electric Vehicle, EV）路径规划与充电优化的方法论进行了综合性对比分析，解决了平衡行驶时间最小化与电池保护之集成决策框架的关键需求。研究人员将问题建模为一个优化模型，纳入交通状况、充电站可用性、电池荷电状态（Battery State-of-Charge, SoC）演化及最小电量约束以缓解里程焦虑（Range Anxiety）。为解决该计算困难问题，研究人员开发并评估了多种求解方法：包括时间高效路径与充电算法（Time Efficient Routing and Charging, TERC）、TERC2及动态TERC2（Dynamic TERC2）等启发式算法；基于经典强化学习（Reinforcement Learning, RL）的Q-learning与迁移Q-learning（Transfer Q-learning）；通过深度Q网络（Deep Q-Network, DQN或Deep Q-Learning, DQL）实现的深度强化学习；以及模拟退火（Simulated Annealing, SA）和模因算法（Memetic Algorithm, MA）等前沿元启发式算法。各方法在具系统分布充电基础设施、不同规模网络及动态交通条件下实施与测试。实验结果表明深度强化学习持续优于其余替代方法：在较大网络上相比表格式Q-learning减少行驶时间15–25%，相比MA减少7.0–8.1%，相比SA减少13.1–16.1%，同时维持更优的电池荷电状态轨迹及更快收敛速度。启发式方法在较小网络中表现具竞争力，但随问题规模增大显现局限性。以启发式解初始化的迁移Q-learning相比标准Q-learning实现加速收敛，但最终性能未超越深度Q网络。系统性对比揭示神经网络函数逼近（Neural Function Approximation）在捕捉EV路径规划问题固有复杂状态空间动态方面具显著优势。上述发现有助于智能交通系统（Intelligent Transportation Systems, ITS）发展，并为城市环境中实施实时EV路径规划方案提供实践见解。

论文解读：《考虑电池寿命的实时电动汽车路径规划与充电优化》

该研究发表于《Internet of Things》。

一、研究背景与意义

传统内燃机车辆的路径规划方法无法适用于电动汽车（Electric Vehicle, EV），因为EV面临续航里程有限、充电时间长、充电基础设施空间分布不均以及电池非线性退化等特有约束。现有文献缺乏对精确数学规划、启发式策略和基于学习的方法在相同实验条件下的系统性对比，且多数公式未充分考虑动态城市环境中的时变交通、充电站排队及电池寿命保护约束。为填补这一空白，研究人员开展了跨范式（精确法、启发式法、强化学习法及元启发式法）的系统比较研究，建立了兼顾行驶时间最小化与电池保存（Battery Preservation，通常限制荷电状态State-of-Charge, SoC于B_min=20%至B_max=80%）的EV路径与充电联合优化框架，具有重要的智能交通系统（Intelligent Transportation System, ITS）理论与应用价值。

二、关键技术方法

研究人员采用Erd?s–Rényi模型生成20至1000节点的有向路网，按覆盖最大化策略布设交流充电站，边属性含距离、时间与能耗，引入交通因子模拟动态环境，并以Tesla Model 3参数（满电续航545 km，平均时速60 km/h，AC充电率约0.2%/min）实例化。首先建立最小化到达时间的目标函数并附流量守恒、时间传播、充电约束及SoC边界（含目的地安全余量E_toStation(D)）的混合整数线性规划（Mixed-Integer Linear Programming, MILP）作为最优基线。随后设计三类启发式：基本时间高效路径与充电（Time Efficient Routing and Charging, TERC）递归插充站算法、双向评估选站的增强版TERC2、允许部分充电的K-最快路径（K-Fastest Paths, KFP）及能实时更新边属性的动态TERC2（Dynamic TERC2）。强化学习（Reinforcement Learning, RL）方面将问题建模为马尔可夫决策过程（Markov Decision Process, MDP），状态含节点位置、剩余SoC百分比、累积时间及终止标志，动作为沿出边移动或在充电站决定补电量，奖励为负耗时并施予越界惩罚，分别实现表格式Q-learning（?-greedy探索、α/?衰减）、以Dynamic TERC2解热启动值表的迁移Q-learning（Transfer Q-learning, TQL）及带经验回放（Experience Replay）与目标网络（Target Network）的深度Q网络（Deep Q-Network, DQN或DQL）。此外实现模拟退火（Simulated Annealing, SA，含2-opt/充电站插入/节点移除扰动及Metropolis准则）与模因算法（Memetic Algorithm, MA，有序交叉OX、变异、2-opt局部搜索）作为元启发式基准。MILP用CPLEX求解，其余用Python 3实现，每组合十次独立重复取均值。

三、研究结果

7.1. Network Generation Methodology

研究人员按所述流程生成测试网络并随机选取满足最小距离要求的起止点对，确保KFP可解。

7.2. Validation Against Optimal Solutions

在20–80节点网络上以MILP（OPL求解）为基准，TERC2与KFP均获最优解，TERC最大最优性间隙7.4%且随规模略增；MILP在120节点需约10分钟且150节点内存溢出，而TERC/TERC2千节点耗时低于14秒，KFP在千节点约76.5秒——说明启发式具良好可扩展性。

7.3. Large-Scale Heuristic Comparison

250–1000节点显示KFP旅行时间至多比TERC2低4.5%、耗电低8%；TERC随规模增大明显劣化。TERC2兼具低耗时、保证解存在及适应动态重规划之优势。

7.4. Dynamic Environment Evaluation

动态交通下Dynamic TERC2较静态TERC2降旅行时间；Q-learning获各规模最低旅行时间但路径较长，说明RL习得时变感知策略。

7.5. Charging Station Density Sensitivity

固定250节点网络中充电站由25增至35座，启发式性能单调改善，Q-learning差距拉大表明RL更好利用扩展动作空间。

7.6. Rural Versus Urban Environments

农村（节点距50–150 km）因长路段致频繁充电压缩方法差异，城市（0–50 km）路由灵活放大RL优势。

7.7. Reinforcement Learning Comparative Analysis

125/250/500节点对比显示：DQL旅行距离最短、收敛最快；TQL因启发式初始化在大网络上较Q-learning快收敛且终值更优；DQL累计回报（负最小）最高，Q值更新波动最平稳。稀疏充电站下DQL仍保持优势。

7.8. Comparison with State-of-the-Art Metaheuristics

250节点：DQL均值旅行时间17.2 h，优于MA(18.5 h, 7.0%)与SA(19.8 h, 13.1%)；500节点：DQL 26.0 h，优于MA(28.3 h, 8.1%)与SA(31.0 h, 16.1%)。能耗上DQL(94.8 kWh)<MA(98.5 kWh)<TERC2(110.2 kWh)<SA(103.6 kWh)<Q-learning(118.4 kWh)。计算效率：TERC2<0.1 s/千节点，SA约52.7 s/千节点，MA超400 s/千节点。

四、讨论与结论翻译

本研究对实时电动汽车路径规划与充电优化方法开展了涵盖精确数学规划、启发式算法（TERC、TERC2、Dynamic TERC2、KFP）及强化学习（Q-learning、迁移Q-learning、深度Q-learning/DQL）的综合性对比分析，并与模拟退火（SA）及模因算法（MA）两类前沿元启发式对照。实验表明深度Q网络（DQL）持续优于所有对比方法：在250节点与500节点网络上较MA减少行驶时间7.0–8.1%，较SA减少13.1–16.1%，较表格式Q-learning减少15–25%，且维持更优电池荷电状态轨迹与更快收敛。以启发式解初始化的迁移Q-learning（TQL）在较大网络上加速收敛但未超越DQL最终性能。模因算法（MA）较TERC2改善行驶时间4.1%及能耗10.6%，但计算耗时显著增加（500节点135.6 s vs TERC2 0.078 s）。结果证实神经网络函数逼近使DQL能捕捉交通模式、充电设施与电池动态间复杂关系，且在充电设施增多时间隙扩大。尽管DQL表现最佳，其存在训练耗时长、超参数敏感、策略不可解释等局限。未来工作拟引入迁移学习缩减训练、贝叶斯超参数优化、可解释AI、随机充电站故障建模及策略梯度或图神经网络（Graph Neural Network, GNN）提升泛化能力。所提方法可应用于网约车导航、电动物流车队管理、自动驾驶电动出租车调度及智慧城市基建规划，助力可持续城市出行系统发展。