【《基于Voronoi图算法的邮政公共服务设施布局优化模型设计案例》7300字】

基于Voronoi图算法的邮政公共服务设施布局优化模型设计案例目录TOC\o"1-3"\h\u22059基于Voronoi图算法的邮政公共服务设施布局优化模型设计案例 1117051.1Voronoi图算法概述 131161.1.1Voronoi图算法概念 240101.1.2Voronoi图算法性质 3322861.1.3Voronoi图生成算法 419631.2基于Voronoi图算法的邮政公共服务设施布局模型构建 5279551.2.1问题描述 6295081.2.2模型假设 6178021.2.3模型设计 6184251.3基于Voronoi图算法的邮政公共服务设施布局模型求解 784071.3.1基于Delaunay三角剖分算法的Voronoi图构造 7209771.3.2基于最小覆盖圆的设施定位 12140691.3.3基于Shamos算法的优化及迭代 12237121.3.4基于ArcGIS的模型可视化 14为了解决邮政公共服务设施布局存在的问题，提高邮政公共服务水平，本章结合Voronoi图的优越特性，设计了基于Voronoi图的邮政公共服务设施布局优化模型，并用ArcGIS地理信息系统软件实现可视化。1.1Voronoi图算法概述Voronoi图是计算机几何的重要结构形式领域的核心方法，也是热点研究内容之一。早在1908年，俄国数学家G.Voronoi在通用的n维情况下提出并探讨了Voronoi图的内涵，德国数学家G.L.Dirichlet、法国科学家R.Descartes、荷兰气象学家A.H.Thiessen等相继探讨并应用了Voronoi图。Voronoi图在天文学、气象学、地理学、图像处理、建筑工程等领域都得到了广泛的应用，如天文学领域研究宇宙物质分布[86]，气象学领域构建自然灾害检测网络[87]，地理学领域用于区位划分和定位。同时，Voronoi图已成为计算几何学科研究中的核心支系，也是解决骨架计算、路径规划、最小树、最大空心圆、凸包运算等问题的重要手段，在空间布局模式识别中也存在优势。本文基于Voronoi图对邮政基本公共服务设施布局进行优化研究。1.1.1Voronoi图算法概念Voronoi图的基本思想是对二维平面的均等化剖分，常适用于处理临近问题。其将空间平面分成n个，任一区域尚且仅有一个控制点（即Voronoi图的质心或发生元），使得区域内的任意点到控制点的距离小于其到其它区域控制点，即点到控制点的距离最近，且相邻种子点的垂直平分线构成Voronoi图的边[88]，如图1.1所示。Voronoi图的定义是：假设是二维平面上形成的一个点集，且任意两点间不共线，任意四点间不形圆，表示与间的直线距离，其中。假设x表示平面中任一离散点，则区域的计算公式为：（1.1）式1.1中，区域为点为控制点的Voronoi区域，Voronoi图为各个点的Voronoi区域组合形成，各Voronoi区域间紧密衔接，最外层的点呈现开放性区域，如图1.2所示。图1.1Voronoi图的平面展示图图1.2Voronoi开放性图Voronoi图是一定数量Voronoi凸边形的集合，每个控制点的空间影响范围为所在的Voronoi凸边形。任一控制点的减少，不会影响其他控制点，但会改变部分Voronoi凸边形的布局范围。这些描述与邮政公共服务设施的布局分析及优化有极大的关联性和相似性。其特点是：每个Voronoi图区域内仅含有一个控制点数据；Voronoi图区域内的任意离散点到相应的控制点的距离最近；位于Voronoi图边上的离散点至其两边Voronoi图区域控制点等距；Voronoi图是n凸变形，则与n个离散点相邻。1.1.2Voronoi图算法性质Voronoi图蕴含许多算法机理，其优势是将图形与数学相互结合，可视化展示其内在原理。主要包括侧向临近性、空心圆性、有效作用范围性、局部动态性、和线性特性等。Voronoi图在邮政公共服务设施布局优化研究中有以下性质：（1）侧向邻近性在现实生活中，任意两个相邻的空间要素与不一定可以径直衔接，如邮政公共服务设施营业场所和社区点之间相邻，但它们在几何上可能并不连续。假设与间没有任何其它空间要素，即相互毗邻时，其构成的Voronoi图必存在一条共享边，因此唯一必要方式就是明确与间是否具有共享的Voronoi边，若有则为侧向临近。（2）空心圆性任意控制点正好是n（n≧3）条Voronoi区域边的交集点。如图1.3所示，以图中任意控制点为圆心画一圆，且使周围的控制点均在其圆外或边上，则为空心圆。定义半径最大的空心圆为最大空心圆，将Voronoi图的这一性质联系到邮政公共服务设施布局优化中，可以由最大空心圆确定在该区域被忽略的邮政公共服务设施覆盖范围，这也是完善邮政公共服务设施布局优化过程中最应该优先考虑的地方。空心圆的圆心可以作为邮政公共服务待优化设施点的待选位置。图1.3Voronoi图的空心圆性（3）影响范围特性任意控制点当且仅对应唯一的Voronoi凸边形，即该控制点的影响范围。因此，Voronoi凸变形在一定程度上反映了其控制点的空间影响范围。若某一控制点被取消，则其相应的影响范围也随之消散。对于欧几里得平面中的任意一点来说，离散点当且只能位于Voronoi区域内或公共边上，即处在某一控制点的影响范围之中。这一特性为研究邮政公共服务设施的服务范围提供了依据。1.1.3Voronoi图生成算法Voronoi图最初的绘制，唯有运用笔、直尺、圆规、纸张等工具实行手绘。直到电子计算机的广泛应用，作为计算几何的核心可视化方法的Voronoi图可以通过计算机进行绘制。常见的Voronoi图构成方法主要有以下两种：矢量算法和栅格算法。矢量算法常用的矢量算法有Delaunay三角划分法、增量法和分治法。Delaunay三角划分法Delaunay三角划分法是根据Voronoi图的定义而来。其主要思想是依据三个核心点确定一个三角形，边与边之间不能交叉，直到连接所有控制点为止形成三角网，这一步为核心，也是难点，常采用凸包插值算法。其次，通过Voronoi图和Delaunay三角网均具有相似的结构特性，即对偶性，依次针对三角网各边绘制垂直平分线，其三条边的交点为Voronoi图区域的顶点；最后，连接相邻的各顶点，形成封闭的Voronoi图区域，最终生成Voronoi图。值得注意的是，Delaunay三角划分法中任意三角网的外接圆内不能包含离散点。2）增量算法增量算法的机理是根据Voronoi图中任意减少一个核心点，只涉及毗邻的Voronoi图区域，不影响整体这一性质。其主要思想是依次增加一个核心点生成Voronoi图，直到所有核心点包含在内。增量法每增加或删除一个核心点，会影响相邻的核心点生成Voronoi区域。3）分治算法分治算法的机理是采用单元区域生成，最后拼接的形式。其主要原理是先将所有核心点划分成若干个均等的区域，每个区域中至少有两个核心点；其次，分别生成每个区域的Voronoi图；最后，将所有区域进行拼接，并对边界开放性区域进行融合，生成公共边，构成最终Voronoi图。该算法采用区域分解的方式降低了生成时间，但算法本身相对复杂，实现起来相对困难。栅格算法栅格算法是地理信息处理软件诞生后的衍生算法，目前的学术适用领域比较局限，但是它可以很好的处理矢量算法尚且未能有效应对的控制点多样性问题，多用于构造多维的Voronoi图。栅格算法采用栅格来描述数据结构。常见的栅格法生成Voronoi图有距离变换法、扩张法和像素生长等方法。其中，像素生长的方法模拟了数学中形态支系的腐蚀和膨胀，将每一个Voronoi图生成的像素逐渐膨胀，其相交的边界为Voronoi图的边。矢量算法的优势在于能够完整的展示要素间的拓扑关系，便于进行可视化分析，可适用工具多，当前相关学术成果较多；缺点是为对控制点有限制，只能是点或线，且存储占比较大。栅格算法出现时间稍晚，优点是对控制点没有限制，可以适用于线和面为控制点的Voronoi图。缺点是精度较低，可视化结果不完美，降低分辨率后信息损失大，且算法耗时长。因此，本文选取Delaunay三角划分法生成Voronoi图。1.2基于Voronoi图算法的邮政公共服务设施布局模型构建针对邮政公共服务设施布局优化模型的构建，采用Voronoi图为基础进行设施布局优化分析，根据社区点居民到达邮政公共服务营业场所距离最短原则，在分析原有布局的基础上，利用Voronoi图的优势，对邮政公共服务设施的服务范围进行划分，并且循环进行邮政公共服务设施的布局优化，直到邮政公共服务设施的服务范围最合理。1.2.1问题描述假设在某行政区域建有n处邮政公共服务设施营业场所，使其服务于该地区的m个社区点的用户。邮政公共服务设施地点选择的主要原则是：既要使n处邮政公共服务设施营业场所的有效服务能力能覆盖该行政区域内的所有社区点，又要使每处邮政公共服务设施营业场所至其服务范围内最远的，需要邮政基本公共服务的社区点的用户的距离尽可能小（即每处邮政公共服务设施营业场所的覆盖半径最小），设施距离，即设施服务半径是社区点的居民普遍关注的因素，缩短设施距离是改善设施空间布局的首要目标，一旦社区点的居民有相关需求，能够在尽可能短的时间内抵达营业场所，并且邮政公共服务设施建设的总投资费用最小。1.2.2模型假设为使得模型构建更加规范化，设定以下几点假设：①设邮政公共服务设施营业场所为，社区点为，确保Q和P同属于同一地理坐标系下，且在该行政区域的合理范围内；②设邮政公共服务设施营业场所、社区点之间的距离主要是欧氏距离，即Q和P的距离为其任意两离散点间的直线距离，不考虑该研究区域内的交通环境、地理环境等因素；③设Q中的各离散点服务质量相同，不考虑面积等因素，只以离散点的坐标值为依据；④不考虑研究区域地形地貌、经济发展水平等因素，P值中各个离散点对Q的需求相同，任意与之间的距离。⑤设研究区域内的居民遵循“就近原则”。1.2.3模型设计基于Voronoi图算法的邮政公共服务设施布局优化模型的流程图如图1.4所示：图1.4基于Voronoi图算法的邮政公共服务设施布局优化模型流程图由图1.4可知，首先，对搜集到的相关点状、线状和面状数据进行数据核查、纠偏和投影，建立空间数据集，运用Delaunay三角剖分算法生成碑林区邮政公共服务设施Voronoi图，结合最小边界几何构建基本覆盖圆，确定服务范围，计算和分析现状相关数据并作为基准；基于最小覆盖圆构建碑林区邮政公共服务设施布局全局性定位优化目标函数，并结合Shamos算法予以实现：通过对单个Voronoi图区域的设施布局进行初步优化，确定新的设施点位置和距离指数；在初步优化的基础上，再次运用Shamos算法进行迭代优化，找寻最优的Voronoi图区域的控制点，即邮政公共服务设施布局最优化点，结合社区点数据，计算得到邮政公共服务最终优化的综合距离。借助ArcGIS模型构建器，予以实现模型优化的可视化。1.3基于Voronoi图算法的邮政公共服务设施布局模型求解1.3.1基于Delaunay三角剖分算法的Voronoi图构造（1）构造原则本文选择基于Delaunay三角剖分算法对Voronoi图进行构造，构造过程遵循以下原则：1）最接近原则：以最近的三点组成三角形，且各线段（三角形的边）皆不相交；2）唯一性原则：不论从区域何处开始构建，最终结果都将保持一致；3）最优性原则：构成三角网的点集内任意四点不共圆；任意两个相邻三角形组成的凸四边形的对角线若可以互换，则两个三角形六个内角中最小的角度不会变大；4）规则性原则：又称最大化最小角原则，若将三角网中的每个三角形的最小角进行升序排列，则Delaunay三角网的排列得到的数值最大；5）区域性原则：新增、删除、移动某一个顶点时只会影响临近的三角形；（2）构造流程构造流程主要分为第一步：第一步建立凸壳，第二步采用逐点插入法生成Delaunay三角网，第三步运用Delaunay三角网的对偶图生成Voronoi图，详细过程如下：1）第一步①初始设置凸壳顶点链表：ConvexHullList；凸壳顶点数组：VertexArray；剖分后三角形链表：Div-TriList；三角形顶点链表：Tri-PointsList。②建立凸壳初始化凸壳顶点链表ConvexHullList，已知点集，任取一点为，确定距离最近的点为，搜索点，围成的三角形为初始凸壳，将这3点放入链表中，如图1.5所示。图1.5初始凸壳示意图插入第个点，对应的凸壳为。组成过程主要有两种情况：①处于凸壳内部，则与有相同的凸壳顶点；②，不处于凸壳内部，作为凸壳的一个顶点。如图1.6（a）为第一种情况，（b）为第二种情况。按逆时针方向排列中的顶点，若在凸壳边左侧，则。当时，需生成新的凸壳，为避免生成凹壳，需要找到到的正切点，将加入列表ConvexHull中。（a）凸壳示意图（b）凸壳示意图图1.6凸壳组成情况①判断在线段左侧右侧的方法：设，若，则在右侧，反之左侧。①找正切点方法：设，若在的左侧和位于的右侧，且在的右侧和的左侧，则是正切点。2）第二步Delaunay三角剖分①凸壳的三角剖分将ConvexHull内数据复制到凸壳顶点数组VertexArray中，对凸壳构建三角网。依次取点构成三角形，若三角形外接圆中包含其他凸壳顶点，则重新选点构网，不包含则将三角形加入到链表Div-TriList，如图1.7所示。图1.7凸壳三角剖分示意图②逐点插入逐一插入新点加入三角形顶点链表Tri_Points，Div-TriList中删除因插入点受影响的三角形的三边，并在受影响区域重新构网，将新生成的三角形加入到三角形链表中，如图1.8所示。图1.8逐点插入示意图③生成三角网重复步骤②直到所有点插入完毕，生成Delaunay三角网，如图1.9所示。图1.9Delaunay三角网6）第三步Voronoi图生成Delaunay三角网与Voronoi图互为对偶图，其三角形的中垂线构成了Voronoi图。设Voronoi点链表为Vor_PointsList；三角形边链表为Tri_EdgeList；边终点数组为End_PointsArray。①从Delaunay三角剖分生成的过程中得到的三角形顶点链表Tri_PointsList中去除掉ConvexHull中的顶点，将剩余点有序加入Vor_PointsList；②依次确定Delaunay三角网的边，加入链表Tri_Edge，如出现重复的边则不再重复加入；③确定Vor_PointsList中每一点相关的边组成的链表Tri_Edge，可得相关的边的另一点，即终点End_Points，结合Tri_Points内点的坐标，可以得到End_Points内的点坐标；④将End_Points内点逆时针排序，则同时也对点相关的三角形进行了排序。计算上述有序三角形的外接圆圆心；⑤逆时针连接外接圆圆心，可得Voronoi图，如图1.10所示。图1.10Delaunay三角剖分Voronoi示意图1.3.2基于最小覆盖圆的设施定位根据Delaunay三角剖分算法构建的Voronoi图为基础，运用ArcGIS10.2，采用最小边界几何工具确定各邮政公共服务营业场所的最小覆盖范围，即点可移动优化的最远距离。通过最小覆盖圆原理，构建基于Voronoi图的最小覆盖圆，其优化模型可以描述如下为：（1.2）式（1.2）中，表示第i个邮政公共服务营业场所的位置，表示第i个邮政公共服务设施点的社区点数，表示第j个社区点，是处的权重，是到的欧几里德距离。由于邮政公共服务营业场所一般是根据“就近原则”服务于用户，因此，可以考虑将构建成Voronoi图，选择其作为服务范围，即在每一个凸边形区域内求解，以满足上述准则的邮政公共服务营业场所的最佳位置，因此，公式（1.3）转化为：（1.3）这样，就把上述的n个邮政公共服务营业场所位置优化的全局求解转化为n个Voronoi凸边形区域中的各个邮政公共服务营业场所的单一位置的求解，再对n个Voronoi凸边形区域进行调整比较，优选出n个邮政公共服务营业场所选址的全局的解决方案。事实上，单个Voronoi凸边形区域中的邮政公共服务营业场所位置的求解，实质是寻求覆盖Voronoi凸边形区域内所有社区点的最小覆盖圆的圆心，针对单个邮政公共服务营业场所选址的问题，运用Shamos算法进行相关求解。1.3.3基于Shamos算法的优化及迭代基于Voronoi图的最小覆盖圆算法只能对全部邮政公共服务营业场所的布局进行优化求解，无法对单个Voronoi凸边形区域内的邮政公共服务营业场所进行位置优化。Shamos算法的优势在于可以计算n个凸包中单个凸包（即凸多边形）对偶点的直径，以此绘制圆，其实质上是寻求覆盖该Voronoi图区域内所有社区点的最小覆盖圆的圆心。Shamos算法的复杂度为O（nlogn），其具体求解过程旨在寻找每个Voronoi区域最小覆盖圆的圆心，使得所有社区点到圆心处（即邮政公共服务营业场所）的距离最短，其算法流程解释如下：①计算社区点集的凸壳：②计算的直径，设为。以为直径作圆C，如果P的离散点都在圆C内，则圆C为所求覆盖圆；③计算社区点集P的最远点意义下的Voronoi图，即；④设w是中的一个最远点意义下的Voronoi区域的顶点，将w设置为圆心，即为邮政公共服务营业场所的最佳位置，选取w到P点集中的最远点的距离为半径做圆，该圆即为所求最小覆盖圆，其圆心为邮政公共服务营业网点位置所在；⑤为了求得满足MINMAX准则的n处邮政公共服务营业场所的最隹位置，可重复以下步骤进行Shamos算法迭代优化：步骤一：在所有凸包内给定n处邮政公共服务营业场所的第一次优化后的位置，生成邮政公共服务营业场所的Voronoi图，并计算各Voronoi区域内社区点到相应的邮政公共服务营业场所的综合距离L；步骤二：运用Shamos算法，针对单个Voronoi图内的所有社区点进行求解，生成最小覆盖圆，并确定新控制点的圆心和半径；步骤三：将各邮政公共服务营业场所移至相应的最小覆盖圆的圆心处；步骤四：重新生成各邮政公共服务营业场所的Voronoi区域图，并计算Voronoi区域内社区点到相应的邮政公共服务营业场所的综合距离；步骤五；核实是否达到终止条件，如若未达到则转至步骤二；达到即结束，求得的当前所有圆心为最优核心点。其中，终止条件为：当距离总和的变化指数小于一个预先设定的微小变量时，终止程序运行，生成最终设施布局优化图如图1.11所示。图1.11基于Shamos算法的设施布局优化图1.3.4基于ArcGIS的模型可视化基于Voronoi图的模型可视化，是将算法与地图结合起来进行归一化处理，以便简化程序流程，提高求解时效，生成可视化的结果图。本文主要借助ArcGIS10.2的ModelBuilder（模型构建器），借助Arcmap中的地理处理工具，对算法进行输出，以便模型的求解。模型构建器是ArcGIS10.2开发的用于构建、修改和管理模型的专用模块，属于二次开发功能。其原理是以现有工具包为基础，选取适用的功能，增加自用算法模块，并按照自建的模型步骤按顺序连接起来，使得缩短了操作流程，提高了工作效率。模型构建器的界面包含菜单栏、常用工具栏，无限制画布（Canvas）等。模型构建器具备三个核心要素：自设的変量（Variable）、工具（Tool）和连接符（Connector）。变量常表