电动汽车换电站选址问题的降阶回溯算法
来源：计算机工程与应用杂志2026年第2期北京时间：
作者：林道晗, 宁爱兵, 刘书傲, 尚春剑, 钟翔
单位：上海理工大学 管理学院，上海 200093；
摘要：换电站是一种为电动汽车提供动力电池快速更换服务的设施，它能够有效解决电动汽车续航里程短的问题，并缩短电动汽车的充电时间，从而提高电动汽车的使用效率。电动汽车换电站选址问题作为一个典型的NP-hard问题，除非[P=NP]，否则不存在多项式时间的精确算法。结合实际情况，按照换电站选址问题的特点以及利益最大化的目标建立数学模型，研究数学性质，并使用数学性质对问题规模进行缩减以降低求解时间以及难度，部分性质可以成批确定某些设施不开设；此外，设计符合换电站选址问题特点的分配子算法、上界子算法、下界子算法，并将其融合进能得到最优解的降阶回溯算法；最后，通过对随机和实际案例的演示进行实证。
关键词：换电站选址问题,精确算法,降阶算法,上下界子算法,回溯算法
基金资助：上海市青年科技英才扬帆计划（24YF2730100）；国家资助博士后研究人员计划（GZC20231675）；教育部人文社科青年项目（24YJC630175）。
