网络Voronoi图启发的粒子群空间优化建模

doi:10.3724/SP.J.1047.2013.00846

地球信息科学学报 ›› 2013, Vol. 15 ›› Issue (6): 846-853.doi: 10.3724/SP.J.1047.2013.00846

网络Voronoi图启发的粒子群空间优化建模

谢顺平, 冯学智, 都金康

南京大学江苏省地理信息技术重点实验室, 南京大学地理与海洋科学学院地理信息科学系, 南京 210046

收稿日期:2013-11-20 修回日期:2013-12-06 出版日期:2013-12-25 发布日期:2013-12-25
作者简介:谢顺平（1957-），男，南京市人，博士，教授级高级工程师，主要从事地理信息系统理论与应用、空间分析模型、智能空间优化等研究。E-mail：xiesp@nju.edu.cn
基金资助:
国家自然科学基金项目（41371044、40401046）。

Network Voronoi Diagram Heuristic-based Particle Swarm Continuous Spatial Optimization Modeling

XIE Shunping, FENG Xuezhi, DU Jinkang

Jiangsu Provincial Key Laboratory of Geographic Information Science and Technology, Nanjing University, Department of Geographic Information Science, School of Geographic and Oceanographic Sciences, Nanjing University, Nanjing 210046, China

Received:2013-11-20 Revised:2013-12-06 Online:2013-12-25 Published:2013-12-25

摘要/Abstract

摘要：

城市化区域多设施空间优化建模是一项实用的关键技术，可为城市公共资源均衡优化配置和空间决策提供支持。本文提出了网络Voronoi图启发的多设施选址粒子群空间优化建模方法，分别给出了基于常规Voronoi图启发的p-中值选址模型和最大覆盖选址模型，以及基于网络Voronoi面启发的p-中值选址模型和最大覆盖选址模型。模型采用Voronoi图定量提取设施功能覆盖和服务范围内的需求，并通过最小化重叠覆盖启发空间优化最大化覆盖分布的需求。p-中值选址模型考虑了需求随路径距离衰减的因素，最大覆盖选址模型顾及了设施对最大覆盖半径范围以内需求的完全覆盖，以及对以外区域的部分衰减覆盖。在空间优化粒子群算法中融入遗传进化机制和常规Voronoi图模拟的粒子动态邻域结构，提高了算法的全局搜索和优化性能。通过对实验区多设施进行的p-中值选址空间优化实验和最大覆盖选址空间优化实验，验证了本文提出的模型、方法和算法的有效性，可应用于城市化区域的空间优化决策支持。

关键词: 空间优化建模, 图启发式, 多设施选址, 粒子群算法, 网络Voronoi图

Abstract:

Spatial optimization modeling for multi facilities in urbanized area is a practical and key technique, and it can provide balance configuration optimization and spatial decision support for urban public resource. A method of particle swarm spatial optimization modeling for multi facilities location based on network Voronoi diagram heuristic is proposed in this paper, in which we presented respectively some p-median location models and maximal covering location models by using ordinary Voronoi diagram heuristic and network Voronoi diagram heuristic. Those models can quantitatively extract the demands coved by the function and service of facilities through the Voronoi diagrams, and inspire spatial optimization to maximize the coverage for distributed demands by minimizing overlapped coverage. The proposed p-median location model considers the factor of demand attenuation with path distance, and the proposed maximal covering model takes it into account that facility's service provides full coverage for the demands within maximal coverage radius and partial attenuation coverage for the demands without maximal coverage radius. The genetic evolution mechanism and the dynamic neighborhood structure of particles simulated by ordinary Voronoi diagram are integrated in the particle swarm spatial optimization to improve global search and optimization performance of the algorithm. Through the research of spatial optimization configuration experiments for multi facilities in experimental city, the proposed method has been verified to be the effective and practical, it can be applied for the spatial location optimization decision in urbanized area.

Key words: Network Voronoi Diagram, Multi-facilities Location, Particle Swarm Optimization, Spatial Optimization Modeling, Diagram Heuristic

谢顺平, 冯学智, 都金康. 网络Voronoi图启发的粒子群空间优化建模[J]. 地球信息科学学报, 2013, 15(6): 846-853.DOI:10.3724/SP.J.1047.2013.00846

XIE Shun-Beng, FENG Hua-Zhi, DOU Jin-Kang. Network Voronoi Diagram Heuristic-based Particle Swarm Continuous Spatial Optimization Modeling[J]. , 2013, 15(6): 846-853.DOI:10.3724/SP.J.1047.2013.00846

参考文献

[1] 黎夏, 刘小平, 李少英. 智能式GIS与空间优化[M].北京:科学出版社, 2010.

[2] Okabe A, Satoh T, Furuta T, et al. Generalized network Voronoi diagrams: Concepts, computational methods and applications[J]. International Journal of Geographical Information Science, 2008, 22(9):965-994.

[3] Okabe A, Okunuki K．A computational method for estimating the demand of retail stores on a street network and its implementation in GIS[J]. Transactions in GIS, 2001, 5(3):209-220．

[4] Kennedy J, Eberhart R C. Particle Swarm Optimization[C]. Proc of IEEE International Conference on Neural Networks. Perth, Australia, l995, 1942-1948.

