Regional Coverage Maximization: Alternative Geographical Space Abstraction and Modeling

Analysis results are often found to vary with the way we abstract geographical space. When continuous geographic phenomena are abstracted, processed, and stored in a digital environment, some level of discretization is often employed. Information loss in a discretization process brings about uncertainty/error, and as a result research findings may be highly dependent on the particular discretization method used. This article examines one spatial problem concerning how to achieve the maximal regional coverage given a limited number of service facilities. Two widely used geographical space abstraction approaches are examined, the point‐based representation and the area‐based representation, and issues associated with each representation scheme are analyzed. To accommodate the limitations of the existing representation schemes, a mixed representation strategy is proposed along with a new maximal covering model. Experiments are conducted to site warning sirens in Dublin, Ohio. Results demonstrate the effectiveness of the mixed representation scheme in finding high‐quality solutions when the regional coverage level is medium or high.     

Contiguity Constraints for Single‐Region Site Search Problems

This paper proposes an explicit set of constraints as a general approach to the contiguity problem in site search modeling. Site search models address the challenging problem of identifying the best area in a study region for a particular land use, given that there are no candidate sites. Criteria that commonly arise in a search include a site's area, suitability, cost, shape, and proximity to surrounding geographic features. An unsolved problem in this modeling arena is the identification of a general set of mathematical programming constraints that can guarantee a contiguous solution (site) for any 0–1 integer‐programming site search formulation. The constraints proposed herein address this problem, and we evaluate their efficacy and efficiency in the context of a regular and irregular tessellation of geographic space. An especially efficient constraint form is derived from a more general form and similarly evaluated. The results demonstrate that the proposed constraints represent a viable, general approach to the contiguity problem.     

Dispersion of Nodes Added to a Network

For location problems in which optimal locations can be at nodes or along arcs but no finite dominating set has been identified, researchers may desire a method for dispersing p additional discrete candidate sites along the m arcs of a network. This article develops and tests minimax and maximin models for solving this continuous network location problem, which we call the added-node dispersion problem (ANDP). Adding nodes to an arc subdivides it into subarcs. The minimax model minimizes the maximum subarc length, while the maximin model maximizes the minimum subarc length. Like most worst-case objectives, the minimax and maximin objectives are plagued by poorly behaved alternate optima. Therefore, a secondary MinSumMax objective is used to select the best-dispersed alternate optima. We prove that equal spacing of added nodes along arcs is optimal to the MinSumMax objective. Using this fact we develop greedy heuristic algorithms that are simple, optimal, and efficient (O( mp )). Empirical results show how the maximum subarc, minimum subarc, and sum of longest subarcs change as the number of added nodes increases. Further empirical results show how using the ANDP to locate additional nodes can improve the solutions of another location problem. Using the p-dispersion problem as a case study, we show how much adding ANDP sites to the network vertices improves the p-dispersion objective function compared with (a) network vertices only and (b) vertices plus randomly added nodes. The ANDP can also be used by itself to disperse facilities such as stores, refueling stations, cell phone towers, or relay facilities along the arcs of a network, assuming that such facilities already exist at all nodes of the network.     

Using Linear Integer Programming for Multi‐Site Land‐Use Allocation

Research in the area of spatial decision support (SDS) and resource allocation has recently generated increased attention for integrating optimization techniques with GIS. In this paper we address the use of spatial optimization techniques for solving multi‐site land‐use allocation (MLUA) problems, where MLUA refers to the optimal allocation of multiple sites of different land uses to an area. We solve an MLUA problem using four different integer programs (IP), of which three are linear integer programs. The IPs are formulated for a raster‐based GIS environment and are designed to minimize development costs and to maximize compactness of the allocated land use. The preference for either minimizing costs or maximizing compactness has been made operational by including a weighting factor. The IPs are evaluated on their speed and their efficacy for handling large databases. All four IPs yielded the optimal solution within a reasonable amount of time, for an area of 8 × 8 cells. The fastest model was successfully applied to a case study involving an area of 30 × 30 cells. The case study demonstrates the practical use of linear IPs for spatial decision support issues.     

