Area coverage maximization in service facility siting

Traditionally, models for siting facilities in order to optimize coverage of area demand have made use of discrete space representations to efficiently handle both candidate facility locations and demand. These discretizations of space are often necessary given the linear functional forms of many siting models and the complexities associated with evaluating continuous space. Recently, several spatial optimization approaches have been proposed to address the more general problem of identifying facility sites that maximize regional coverage for the case where candidate sites and demand are continuously distributed across space. One assumption of existing approaches is that only demand falling within a prescribed radius of the facility can be effectively served. In many practical applications, however, service areas are not necessarily circular, as terrain, transportation, and service characteristics of the facility often result in irregular shapes. This paper develops a generalized service coverage approach, allowing a sited facility to have any continuous service area shape, not simply a circle. Given that demand and facility sites are assumed to be continuous throughout a region, geometrical properties of the demand region and the service facility coverage area are exploited to identify a facility site to optimize the correspondence between the two areas. In particular, we consider the case where demand is uniformly distributed and the service area is translated to maximize coverage. A heuristic approach is proposed for efficient model solution. Application results are presented for siting a facility given differently shaped service areas.

Using GIS and K = 3 Central Place Lattices for Efficient Solutions to the Location Set‐Covering Problem in a Bounded Plane

One of the simplest location models in terms of its constraint structure in location‐allocation modeling is the location set‐covering problem (LSCP). Although there have been a variety of geographic applications of the set‐covering problem (SCP), the use of the SCP as a facility location model is one of the most common. In the early applications of the LSCP, both potential facility sites as well as demand were represented by points discretely located in geographic space. The advent of geographic information systems (GIS), however, has made possible a greater range of object representations that can reduce representation error. The purpose of this article is to outline a methodology using GIS and K = 3 central place lattices to solve the LSCP when demand is continuously distributed over a bounded area and potential facility sites have not been defined a priori. Although, demand is assumed to exist over an area, it is shown how area coverage can be accomplished by the coverage of a point pattern. Potential facility site distributions based on spacings that are powers of one‐third the coverage distance are also shown to provide more efficient coverage than arbitrarily chosen spacings. Using GIS to make interactive adjustments to an incomplete coverage also provides an efficient alternative to smaller spacings between potential facility sites for reducing the number of facilities necessary for complete coverage.     

Assessing representation error in point-based coverage modeling

 Accurately representing geographic space in a digital environment continues to confound and challenge researchers. Carrying out spatial analysis in a setting where geographic representation is subject to change poses problems to be addressed. In this paper we examine spatial representation in the context of coverage-based location modeling. A geographic region can be represented in a variety of ways. We present an evaluation of spatial representation in the location of facilities that provide coverage oriented services. The analysis shows that the modeling results are sensitive to how spatial demand for service is represented in a digital environment. We develop an approach for evaluating representational appropriateness. This research contributes to spatial analysis integrated in geographic information system environment. Received: 10 January 2001 / Accepted: 8 April 2002     

Obstacle‐limited service coverage: A new geospatial approach

Service coverage is a crucial component of spatial decision‐making involving facility siting. Determining coverage requires knowledge about travel behavior and accessibility across a region, as well as supporting methods of measurement and derivation when actual travel cannot necessarily be observed. When service is provided using vehicles that move freely without the restriction posed by roads (e.g., airplanes, helicopters, unmanned aerial vehicles/drones, boats, ships, and submarines), straight‐line travel is regularly assumed. However, this common assumption is often violated by geographical obstructions, resulting in overestimated service coverage. To date, no methods have been developed capable of accounting for obstacle‐limited service coverage. Existing methods either completely ignore obstructions or crudely estimate impacts on travel. In this research, we develop a novel method, ESP‐Cover, capable of deriving accurate obstacle‐limited coverage without introducing representation errors. A location siting problem involving drone‐based package delivery is presented to highlight the necessity of explicitly accounting for obstacles in system design. The assessment results demonstrate the importance of accurate derivation of the obstacle‐limited coverage for spatial decision‐making and the accuracy of the ESP‐Cover method in coverage derivation.     

A Clustering‐Based Approach to the Capacitated Facility Location Problem1

