Identifying regions based on flexible user-defined constraints

The identification of regions is both a computational and conceptual challenge. Even with growing computational power, regionalization algorithms must rely on heuristic approaches in order to find solutions. Therefore, the constraints and evaluation criteria that define a region must be translated into an algorithm that can efficiently and effectively navigate the solution space to find the best solution. One limitation of many existing regionalization algorithms is a requirement that the number of regions be selected a priori. The recently introduced max-p algorithm does not have this requirement, and thus the number of regions is an output of, not an input to, the algorithm. In this paper, we extend the max-p algorithm to allow for greater flexibility in the constraints available to define a feasible region, placing the focus squarely on the multidimensional characteristics of the region. We also modify technical aspects of the algorithm to provide greater flexibility in its ability to search the solution space. Using synthetic spatial and attribute data, we are able to show the algorithm’s broad ability to identify regions in maps of varying complexity. We also conduct a large-scale computational experiment to identify parameter settings that result in the greatest solution accuracy under various scenarios. The rules of thumb identified from the experiment produce maps that correctly assign areas to their ‘true’ region with 94% average accuracy, with nearly 50% of the simulations reaching 100% accuracy.     

The Network-Max-P-Regions model

This paper introduces a new p-regions model called the Network-Max-P-Regions (NMPR) model. The NMPR is a regionalization model that aims to aggregate n areas into the maximum number of regions (max-p) that satisfy a threshold constraint and to minimize the heterogeneity while taking into account the influence of a street network. The exact formulation of the NMPR is presented, and a heuristic solution is proposed to effectively compute the near-optimized partitions in several simulation datasets and a case study in Wuhan, China.     

Multi-objective spatially constrained clustering for regionalization with particle swarm optimization

Regionalization is an important part of the spatial analysis process, and the solution should be contiguity-constrained in each region. In general, several objectives need to be optimized in practical regionalization, such as the homogeneity of regions and the heterogeneity among regions. Therefore, multi-objective techniques are more suitable for solving regionalization problems. In this paper, we design a multi-objective particle swarm optimization algorithm for solving regionalization problems. Towards this goal, a novel particle representation for regionalization is proposed, which can be expressed in continuous space and has flexible constraints on the number of regions. In the process of optimization, a contiguous-region method is designed that satisfies the constraints and improves the efficiency. The decision solution is selected in the Pareto set based on a trade-off between the objective functions, and the number of regions can be automatically determined. The proposed method outperforms six regionalization algorithms in terms of both the number and the quality of the solutions.     

K-guarding of polyhedral terrain

Site visibility analysis is an important research topic with many applications in Geographical Information Systems. This paper introduces a new paradigm in terrain guarding, called k-guarding. K-guarding is a generalization of the classic guarding problem where, instead of only one guard, each surface patch is guarded by at least k guards. Afterwards, two optimization problems based on k-guarding are defined: an optimum k-guarding, and a constrained k-guarding. There are three heuristic approaches—k-greedy add, k-stingy drop, and k-reverse greedy—that are proposed as a solution to the above-mentioned optimization problems. The first two are known approaches adapted to k-guarding, while k-reverse greedy is a new, original heuristic. The heuristics are compared using actual topographic surfaces. It is shown that our approach (k-reverse greedy) gives on average the best near optimum solutions. The most surprising finding of the experiments is that the combination of heuristics introduced here yields even better results.     

Parallelization of a regionalization heuristic in distributed computing platforms – a case study of parallel-p-compact-regions problem

In this paper, we report efforts to develop a parallel implementation of the p-compact regionalization problem suitable for multi-core desktop and high-performance computing environments. Regionalization for data aggregation is a key component of many spatial analytical workflows that are known to be NP-Hard. We utilize a low communication cost parallel implementation technique that provides a benchmark for more complex implementations of this algorithm. Both the initialization phase, utilizing a Memory-based Randomized Greedy and Edge Reassignment (MERGE) algorithm, and the local search phase, utilizing Simulated Annealing, are distributed over available compute cores. Our results suggest that the proposed parallelization strategy is capable of solving the compactness-driven regionalization problem both efficiently and effectively. We expect this work to advance CyberGIS research by extending its application areas into the regionalization world and to make a contribution to the spatial analysis community by proposing this parallelization strategy to solve large regionalization problems efficiently.     

