一类网络k-中心选址问题的改进算法  

k-center of network location problem based on improved algorithm

作　　者：王开华[1] 王玉北[2] 曲晓波 刘洪伟[1] 

机构地区：[1]解放军理工大学通信工程学院 [2]解放军理工大学工程兵工程学院 [3]61213部队通信修理所

出　　处：《解放军理工大学学报（自然科学版）》2006年第5期442-445,共4页Journal of PLA University of Science and Technology(Natural Science Edition)

摘　　要：为解决基于城市道路交通网络的应急设施选址问题,建立了此问题的网络k-中心选址抽象模型。针对此模型在分析研究已有算法的基础上,设计了一种具有多项式时间的改进置换迭代算法,证明了算法迭代的有效性,分析了算法的计算复杂度,并利用实例进行了对比分析。实例分析表明,改进的置换迭代算法降低了受限p-中心的并行迭代算法中的网络中心置换的条件,而算法的效率有明显的提高。To solve the problem of the optimal location of emergency establishments in the city,a k-center of network location abstract model was established, and aiming at the model, an improved exchange-iterative algorithm was designed based on the current algorithms. Then, the validity of the iterative algorithm was proved, and the complexity of the operation computed. The instance analysis indicates that the improved exchange-iterative algorithm reduces the exchange conditions of network center p-center of the re- stricted iterative algorithm, while the efficiency of the proposed algorithm is greatly improved.

关 键 词：网络选址 k-中心问题 算法 

分 类 号：TB114.1[理学—运筹学与控制论]