This research develops a clustering‐based location‐allocation method to the Capacitated Facility Location Problem (CFLP), which provides an approximate optimal solution to determine the location and coverage of a set of facilities to serve the demands of a large number of locations. The allocation is constrained by facility capacities – different facilities may have different capacities and the overall capacity may be inadequate to satisfy the total demands. This research transforms this special location‐allocation problem into a clustering model. The proposed approach has two parts: (1) the allocation of demands to facilities considering capacity constraints while minimizing the cost; and (2) the iterative optimization of facility locations using an adapted K‐means clustering method. The quality of a location‐allocation solution is measured using an objective function, which is the demand‐weighted distance from demand locations to their assigned facilities. The clustering‐based method is evaluated against an adapted Genetic Algorithm (GA) alternative, which integrates the allocation component as described above but uses GA operations to search for ‘optimal’ facility locations. Experiments and evaluations are carried out with various data sets (including both synthetic and real data).     

Open-source approaches for location cover models: capabilities and efficiency

Journal of Geographical Systems - Location cover models are aimed at siting facilities so as to provide service to demand efficiently. These models are crucial in the management, planning and...     

基于时空影响因子的未来社区生活圈公共服务设施优化配置北大核心CSCD

公共服务设施作为社区生活圈的核心内容,直接决定了社区生活圈的生活品质。对社区公共服务设施建设情况进行量化评价,并对设施建设的未来规划提供科学决策支持逐渐成为规划者和决策者的一大难题。本文通过ArcGIS工具对POI数据进行处理、统计和可视化,在总结他人社区生活圈量化评价方法的基础上,结合温州本地特色,搭建了一套社区生活圈公共服务设施评价模型。利用该模型可对各类社区进行综合评分和分级,并根据模型评分结果挖掘公共服务设施未来优化方向。此外,还实现了社区生活圈评分的动态计算与展示,为社区服务设施建设选址、路网建设与公共服务设施建设优先级评定等提供决策支持。既可帮助规划者和决策者快速建立对整个区域生活圈建设现状的量化认知,又可助力公共服务设施的优化配置,为社区生活圈公共服务品质评价与提升探寻全新的思路与方法。     

基于网络Voronoi图启发式和群智能的最大覆盖空间优化

提出一种基于网络Voronoi面域图的最大覆盖选址模型及相应的粒子群优化方法,并应用于城市响应时间敏感型公共服务设施的空间优化。本文考虑设施功能沿交通网络辐射以及需求非均匀分布情形,对设施在网络连续空间上进行布局优化,选址模型采用网络Voronoi面域图划分布局设施的功能辐射域,以启发空间优化最小化重叠覆盖。模型同时顾及了设施利用率的最大化,规定设施对给定距离以内的需求实行的完全服务覆盖和对给定距离以外的需求实行随距离衰减的部分服务覆盖。本研究提出基于遗传机制和广义Voronoi图改进的粒子群算法以提高其空间优化性能,通过对南京市消防站最大覆盖空间优化实验表明,该研究取得了较为理想的结果,可应用于城市化区域应急设施最大覆盖空间优化。     

Accessibility tradeoffs in public transit planning

 Spatial accessibility is a critical consideration in the provision of services, both public and private. In public transit planning, accessibility is comprised of access and geographic coverage. Interestingly, these two considerations are somewhat at odds with each other. Access is important because it is the process associated with getting to and departing from the service. Such access is typically perceived of in spatial terms as the physical proximity to transit stops or stations. Additional stops along a route usually mean greater access, because a stop is more likely to be within an acceptable walking/driving standard for a larger number of people. On the other hand, more stops and greater access slow transit travel speeds, thereby decreasing the area of service reachable given a travel time budget. More stops along a route translate to greater service interruption and longer travel times. The faster the travel time, the more desirable the service. Further, if travel times become excessive, then user demand for service will decrease. All of this means that stop spacing along a route is central to accessibility, as it is a tradeoff of access (more stops) and geographic coverage (service efficiency through less stops). This paper details modeling approaches for addressing accessibility concerns in an integrated fashion. Bus-based transit service in Columbus, Ohio will be utilized to illustrate the usefulness of these approaches in transit planning. Received: September 2002 / Accepted: January 2003 This research was supported in part by an Ohio State University seed grant.     

Joint distribution of distances to the first and the second nearest facilities

