A Family of Location Models for Multiple-Type Discrete Dispersion

One of the defining objectives in location science is to maximize dispersion. Facilities can be dispersed for a wide variety of purposes, including attempts to optimize competitive market advantage, disperse negative impacts, and optimize security. With one exception, all of the extant dispersion models consider only one type of facility, and ignore problems where multiple types of facilities must be located. We provide examples where multiple-type dispersion is appropriate and based on this develop a general class of facility location problems that optimize multiple-type dispersion. This family of models expands on the previously formulated definitions of dispersion for single types of facilities, by allowing the interactions among different types of facilities to determine the extent to which they will be spatially dispersed. We provide a set of integer-linear programming formulations for the principal models of this class and suggest a methodology for intelligent constraint elimination. We also present results of solving a range of multiple-type dispersion problems optimally and demonstrate that only the smallest versions of such problems can be solved in a reasonable amount of computer time using general-purpose optimization software. We conclude that the family of multiple-type dispersion models provides a more comprehensive, flexible, and realistic framework for locating facilities where weighted distances should be maximized, when compared with the special case of locating only a single type of facility.     

The Multi‐level Location Set Covering Model

The classical Location Set Covering Problem involves finding the smallest number of facilities and their locations so that each demand is covered by at least one facility. It was first introduced by Toregas in 1970. This problem can represent several different application settings including the location of emergency services and the selection of conservation sites. The Location Set Covering Problem can be formulated as a 0–1 integer‐programming model. Roth (1969) and Toregas and ReVelle (1973) developed reduction approaches that can systematically eliminate redundant columns and rows as well as identify essential sites. Such approaches can often reduce a problem to a size that is considerably smaller and easily solved by linear programming using branch and bound. Extensions to the Location Set Covering Model have been proposed so that additional levels of coverage are either encouraged or required. This paper focuses on one of the extended model forms called the Multi‐level Location Set Covering Model. The reduction rules of Roth and of Toregas and ReVelle violate properties found in the multi‐level model. This paper proposes a new set of reduction rules that can be used for the multi‐level model as well as the classic single‐level model. A demonstration of these new reduction rules is presented which indicates that such problems may be subject to significant reductions in both the numbers of demands as well as sites.     

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.     

On the Finite Optimality Set of the Vector Assignment p‐Median Problem

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.     

Multi‐Domain User‐Generated Content Based Model to Enrich Road Network Data for Multi‐Criteria Route Planning

By utilizing today's web‐based technologies, people can act as sensors and share their perceptions, emotions and observations in a variety of data forms, such as images, videos, texts, Global Positioning System (GPS) trajectories and maps. These forms are collectively called user‐generated content (UGC). These data are in different domains and have a multi‐modality nature. Although recent efforts have probed the acquisition of local knowledge by using single‐domain UGC data in specific applications, such efforts have not thus far presented a model considering multi‐domain UGC specifically to enrich road network data. This article aims at presenting such a model wherein, with the help of each data domain of UGC, one aspect of people knowledge about the road segment is obtained. These different aspects of knowledge are integrated using a Skyline operator to support multi‐criteria route finding. We name this model ERSBU (enriching road segments based on UGC). In ERSBU, road segments are basic spatial units, and their subjective properties have been extracted by using available UGC. The scenic score for each road segment was computed by using geo‐tagged Panoramio photos. The accessibility level of each road segment to different facilities was calculated based on data captured from Wikimapia and OpenStreetMap. Moreover, for measuring the movement popularity of each road segment, Wikiloc and Everytrail GPS trajectories were utilized. For the implementation of the ERSBU model, Tehran region 6 was considered the case study area. The Evaluation of the results proved that road segments that achieved a high score based on knowledge extracted from UGC also mostly gained top scores by analyzing traditional maps. ERSBU allows users to accomplish more‐qualitative path finding by considering the multi‐view characteristics of road segments.     

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.     

Programming Models for Facility Dispersion: The p-Dispersion and Maxisum Dispersion Problems

The p-dispersion problem is to locate p facilities on a network so that the minimum separation distance between any pair of open facilities is maximized. This problem is applicable to facilities that pose a threat to each other and to systems of retail or service franchises. In both of these applications, facilities should be as far away from the closest other facility as possible. A mixed-integer program is formulated that relies on reversing the value of the 0–1 location variables in the distance constraints so that only the distance between pairs of open facilities constrain the maximization. A related problem, the maxisum dispersion problem, which aims to maximize the average separation distance between open facilities, is also formulated and solved. Computational results for both models for locating 5 and 10 facilities on a network of 25 nodes are presented, along with a multicriteria approach combining the dispersion and maxisum problems. The p -dispersion problem has a weak duality relationship with the (p-1)-center problem in that one-half the maximin distance in the p-dispersion problem is a lower bound for the minimax distance in the center problem for (p-1) facilities. Since the p-center problem is often solved via a series of set-covering problems, the p-dispersion problem may prove useful for finding a starting distance for the series of covering problems.     

On Covering Problems and the Central Facilities Location Problem

