摘要：最大覆盖选址问题在实际生活中有广泛的应用,是组合优化中的一个NP-Hard问题。首先提出问题的上下界子算法,然后研究数学性质,其中包括可以批量确定某些设施一定开设或一定不开设的性质。最后,利用上下界子算法和这些数学性质设计出一种可以快速减小问题规模且能求出最优解的降阶回溯算法。通过一个示例阐述该算法的执行过程。

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

摘要：电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。