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

• 作者: 孙文彬 赵学胜 闫志远
• 来源期刊: 中国矿业大学学报
• 学科: 地球科学
• 关键词: P-中位问题 网络分割 解的质量 目标函数
• 年，卷（期）: 2016,（6）
• 页码范围: 1294-1299
• 分类号: P208
• 语种: 中文

摘要

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