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

Branch and bound algorithm for minimum cost charging station location problem

作　　者：孙智勇 宁爱兵[1] 傅汤毅 尹思淼 张惠珍[1] Sun Zhiyong;Ning Aibing;Fu Tangyi;Yin Simiao;Zhang Huizhen(Business School,University of Shanghai for Science&Technology,Shanghai 200093,China)

机构地区：[1]上海理工大学管理学院,上海200093

出　　处：《计算机应用研究》2022年第1期80-83,共4页Application Research of Computers

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

摘　　要：电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。The location problem of electric vehicle charging station is a hot issue in the current society,its essence is the classical NP-hard problem in combinatorial optimization.This paper studied the location of charging station based on the minimum opening cost.Firstly,this paper established the mathematical model of the problem,then studied the mathematical properties of the problem and gave the corresponding proof.It used these properties to reduce the scale of the problem,so as to reduce the difficulty of solving the problem.Then this paper designed the upper and lower bound sub algorithm and the reduced order sub algorithm.Based on these sub algorithms,this paper proposed the branch and bound algorithm which could quickly reduce the size of the problem and obtain the optimal solution,which reduced the time complexity and pruned the solution space to speed up the solution speed.Finally,it gave an example to illustrate the principle and implementation of the algorithm.

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

分 类 号：O223[理学—运筹学与控制论]