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

为解决基于城市道路交通网络的应急设施选址问题,建立了此问题的网络k-中心选址抽象模型。针对此模型在分析研究已有算法的基础上,设计了一种具有多项式时间的改进置换迭代算法,证明了算法迭代的有效性,分析了算法的计算复杂度,并利用实例进行了对比分析。实例分析表明,改进的置换迭代算法降低了受限p-中心的并行迭代算法中的网络中心置换的条件,而算法的效率有明显的提高。

k -center of network location problem based on improved algorithm

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 restricted iterative algorithm,while the efficiency of the proposed algorithm is greatly improved.