最小费用充电站选址问题的分支定界算法

来源：计算机应用研究杂志2022年第1期北京时间：

作者：孙智勇,宁爱兵,傅汤毅,尹思淼,张惠珍,

单位：上海理工大学管理学院,上海200093；

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

关键词：充电站选址,精确算法,上界算法,下界算法,分支定界算法,

基金资助：国家自然科学基金项目(71401106)；上海市“管理科学与工程”高原学科建设项目；；