This paper derives the joint distribution of the distances to the first and the second nearest points for regular and random patterns. Distance is measured as the Euclidean and the rectilinear distances on a continuous plane. The joint distribution extends the kth nearest distance distribution of previous works. The kth nearest distance distribution only shows how the distance to the kth nearest point is distributed, whereas the joint distribution provides the relationship between the distances. An application of the joint distribution can be found in a facility location problem with non-closest facility service where the distance to the second nearest facility is also important. The joint distribution that allows us to examine the first and the second nearest distances simultaneously is useful for evaluating the reliability of facility location when some of the existing facilities are closed. The joint distribution of the road network distances is also obtained to confirm that the model on a continuous plane can be applied to actual road networks.     

Spatial analysis of public health facilities in Riyadh Governorate,Saudi Arabia: a GIS-based study to assess geographic variations of service provision and accessibility

Much attention has been given to address public health policy in Saudi Arabia, particularly for the management, quality, and coverage issues. However, assessment of spatial patterns, distribution, and provision of public health services has been neglected. This paper analyzes the availability and accessibility of public health facilities across Riyadh Governorate, Saudi Arabia at the subnational level. Spatial and attribute data of public health facilities potentially have been analyzed using GIS to produce accurate measure of accessibility. The spatial pattern of service distribution was examined using average nearest neighbor. Distances from demand points (populations) to providers (facilities) were calculated for each district using near analysis. In addition, the ratios of public health facility to population were calculated to identify underserved and overserved areas. The findings clearly indicate that the spatial pattern of the distribution of public health facilities was significantly clustered (p value < 0.001) with Z-score of ?10.9. Several districts within the central parts of the governorate were identified as having a higher density of facilities, while most of districts that are located in the marginal parts exhibit very low density of health facilities. Overall, there was a considerable variation in the average distance from district centroids to health facilities. Substantially, less than half of the population (45.4%) living in 61 districts has access to public health facility within less than 1-km distance. In contrast, the greatest increase in distances was observed for 6% of population living in 38 districts. People that live in such districts need to travel long distances for public health care. The output of this analysis can assist policy-makers and authorities of Riyadh Governorate in planning public health delivery.     

A bounding-based solution approach for the continuous arc covering problem

Road segments, telecommunication wiring, water and sewer pipelines, canals and the like are important features of the urban environment. They are often conceived of and represented as network-based arcs. As a result of the usefulness and significance of arc-based features, there is a need to site facilities along arcs to serve demand. Examples of such facilities include surveillance equipment, cellular towers, refueling centers and emergency response stations, with the intent of being economically efficient as well as providing good service along the arcs. While this amounts to a continuous location problem by nature, various discretizations are generally relied upon to solve such problems. The result is potential for representation errors that negatively impact analysis and decision making. This paper develops a solution approach for the continuous arc covering problem that theoretically eliminates representation errors. The developed approach is applied to optimally place acoustic sensors and cellular base stations along a road network. The results demonstrate the effectiveness of this approach for ameliorating any error and uncertainty in the modeling process.     

Challenges in applying capacitated covering models

Service system planning has long been supported by location‐covering models designed to address access and accessibility issues. An important aspect of many systems is limits on service, often conceptualized as facility capacities. Much research can be found that proposes modeling approaches and solution techniques to account for capacitated covering problems, and commercial GIS software exists that is capable of structuring and applying facility service limits. This article reviews issues and challenges associated with the application of capacitated covering models, including critical evaluation of allocation approaches and GIS capabilities. Case studies involving service provision in two cities in California—San Jose and Santa Barbara—are provided to highlight associated issues faced in practice. While user‐friendly commercial software makes it easy to access capacitated cover models, there remain challenges for addressing underlying considerations and assumptions in practice.     

Integrating the maximum capture problem into a GIS framework

This paper presents a methodology for reformulating the maximal capture problem by using the data representation and manipulation capabilities of GIS to define: (1) the coverage region captured by each potential facility, and (2) each unique demand region covered by a specific combination of potential facilities. The formulation is modeled on the maximum covering problem although the integer restriction on the demand capture variables is relaxed. Because demand regions are not exogenously given, areal interpolation is used to estimate the demand associated with each of these regions The model is used to determine the location on a network for a set of home improvement stores that are hypothetically in competition with existing Home Depot stores in Southeastern New Hampshire.      