Assessing Activity Pattern Similarity with Multidimensional Sequence Alignment Based on a Multiobjective Optimization Evolutionary Algorithm

Due to the complexity and multidimensional characteristics of human activities, assessing the similarity of human activity patterns and classifying individuals with similar patterns remains highly challenging. This article presents a new and unique methodology for evaluating the similarity among individual activity patterns. It conceptualizes multidimensional sequence alignment as a multiobjective optimization problem and solves this problem with an evolutionary algorithm (EA). The study utilizes sequence alignment to code multiple facets of human activities into multidimensional sequences and to treat similarity assessment as a multiobjective optimization problem that aims to minimize the alignment cost for all dimensions simultaneously. A multiobjective optimization evolutionary algorithm is used to generate a diverse set of optimal or near‐optimal alignment solutions. Evolutionary operators are specifically designed for this problem, and a local search method is also incorporated to improve the search ability of the algorithm. We demonstrate the effectiveness of our method by comparing it with a popular existing method called ClustalG using a set of 50 sequences. The results indicate that our method outperforms the existing method for most of our selected cases. The multiobjective EA presented in this article provides an effective approach for assessing activity pattern similarity and a foundation for identifying distinctive groups of individuals with similar activity patterns. Debido a la complejidad y el carácter multidimensional de las actividades humanas, la evaluación de la similitud de los patrones de la actividad humana y la clasificación de individuos con patrones similares sigue siendo una tarea muy difícil. Este artículo presenta una metodología novedosa y única para evaluar la similitud entre los patrones de actividad individual. Se conceptualiza el método de alineación de secuencias multidimensionales (Multidimensional Sequence Alignment‐MDSA) como un problema de optimización multiobjetivo y se resuelve mediante un algoritmo evolutivo (evolutionary algorithm‐EA). El estudio utiliza la alineación de secuencias para codificar múltiples facetas de las actividades humanas en secuencias multidimensionales y para tratar la evaluación de similitud como un problema de optimización multiobjetivo que tiene como objetivo reducir al mínimo el coste de alineación para todas las dimensiones simultáneamente . Los autores utilizan algoritmo evolutivo de optimización multiobjetivo (multiobjective optimization evolutionary algorithm‐MOEA) para generar un conjunto diverso de soluciones de alineación óptimas o casi óptimas. Los operadores evolutivos del algoritmo están diseñados específicamente para este problema, al cual se le incorpora un método de búsqueda local para mejorar su desempeño. Los autores demuestran la eficacia del método propuesto mediante su comparación al método existente ClustalG haciendo uso de un conjunto de 50 secuencias. Los resultados indican que el método propuesto supera a los métodos existentes para la mayoría de casos seleccionados. La EA multiobjetivo presentado en este artículo proporciona un método eficaz para evaluar similitudes del patrón de actividad y constituye un componente fundamental para la identificación de grupos distintivos de personas con patrones de actividad similares. 由于人类活动的复杂性和多维度特性,人类活动模式的相似性评估和基于相似模式的个体分类仍具有较高的挑战性。本文提出了一种新型的、独特的方法来评估个体活动模式的相似性。该研究利用序列比对将人类活动的多个方面编码成多维序列,并将活动模式相似性评估作为一个多目标优化问题,其目的是使所有维度的比对成本同时最低。多目标最优进化算法被用于生成一组不同的最优或接近最优的比对解决方案。为此特别设计了进化算子,并集成一种局部搜索方法提高了算法的整体搜索能力。为验证该方法的有效性,本文以50对序列作为实验,并与常用的ClustalG方法进行了对比。研究结果表明,该方法在多数选取案例中性能优于ClustalG方法。因此,本文提出的多目标进化（EA）算法为个体活动模式相似性评估提供了一种有效方法,也为具有相似活动模式个体中特定群体识别奠定了基础。     

