基于网络分割的P-中位问题求解方法

P-median algorithm based on network subdivision method

针对传统的PMP（P-median problem）算法在单机环境下无法突破大规模地理网络求解时的空间和时间瓶颈,提出了一种基于网络分割的大规模稀疏网络P-中位问题求解方法.采用多层k-路划分算法对网络进行分割,将大规模PMP问题转换为多个小规模的PMP问题;研究了＂子网络求解-归并-调整中位点数＂操作对PMP解质量的优化效果;应用测试数据评价了网络分割对PMP解质量的影响.结果表明：该算法能够在单机环境下解算大规模PMP问题;分割后PMP解的偏差率在0.16%～2.82%之间;随着中位点数的增加,网络分割对PMP解质量的影响呈减弱的趋势.

Traditional P-median problem（PMP）algorithms based on personal computer（PC）are facing two main bottlenecks,which are PC memory limitation and unacceptable consuming time.A new PMP algorithm for large-scale network problem was proposed based on network subdivision method.Firstly,we subdivided large-scale network into a number of small-scale networks by using multi-level k-path subdivision scheme and the result of merging subdivided networks PMP objective function values can be considered as initial solution.Then,initial solution was optimized by carrying out computing subdivided network solutions,merging solutions and changing the P-median point number of each subdivided networks repeatedly.At last,the subdividing scheme impact of PMP solution was assessed by using test data.The result indicates that Large-scale network P-median problem solutions can be acquired based on PC;the error of PMP solution caused by subdividing scheme is between 0.16% and 2.82%;with the number increasing of P-median points,the error of subdividing scheme becomes smaller.