A unified approach for location-allocation analysis: integrating GIS,distributed computing and spatial optimization

Location-allocation modeling is an important area of research in spatial optimization and GIScience. A large number of analytical models for location-allocation analysis have been developed in the past 50 years to meet the requirements of different planning and spatial-analytic applications, ranging from the location of emergency response units (EMS) to warehouses and transportation hubs. Despite their great number, many location-allocation models are intrinsically linked to one another. A well-known example is the theoretical link between the classic p-median problem and coverage location problems. Recently, Lei and Church showed that a large number of classic and new location models can be posed as special case problems of a new modeling construct called the vector assignment ordered median problem (VAOMP). Lei and Church also reported extremely high computational complexity in optimally solving the best integer linear programming (ILP) formulation developed for the VAOMP even for medium-sized problems in certain cases.

In this article, we develop an efficient unified solver for location-allocation analysis based on the VAOMP model without using ILP solvers. Our aim is to develop a fast heuristic algorithm based on the Tabu Search (TS) meta-heuristic, and message passing interface (MPI) suitable for obtaining optimal or near-optimal solutions for the VAOMP in a real-time environment. The unified approach is particularly interesting from the perspective of GIScience and spatial decision support systems (DSS) as it makes it possible to solve a wide variety of location models in a unified manner in a GIS environment. Computational results show that the TS method can often obtain in seconds, solutions that are better than those obtained using the ILP-based approach in hours or a day.     

Geospatial data conflation: a formal approach based on optimization and relational databases

ABSTRACT

Geospatial data conflation is aimed at matching counterpart features from two or more data sources in order to combine and better utilize information in the data. Due to the importance of conflation in spatial analysis, different approaches to the conflation problem have been proposed ranging from simple buffer-based methods to probability and optimization based models. In this paper, I propose a formal framework for conflation that integrates two powerful tools of geospatial computation: optimization and relational databases. I discuss the connection between the relational database theory and conflation, and demonstrate how the conflation process can be formulated and carried out in standard relational databases. I also propose a set of new optimization models that can be used inside relational databases to solve the conflation problem. The optimization models are based on the minimum cost circulation problem in operations research (also known as the network flow problem), which generalizes existing optimal conflation models that are primarily based on the assignment problem. Using comparable datasets, computational experiments show that the proposed conflation method is effective and outperforms existing optimal conflation models by a large margin. Given its generality, the new method may be applicable to other data types and conflation problems.     

Regionalization with dynamically constrained agglomerative clustering and partitioning (REDCAP)

Regionalization is to divide a large set of spatial objects into a number of spatially contiguous regions while optimizing an objective function, which is normally a homogeneity (or heterogeneity) measure of the derived regions. This research proposes and evaluates a family of six hierarchical regionalization methods. The six methods are based on three agglomerative clustering approaches, including the single linkage, average linkage (ALK), and the complete linkage (CLK), each of which is constrained with spatial contiguity in two different ways (i.e. the first‐order constraining and the full‐order constraining). It is discovered that both the Full‐Order‐CLK and the Full‐Order‐ALK methods significantly outperform existing methods across four quality evaluations: the total heterogeneity, region size balance, internal variation, and the preservation of data distribution. Moreover, the proposed algorithms are efficient and can find the solution in O(n ²log n) time. With such data scalability, for the first time it is possible to effectively regionalize large data sets that have 10 000 or more spatial objects. A detailed comparison and evaluation of the six methods are carried out with the 2004 US presidential election data.     

Integration of genetic algorithms and GIS for optimal location search