Location Modeling Utilizing Maximum Service Distance Criteria

The location set-covering problem (LSCP) and the maximal covering location problem (MCLP) have been the subject of considerable interest. As originally defined, both problems allowed facility placement only at nodes. This paper deals with both problems for the case when facility placement is allowed anywhere on the network. Two theorems are presented that show that when facility placement is unrestricted, for either the LSCP or MCLP at least one optimal solution exists that is composed entirely of points belonging to a finite set of points called the network intersect point set (NIPS). Optimal solution approaches to the unrestricted site LSCP and MCLP problems that utilize the NIPS and previously developed solution methodologies are presented. Example solutions show that considerable improvement in the amount of coverage or the number of facilities needed to insure total coverage can be achieved by allowing facility placement along arcs of the network. In addition, extensions to the arc-covering model and the ambulance-hospital model of ReVelle, Toregas, and Falkson are developed and solved.     

The Pickup Problem: Consumers' Locational Preferences in Flow Interception

This article addresses the pickup problem , wherein patrons briefly interrupt their predetermined journeys to obtain a simple good, such as fast food or a video, and then resume their journeys. This is a problem from the class known as the flow-interception location problems. Traditional flow-interception location models (FILMs) are used to select service locations such that the intercepted flows are maximized. In these traditional models, only flow quantities are considered; these models do not consider where a pickup is made in a journey. However, in the real world, consumers often wish to obtain a product or service at or near a specific location along their trips. The pickup model (PUP) proposed here considers consumers' locational preferences, providing a much broader, more realistic approach than FILM (a special case of PUP) to problems in the private and public sectors. By considering which patrons are served where, PUP transforms the FILM into a flow-interception location-allocation model, providing a fruitful garden for further research. Geographic information systems and optimization engines are integrated to investigate the PUP model in real-world transportation systems. Reported findings demonstrate that the optimal locations identified by traditional models arise solely from network flow structure, whereas the optimal locations identified by PUP result from trade-offs between network flow structure and the importance of proximity to preferred locations. One important discovery is that PUP solutions are superior to those of traditional FILMs if consumers have locational preferences. Up-to-date, real-world transportation networks provide a realistic test-bed for this and other models of the flow-interception type.     

An Efficient Search Strategy for Site-Selection Decisions in an Expert System

This paper describes an algorithm for spatial search, which is used in an expert system for site selection. The algorithm, named ProfMat, is able to find the best site in the area of interest even when the number of possible sites is large and many decision criteria are involved. Compared to commonly used search procedures, ProfMat improves the efficiency of spatial search in two ways. First, the best site is identified through an iterative rather than a linear process of selection and evaluation of optional sites. Second, an area is searched by narrowing down the focus to increasingly smaller areas and, thus, sites are evaluated as much as possible groupwise. The ProfMat procedure is illustrated by analyzing the problem of retail site selection. A comparison with alternative search procedures shows that ProfMat considerably reduces the evaluation costs needed to find the best site. The implementation of the algorithm in an expert system shows how ProfMat can be used in combination with specialist's knowledge to solve site-selection problems. The efficiency of the procedure allows considering large sets of optional sites, so that it may improve the quality of the outcome.     

Elimination of Source A and B Errors in p-Median Location Problems

The p-median problem is a powerful tool in analyzing facility location options when the goal of the location scheme is to minimize the average distance that demand must traverse to reach its nearest facility. It may be used to determine the number of facilities to site, as well as the actual facility locations. Demand data are frequently aggregated in p-median location problems to reduce the computational complexity of the problem. Demand data aggregation, however, results in the loss of locational information. This loss may lead to suboptimal facility location configurations (optimality errors) and inaccurate measures of the resulting travel distances (cost errors). Hillsman and Rhoda (1978) have identified three error components: Source A, B, and C errors, which may result from demand data aggregation. In this article, a method to measure weighted travel distances in p-median problems which eliminates Source A and B errors is proposed. Test problem results indicate that the proposed measurement scheme yields solutions with lower optimality and cost errors than does the traditional distance measurement scheme.     