[5] Eberhart R C, Shi Y. Particle swarm optimization: Developments, applications and resources[C]. In: Proc. Congress on Evolutionary Computation. IEEE Service Center. Piscataway, NJ, USA, 2001, 81-86.

[6] 谢顺平, 冯学智, 鲁伟. 基于道路网络分析的Voronoi面域图构建算法[J]. 测绘学报, 2010, 39(1):88-94.

[7] Okabe A, Suzuki A. Locational optimization problems solving through Voronoi diagrams[J]. Europe Journal Operation Research, 1997(98):445-456.

[8] 陈军, 赵仁亮, 乔朝飞. 基于Voronoi图的GIS空间分析研究[J]. 武汉大学学报×信息科学版, 2003, 28 (特刊):32-37.

[9] 王新生, 余瑞林, 姜友华. 基于道路网络的商业网点市场域分析[J]. 地理研究, 2008, 27(1):85-92.

[10] 谢顺平, 冯学智, 王结臣, 等. 基于网络加权Voronoi图分析的南京市商业中心辐射域研究[J]. 地理学报, 2009, 64(12):1467-1476.

[11] 杜国明, 陈晓翔, 黎夏. 基于粒子群优化算法的空间优化决策[J].地理学报, 2006, 61(12): 1290-1298.

[12] 黎海波, 黎夏, 刘小平, 等. 多目标粒子群算法与选址中的形状优化[J]. 遥感学报, 2008, 12(5):724-733.

[13] 谢顺平, 冯学智, 都金康. 基于网络Voronoi图启发式和群智能的最大覆盖空间优化[J]. 测绘学报, 2011, 40(6):778-784.

[14] Mladenovi? N, Brimberg J, Hansen P, Moreno-Pérez J A. The p-median problem: A survey of metaheuristic approaches[J]. European Journal of Operational Research, 2007 (179):927-939.

[15] Sáez-Aguado J, Trandafir P C. Some heuristic methods for solving p-median problems with a coverage constraint[J]. European Journal of Operational Research, 2012(220):320-327.

[16] Yaghini M, Karimi M, Rahbar M. A hybrid metaheuristic approach for the capacitated p-median problem[J]. Applied Soft Computing, 2013(13):3922-3930.

[17] Church R.L., Revelle, C.S., The maximal covering location problem[C]. Papers of the Regional Science Association, 1974(32):101-118.

[18] Alexandris G, Giannikos I. A new model for maximal coverage exploiting GIS capabilities[J]. European Journal of Operational Research, 2010(202): 328-338.

[19] Karasakal O, Karasakal E K. A maximal covering location model in the presence of partial coverage[J]. Computers & Operations Research, 2004(31):1515-1526.

[20] Murawski L, Church R L. Improving accessibility to rural health services: The maximal covering network improvement problem[J]. Socio-Economic Planning Sciences, 2008(43):102-110.

[21] 马云峰, 杨超, 张敏, 等. 基于时间满意的最大覆盖选址问题[J]. 中国管理科学, 2006, 14(2): 45-51.

[22] Berman O．The p maximal cover-partial center problem on networks[J]．European Journal of Operation Research, 1994(72):432-442.

[23] Berman O, Drezner Z, Krass D, et al. The variable radius covering problem[J]. European Journal of Operational Research. 2009(196):516–525.

[24] 曾建潮, 介婧, 崔志华. 粒子群算法[M]. 北京: 科学出版社, 2004.

[25] Eberhart R C, Shi Y. Particle swarm optimization: Developments, applications and resources. In: Proc. Congress on Evolutionary Computation. IEEE Service Center. Piscataway, NJ, USA, 2001: 81-86.

[26] 倪庆剑, 邢汉承, 张志政, 等. 粒子群优化算法研究进展[J]. 模式识别与人工智能, 2007, 20(3):349-357.

[27] 李宁, 刘飞, 孙德宝. 基于带变异算子粒子群优化算法的约束布局优化研究[J]. 计算机学报, 2004, 27(7):897-903.

[28] 陶新民, 刘福荣, 刘玉, 等. 一种多尺度协同变异的粒子群优化算法[J]. 软件学报, 2012, 23(7):1805-1815.

网络Voronoi图启发的粒子群空间优化建模

Network Voronoi Diagram Heuristic-based Particle Swarm Continuous Spatial Optimization Modeling

PDF (PC)

赞

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

Metrics

本文评价

推荐阅读 0

[1]	张菊, 房世波, 刘汉湖. 基于微波数据与光学数据集成的机器学习技术在作物产量估算中的应用[J]. 地球信息科学学报, 2021, 23(6): 1082-1091.
[2]	李志红, 李旺平, 王玉, 陈璐, 郁林, 周兆叶, 郝君明, 吴晓东, 李传华. 基于离散粒子群算法的2种新型水体提取方法的对比与验证[J]. 地球信息科学学报, 2021, 23(6): 1106-1117.
[3]	信睿, 艾廷华, 杨伟, 冯涛. 顾及出租车OD点分布密度的空间Voronoi剖分算法及OD流可视化分析[J]. 地球信息科学学报, 2015, 17(10): 1187-1195.
[4]	冯永玖, 童小华, LIU Yan, 刘妙龙. 城市形态演化的粒子群智能随机元胞模型与应用——以上海市嘉定区为例[J]. 地球信息科学学报, 2010, 12(1): 17-25.