Optimal location search is frequently required in many urban applications for siting one or more facilities. However, the search may become very complex when it involves multiple sites, various constraints and multiple‐objectives. The exhaustive blind (brute‐force) search with high‐dimensional spatial data is infeasible in solving optimization problems because of a huge combinatorial solution space. Intelligent search algorithms can help to improve the performance of spatial search. This study will demonstrate that genetic algorithms can be used with Geographical Information systems (GIS) to effectively solve the spatial decision problems for optimally sitting n sites of a facility. Detailed population and transportation data from GIS are used to facilitate the calculation of fitness functions. Multiple planning objectives are also incorporated in the GA program. Experiments indicate that the proposed method has much better performance than simulated annealing and GIS neighborhood search methods. The GA method is very convenient in finding the solution with the highest utility value.     

盐城开发空间区划及其思考

在国家“十一五”规划纲要中, 将国土空间划分为优化开发、重点开发、限制开发和禁止开发四类主体功能区, 这是新时期传统区划理论和方法为国民经济和社会发展服务的一次重要创新。作者认为: 主体功能区划主要在于解决区域问题, 用科学发展观协调区域发展。 因此, 功能区区划的理论和方法也需要与时俱进的创新。文章通过盐城沿海开发空间区划实例进行功能区区划的理论和方法探索。首先, 综合经济区划。运用传统的综合经济区划理论与方法进行经济区划分, 大致确定不同经济区的经济发展布局方向; 其次, 控制开发区划。 综合考虑上述综合经济区的功能, 景观生态体系建设需要, 土地利用现状、辐射沙洲分布、近海海域污染、海港分布、水源保护地以及自然保护区和生态保护区等, 确定相关的禁止开 发区和限制开发区; 第三, 开发潜力区划。以乡镇为基本单元, 运用多因子分析方法, 按照资源环境承载力、现有开发密度强度、未来发展潜力3 个主因子进行开发潜力区划; 最后, 在上述三个区划的基础上, 进行主体功能区划。文章也认为: 主体功能区实质是一种区域发展政策区, 其区划也只是一种纯粹的区域划分, 是目前经济社会发展规划、土地利用规划和城市总体规划“三规”分立走向“三规”合一的空间平台。     

Improving the performance of genetic algorithms for land-use allocation problems

Multi-objective optimization can be used to solve land-use allocation problems involving multiple conflicting objectives. In this paper, we show how genetic algorithms can be improved in order to effectively and efficiently solve multi-objective land-use allocation problems. Our focus lies on improving crossover and mutation operators of the genetic algorithms. We tested a range of different approaches either based on the literature or proposed for the first time. We applied them to a land-use allocation problem in Switzerland including two conflicting objectives: ensuring compact urban development and reducing the loss of agricultural productivity. We compared all approaches by calculating hypervolumes and by analysing the spread of the produced non-dominated fronts. Our results suggest that a combination of different mutation operators, of which at least one includes spatial heuristics, can help to find well-distributed fronts of non-dominated solutions. The tested modified crossover operators did not significantly improve the results. These findings provide a benchmark for multi-objective optimization of land-use allocation problems with promising prospectives for solving complex spatial planning problems.     

Estimating Model Parameters from Self-Potential Anomaly of 2D Inclined Sheet Using Whale Optimization Algorithm: Applications to Mineral Exploration and Tracing Shear Zones

The use of spontaneous potential (SP) anomalies is well known in the geophysical literatures because of its effectiveness and significance in solving many complex problems in mineral exploration. The inverse problem of self-potential data interpretation is generally ill-posed and nonlinear. Methods based on derivative analysis usually fail to reach the optimal solution (global minimum) and trapped in a local minimum. A new simple heuristic solution to SP anomalies due to 2D inclined sheet of infinite horizontal length is investigated in this study to solve these problems. This method is based on utilizing whale optimization algorithm (WOA) as an effective heuristic solution to the inverse problem of self-potential field due to a 2D inclined sheet. In this context, the WOA was applied first to synthetic example, where the effect of the random noise was examined and the method revealed good results using proper MATLAB code. The technique was then applied on several real field profiles from different localities aiming to determine the parameters of mineralized zones or the associated shear zones. The inversion parameters revealed that WOA detected accurately the unknown parameters and showed a good validation when compared with the published inversion methods.

     

