基于充电器类型与用户偏好的电动汽车分配优化算法

《World Electric Vehicle Journal》：Optimizing Algorithms to Allocate Electric Vehicles Based on Charger Types and User Preferences

　　

电动汽车(Electric Vehicle, EV)对于减少城市交通中的温室气体排放至关重要。然而，其推广应用需要高效的充电基础设施和分配策略。本文开发了五种启发式算法，用于将电动汽车分配到城市充电站。该分配过程纳入了关键约束，如用户偏好和充电器类型兼容性，同时遵守由功率输出规则决定的充电站容量限制。所提出的方法包括四种初始分配启发式算法，涵盖以容量为中心的方法、最近邻方法和随机分配方法，并由一种局部搜索算法对解进行精化。为评估这些启发式算法，研究人员从文献中改编了一个同时最小化充电站建设成本和车辆行驶成本的优化模型。计算实验在合成实例和真实世界案例研究中均得以开展。结果表明，所开发的启发式算法，尤其是在经局部搜索增强后，能在极具竞争力的计算时间内提供高质量、接近最优的解。因此，本研究为城市规划者提供了一种可扩展的决策支持工具，展示了基础设施成本与用户偏好的联合优化如何促进可持续城市交通并加速电动汽车的普及。最终，这些发现为扩展异构电动汽车基础设施、促进城市可持续性以及减少交通相关碳排放提供了可操作的见解。

基于充电器类型与用户偏好的电动汽车分配优化算法论文解读

一、研究背景与存在问题

电动汽车(Electric Vehicle, EV)在全球范围内的销量持续增长，巴西的电动汽车销量亦从2014年的61辆增至2024年的125,000辆。然而，电动汽车的普及依赖于高效的充电基础设施与分配策略。现有文献虽已从交通流量分布、候选站选择、电网能量成本、行驶时间等多类指标出发研究充电站选址问题，但鲜有研究在分配模型中考虑同一充电站内不同充电器类型的差异。多数优化模型仅单独考虑快充充电器、常规充电器或电池更换站，且用户偏好（如充电价格、便利店可用性、交通流量）与充电器类型兼容性未能充分纳入约束体系。此外，电动汽车到充电站的分配属于NP-hard组合优化问题。为此，本研究开发了考虑充电站容量、充电器类型及用户偏好的多种启发式算法。该成果发表于《World Electric Vehicle Journal》。

二、研究内容与总体结论

研究人员从文献改编了一个以最小化充电站建设财务成本与车辆行驶总距离为目标的数学优化模型，并在原模型基础上新增两项约束，确保车辆的用户偏好和所需充电器类型与候选站提供的偏好集合和充电器类型集合严格匹配。充电基础设施分为Level 2（Class 1 Type 2，19 kW；Class 2 GB/T中国标准AC，22 kW）与Level 3（Class 3 CHAdeMO，50 kW；Class 4 CCS2，150 kW；Class 5 GB/T中国标准DC，60 kW）五类充电器。实验表明，所提出的启发式算法，尤其经局部搜索增强后，可在极具竞争力的计算时间内获得高质量、接近最优的解，为城市规划者提供了可扩展的决策支持工具。

三、主要关键技术方法

研究人员采用的主要方法包括：（1）数学优化模型：最小化充电站建设成本与车辆行驶成本，约束涵盖单站唯一分配、站容量、用户偏好匹配、充电器类型匹配及二元变量完整性；（2）四种初始分配启发式：容量优先算法(AVtoCSCapacity)、最近邻算法(AVtoCSNN)、随机分配算法(AVtoCSRandom)及主随机版本(AVtoCSMainRandom)；（3）局部搜索算法(AVtoCSLSearch)：通过交换不同充电站间的车辆分配来精化解；（4）实例来源：合成实例在34 km×34 km区域（约对应巴西大维多利亚都市区，面积1135 km2）内随机生成坐标；案例研究采用大维多利亚67个真实充电站的位置与充电器类型数据，车辆需求与用户偏好为合成数据，并假设70%车辆充电。

四、研究结果

4.1 小规模与中等规模实例结果
在19个实例（20V–6CS至150V–80CS）中，容量优先算法在所有实例获得100%用户偏好成功率(User Preference Success Rate, UPSR)，且多数目标函数成本低于最近邻算法；最近邻算法计算时间最短；主随机算法在累计10次运行条件下获得最佳目标函数成本，14/19个实例UPSR超过95%。

4.2 局部搜索参数设置
局部搜索最坏情况复杂度为O(n⁴)，对不超过150辆车的实例无需调参；对200辆车及以上的大规模实例，迭代次数上限设为50次，以确保计算可行性。

4.3 随机分配算法统计分析
对随机分配算法执行最多1000次，结合三倍标准差离群值剔除与夏皮罗-威尔克(Shapiro-Wilk)正态性检验，发现各实例目标函数值近似服从正态分布且异常值极少，决策者可结合累积分布函数设定目标成本并估计达成概率。

4.4 基于大维多利亚真实数据的案例研究
对40辆车与67个候选站，算法结果UPSR最高为100%，但现有站无法无排队地完全服务全部车辆。在170V–67CSmod和184V–67CSmod替代场景（所有站满足全部偏好、每个Type 2接口含两个连接器、仅70%车辆充电）中，分别有118辆和127辆车可获充电服务，且无排队、UPSR为100%。24小时动态行为分析进一步表明，充电站可按时段满足不同用户偏好组合。

4.5 大规模实例结果
在200–1000辆车、80–300个充电站实例中，容量优先算法在所有实例UPSR均为100%；最近邻算法在目标函数成本上总体最优（200V–80CS除外），但其UPSR仅介于69.50%–83.18%；主随机算法计算时间最短。利用最小二乘法拟合开放充电站数量与车辆数的线性关系，可用以预测长期渗透率下的基础设施需求：若按每半年约10%增长率，102个月内车辆从200增至1000辆，开放站需从约50增至约200个；对大维多利亚现有67个站，60个月内需扩建至约115个站以服务约478辆车。

4.6 理论可解释性与计算复杂度
该分配问题本质为NP-hard。局部搜索对小型至中型实例（≤150辆车）执行穷尽邻域搜索，最坏复杂度为O(n⁴)；对大型实例（≥200辆车）施加迭代上限，将复杂度约束在可控范围内，防止组合爆炸。

五、讨论总结与研究结论

讨论部分指出，电动汽车制造涉及电池、电力电子与充电技术等多工业部门，导致车辆充电系统多样化，这使充电基础设施规划更具挑战性。所有算法均考虑站容量与充电器类型，但各有侧重（邻近性、用户偏好、开放候选站数量），利益相关者可根据投资策略或用户满意度目标权衡选择，例如接受90%的UPSR可显著降低因增开高成本候选站带来的资本支出。确定性算法在目标函数成本上优于随机启动程序，验证了所提方法的有效性；算法均具有低内存消耗与高鲁棒性。局限性包括最坏情形假设所有车辆同时充电、每用户仅可指定单一偏好，以及对随机到达、非线性电池充电动力学和分时电价等现实因素的抽象。

研究结论（翻译）：本文提出了用于电动汽车向充电站战略分配的优化算法，解决了向可持续低碳城市交通转型中的一个关键瓶颈。通过整合站容量、异构充电器类型与多元化用户偏好（含交通流量、便利设施和充电成本）等关键现实约束，研究人员开发了一套启发式算法，能够求解包含多达1000辆电动汽车和300个充电站的小型至大规模实例。严格的计算验证及真实数据案例研究证明，所提出的确定性方法显著优于随机启动程序，从而验证了所开发搜索机制的结构设计。