容量限制Power图的快速生成及应用

摘要

与Voronoi图不同，Power图有着精确限容的特性。在普通Power图上添加容量限制约束即得到容量限制Power图。现有生成容量限制Power图的算法时间复杂度高，速度较慢。本文提出了一种Power图的快速估计算法，其时间性能优于当前的试位法。在此基础上，施加质心限制、容量限制后得容量限制质心Power图(CCCPD)，用以近似求解连续域上的容量限制P-中值问题。
　　本文主要工作如下:
　　1)综述了Voronoi图、CVT(Centroidal Voronoi Tessellations)和Power图的研究历程和生成算法。
　　2)提出一种容量限制Power图(CCPD)算法，加速Power图的生成。首先建立Power图权值与容量之间的解析式;其次构建算法环境，实现CCPD算法;最后分析CCPD算法各种性能，同时与Balzer的试位法进行对比。实验验证该方法具有生成速度快、精确度高、便于计算和对密度场适应性强等优点。
　　3)引入基于质心的容量限制Power图(CCCPD)对连续容量限制P-中值进行建模，求解稠密需求下的城市应急中心布局问题。以城市人口密度函数为密度场，为应急中心指定服务容量限制，然后采用CCCPD进行优化求解，最后通过实验对比和分析证明了方法的有效性。

目录

声明

致谢

摘要

第一章 绪论

1．1 国内外研究概况

1．1．1 Voronoi图研究及应用

1．1．2 CVT研究及应用

1．1．3 Power图研究及应用

1．2 研究内容与论文结构

1．2．1 研究内容

1．2．2 论文结构

第二章 Power图基础

2．1 Voronoi图

2．2 Power图

2．3 容量限制Power图

2．4 容量限制Power图的生成算法

2．4．1 Balzer试位法

2．4．2 试位法分析

2．4．3 Balzer试位法算法

2．5 本章小结

第三章 一种Power图的快速计算方法

3．1 解析算法

3．1．1 Power权值与容量的单调性

3．1．2 Power图权值的快速估算

3．1．3 CCPD生成效果图

3．2 解析算法流程图

3．3 CCPD解析算法

3．4 CCCPD算法

3．5 本章小结

第四章 Power图快速生成算法分析

4．1 实验环境简介

4．1．1 CGAL-4.2

4．1．2 QT

4．2 时间性能分析

4．3 容量限制分析

4．4 可视化分析

4．5 实例展示

4．6 本章小结

第五章 基于Power图理论的连续域上P-中值求解

5．1 P-中值问题

5．2 连续域上的容量限制P-中值问题

5．3 CCCPD与连续域上的容量限制P-中值问题

5．4 实际应用实例

5．4．1 CCCPD算法时间分析

5．4．2 连续域容量限制的P-中值实例

5．4．3 实际应用实例可视化结果与误差分析

5．5 本章小结

第六章 总结与展望

6．1 论文总结

6．2 论文展望

参考文献

攻读硕士学位期间的学术活动及成果情况