详情

原文传递求解电动汽车复杂路径问题的进化算法研究

论文题名：	求解电动汽车复杂路径问题的进化算法研究
关键词：	电动汽车;路径问题;充电决策;进化算法
摘要：	伴随着全球经济快速增长，能源匮乏、环境污染等现象日益严峻，绿色物流以减少能源消耗、降低环境污染为目标，受到各国政府和国际组织的倡导，发展绿色物流已成为实现可持续和高质量发展的重要手段。电动汽车(ElectricVehicle,EV)因节能零污染的显著优势，正逐步成为绿色物流配送中主要的新能源运输工具，开发有效解决电动汽车车辆路径问题(CapacitatedElectricVehicleRoutingProblem,CEVRP)的算法，提高路径规划精度，减少计算成本，优化时间效率，对改善电动汽车路径规划质量具有重要的意义。进化算法具备良好的全局搜索能力，研究表明，其可以有效解决车辆路径问题。然而，电动汽车与传统燃油汽车不同，在路径规划时除考虑容量相关的约束外，还需要考虑电池电量相关的约束，与容量约束相关的路由子问题和与电量约束相关的充电子问题之间存在强耦合关系，搜索空间极度复杂，严重影响算法性能和收敛速度。不仅如此,在实际物流场景中，由于物流规模日益增大，现有算法在大规模电动汽车路径规划问题上的实效性显著降低。综上所述，针对电动汽车复杂路径问题，本文首先提出一种基于双种群的协同进化框架以求解强耦合的电动汽车车辆路径问题;然后针对实际应用中的大规模情形，提出一种基于代理模型辅助加速的进化算法以高效求解大规模电动汽车车辆路径问题。本文主要研究工作如下: 　　(1)针对电动汽车车辆路径问题中子问题之间存在强耦合关系导致算法很难快速寻找到最优解，提出一种基于双种群的协同进化框架。由于大多数现有方法通常对两个子问题采用分阶段交替优化的方式，并未考虑两个子问题之间的强耦合关系，所提基于双种群的协同进化框架通过采用两个种群协作、同时优化路由问题和充电问题，可以很好地考虑二者之间的耦合关系并进行协同一致搜索。具体来说，首先采用一个种群用于处理与容量约束相关的路由子问题，并提出一种改进的蚁群优化算法生成包含充电站的完整路由，以考虑充电站位置对路由规划的影响;其次，采用另一个种群用于优化与电量约束相关的充电子问题，并设计一种二进制遗传算法用于生成一组基于0-1编码的充电决策方案，通过提供多种充电方案以更好地匹配最优路由，从而减少冗余的搜索;最后，设计一种高效的信息交互策略促进两个种群之间协同进化，通过有效信息交互，一致收敛至原始问题的最优解。实验结果表明，与四种先进算法相比，所提算法具有更好的收敛性能，在多种不同分布场景的34个测试问题上，能获得21个更好的全局最优解。　　(2)针对现有算法在求解大规模电动汽车车辆路径问题时存在效率低下的问题，提出一种基于代理模型辅助加速的进化算法(Surrogate-assistedAcceleratedEvolutionaryAlgorithm,SAEA)。现有算法通常采用分阶段迭代优化的思想，先优化一组路由，然后优化每个路由的相应充电位置方案。由于需要对每个路由相应的充电位置方案都要进行一次完整的优化，这将导致大量计算资源的消耗，尤其在实际应用中客户数量急剧增加，现有算法在计算效率上表现不足。因此，本文提出一种基于代理模型辅助加速的进化算法，主要思想是在充电优化阶段引入代理模型，替代部分真实充电优化过程，直接预测完整路由所对应的总距离，用以快速挑选高质量路由进入下一代，从而加速算法的计算效率。具体来说，首先在路由优化阶段，采用改进的最大最小蚁群系统算法生成高质量的路由;其次在充电优化阶段，引入代理模型构建只含客户的路由与对其加入真实优化充电方案后组成的完整路径总长度之间的对应关系，以达到输入客户访问部分路由，能直接预测加入充电站后完整路径的总距离，从而快速选择出有潜力的路由进行优化。实验结果表明，所提出的算法获得的解质量相比其他先进算法具有一定的竞争力,且在计算效率上平均提高了将近14个百分点。
作者：	秦芳
专业：	软件工程
导师：	张兴义;王朝
授予学位：	硕士
授予学位单位：	安徽大学
学位年度：	2023