Municipal site leasehold in Sweden: A land policy instrument in Decay

Municipal site leasehold in Sweden is in need of renovation. Municipalities are troubled with securing returns on investments and increments in land values, leaseholders by unpredictability and sharply increased fees, and both are troubled by growing numbers of costly court cases. As a result, the use of site leasehold has come to a near standstill. Recent developments in the use of site leasehold in Sweden are charted, problems are highlighted, and possible solutions are discussed by way of comparison with other countries. If municipal site leasehold is to play a meaningful role in Swedish land policy, it must be reformed.     

Spatial Search for the Lowest Price

Search for low prices often requires that individuals make decisions not only about the optimal amount of search, but also about the optimal route to be taken through a set of known locations. In this paper, the fixed sample size strategy used in economic models of search is extended to account for the travel costs that are incurred as alternatives are examined. Analytical results for the optimal amount of search are given, and alternative routing algorithms for a modified version of the traveling-salesman problem are evaluated.     

Generating Alternative Land‐use Allocation for Mixed Use Areas: Multi‐Objective Optimization Approach

Current research is carried out with an intention to present an optimization approach for the urban land‐use allocation problem by generating Pareto optimum solutions considering two objectives—maximizing compatibility among adjacent space uses of a study area without compromising the area’s total land price and maximizing the price of plot of each individual owner. Considering the non‐linear characteristics of the objective functions, a multi‐objective evolutionary algorithm approach called Non‐Dominated Sorting Genetic Algorithm‐II (NSGA‐II) is applied to obtain Pareto optimal land‐use allocation subject to different set of constraints. The objective functions are tested over a case study area of Dhaka, Bangladesh. The resulting NSGA‐II model produces 24 Pareto optimal solutions of land‐use allocation, allowing tradeoff between maximizing compatibility and land price from one solution to other. This research also expresses the potential of the model to aid the policymakers and city planners of development authorities by providing alternative land‐use plans, and thereby predicting the consequences of any plan before practical application.     

Surfing for Problems: Advocacy Group Strategy in U.S. Forestry Policy

John Kingdon sets out a multiple streams approach to policymaking, whereby problems, solutions, and politics develop independently of one another. Kingdon's work suggests that advocates with pet policies may continually search the problem stream, looking for prominent issues to attach to their preferred solutions. I call this process "problem surfing." This paper provides an empirical test of problem surfing through the use of a case study of environmental advocacy. The paper examines Wilderness Society and Sierra Club advocacy for sustainable forestry practices from 1971 to 1994 through an analysis of articles in member magazines and interview data. Problem surfing is revealed to be a complex strategic process. I find evidence that advocacy groups adjust the problems they associate their solutions with over time to take advantage of salient issues. However, problem surfing appears to be influenced by more than just problem salience.     

Land Rights under Stress in Darfur: A Volatile Dynamic of the Conflict

Abstract

The aggravation of land rights over time in Darfur was a primary factor in the initiation of the conflict, and has emerged as a particularly dif?cult set of issues in the search for viable peace. While the prospect of being able to keep land acquired in course of the conflict was a primary factor in recruitment for the Janjaweed, it came on the heels of a set of changes in the environment, land use and population patterns, institutions, law and governance that produced a highly unwieldy and volatile land rights scenario. This article explores the role of land tenure in the Darfur conflict, examining the aggravation of rights, custom, and law over time, and then focusing on two of the primary war-related tenure problems currently facing Darfur — use of land rights as tools of belligerence, and the land dispossession — secondary occupation problem.     

Variable Residential Density: Optimum Traffic Density and City Size

In this paper we derive the optimal allocation of land between transportation and housing uses in an outer ring of a circular city, where the net population density is a constant, an exponent-decaying, or a power-decreasing function. We are also able to show that, under these circumstances, at no point in the optimal solution is all the land allocated to transportation use, proof that is, unlike previous work, independent of the solution of the same problem in the inner ring (Central Business District).     

