基于Power图求解容量限制P-中值问题

doi:10.11772/j.issn.1001-9081.2015.06.1623

计算机应用 ›› 2015, Vol. 35 ›› Issue (6): 1623-1627.DOI: 10.11772/j.issn.1001-9081.2015.06.1623

基于Power图求解容量限制P-中值问题

郑利平, 江婷, 周乘龙, 程亚军

合肥工业大学计算机与信息学院, 合肥 230009

收稿日期:2015-01-05 修回日期:2015-04-09 发布日期:2015-06-12
通讯作者: 郑利平(1978-),男,湖北麻城人,副教授,博士,CCF会员,主要研究方向:可视化、群体和疏散仿真;zhenglp@hfut.edu.cn
作者简介:江婷(1989-),女,安徽芜湖人,硕士研究生,主要研究方向:仿真建模;周乘龙(1990-),男,安徽安庆人,硕士研究生,主要研究方向:布料动画仿真;程亚军(1990-),男,安徽黄山人,硕士研究生,主要研究方向:群体仿真。
基金资助:
国家自然科学基金资助项目(61300118, 61370167, 61305093);安徽省科技强警项目(1401b042009)。

Solving approach of capacity constrained P-median problem based on Power diagram

ZHENG Liping, JIANG Ting, ZHOU Chenglong, CHENG Yajun

School of Computer and Information, Hefei University of Technology, Hefei Anhui 230009, China

Received:2015-01-05 Revised:2015-04-09 Published:2015-06-12

摘要/Abstract

摘要：

针对稠密需求下连续域上的容量P-中值问题,提出基于质心的容量限制Power图(CCCPD)理论,对连续P-中值问题进行近似建模,并加快计算过程。扩展Balzer试位法构造Power图,施加质心限制满足P-中值要求,施加容量限制满足需求密度下的容量要求。实验结果表明所提算法可快速得到近似可行解,同Alper Murata方法相比,计算效率高;同质心容量限制Voronoi图(CCCVT)相比,具有容量限制精确度高等优点,并能适应各种复杂需求密度函数。

关键词: P-中值, 连续域, 容量限制, Power图, 质心

Abstract:

Aiming at the capacity P-median problem of continuous domains under the dense demand, the Centroidal Capacity Constrained Power Diagram (CCCPD) theory was proposed to approximately model the continuous P-median problem and accelerate the solving process. The Power diagram was constructed by extended Balzer's method, centroid restriction was imposed to satisfy the requirements of P-median, and capacity constraint was imposed to meet the capacity requirements of certain demand densities. The experimental results show that the proposed algorithm can quickly obtain an approximate feasible solution, having the advantages of better computing efficiency and capacity accuracy compared to Alper Murata's method and Centroidal Capacity Constrained Voronoi Tessellation (CCCVT) respectively. Additionally, the proposed method has excellent adaptability to complex density functions.

Key words: P-median, continuous domain, capacity constraint, Power diagram, centroid

中图分类号:

TP391.9

郑利平, 江婷, 周乘龙, 程亚军. 基于Power图求解容量限制P-中值问题[J]. 计算机应用, 2015, 35(6): 1623-1627.

ZHENG Liping, JIANG Ting, ZHOU Chenglong, CHENG Yajun. Solving approach of capacity constrained P-median problem based on Power diagram[J]. Journal of Computer Applications, 2015, 35(6): 1623-1627.

参考文献