An improved artificial bee colony algorithm for optimal land-use allocation

Land-use allocation is of great importance for rapid urban planning and natural resource management. This article presents an improved artificial bee colony (ABC) algorithm to solve the spatial optimization problem. The new approach consists of a heuristic information-based pseudorandom initialization (HIPI) method for initial solutions and pseudorandom search strategy based on a long-chain (LC) mechanism for neighborhood searches; together, these methods substantially improve the search efficiency and quality when handling spatial data in large areas. We evaluated the approach via a series of land-use allocation experiments and compared it with particle swarm optimization (PSO) and genetic algorithm (GA) methods. The experimental results show that the new approach outperforms the current methods in both computing efficiency and optimization quality.     

基于微粒群优化算法的空间优化决策

空间优化决策是GIS应用中复杂而又常见的问题。由于涉及到大量的组合,使用穷举法等方法难以找到最优的解决方案,因此需要运用新的理论方法来解决这类问题。微粒群优化算法是近年来新兴的一种优化技术,与GIS相结合可解决空间优化决策问题。首先,对微粒群优化算法和空间优化决策问题作了简单介绍;然后,基于人口密度、最短距离约束条件下,通过GIS技术,对微粒群优化算法用于空间优化决策的方法、实施过程作了详细阐述;接着,用4×4方格单元对PSO方法的正确性、有效性进行了验证;最后,以广州市芳村区为例,对该方法进行实例验证。通过实验,证明微粒群优化算法具有较好的收敛速度、较高的结果精度,是解决空间优化决策问题的一种有效方法。     

多叉树蚁群算法及在区位选址中的应用研究

本文提出了基于多叉树蚁群算法(ant colony optimization based on multi-way tree) 的区 位选址优化方法。在多目标和大型空间尺度约束条件下,地理区位选址的解决方案组合呈现 海量规模、空间搜索量庞大,难以求出理想解。基于多叉树的蚁群算法对地理空间进行多叉树划分,在多叉树的层上构造蚂蚁路径(ant path),让蚂蚁在多叉树的搜索路径上逐步留下信息 素,借助信息素的通讯来间接协作获得理想的候选解。采用该方法用于广州市的地理区位选址,取得良好结果。实验结果表明：采用基于多叉树的蚁群算法,改善了蚂蚁在空间搜索能 力,适合求解大规模空间下的区位选址问题。     

Leveraging parallel spatio-temporal computing for crime analysis in large datasets: analyzing trends in near-repeat phenomenon of crime in cities

ABSTRACT

Crime often clusters in space and time. Near-repeat patterns improve understanding of crime communicability and their space–time interactions. Near-repeat analysis requires extensive computing resources for the assessment of statistical significance of space–time interactions. A computationally intensive Monte Carlo simulation-based approach is used to evaluate the statistical significance of the space-time patterns underlying near-repeat events. Currently available software for identifying near-repeat patterns is not scalable for large crime datasets. In this paper, we show how parallel spatial programming can help to leverage spatio-temporal simulation-based analysis in large datasets. A parallel near-repeat calculator was developed and a set of experiments were conducted to compare the newly developed software with an existing implementation, assess the performance gain due to parallel computation, test the scalability of the software to handle large crime datasets and assess the utility of the new software for real-world crime data analysis. Our experimental results suggest that, efficiently designed parallel algorithms that leverage high-performance computing along with performance optimization techniques could be used to develop software that are scalable with large datasets and could provide solutions for computationally intensive statistical simulation-based approaches in crime analysis.     

A land use/land cover change geospatial cyberinfrastructure to integrate big data and temporal topology

ABSTRACT

