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

作     者：孙文彬 闫志远 赵学胜 SUN Wenbin;YAN Zhiyuan;ZHAO Xuesheng

作者机构：中国矿业大学(北京)地球科学与测绘工程学院北京100083 

出 版 物：《中国矿业大学学报》 (Journal of China University of Mining & Technology)

年 卷 期：2016年第45卷第6期

页      面：1294-1299页

核心收录：

学科分类：081603[工学-地图制图学与地理信息工程] 081802[工学-地球探测与信息技术] 07[理学] 08[工学] 070503[理学-地图学与地理信息系统] 0818[工学-地质资源与地质工程] 0705[理学-地理学] 0816[工学-测绘科学与技术] 

基　　金：国家自然科学基金项目(41201416) 

主　　题：P-中位问题 网络分割 解的质量 目标函数 

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