[1] CHAN Y. Facility location: a survey of applications and methods, springer series in operations research by Z. Drezner [J]. Transportation Science, 1999, 33(4): 429-430.
[2] KUNKEL A G, ITALLIE E S V, WU D. Optimal distribution of medical backpacks and health surveillance assistants in Malawi [J]. Health Care Management Science, 2014, 17(3): 230-244.
[3] FLESZAR K, HINDI K S. An effective VNS for the capacitated p-median problem [J]. European Journal of Operational Research, 2008, 191(3): 612-622.
[4] XU X, LI X, LI X, et al. Notice of retraction an improved scatter search algorithm for capacitated p-median problem [C]//Proceedings of the 2010 2nd International Conference on Computer Engineering and Technology. Piscataway: IEEE, 2010, 2: V2-316-V2-320.
[5] MAZINAN H G, AHMADI G R, KHAJI E. An efficient hybrid CS and k-means algorithm for the capacitated p-median problem [EB/OL]. [2014-12-08]. http://arxiv.org/abs/1406.7473.
[6] STEFANELLO F, de ARAUJO O C B, MVLLER F M. Matheuristics for the capacitated p-median problem [J]. International Transactions in Operational Research, 2014, 22(1): 149-167.
[7] MURAT A, VERTER V, LAPORTE G. A continuous analysis framework for the solution of location-allocation problems with dense demand [J]. Computers and Operations Research, 2010, 37(1):123-136.
[8] MURAT A, VERTER V, LAPORTE G. A multi-dimensional shooting algorithm for the two-facility location-allocation problem with dense demand [J]. Computers and Operations Research, 2011, 38(2): 450-463.
[9] ZHENG L, LIU Y, JIANG T, et al. A layout approach of city emergency centers with dense demand [J]. Journal of Computer-Aided Design & Computer Graphics, 2014, 26(6): 948-955.(郑利平, 刘玉飞, 江婷, 等.稠密需求下城市应急中心布局方法[J]. 计算机辅助设计与图形学学报, 2014, 26(6):948-955.)
[10] AURENHAMMER F, HOFFMANN F, ARONOV B. Minkowski-type theorems and least-squares clustering [J]. Algorithmica, 1998, 20(1): 61-76.
[11] BALZER M and HECK D. Capacity-constrained Voronoi diagrams in finite spaces [C]//Proceedings of the 5th Annual International Symposium on Voronoi Diagrams in Science and Engineering. Piscataway: IEEE, 2008: 44-56.
[12] BALZER M. Capacity-constrained Voronoi diagrams in continuous spaces [C]//ISVD'09: Proceedings of the 2009 Sixth International Symposium on Voronoi Diagrams. Piscataway: IEEE, 2009: 79-88.
[13] BALZER M, DEUSSEN O. Voronoi treemaps [C]//INFOVIS'05: Proceedings of the 2005 IEEE Symposium on Information Visualization. Washington, DC: IEEE Computer Society, 2005: 49-56.
[14] REITSMA R, TRUBIN S, MORTENSEN E. Weight-proportional space partitioning using adaptive Voronoi diagrams [J]. GeoInformatica, 2007, 11(3): 383-405.
[15] BALZER M, SCHLÖMER T, DEUSSEN O. Capacity-constrained point distributions: a variant of Lloyd's method [EB/OL]. [2014-12-03]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.177.6047.
[16] DU Q, FABER V, GUNZBURGER M. Centroidal Voronoi tessellations: applications and algorithms [J]. SIAM Review, 1999, 41(4): 637-676.
[17] MACQUEEN J. Some methods for classification and analysis of multivariate observations [EB/OL]. [2014-12-03]. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.308.8619.
[18] CORTES J, MARTINEZ S, KARATAS T, et al. Coverage control for mobile sensing networks[C]//ICRA'02:Proceedings of the 2002 IEEE International Conference on Robotics and Automation. Piscataway: IEEE, 2002: 1327-1332.

基于Power图求解容量限制P-中值问题

Solving approach of capacity constrained P-median problem based on Power diagram

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	杜柳青, 许贺作, 余永维, 张建恒. 基于改进SURF算法的柔性装夹机器人快速工件匹配方法[J]. 计算机应用, 2018, 38(7): 2050-2055.
[2]	吕立国, 季伟东. 结合质心思想和柯西变异策略的粒子群优化算法[J]. 计算机应用, 2017, 37(5): 1369-1375.
[3]	包威, 毛莺池, 王龙宝, 陈小丽. 基于动态分簇的移动目标追踪方法[J]. 计算机应用, 2017, 37(1): 65-72.
[4]	魏培, 姜平, 贺晶晶, 张会猛. 基于内三角形质心算法的超宽带室内定位[J]. 计算机应用, 2017, 37(1): 289-293.
[5]	刘勇, 张锦龙, 张彦波, 王韬. 改进的狭长空间中加权质心定位算法[J]. 计算机应用, 2015, 35(5): 1273-1275.
[6]	陈寿文. 基于质心和自适应指数惯性权重改进的粒子群算法[J]. 计算机应用, 2015, 35(3): 675-679.
[7]	陈晓海, 彭舰, 刘唐. 基于最优信标节点的无线传感器网络质心定位算法[J]. 计算机应用, 2015, 35(1): 5-9.
[8]	曾鹤杨宜民. 基于零力矩点预观控制的在线步态规划[J]. 计算机应用, 2014, 34(2): 514-518.
[9]	李颖芳晏立杨波. 传感器网络节点表面部署优化算法[J]. 计算机应用, 2013, 33(10): 2730-2733.
[10]	唐杰黄宏光. 基于投影栅格扫描的无线传感器网络三维定位算法[J]. 计算机应用, 2013, 33(09): 2470-2473.
[11]	张爱清叶新荣胡海峰. 无线传感器网络质心定位新算法及性能分析[J]. 计算机应用, 2012, 32(09): 2429-2431.
[12]	于国晨刘永信李晓红. 基于三维线性倒立摆的仿人机器人步态规划[J]. 计算机应用, 2012, 32(09): 2643-2647.
[13]	胡金东. 双足机器人步行模式的在线全身修正[J]. 计算机应用, 2011, 31(01): 286-288.
[14]	胡丹丹李万民刘芳高庆吉. 基于Fisher准则的多铆钉线聚类融合识别算法[J]. 计算机应用, 2010, 30(4): 953-955.
[15]	朱志良赵玉丽于海. 基于像素分布与三角形分割的快速分形图像压缩算法[J]. 计算机应用, 2010, 30(2): 337-340.