基于网络分割的P-中位问题求解方法
来源期刊:中国矿业大学学报2016年第6期
论文作者:孙文彬 闫志远 赵学胜
文章页码:1294 - 1299
关键词:P-中位问题;网络分割;解的质量;目标函数;
摘 要:针对传统的PMP(P-median problem)算法在单机环境下无法突破大规模地理网络求解时的空间和时间瓶颈,提出了一种基于网络分割的大规模稀疏网络P-中位问题求解方法.采用多层k-路划分算法对网络进行分割,将大规模PMP问题转换为多个小规模的PMP问题;研究了"子网络求解-归并-调整中位点数"操作对PMP解质量的优化效果;应用测试数据评价了网络分割对PMP解质量的影响.结果表明:该算法能够在单机环境下解算大规模PMP问题;分割后PMP解的偏差率在0.16%2.82%之间;随着中位点数的增加,网络分割对PMP解质量的影响呈减弱的趋势.
孙文彬,闫志远,赵学胜
中国矿业大学(北京)地球科学与测绘工程学院
摘 要:针对传统的PMP(P-median problem)算法在单机环境下无法突破大规模地理网络求解时的空间和时间瓶颈,提出了一种基于网络分割的大规模稀疏网络P-中位问题求解方法.采用多层k-路划分算法对网络进行分割,将大规模PMP问题转换为多个小规模的PMP问题;研究了"子网络求解-归并-调整中位点数"操作对PMP解质量的优化效果;应用测试数据评价了网络分割对PMP解质量的影响.结果表明:该算法能够在单机环境下解算大规模PMP问题;分割后PMP解的偏差率在0.16%2.82%之间;随着中位点数的增加,网络分割对PMP解质量的影响呈减弱的趋势.
关键词:P-中位问题;网络分割;解的质量;目标函数;