电动汽车换电站选址问题的降阶回溯算法

作     者：林道晗 宁爱兵 刘书傲 尚春剑 钟翔 

作者机构：上海理工大学管理学院 

出 版 物：《计算机工程与应用》 (Computer Engineering and Applications)

年 卷 期：2025年

学科分类：0808[工学-电气工程] 08[工学] 082303[工学-交通运输规划与管理] 082302[工学-交通信息工程及控制] 0823[工学-交通运输工程] 

基　　金：上海市青年科技英才扬帆计划(24YF2730100) 国家资助博士后研究人员计划(GZC20231675) 教育部人文社科青年项目(24YJC630175) 

主　　题：换电站选址问题 精确算法 降阶算法 上下界子算法 回溯算法 

摘      要：换电站是一种为电动汽车提供动力电池快速更换服务的设施，它能够有效解决电动汽车续航里程短的问题，并缩短电动汽车的充电时间，从而提高电动汽车的使用效率。电动汽车换电站选址问题作为一个典型的NP-hard问题，除非P=NP，否则不存在多项式时间的精确算法。本文首先结合实际情况，按照换电站选址问题的特点以及利益最大化的目标建立数学模型，研究数学性质，并使用数学性质对问题规模进行缩减以降低求解时间以及难度，部分性质可以成批确定某些设施不开设；此外，设计符合换电站选址问题特点的分配子算法、上界子算法、下界子算法，并将其融合进能得到最优解的降阶回溯算法；最后，通过对随机和实际案例的演示进行实证。