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

摘要：有容量集合覆盖选址问题是组合优化中的一个经典的NP-Hard问题,在许多工程领域和科学领域中的应用十分广泛.本文将集合覆盖问题的模型应用到有容量设施选址问题中,首先研究了该问题的数学性质并给予相应的证明,利用这些数学性质能够对问题进行降阶,降低问题求解难度;然后设计了上界子算法、下界子算法和分配子算法,基于这些子算法提出了一种能够快速缩小问题规模同时能得到精确解的降阶回溯算法;最后文章通过分析和求解一个示例来进一步阐述本文算法的原理和执行过程.