一种求解学区划分问题的混合启发式算法

针对目前求解学区划分问题算法搜索过程缺乏记忆,搜索效率不高,容易陷入局部最优而收敛慢等问题,该文提出一种多启动(M)框架下,迭代禁忌搜索(ITS)算法与模拟退火(SA)算法混合的M-ITS-SA算法。该算法包括构造初始解、禁忌搜索、SA算法优化与求解等。运用K-Medoids模型对学校分组后,采用M-ITS-SA算法对学区进行划分与优化,并从多个分区方案中求解最优分区方案。学区划分实验结果表明:该文提出的M-ITS-SA算法能够保证分区的空间连续性,适用于单校和多校划片,并在入学总距离上与混合元启发算法(M-ILS-SPP)保持相当的同时,大大降低了超额招生人数和总用时,具有良好的寻优能力和收敛性,优于M-ILS-SPP算法。     

A spatial parallel heuristic approach for solving very large‐scale vehicle routing problems

The vehicle routing problem (VRP) is one of the most prominent problems in spatial optimization because of its broad applications in both the public and private sectors. This article presents a novel spatial parallel heuristic approach for solving large‐scale VRPs with capacity constraints. A spatial partitioning strategy is devised to divide a region of interest into a set of small spatial cells to allow the use of a parallel local search with a spatial neighbor reduction strategy. An additional local search and perturbation mechanism around the border area of spatial cells is used to improve route segments across spatial cells to overcome the border effect. The results of one man‐made VRP benchmark and three real‐world super‐large‐scale VRP instances with tens of thousands of nodes verify that the presented spatial parallel heuristic approach achieves a comparable solution with much less computing time.     

A spatial‐temporal‐semantic approach for detecting local events using geo‐social media data

Social media networks allow users to post what they are involved in with location information in a real‐time manner. It is therefore possible to collect large amounts of information related to local events from existing social networks. Mining this abundant information can feed users and organizations with situational awareness to make responsive plans for ongoing events. Despite the fact that a number of studies have been conducted to detect local events using social media data, the event content is not efficiently summarized and/or the correlation between abnormal neighboring regions is not investigated. This article presents a spatial‐temporal‐semantic approach to local event detection using geo‐social media data. Geographical regularities are first measured to extract spatio‐temporal outliers, of which the corresponding tweet content is automatically summarized using the topic modeling method. The correlation between outliers is subsequently examined by investigating their spatial adjacency and semantic similarity. A case study on the 2014 Toronto International Film Festival (TIFF) is conducted using Twitter data to evaluate our approach. This reveals that up to 87% of the events detected are correctly identified compared with the official TIFF schedule. This work is beneficial for authorities to keep track of urban dynamics and helps build smart cities by providing new ways of detecting what is happening in them.     

An enhanced approach for surface flow routing over drainage‐constrained triangulated irregular networks

The accuracy and efficiency of the simulations in distributed hydrological models must depend on the proper estimation of flow directions and paths. Numerous studies have been carried out to delineate the drainage patterns based on gridded digital elevation models (DEMs). The triangulated irregular network (TIN) has been increasingly applied in hydrological applications due to the advantages of high storage efficiency and multi‐scale adaptive performance. Much of the previous literature focuses mainly on filling the depressions on gridded DEMs rather than treating the special cases in TIN structures, which has hampered its applications to hydrological models. This study proposes a triangulation‐based solution for the removal of flat areas and pits to enhance the simulation of flow routing on triangulated facet networks. Based on the drainage‐constrained TIN generated from only a gridded DEM by the compound point extraction (CPE) method, the inconsistent situations including flat triangles, V‐shape flat edges and sink nodes are respectively identified and rectified. The optimization algorithm is an iterative process of TIN reconstruction, in which the flat areas are generalized into their center points and the pits are rectified by embedding break lines. To verify the proposed algorithm and investigate the potential for flow routing, flow paths of steepest descent are derived by the vector‐based tracking algorithm based on the optimized TIN. A case study of TIN optimization and flow path tracking was performed on a real‐world DEM. The outcomes indicate that the proposed approach can effectively solve the problem of inconsistencies without a significant loss in accuracy of the terrain model.     

基于不同学科解决粗差探测问题的方法研究

