Search

Geospatial data conflation is the process of combining multiple datasets about a geographic phenomenon to produce a single, richer dataset. It has received increased research attention due to its many applications in map making, transportation, planning, and temporal geospatial analyses, among many others. One approach to conflation, attempted from the outset in the literature, is the use of optimization‐based conflation methods. Conflation is treated as a natural optimization problem of minimizing the total number of discrepancies while finding corresponding features from two datasets. Optimization‐based conflation has several advantages over traditional methods including conciseness, being able to find an optimal solution, and ease of implementation. However, current optimization‐based conflation methods are also limited. A main shortcoming with current optimized conflation models (and other traditional methods as well) is that they are often too weak and cannot utilize the spatial context in each dataset while matching corresponding features. In particular, current optimal conflation models match a feature to targets independently from other features and therefore treat each GIS dataset as a collection of unrelated elements, reminiscent of the spaghetti GIS data model. Important contextual information such as the connectivity between adjacent elements (such as roads) is neglected during the matching. Consequently, such models may produce topologically inconsistent results. In this article, we address this issue by introducing new optimization‐based conflation models with structural constraints to preserve the connectivity and contiguity relation among features. The model is implemented using integer linear programming and compared with traditional spaghetti‐style models on multiple test datasets. Experimental results show that the new element connectivity (ec‐bimatching) model reduces false matches and consistently outperforms traditional models. [ABSTRACT FROM AUTHOR]

Measuring the similarity between counterpart geospatial features is crucial in the effective conflation of spatial datasets from difference sources. This article proposes a new similarity metric called the "map turning function distance" (MTFD) for matching linear features such as roads based on the well‐known turning function (TF) distance in computer vision. The MTFD overcomes the limitations of the traditional TF distance, such as the inability to handle partial matches and insensitivity to differences in scale and rotation. In particular, the MTFD allows one to: (a) partially match a linear feature to a portion of a larger feature from a certain position of match; and (b) consider both the shape and orientation differences of polylines based on comparing their turning angles. In finding the best match position, we prove that the optimal position can be found among a finite set of positions on the target feature. We then combine the MTFD with widely used point‐offset distances such as the Hausdorff distance to form a composite similarity metric. Our experiments with real road datasets demonstrate that the new metric has greater discriminative power than traditional point‐offset‐based similarity measures, and significantly improves the precision of two tested conflation models. [ABSTRACT FROM AUTHOR]

The p-center problem is one of the most important models in location theory. Its objective is to place a fixed number of facilities so that the maximum service distance for all customers is as small as possible. This article develops a reliable p-center problem that can account for system vulnerability and facility failure. A basic assumption is that located centers can fail with a given probability and a customer will fall back to the closest nonfailing center for service. The proposed model seeks to minimize the expected value of the maximum service distance for a service system. In addition, the proposed model is general and can be used to solve other fault-tolerant center location problems such as the (p, q)-center problem using appropriate assignment vectors. I present an integer programming formulation of the model and computational experiments, and then conclude with a summary of findings and point out possible future work. [ABSTRACT FROM AUTHOR]

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 important classes of facility dispersion problems involves the location of a number of facilities where the intent is to place them as far apart from each other as possible. Four basic forms of the p-facility dispersion problem appear in the literature. Erkut and Neuman present a classification system for these four classic constructs. More recently, Curtin and Church expanded upon this framework by the introduction of 'multiple types' of facilities, where the dispersion distances between specific types are weighted differently. This article explores another basic assumption found in all four classic models (including the multitype facility constructs of Curtin and Church): that dispersion is accounted for in terms of either distance to the closest facility or distances to all facilities (from a given facility), whether applied to a single type of facility or across a set of facility types. In reality, however, measuring dispersion in terms of whether neighboring facilities to a given facility are dispersed rather than whether all facilities are dispersed away from the given facility often makes more sense. To account for this intermediate measure of dispersion, we propose a construct called partial-sum dispersion. We propose four 'partial-sum' dispersion problem forms and show that these are generalized forms of the classic set of four models codified by Erkut and Neuman. Further, we present a unifying model that is a generalized form of all four partial-sum models as well as a generalized form of the original four classic model constructs. Finally, we present computational experience with the general model and conclude with a few examples and suggestions for future research. Una de las clases importantes dentro de los problemas de dispersión de instalaciones de servicios/infraestructura es el caso en el que la localización de un número de instalaciones debe cumplir la condición de maximizar la distancia entre cada par. La literatura especializada cita cuatro formas básicas del problema de dispersión llamados tipo p-instalación ( p-facility) (Shier 1977; Luna y Chaudhry 1984; Kuby 1987; Erkut y Neuman, 1991). Erkut y Neuman (1991) presentan un sistema de clasificación para estas cuatro formas clásicas. Recientemente, Curtin e Iglesia (2006) ampliaron este marco metodológico al incorporar múltiples tipos de instalaciones, permitiendo que las distancias de dispersión entre diferentes tipos específicos de instalaciones sean ponderadas de manera diferente. El artículo presente explora otro supuesto básico que se encuentra en los cuatro modelos clásicos (y las modifcaciones para acomodar instalaciones multi-tipo de Curtin e Iglesia): la dispersión es cuantificada en términos de la distancia entre una instalación dada y la instalación más cercana, o entre una instalación dada y la totalidad de las instalaciones. Este supuesto se mantiene si las distancias son aplicadas a un solo tipo de instalación o a múltiples tipos de instalaciones. Sin embargo, en realidad, tiene más sentido medir la dispersión en relación a las instalaciones vecinas, en vez de en relación a la totalidad las instalaciones. Para incorporar esta realidad a un nuevo tipo de medida intermedia de dispersión, se propone una medida llamada dispersión de suma parcial ( partial-sum dispersion). Proponemos cuatro tipos de problemas de dispersión de tipo parcial-sum y demostramos que éstas son formas generalizadas de los cuatro modelos clásicos presentados por Erkut y Neuman (1991). Además, se presenta un modelo unificado que es una forma generalizada de los cuatro modelos tipo partial-sum, así como una forma generalizada de las cuatro tipos en el modelo clásico. Por último, se presenta los resultados de pruebas computacionales usando el modelo general y se concluye con algunos ejemplos y sugerencias para investigaciones futuras. 设施分散问题中重要的一类是大量设施的布局，其意图是将它们在空间上尽可能离得更远。目前文献中主要讨论了4种基本形式(Shier 1977; Moon and Chaudhry 1984; Kuby 1987; Erkut and Neuman 1991)。Erkut and Neuman (1991)提出了这4种经典结构的一种分类系统。Curtin and Church (2006)引入设施'多种类型'对上述分类框架进行拓展，在特定类别之间的分散距离的权重存在不同。本文探索了在4种经典模型中所发现的另一种基本假设（包含Curtin and Church的多种类型设施结构）：无论是在单一类型设施或包括多种类型设施中，分散度在解释某一给定设施到最近设施的距离或到所有设施的距离方面都是合理的。然而，在现实中设施分散度度量方面，测量某一给定设施的邻近设施的分散度特征相比于测量给定设施的所有其他设施的散布特征通常更有意义。为解释这种分散度的中间度量，本文提出了一种称为'局部和整体'的结构，包括4种分散问题形式，它们是Erkut and Neuman 4种传统类型的广义形式。本文进而提出了一个统一模型，即所有 '局部和整体'模型和经典类型结构一种广义形式。最后，对统一模型进行了计算检验，并基于几个实证进行了总结，还提出了未来的研究建议。 [ABSTRACT FROM AUTHOR]