Big data have shifted spatial optimization from a purely computational-intensive problem to a data-intensive challenge. This is especially the case for spatiotemporal (ST) land use/land cover change (LUCC) research. In addition to greater variety, for example, from sensing platforms, big data offer datasets at higher spatial and temporal resolutions; these new offerings require new methods to optimize data handling and analysis. We propose a LUCC-based geospatial cyberinfrastructure (GCI) that optimizes big data handling and analysis, in this case with raster data. The GCI provides three levels of optimization. First, we employ spatial optimization with graph-based image segmentation. Second, we propose ST Atom Model to temporally optimize the image segments for LUCC. At last, the first two domain ST optimizations are supported by the computational optimization for big data analysis. The evaluation is conducted using DMTI (DMTI Spatial Inc.) Satellite StreetView imagery datasets acquired for the Greater Montreal area, Canada in 2006, 2009, and 2012 (534 GB, 60 cm spatial resolution, RGB image). Our LUCC-based GCI builds an optimization bridge among LUCC, ST modelling, and big data.     

Optimal rural land use allocation in central China: Linking the effect of spatiotemporal patterns and policy interventions

Rural land use development is experiencing a transition stage of socioeconomic and land use development in China. Historic land use transition process and policy interventions have key influence on the applicability of land use allocation solutions in future land use management. Strategic land use allocation is therefore required to possess a good adjustment capability to the transition process. Although heuristic optimization methods have been promising to solve land use allocation problems, most of them ignored the spatially explicit effect of historic land use transition and policies. To help resolve this issue, this study aims to optimize future land use pattern in the context of rural land use development. We took Yunmeng County, one of the typical major grain producing and rapidly urbanizing areas in central China, as a case study and solved the sustainable land use allocation problem by using an improved heuristic optimization model. The model was constructed based on the integration of a spatial discrete particle swarm optimization and cellular automata-Markov simulation approach. The spatiotemporal land use patterns and policy interventions were represented by the CA-Markov as in spatially explicit transition rules, and then incorporated into the discrete PSO for optimal land use solutions. We examined the influence of the joint effect of spatiotemporal land use patterns and policy interventions on the land use allocation outcome. Our results demonstrate the robustness and potential of the proposed model, and, more importantly, indicate the significance of incorporating the spatiotemporal land use patterns and policy interventions into rural land use allocation.     

Efficient regionalization techniques for socio‐economic geographical units using minimum spanning trees

Regionalization is a classification procedure applied to spatial objects with an areal representation, which groups them into homogeneous contiguous regions. This paper presents an efficient method for regionalization. The first step creates a connectivity graph that captures the neighbourhood relationship between the spatial objects. The cost of each edge in the graph is inversely proportional to the similarity between the regions it joins. We summarize the neighbourhood structure by a minimum spanning tree (MST), which is a connected tree with no circuits. We partition the MST by successive removal of edges that link dissimilar regions. The result is the division of the spatial objects into connected regions that have maximum internal homogeneity. Since the MST partitioning problem is NP‐hard, we propose a heuristic to speed up the tree partitioning significantly. Our results show that our proposed method combines performance and quality, and it is a good alternative to other regionalization methods found in the literature.     

A regionalization method for clustering and partitioning based on trajectories from NLP perspective

ABSTRACT

Regionalization attempts to group units into a few subsets to partition the entire area. The results represent the underlying spatial structure and facilitate decision-making. Massive amounts of trajectories produced in the urban space provide a new opportunity for regionalization from human mobility. This paper proposes and applies a novel regionalization method to cluster similar areal units and visualize the spatial structure by considering all trajectories in an area into a word embedding model. In this model, nodes in a trajectory are regarded as words in a sentence, and nodes can be clustered in the feature space. The result depicts the underlying socio-economic structure at multiple spatial scales. To our knowledge, this is the first regionalization method from trajectories with natural language processing technology. A case study of mobile phone trajectory data in Beijing is used to validate our method, and then we evaluate its performance by predicting the next location of an individual’s trajectory. The case study indicates that the method is fast, flexible and scalable to large trajectory datasets, and moreover, represents the structure of trajectory more effectively.