Research On Network Voronoi Diagram Model For Spatial Optimization Analysis

The network Voronoi diagram model is an effective method to divide geospatial space,which based on the shortest path time analysis can truly express the transfer direction and relationship of the facility service requirements.The network weighted Voronoi diagram is developed by combining spatial interaction model,breakpoint theory,gravity polygon and potential energy model takes into account the difference of the facility center scale.Moreover,its simulation mechanism and environment are basically consistent with the actual service demand distribution.Therefore,the network weighted Voronoi diagram is a scientific way to the geospatial division of facility radiation area.The heuristic information from facility radiation areas is able to provide high information support for facility service situation analysis,location performance evaluation,load balance evaluation,maximum coverage area optimization,and so on.In fact,the practical space optimization technology imposes higher requirements on computational performance of the network Voronoi diagram model construction algorithm,while serial algorithm can not make the graph model rapid response to spatial optimization technology.Hence,high performance constructing graph algorithm is needed to achieve timely responsiveness requirements of spatial optimization analysis and improve application of the graph model.This paper is relyed on requirements of high performance constructing graph algorithm in the National Natural Science Foundation of China "Research on network Voronoi diagram heuristics and group intelligence spatial optimization modeling method"(Grant No.41671390).In depth analysis for the key way to improve performance of the graph model,the modified Dijkstra algorithm and OpenMP parallel computing technology are used for carrying out a research about high performance network Voronoi diagram model for spatial analysis and optimization.The main contents and conclusions are as below:(1)The high-performance algorithm for constructing network Voronoi diagram model.Based on facility location layout and radiation difference of road network system,a parallel algorithm for searching and generating the facility adjacent road nodes,the modified Dijkstra algorithm,a parallel algorithm for road network Voronoi division,a parallel algorithm for raster cell Voronoi division are all applied to construct high performance network Voronoi diagram model.The modified Dijkstra algorithm decreases the time complexity of shortest path analysis from O(n2)to O(nlogn).In addition,the OpenMP parallel computing model is able to significantly reduce more time spent on massive raster cell Voronoi division than serial algorithm.The results show high performance constraction graph algorithm can save nearly half execution time of serial algorithm.According to the evaluation results of relative speedup and standard efficiency,when task volume is fixed,the larger number of threads is,the less construction time is spent,while the lower computational efficiency of each thread is,the more system memory resources will be wasted.(2)Location-related information acquisition derived from facility radiation areas.The network Voronoi diagram model is an accurate method to divide facility radiation areas.In addition,the location-related information mined from the graph model can provide data support for multi-facility location selection and intelligent space optimization.The network weighted Voronoi diagram based on shortest path time analysis is able to simulate the actual facilitiy radiation situation.Furthermore,the introduction of different metro scale conditions is capable of simulating real situation of the change between old and new radiative patter of facilities.Location-related information is acquired from facility radiation areas by using spatial analysis and data minning method,which is about facility loctation-related information includes:traffic location condition,coverage number of rode nodes,coverage area,coverage perimeter,coverage population,radiation farthest path time,radiation average path time,coverage road network density,facility nearest to road segment,facility nearest to road node,location of facility nearest to road node,nearest function facility,time to nearest function facility,farthest function facility,time to furthest function facility,and so on.The location-related information can be applied to facility radiation situation analysis,load balance assessment,and location performance assessment.It can also provide data service for multi-facility spatial optimization and high information service for multi-facility location selection.The paper adopts the improved Dijkstra algorithm and OpenMP parallel computing technology to save the time spent in the serial algorithm for constructing graph model.The high performance construction algorithm of graph model makes the network Voronoi diagram model quickly respond to the callback of spatial optimization technology.In addition,the location-related information obtained from graph model can further enhance the practicability and extent of the graph model.