A number of variations of facilities location problems have appeared in the research literature in the past decade. Among these are problems involving the location of multiple new facilities in a discrete solution space, with the new facilities located relative to a set of existing facilities having known locations. In this paper a number of discrete solution space location problems are treated. Specifically, the covering problem and the central facilities location problem are shown to be related. The covering problem involves the location of the minimum number of new facilities among a finite number of sites such that all existing facilities (customers) are covered by at least one new facility. The central facilities location problem consists of the location of a given number of new facilities among a finite number of sites such that the sum of the weighted distances between existing facilities and new facilities is minimized. Computational experience in using the same heuristic solution procedure to solve both problems is provided and compared with other existing solution procedures.     

Multiple Facilities Location in the Plane Using the Gravity Model

Two problems are considered in this article. Both problems seek the location of p facilities. The first problem is the p median where the total distance traveled by customers is minimized. The second problem focuses on equalizing demand across facilities by minimizing the variance of total demand attracted to each facility. These models are unique in that the gravity rule is used for the allocation of demand among facilities rather than assuming that each customer selects the closest facility. In addition, we also consider a multiobjective approach, which combines the two objectives. We propose heuristic solution procedures for the problem in the plane. Extensive computational results are presented.     

Accuracy of Count Data Estimated by the Point‐in‐Polygon Method

This paper analyzes the accuracy of count data estimated by the point‐in‐polygon method. A point‐in‐polygon interpolation model is proposed, based on a stochastic distribution of points and the target zone, in order to represent a variety of situations. The accuracy of estimates is numerically investigated in relation to the size of the target zone and the distribution of points, and the optimal location of representative points is discussed. The major findings of this paper are as follows: (1) though the relative accuracy of estimates generally increases monotonously with the size of the target zone, the monotoneity is often disturbed by the periodicity in the spatial configuration of source zones and the point distribution; (2) the point‐in‐polygon and the areal weighting interpolation methods have the same accuracy of estimates when points are concentrated in less than 12–15 percent area around the representative point in source zones; (3) the point‐in‐polygon method is not so robust against the locational gap between points and the representative point; (4) the optimal location of representative points is given by the spatial median of points.     

Geographic information system‐based evaluation of spatial accessibility to maternal health facilities in Siaya County,Kenya

Maternal mortality is a major problem in middle‐income and low‐income countries, and the availability and accessibility of healthcare facilities offering safe delivery is important in averting maternal deaths. Siaya County, in Kenya, has one of the highest maternal mortality rates in the country—far more than the national average. This study aimed to evaluate geographic access to health facilities offering delivery services in Siaya County. A mixed‐methods approach incorporating geographic information system analysis and individual data from semi‐structured interviews was used to derive travel time maps to facilities using different travel scenarios: AccessMod5 and ArcGIS were used for these tasks. The derived maps were then linked to georeferenced household survey data in a multilevel logistic regression model in R to predict the probability of expectant women delivering in a health facility. Based on the derived travel times, 26 per cent (13,140) and 67 per cent (32,074) of the estimated 46,332 pregnant women could reach any facility within one and two hours, respectively, while walking with the percentage falling to seven per cent (3,415) and 20 per cent (8,845) when considering referral facilities. Motorised transport significantly increased coverage. The findings revealed that the predicted probability of a pregnant woman delivering in a health facility ranged between 0.14 and 0.86. Significant differences existed in access levels with transportation‐based interventions significantly increasing coverage. The derived maps can help health policy planners identify underserved areas and monitor future reductions in inequalities. This work has theoretical implications for conceptualising healthcare accessibility besides advancing the literature on mixed methodologies.     

Multi‐scalar Labour Agency in Global Production Networks: Contestation and Crisis in the South African Fruit Sector

Integration into global production networks poses significant challenges, and also opens up opportunities, for labour agency. Governance by lead firms affects working conditions and can drive precarious employment; this interacts with and can constrain national labour legislation covering labour rights. The global production networks (GPN) approach facilitates examination of commercial value chains, their interaction with institutionally and societally embedded labour markets, and potential leverage points for labour contestation transcending local, national and global scales. This informs analysis of commercial/societal articulations as contested processes opening space for multi‐scalar labour agency within global production networks. This article examines how tensions between global commercial and societally embedded dimensions of global production networks drive precarious work, and seeks to understand the implications for emergent forms of multi‐scalar community‐based labour agency. These questions are explored through an examination of labour casualization and contestation in South African fruit production in 2012–13, using the GPN approach. The authors find that multi‐scalar channels of labour agency leveraging both global commercial and government actors can enable reworking by unorganized community‐based labour to bargain for better pay and conditions, but if the underlying global commercial logic is to be challenged, more systemic strategies are required.     

Nonparametric Significance Test for Discovery of Network‐Constrained Spatial Co‐Location Patterns