通过对已有粗差探测成果的研究,本文按照基于的学科不同将其大致分为4类:数理统计粗差探测方法,基于多元统计分析粗差探测方法,线性代数粗差探测方法,人工智能粗差探测方法。然后从这4个方面辐射出已有的关于粗差发现、定位、定值等相关方法的研究,并且针对国内学者对用人工智能方法实现粗差探测未进行成熟研究的现状,提出可行策略并进行实现从而为人工智能和测量数据处理2个学科的结合开拓新的研究方向。     

A Topology‐Inferred Graph‐Based Heuristic Algorithm for Map Simplification

In this article we present a heuristic map simplification algorithm based on a novel topology‐inferred graph model. Compared with the existing algorithms, which only focus either on geometry simplification or on topological consistency, our algorithm simplifies the map composed of series of polylines and constraint points while maintaining the topological relationships in the map, maximizing the number of removal points, and minimizing error distance efficiently. Unlike some traditional geometry simplification algorithms, such as Douglas and Peucker's, which add points incrementally, we remove points sequentially based on a priority determined by heuristic functions. In the first stage, we build a graph to model the topology of points in the map from which we determine whether a point is removable or not. As map generalization is needed in different applications with different requirements, we present two heuristic functions to determine the priority of points removal for two different purposes: to save storage space and to reduce computation time. The time complexity of our algorithm is which is efficient enough to be considered for real‐time applications. Experiments on real maps were conducted and the results indicate that our algorithm produces high quality results; one heuristic function results in higher removal points saving storage space and the other improves the time performance significantly.     

A heuristic multi-criteria classification approach incorporating data quality information for choropleth mapping

ABSTRACT

Despite conceptual and technology advancements in cartography over the decades, choropleth map design and classification fail to address a fundamental issue: estimates that are statistically indifferent may be assigned to different classes on maps or vice versa. Recently, the class separability concept was introduced as a map classification criterion to evaluate the likelihood that estimates in two classes are statistical different. Unfortunately, choropleth maps created according to the separability criterion usually have highly unbalanced classes. To produce reasonably separable but more balanced classes, we propose a heuristic classification approach to consider not just the class separability criterion but also other classification criteria such as evenness and intra-class variability. A geovisual-analytic package was developed to support the heuristic mapping process to evaluate the trade-off between relevant criteria and to select the most preferable classification. Class break values can be adjusted to improve the performance of a classification.     

A modular graph transformation rule set for IFC‐to‐CityGML conversion

Conversion of Industry Foundation Classes (IFC) building models into CityGML city models is one of the operational scenarios for BIM–GIS integration, with a variety of applications producing and consuming data on either side. Given the in‐depth cross‐domain knowledge required to specify such conversions, the heterogeneity of the IFC input data and the use cases for the resulting CityGML, flexible and configurable solutions are needed that make conversion details accessible to domain specialists. Graph transformation as a conversion method fulfils these requirements. We propose to extend the modularity given by single transformation rules at a more coarse‐grained level and identify four layers with modules of associated rules. We describe a self‐contained set of rules across these modules and demonstrate its application to a range of building models.     

Geo‐Social Model: A Conceptual Framework for Real‐time Geocollaboration

Synchronous geocollaboration helps geographically dispersed people to work together in a shared geospatial environment. Its real‐time nature, multiple users' interaction and diversity of work context impose some special social, organizational and technological requirements, making the development of such real‐time geocollaboration systems a challenging task. A conceptual framework is therefore needed to specify and describe what synchronous geocollaboration is, considering its social, spatial and technical aspects. The geo‐social model presented in this article describes a conceptual framework for synchronous geocollaboration systems addressing the above aspects, identifies the core elements of the system and describes how these elements collaborate with each other. This model is presented using application‐level ontology and is then applied to a multi‐agent system based prototype in which multiple users can interact and negotiate in a shared 3D geospatial environment.     

Automated Digital Photogrammetry: A Valuable Tool for Small‐scale Geomorphological Research for the Non‐photogrammetrist?

Digital photogrammetry provides a tool with which to automatically generate digital elevation models (DEMs). The necessary equipment is now both readily available and affordable: thus there is considerable potential for this technique to be widely adopted in geomorphological studies. But is it possible for geomorphologists without a background in photogrammety to use it successfully? As part of a larger study into rill initiation by overland flow, a non‐metric digital camera and ERDAS IMAGINE OrthoMAX software were used to generate small‐scale DEMs of soil surface microtopography. This paper reports on the procedure used, highlights potential pitfalls, and comments on the quality of the resultant DEMs. Whilst acquisition of high‐quality images using a digital camera is relatively straightforward, problems were subsequently encountered due to the small size of the internal imager and the need for camera calibration. Potential stumbling blocks in the use of the software lay in the setting‐up of ground control points and the use of tie‐points and check‐points, as well as several software glitches not identified in the current manual. Nonetheless, once these problems were overcome the technique proved to be a simple, effective and fast tool for generating high quality microtopographical DEMs. This methodology shows great promise for future geomorphological studies that require these kinds of surface data.     