A site selection framework for urban power substation at micro-scale using spatial optimization strategy and geospatial big data

The world is facing more energy crises due to extreme weather and the rapidly growing demand for electricity. Siting new substations and optimizing the location of existing ones are necessary to address the energy crisis. The current site selection lacks consideration of spatial and temporal heterogeneity in urban power demand, which results in unreasonable energy transfer and waste, leading to power outages in some areas. Aiming to maximize the grid coverage and transformer utilization, we propose a multi-scene micro-scale urban substation siting framework (UrbanPS): (1) The framework uses multi-source big data and the machine learning model to estimate fine-scale power consumption for different scenarios; (2) the region growing algorithm is used to divide the power supply area of substations; and the (3) location set coverage problem and genetic algorithm are introduced to optimize the substation location. The UrbanPS was used to perform siting optimization of 110 kV terminal substations in Pingxiang City, Jiangxi Province. Results show that the coverage and utilization rate of the optimization results under different power consumption scenarios are close to 99%. We also found that the power can be saved by dynamic regulation of substation operation.     

A spatial‐knowledge‐enhanced heuristic for solving the p‐median problem

The p‐median problem (PMP) is one of the most applied location problems in urban and regional planning. As an NP‐hard problem, the PMP remains challenging to solve optimally, especially for large‐sized problems. A number of heuristics have been developed to obtain PMP solutions in a fast manner. Among the heuristics, the Teitz and Bart (TB) algorithm has been found effective for finding high‐quality solutions. In this article, we present a spatial‐knowledge‐enhanced Teitz and Bart (STB) heuristic method for solving PMPs. The STB heuristic prioritizes candidate facility sites to be examined in the solution set based on the spatial distribution of demand and service provision. Tests based on a range of PMPs demonstrate the effectiveness of the STB heuristic. This new algorithm can be incorporated into current commercial GIS packages to solve a wide range of location‐allocation problems.     

基于GIS的北京市中心城、新城公共服务设施现状分析

公共服务设施的布局是否合理关系到居民的生活质量,关系到新城能否实现为中心城疏解人口及功能的规划目标,因此,对中心城、新城公共设施布局公平性和合理性的研究具有重要的科学和现实意义。本文基于GIS,结合人口数据、步行路网数据,分析了中心城、新城公共服务设施可覆盖人口、服务面积及存在的问题,对于优化北京市公共设施的布局具有一定的借鉴意义。     

面向公平分配的时变应急服务覆盖优化

应急服务需要根据实际情况在城市的某些区位中提前布置,才能保证需求发生时能在规定时间内到达需求位置,提供应急服务。布置区位时,需要根据时变交通条件的变化,适当考虑时空的合理分布,以为城市居民提供较为公平的服务覆盖。传统最大区位覆盖模型较少考虑服务的公平分配,特别是在时变交通和复杂大规模路网条件下,缺乏对公平量度的显式建模。基于目前区域覆盖优化模型的最近进展,扩展了传统最大区位覆盖模型,建立面向公平分配的时变应急服务覆盖模型,提出了相应的启发式高效求解方法。利用武汉市数据进行实验验证,证实模型求解得到的区位配置解较之传统模型,不仅提供了更加公平的应急服务覆盖,也考虑到了时变交通条件,改善了应急资源在时空上的均衡配置水平,整体上提高了应急服务质量。     

Hedging against service disruptions: an expected median location problem with site-dependent failure probabilities

The vector assignment p-median problem (VAPMP) (Weaver and Church in Transp Sci 19(1):58–74, 1985) was one of the first location-allocation models developed to handle split assignment of a demand to multiple facilities. The underlying construct of the VAPMP has been subsequently used in a number of reliable facility location and backup location models. Although in many applications the chance that a facility fails may vary substantially with locations, many existing models have assumed a uniform failure probability across all sites. As an improvement, this paper proposes a new model, the expected p-median problem as a generalization of existing approaches by explicitly considering site-dependent failure probabilities. Multi-level closest assignment constraints and two efficient integer linear programming (ILP) formulations are introduced. While prior research generally concludes that similar problems are not integer-friendly and cannot be solved by ILP software, computational results show that our model can be used to solve medium-sized location problems optimally using existing ILP software. Moreover, the new model can be used to formulate other reliable or expected location problems with consideration of site-dependent failure probabilities.