Spatial co‐location patterns are useful for understanding positive spatial interactions among different geographical phenomena. Existing methods for detecting spatial co‐location patterns are mostly developed based on planar space assumption; however, geographical phenomena related to human activities are strongly constrained by road networks. Although these methods can be simply modified to consider the constraints of networks by using the network distance or network partitioning scheme, user‐specified parameters or priori assumptions for determining prevalent co‐location patterns are still subjective. As a result, some co‐location patterns may be wrongly reported or omitted. Therefore, a nonparametric significance test without priori assumptions about the distributions of the spatial features is proposed in this article. Both point‐dependent and location‐dependent network‐constrained summary statistics are first utilized to model the distribution characteristics of the spatial features. Then, by using these summary statistics, a network‐constrained pattern reconstruction method is developed to construct the null model of the test, and the prevalence degree of co‐location patterns is modeled as the significance level. The significance test is evaluated using the facility points‐of‐interest data sets. Experiments and comparisons show that the significance test can effectively detect network‐constrained spatial co‐location patterns with less priori knowledge and outperforms two state‐of‐the‐art methods in excluding spurious patterns.     

SPACE–TIME MEASURES OF DEMAND FOR SERVICE: BRIDGING LOCATION MODELLING AND ACCESSIBILITY STUDIES THROUGH A TIME‐GEOGRAPHIC FRAMEWORK

Demand for service in location modelling is often evaluated based on the spatial proximity of fixed and static reference locations of demand (e.g. home) to a facility, which ignores person‐specific activity–travel patterns and the temporal changes in demand for service throughout the day. To address these limitations, this study draws upon recent developments in space–time measures of individual accessibility to explore the spatial and temporal structures of demand by considering individuals' space–time constraints and impact of existing urban structures. Based on a time‐geographic framework, eight space–time demand measures were developed and compared with three conventional location‐based demand measures for 12 hospitals through an empirical study conducted in Columbus, Ohio. The results show that geographic proximity between clients' home and facilities may not be an effective indicator for service demand, and conventional demand measures tend to underestimate potential demand for service in most situations. The study concludes that space–time demand measures that take into account people's activity‐travel patterns in space–time would lead to better estimation of demand for service in most cases.     

Facility Location Under Zone Pricing

Zone pricing consists in determining simultaneously several delivered prices together with the zones where these prices apply. A model and algorithm are proposed to determine optimal facility locations, prices, tariff-zones, and market areas in order to maximize the firm's profit under zone pricing. The resulting nonlinear mixed-integer program is tackled by projecting the objective function on the price space, solving repeatedly uncapacitated facility location problems for fixed values of the prices. The implicit profit function so defined is optimized by branch-and-bound. Computational results are reported.     

A Multi‐disciplinary Approach to the Archaeological Investigation of a Bedrock‐Dominated Shallow‐Marine Landscape: an example from the Bay of Firth,Orkney, UK

Investigation of shallow‐marine environments for submerged prehistoric archaeology can be hampered in many localities by extensive bedrock exposure and thus limited preservation potential. Using the concept of ‘seamless archaeology’ where land‐based archaeology is integrated across the intertidal zone through to the offshore, a multi‐disciplinary approach is essential. This approach taken in the Bay of Firth, Orkney uses geophysics, historical archive and ethno‐archaeology, coastal geomorphology, palaeo‐environmental analyses and sea‐level science, and allows a clearer understanding of the landscape in which prehistoric settlers lived. While acknowledging the limitations of the preserved environment, we are successful in identifying areas of archaeological potential on the sea‐bed for both upstanding structural elements as well as sediment preservation that contains evidence for human occupation. This has wider implications beyond Orkney's World Heritage sites to provide a blueprint for similar studies elsewhere in the coastal zone. © 2012 The Authors     

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.     

A Unified Model for Dispersing Facilities

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种传统类型的广义形式。本文进而提出了一个统一模型,即所有 “局部和整体”模型和经典类型结构一种广义形式。最后,对统一模型进行了计算检验,并基于几个实证进行了总结,还提出了未来的研究建议。     

Adaptive Cell Tower Location Using Geostatistics. 基于地统计学的适应性基站发射塔选址研究

In this article, we address the problem of allocating an additional cell tower (or a set of towers) to an existing cellular network, maximizing the call completion probability. Our approach is derived from the adaptive spatial sampling problem using kriging, capitalizing on spatial correlation between cell phone signal strength data points and accounting for terrain morphology. Cell phone demand is reflected by population counts in the form of weights. The objective function, which is the weighted call completion probability, is highly nonlinear and complex (nondifferentiable and discontinuous). Sequential and simultaneous discrete optimization techniques are presented, and heuristics such as simulated annealing and Nelder–Mead are suggested to solve our problem. The adaptive spatial sampling problem is defined and related to the additional facility location problem. The approach is illustrated using data on cell phone call completion probability in a rural region of Erie County in western New York, and accounts for terrain variation using a line‐of‐sight approach. Finally, the computational results of sequential and simultaneous approaches are compared. Our model is also applicable to other facility location problems that aim to minimize the uncertainty associated with a customer visiting a new facility that has been added to an existing set of facilities.     

Theoretical and Computational Links between the p-Median,Location Set-covering,and the Maximal Covering Location Problem

It has been shown that the p-median problem, the location set-covering and the maximal covering location problems are important facility location models. This paper gives a historical perspective of the development of these models and identifies the theoretical links between them. It is shown that the maximal covering location problem can be structured and solved as a p-median problem in addition to the several approaches already developed. Computational experience for several maximal covering location problems is given.