A Back‐Propagation Neural Network‐Based Approach for Multi‐Represented Feature Matching in Update Propagation

Spatial data infrastructures, which are characterized by multi‐represented datasets, are prevalent throughout the world. The multi‐represented datasets contain different representations for identical real‐world entities. Therefore, update propagation is useful and required for maintaining multi‐represented datasets. The key to update propagation is the detection of identical features in different datasets that represent corresponding real‐world entities and the detection of changes in updated datasets. Using polygon features of settlements as examples, this article addresses these key problems and proposes an approach for multi‐represented feature matching based on spatial similarity and a back‐propagation neural network (BPNN). Although this approach only utilizes the measures of distance, area, direction and length, it dynamically and objectively determines the weight of each measure through intelligent learning; in contrast, traditional approaches determine weight using expertise. Therefore, the weight may be variable in different data contexts but not for different levels of expertise. This approach can be applied not only to one‐to‐one matching but also to one‐to‐many and many‐to‐many matching. Experiments are designed using two different approaches and four datasets that encompass an area in China. The goals are to demonstrate the weight differences in different data contexts and to measure the performance of the BPNN‐based feature matching approach.     

A GIS Toolbox for Measuring and Mapping Person‐Based Space‐Time Accessibility

This article presents a toolbox to compute and map person‐based accessibility indicators, based on classical time geography concepts. The intent is to provide GIS and urban planning practitioners with a user‐friendly and easily customizable tool. While it relies on well‐known concepts, the toolbox implements a major innovation in person‐based accessibility assessment by taking into account opening hours when measuring the accessibility of urban facilities. The toolbox can be downloaded from http://bit.ly/1h6yg5Z .     

A multi‐criteria decision‐making approach for geometric matching of areal objects

We propose a method for geometric areal object matching based on multi‐criteria decision making. To enable this method, we focused on determining the matched areal object pairs that have all relations, one‐to‐one relationships to many‐to‐many relationships, in different spatial data sets by fusing geometric criteria without user invention. First, we identified candidate corresponding areal object pairs with a graph‐based approach in training data. Second, three matching criteria (areal hausdorff distance, intersection ratio, and turning function distance) were calculated in candidate corresponding pairs and these criteria were normalized. Third, the shape similarity was calculated by weighted linear combination using the normalized matching criteria (similarities) with the criteria importance through intercriteria correlation method. Fourth, a threshold (0.738) of the shape similarity estimated in the plot of precision versus recall versus all possible thresholds of training data was applied, and the matched pairs were determined and identified. Finally, we visually validated the detection of similar areal feature pairs and conducted statistical evaluation using precision, recall, and F‐measure values from a confusion matrix. Their values were 0.905, 0.848, and 0.876, respectively. These results validate that the proposed classifier, which detects 87.6% of matched areal pairs, is highly accurate.     

A Parallel Scheme for Large‐scale Polygon Rasterization on CUDA‐enabled GPUs

This research develops a parallel scheme to adopt multiple graphics processing units (GPUs) to accelerate large‐scale polygon rasterization. Three new parallel strategies are proposed. First, a decomposition strategy considering the calculation complexity of polygons and limited GPU memory is developed to achieve balanced workloads among multiple GPUs. Second, a parallel CPU/GPU scheduling strategy is proposed to conceal the data read/write times. The CPU is engaged with data reads/writes while the GPU rasterizes the polygons in parallel. This strategy can save considerable time spent in reading and writing, further improving the parallel efficiency. Third, a strategy for utilizing the GPU's internal memory and cache is proposed to reduce the time required to access the data. The parallel boundary algebra filling (BAF) algorithm is implemented using the programming models of compute unified device architecture (CUDA), message passing interface (MPI), and open multi‐processing (OpenMP). Experimental results confirm that the implemented parallel algorithm delivers apparent acceleration when a massive dataset is addressed (50.32 GB with approximately 1.3 × 10⁸ polygons), reducing conversion time from 25.43 to 0.69 h, and obtaining a speedup ratio of 36.91. The proposed parallel strategies outperform the conventional method and can be effectively extended to a CPU‐based environment.     

