电动汽车的充电站选址问题是当前社会的热点问题, 其实质是组合优化 中经典的NP-难问题. 文章首先研究了该问题良好的数学性质并给予相应的证明, 其中 包括可以批量确定某些设施一定开设或一定不开设的性质, 利用这些性质降低问题的规 模, 从而降低问题的求解难度; 然后设计了上界子算法, 下界子算法, 分配子算法以及降阶子算法, 基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的降 阶回溯算法; 最后通过分析和求解一个示例来进一步阐述文章算法的原理和执行过程, 结 果表明所提出的算法能够有效地降低时间复杂度.

The location of electric vehicle charging station is a hot issue in the current society, Its essence is the classical NP-hard problem in combinatorial optimization. In this paper, we study some good mathematical properties of the problem and give corresponding proofs, which including the properties that can determine batches of facilities that must engage or not; then according to these mathematical properties, the upper bound sub algorithm, the lower bound sub algorithm and the reduced order sub algorithm are designed, which can reduce the scale of the problem quickly. Furthermore, according to the maximum flow algorithm in graph theory, the sub algorithm of the problem is designed. Based on these sub-algorithms, a backtracking algorithm with reduction that can rapidly reduce the problem size and obtain a global best solution is proposed. Finally, an instance is given to illustrate the principle and implementation of the proposed algorithm. The results show that the proposed algorithm can effectively reduce the time complexity.