The hub location problem has been widely used in analyzing hub-and-spoke systems. The basic assumption is that a large number of demands exist to travel from origins to destinations via a set of intermediate transshipment nodes. These intermediate nodes can be lost, due to reasons such as natural disasters, outbreaks of disease, labor strikes, and intentional attacks. This article presents a hub interdiction median ( HIM) problem. It can be used to identify the set of critical facilities in a hub-and-spoke system that, if lost, leads to the maximal disruption of the system's service. The new model is formulated using integer linear programming. Special constraints are constructed to account for origin-to-destination demand following the least-cost route via the remaining hubs. Based on the HIM problem, two hub protection problems are defined that aim to minimize the system cost associated with the worst-case facility loss. Computational experiment results are presented along with a discussion of possible future work. El problema de la ubicación de la central ( hub) ha sido ampliamente analizado para el caso de los sistemas de sistemas radiales ( hub-and-spoke). La presunción inicial es que existe un gran número de demandas que viajan desde puntos de origen hasta sus puntos de destino a través de un set de nodos intermedios de trasbordo. Estos nodos intermedios pueden perderse por diferentes motivos, como desastres naturales, brotes de enfermedades, huelgas de trabajadores, o ataques intencionales. Este artículo presenta un problema de tipo mediana de interdicción de hub, conocido como hub interdiction median-HIM. Puede usarse para identificar un set de instalaciones críticas de un sistema tipo hub-and-spoke que, si se pierde, conduce a la máxima interrupción del servicio del sistema. El nuevo modelo se ha formulado utilizando programación entera lineal, ( integer linear programming-ILP). El modelo construye restricciones especiales para dar cuenta de la demanda de 'origen-a-destino' (O-D), siguiendo la ruta de menor costo, a través de los hubs restantes. Basándonos en el problema de HIM, se definen dos problemas de protección de hub que buscan minimizar el costo asociado al peor caso posible de pérdida de instalaciones. Se presentan además, resultados de experimentos computacionales, así como a una discusión sobre posibles futuros trabajos en la materia. 枢纽区位研究已广泛应用于中枢辐射型系统分析，其基本假设条件为起始点到目的地之间存在大量旅行需求的中间转运节点。但自然灾害、突发疾病、劳务罢工和蓄意攻击等因素可能导致中间转运节点的丧失。本文提出了一种枢纽封闭中心模型（HIM），可用于识别中枢辐射型系统的重要节点，一旦这些节点丧失，将导致整个系统服务最大程度的瓦解。新模型通过整数线性规划公式建立。模型特殊约束条件的建立基于最小成本路径通过余下枢纽的花费来解释始发到目的地（ origin-to-destination）需求量。基于HIM问题，双枢纽保护问题被定义为旨在最小化系统花费及其与之关联的最坏情况下节点丢失问题。最后，根据计算的经验结果讨论未来可能深入的研究。 [ABSTRACT FROM AUTHOR]