A closed-form of Newton method for solving over-determined pseudo-distance equations

The Newton method has been widely used for solving nonlinear least-squares problem. In geodetic adjustment, one would prefer to use the Gauss–Newton method because of the parallel with linear least-squares problem. However, it is proved in theory as well as in practice that the Gauss–Newton method has slow convergence rate and low success rate. In this paper, the over-determined pseudo-distance equations are solved by nonlinear methods. At first, the convergence of decent methods is discussed after introducing the conditional equation of nonlinear least squares. Then, a compacted form of the Hessian matrix from the second partial derivates of the pseudo-distance equations is given, and a closed-form of Newton method is presented using the compacted Hessian matrix to save the computation and storage required by Newton method. At last, some numerical examples to investigate the convergence and success rate of the proposed method are designed and performed. The performance of the closed-form of Newton method is compared with the Gauss–Newton method as well as the regularization method. The results show that the closed-form of Newton method has good performances even for dealing with ill-posed problems while a great amount of computation is saved.     

提高对流层天顶总延迟解算精度的新方法探讨

对流层天顶总延迟的解算精度,直接影响长基线解算的精度和大气水汽含量的计算精度。文中提出克利金内插法解算天顶总延迟的新方法,并利用南极长城站和周边IGS跟踪站的GPS数据,通过高精度解算软件GAMIT/GLOBK,解算出长城站上空的对流层天顶总延迟,将其与利用内插方法解算的天顶总延迟进行了对比分析,得出:利用该内插方法获取的南极长城站在夏季的天顶总延迟的均方差可达0.2mm,这对今后GPS高精度定位和GPS气象学应用来说,具有重要意义。     

A web‐based visualization tool for exploring stakeholder conflicts in land‐use planning

This article describes an open source web‐based visualization tool for exploring stakeholder conflicts in land‐use planning. It implements a multi‐criteria, decision‐analytic framework which solves a conflict‐constrained knapsack problem in order to find Pareto efficient combinations of actions which maximize public value, given the conflict constraint. The user interface is centered around an interactive map in which geographical subareas are color‐shaded in proportion to the mean strength of preference for a particular chosen action within the population in the selected area. The aim of this work is to investigate the use of web technologies and formal problem‐solving methods for improving public participation in land‐use planning and support local governments in the pursuit of improved decision‐making. The tool was developed using the free statistical programming language R and the web application framework Shiny. Its usefulness is demonstrated through a case study in Upplands Väsby municipality in Stockholm County, Sweden. The article ends with a summary together with some ideas for future research and development.     

A Temporal Variant‐Invariant Validation Approach for Agent‐based Models of Landscape Dynamics

Agent‐based modeling provides a means for addressing the way human and natural systems interact to change landscapes over time. Until recently, evaluation of simulation models has focused on map comparison techniques that evaluate the degree to which predictions match real‐world observations. However, methods that change the focus of evaluation from patterns to processes have begun to surface; that is, rather than asking if a model simulates a correct pattern, models are evaluated on their ability to simulate a process of interest. We build on an existing agent‐based modeling validation method in order to present a temporal variant‐invariant analysis (TVIA). The enhanced method, which focuses on analyzing the uncertainty in simulation results, examines the degree to which outcomes from multiple model runs match some reference to how land use parcels make the transition from one land use class to another over time. We apply TVIA to results from an agent‐based model that simulates the relationships between landowner decisions and wildfire risk in the wildland‐urban interface of the southern Willamette Valley, Oregon, USA. The TVIA approach demonstrates a novel ability to examine uncertainty across time to provide an understanding of how the model emulates the system of interest.     

A four‐dimensional agent‐based model: A case study of forest‐fire smoke propagation

Dynamic geospatial complex systems are inherently four‐dimensional (4D) processes and there is a need for spatio‐temporal models that are capable of realistic representation for improved understanding and analysis. Such systems include changes of geological structures, dune formation, landslides, pollutant propagation, forest fires, and urban densification. However, these phenomena are frequently analyzed and represented with modeling approaches that consider only two spatial dimensions and time. Consequently, the main objectives of this study are to design and develop a modeling framework for 4D agent‐based modeling, and to implement the approach to the 4D case study for forest‐fire smoke propagation. The study area is central and southern British Columbia and the western parts of Alberta, Canada for forest fires that occurred in the summer season of 2017. The simulation results produced realistic spatial patterns of the smoke propagation dynamics.