A Combined Cluster and Interaction Model: The Hierarchical Assignment Problem

This article presents a new spatial modeling approach that deals with interactions between individual geographic entities. The developed model represents a generalization of the transportation problem and the classical assignment problem and is termed the hierarchical assignment problem (HAP). The HAP optimizes the spatial flow pattern between individual origin and destination locations, given that some grouping, or aggregation of individual origins and destinations is permitted to occur. The level of aggregation is user specified, and the aggregation step is endogenous to the model itself. This allows for the direct accounting of aggregation costs in pursuit of optimal problem solutions. The HAP is formulated and solved with several sample data sets using commercial optimization software. Trials illustrate how HAP solutions respond to changes in levels of aggregation, as well as reveal the diverse network designs and allocation schemes obtainable with the HAP. Connections between the HAP and the literature on the p-median problem, cluster analysis, and hub-and-spoke networks are discussed and suggestions for future research are made.     

A Model of Contiguity for Spatial Unit Allocation

We consider a problem of allocating spatial units (SUs) to particular uses to form "regions" according to specified criteria, which is here called "spatial unit allocation." Contiguity—the quality of a single region being connected—is one of the most frequently required criteria for this problem. This is also one that is difficult to model in algebraic terms for algorithmic solution. The purpose of this article is to propose a new exact formulation of contiguity that can be incorporated into any mixed integer programming model for SU allocation. The resulting model guarantees to enforce contiguity regardless of other included criteria such as compactness. Computational results suggest that problems involving a single region and fewer than about 200 SUs are optimally solved in fairly reasonable time, but that larger problems must rely on heuristics for approximate solutions. It is also found that a problem of any size can be formulated in a more tractable form when a fixed number of SUs are to be selected or when a certain SU is selected in advance.     

Two New Location Covering Problems: The Partial P-Center Problem and the Partial Set Covering Problem

Two new covering problems are introduced. The partial covering P-center problem minimizes a coverage distance in such a way that a given fraction of the population is covered. The partial set covering problem seeks the minimum number of facilities needed to cover an exogenously specified fraction of the population within a given coverage distance. The problems are formulated as integer linear programming problems. Bisection search algorithms are outlined for the two problems. The search algorithm repeatedly solves a Lagrangian relaxation of the maximal covering problem. Computational results for the Lagrangian relaxation of the maximal covering problem and for the bisection search algorithms are presented on problems with up to 150 nodes.     

CENTER POINTS, EQUILIBRIUM POSITIONS, AND THE OBNOXIOUS LOCATION PROBLEM

ABSTRACT. Real variable analysis has een used to great benefit in a variety of classical problems in location theory. In this paper we explore basic complex variable techniques in one formulation of the obnoxious location problem. A general definition of center points is first given and used to formulate several alternate versions of the obnoxious location problem. A logarithmic transformation is then used to demonstrate some equivalences between these families of distinct location problems (defined via center points). A prototype logarithmic potential function which results from this formulation is then investigated, and it is demonstrated that the extremal solutions with this objective reside on the boundary of its domain of definition. An application using zero- and one-dimensional centers is discussed, and a generalization to the spatial obnoxious problem is also briefly examined. We define a zero-dimensional center as a critical point of the logarithmic potential function, and it is shown that these centers are equivalent to the solutions of the Complex Moment Problem.     

Two New Location Covering Problems: The Partial P-Center Problem and the Partial Set Covering Problem

Two new covering problems are introduced. The partial covering P-center problem minimizes a coverage distance in such a way that a given fraction of the population is covered. The partial set covering problem seeks the minimum number of facilities needed to cover an exogenously specified fraction of the population within a given coverage distance. The problems are formulated as integer linear programming problems. Bisection search algorithms are outlined for the two problems. The search algorithm repeatedly solves a Lagrangian relaxation of the maximal covering problem. Computational results for the Lagrangian relaxation of the maximal covering problem and for the bisection search algorithms are presented on problems with up to 150 nodes.