一种求解带宽限制的中位问题的启发式算法  

Heuristic Algorithm for Solving Bandwidth Limited Median Problem

作　　者：陈丽丰 金忠 CHEN Lifeng;JIN Zhong(School of Computer Science and Engineering,Nanjing University of Science and Technology,Nanjing 210094)

机构地区：[1]南京理工大学计算机科学与工程学院

出　　处：《计算机与数字工程》2019年第10期2487-2491,共5页Computer & Digital Engineering

基　　金：国家自然科学基金项目(编号：61373063,61375007);国家重点基础研究发展计划(编号：2014CB349303)资助

摘　　要：针对带宽限制的中位问题,论文运用将设施点视为需求点的广义需求点思想,给出了根据当前解的最小费用流快速求邻域解的最小费用流的方法,并证明了该方法的正确性。然后给出了基于广义需求点思想的启发式算法,实验证明,该算法在带宽限制的中位问题的求解上要明显优于传统的启发式算法。Aiming at the bandwidth limited median problem,this paper uses the idea of generalized customer point by regarding facility point as customer point,and the method to fast obtain the minimum cost flow of neighborhood according to the minimum cost flow of the current solution is given and proved correct.Experiment shows that the heuristic algorithm based on generalized customer point is better than traditional heuristic algorithms on solving the bandwidth limited median problem.

关 键 词：设施选址问题 最小费用流 广义需求点 启发式算法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]