Search

Geospatial data conflation involves matching and combining two maps to create a new map. It has received increased research attention in recent years due to its wide range of applications in GIS (Geographic Information System) data production and analysis. The map assignment problem (conceptualized in the 1980s) is one of the earliest conflation methods, in which GIS features from two maps are matched by minimizing their total discrepancy or distance. Recently, more flexible optimization models have been proposed. This includes conflation models based on the network flow problem and new models based on Mixed Integer Linear Programming (MILP). A natural question is: how are these models related or different, and how do they compare? In this study, an analytic review of major optimized conflation models in the literature is conducted and the structural linkages between them are identified. Moreover, a MILP model (the base-matching problem) and its bi-matching version are presented as a common basis. Our analysis shows that the assignment problem and all other optimized conflation models in the literature can be viewed or reformulated as variants of the base models. For network-flow based models, proof is presented that the base-matching problem is equivalent to the network-flow based fixed-charge-matching model. The equivalence of the MILP reformulation is also verified experimentally. For the existing MILP-based models, common notation is established and used to demonstrate that they are extensions of the base models in straight-forward ways. The contributions of this study are threefold. Firstly, it helps the analyst to understand the structural commonalities and differences of current conflation models and to choose different models. Secondly, by reformulating the network-flow models (and therefore, all current models) using MILP, the presented work eases the practical application of conflation by leveraging the many off-the-shelf MILP solvers. Thirdly, the base models can serve as a common ground for studying and writing new conflation models by allowing a modular and incremental way of model development. [ABSTRACT FROM AUTHOR]

Geospatial data conflation is the process of identifying and merging the corresponding features in two datasets that represent the same objects in reality. Conflation is needed in a wide range of geospatial analyses, yet it is a difficult task, often considered too unreliable and costly due to various discrepancies between GIS data sources. This study addresses the reliability issue of computerized conflation by developing stronger optimization-based conflation models for matching two network datasets with minimum discrepancy. Conventional models match roads on a feature-by-feature basis. By comparison, we propose a new node-arc conflation model that simultaneously matches road-center lines and junctions in a topologically consistent manner. Enforcing this topological consistency increases the reliability of conflation and reduces false matches. Similar to the well-known rubber-sheeting method, our model allows for the use of network junctions as "control" points for matching network edges. Unlike rubber sheeting, the new model is automatic and matches all junctions (and edges) in one pass. To the best of our knowledge, this is the first optimized conflation model that can match nodes and edges in one model. Computational experiments using six road networks in Santa Barbara, CA, showed that the new model is selective and reduces false matches more than existing optimized conflation models. On average, it achieves a precision of 94.7% with over 81% recall and achieves a 99.4% precision when enhanced with string distances. [ABSTRACT FROM AUTHOR]

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 classicp-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. [ABSTRACT FROM PUBLISHER]

The vector assignment p-median problem (VAPMP) is one of the first discrete location problems to account for the service of a demand by multiple facilities, and has been used to model a variety of location problems in addressing issues such as system vulnerability and reliability. Specifically, it involves the location of a fixed number of facilities when the assumption is that each demand point is served a certain fraction of the time by its closest facility, a certain fraction of the time by its second closest facility, and so on. The assignment vector represents the fraction of the time a facility of a given closeness order serves a specific demand point. Weaver and Church showed that when the fractions of assignment to closer facilities are greater than more distant facilities, an optimal all-node solution always exists. However, the general form of the VAPMP does not have this property. Hooker and Garfinkel provided a counterexample of this property for the nonmonotonic VAPMP. However, they do not conjecture as to what a finite set may be in general. The question of whether there exists a finite set of locations that contains an optimal solution has remained open to conjecture. In this article, we prove that a finite optimality set for the VAPMP consisting of "equidistant points" does exist. We also show a stronger result when the underlying network is a tree graph. [ABSTRACT FROM AUTHOR]

One of the most important tasks in remote sensing data processing is the production of orthorectified images. Such tasks are computationally intensive and can become a bottleneck for remote sensing image processing, particularly in high-throughput environments, such as large satellite imagery processing centers. This letter explores the use of massive parallel processing graphical processing unit (GPU) in a clustered network environment to speed up image processing tasks, such as orthorectification. Our parallelization method is based on inverse sensor model and the stream model for image processing, which allow the flexibility of placing computational units on proper computation units, such as GPU, CPU cores, or nodes in a cluster. In our experiments on images of two satellites, more than 198 times and 50.3 times speedup over one and multiple thread CPU versions have been achieved, respectively. [ABSTRACT FROM PUBLISHER]

The vector assignment p-median problem (VAPMP) and the ordered p-median problem (OMP) are important extensions of the classic p-median problem. The VAPMP extends the p-median problem by allowing assignment of a demand to multiple facilities, and a wide variety of multi-assignment and backup location problems are special cases of this problem. The OMP optimizes a weighted sum of service distances according to their relative ranks among all demands. The OMP is well known as it represents a generalization of both the p-median and the p-center problems. In this article, a new model is developed which extends both the VAPMP and OMP problems. In addition, beyond median, center, and vector assignment, this new model can resolve problems where the system objective involves maximizing distance. The new model also gives rise to meaningful special-case problems, such as a “reliable p-center” problem. Different integer linear programming (ILP) formulations of the new problem are presented and tested. It is demonstrated that an efficient formulation for a special case of the VAOMP problem can solve medium sized problems optimally in a reasonable amount of time. [ABSTRACT FROM PUBLISHER]

In the classic p-median problem, it is assumed that each point of demand will be served by his or her closest located facility. The p-median problem can be thought of as a ‘‘single-level’’ allocation and location problem, as all demand at a specific location is assigned as a whole unit to the closest facility. In some service protocols, demand assignment has been defined as ‘‘multilevel’’ where each point of demand may be served a certain percentage of the time by the closest facility, a certain percentage of the time by the second closest facility, and so on. This article deals with the case in which there is a need for ‘‘explicit’’ closest assignment (ECA) constraints. The authors review past location modeling work that involves single-level ECA constraints as well as specific constraint constructs that have been proposed to ensure single-level closest assignment. They then show how each of the earlier proposed ECA constructs can be generalized for the ‘‘multilevel’’ case. Finally, the authors provide computational experience using these generalized ECA constructs for a novel multilevel facility interdiction problem introduced in this article. Altogether, this article proposes both a new set of constraint structures that can be used in location models involving multilevel assignment as well as a new facility interdiction model that can be used to optimize worst case levels of facility disruption. [ABSTRACT FROM AUTHOR]