An extension of GIS-based least-cost path modelling to the location of wide paths

The computation of least-cost paths over a cost surface is a well-known and widely used capability of raster geographic information systems (GISs). It consists in finding the path with the lowest accumulated cost between two locations in a raster model of a cost surface, which results in a string-like, thin and long sequence of cells. In this article, a new extension of raster-based least-cost path modelling is proposed. The new modelling approach allows the computation of paths or corridors with a fixed width, larger than one cell. These swaths are called wide paths and may be useful in circumstances where the detail level of the raster cost surfaces is higher than the width of the desired path or corridor. The wide path model presented in the article is independent of the choice of least-cost algorithms, because the transformation from regular to wide paths is applied to the construction of nodes and edges of an induced graph. The article gives the foundations and discusses the particularities of such paths, regardless of the imposed width, and explores the difference from the usual least-cost path model. Test cases were included, one hypothetical and the other with real data. The results are coherent and indicative of the applicability of wide paths.     

A spatial and statistical analysis of the impact of transformation of raster cost surfaces on the variation of least-cost paths

Planners who are involved in locational decision-making often use raster-based geographic information systems to quantify the value of land in terms of suitability or cost for a certain use. From a computational point of view, this process can be seen as a transformation of one or more sets of values associated with a grid of cells into another set of such values through a function reflecting one or more criteria. While it is generally anticipated that different transformations lead to different ‘best’ locations, little has been known on how such differences arise (or do not arise). The paper attempts to answer this question in the context of path planning through a series of computational experiments using a number of random landscape grids with a variety of spatial and nonspatial structures. In the experiments, we generated least-cost paths on a number of cost grids transformed from the landscape grids using a variety of transformation parameters and analyzed the locations and (weighted) lengths of those paths. Results show that the same pair of terminal cells may well be connected by different least-cost paths on different cost grids though derived from the same landscape grid and that the variation among those paths is affected by how given values are distributed in the landscape grid as well as by how derived values are distributed in the cost grids. Most significantly, the variation tends to be smaller when the landscape grid contains more distinct patches of cells potentially attracting or distracting cost-saving passage or when the cost grid contains a smaller number of low-cost cells.     

A new algorithm to find raster-based least-cost paths using cut and fill operations

We developed a least-cost path analysis algorithm that satisfies a slope threshold condition in hilly terrain. The new algorithm uses an expanding moving-window to explore a combination of cells that satisfy an elevation threshold condition and then supplements this by executing cut and fill operations when there are obstacle cells between source and destination cells. Cut and fill factors regarding the difference in the actual elevation and revised elevation are considered and a least-cost path is analyzed after calculating the accumulated travel cost to the destination point. After applying the developed algorithm to synthetic and real-world data, the least accumulated travel cost from the source point can then be calculated for all cells on the raster surface by considering various slope thresholds, moving-window sizes and raster data resolutions. This algorithm can be implemented as a useful tool in GIS software as well as engineering design software utilized in the construction and mining industries.     

A heuristic for the maximum value region problem in raster space

From a single-attribute raster layer in which each cell is assigned a numerical value, a connected set of a specified number of cells that has the maximum (or minimum) total value is selected. This is a highly common decision problem in the context of raster-based geographic information systems (GIS) and seems general enough to deserve inclusion in the standard functionality of such systems. Yet it is a computationally difficult optimization problem, for which no efficient exact solution method has been found. This article presents a new dynamic programming-based heuristic method for the problem. Its performance is tested with randomly generated raster layers with various degrees of spatial autocorrelation. Results suggest that the proposed heuristic is a promising alternative to the existing integer programming-based exact method, as it can handle significantly larger raster data with fair accuracy.     

基于栅格数据和图论算法的生态廊道识别

利用图论中最短路算法思想和ArcGIS的空间分析功能,对生境中动物迁徙廊道的识别与构建进行研究。通过对具有不同空间自相关特征的模拟景观进行分析,发现该方法具有较好的适应性,能识别出不同类型模拟景观的廊道。在模拟景观分析的基础上,将该算法应用于长沙市大河西先导区,计算了先导区重要栖息地之间的廊道。研究表明该计算方法提取的生态廊道具有明显的冗余性,充分反映了物种在不同栖息地之间迁徙的需求,具有一定的生态学意义。同时廊道提取结果在一定程度上反映了城市发展对生态系统尤其是生态廊道的胁迫与挤占。通过对廊道空间结构的分析还发现生态廊道存在一定的瓶颈区域,对该区域的生态恢复与重建将对物种多样性的保持起到关键作用。该方法为区域土地管理以及生态环境保护规划提供一定的科学依据。     

Characterization of neighborhood sensitivity of an irregular cellular automata model of urban growth

The neighborhood definition, which determines the influence on a cell from its nearby cells within a localized region, plays a critical role in the performance of a cellular automaton (CA) model. Raster CA models use a cellular grid to represent geographic space, and are sensitive to the cell size and neighborhood configuration. However, the sensitivity of vector-based CAs, an alternative to the raster-based counterpart, to neighborhood type and size remains uninvestigated. The present article reports the results of a detailed sensitivity analysis of an irregular CA model of urban land use dynamics. The model uses parcel data at the cadastral scale to represent geographic space, and was implemented to simulate urban growth in Central Texas, USA. Thirty neighborhood configurations defined by types and sizes were considered in order to examine the variability in the model outcome. Results from accuracy assessments and landscape metrics confirmed the model’s sensitivity to neighborhood configurations. Furthermore, the centroid intercepted neighborhood with a buffer of 120 m produced the most accurate simulation result. This neighborhood produced scattered development while the centroid extent-wide neighborhood resulted in a clustered development predominantly near the city center.     

Robust inferences of travel paths from GPS trajectories

Monitoring and predicting traffic conditions are of utmost importance in reacting to emergency events in time and for computing the real-time shortest travel-time path. Mobile sensors, such as GPS devices and smartphones, are useful for monitoring urban traffic due to their large coverage area and ease of deployment. Many researchers have employed such sensed data to model and predict traffic conditions. To do so, we first have to address the problem of associating GPS trajectories with the road network in a robust manner. Existing methods rely on point-by-point matching to map individual GPS points to a road segment. However, GPS data is imprecise due to noise in GPS signals. GPS coordinates can have errors of several meters and, therefore, direct mapping of individual points is error prone. Acknowledging that every GPS point is potentially noisy, we propose a radically different approach to overcome inaccuracy in GPS data. Instead of focusing on a point-by-point approach, our proposed method considers the set of relevant GPS points in a trajectory that can be mapped together to a road segment. This clustering approach gives us a macroscopic view of the GPS trajectories even under very noisy conditions. Our method clusters points based on the direction of movement as a spatial-linear cluster, ranks the possible route segments in the graph for each group, and searches for the best combination of segments as the overall path for the given set of GPS points. Through extensive experiments on both synthetic and real datasets, we demonstrate that, even with highly noisy GPS measurements, our proposed algorithm outperforms state-of-the-art methods in terms of both accuracy and computational cost.     

Refining Hernando de Soto's Route Using Electric Circuit Theory and CircuitScape

A least-cost path (LCP) analysis and a circuit theory analysis were used to estimate the path followed by Hernando de Soto as he crossed the Appalachian Mountains between Tennessee and North Carolina in 1540. The analyses were performed on the slope of the terrain and on a function of the slope that estimates hiking speed. The analyses were performed on data sets with 90-m and 180-m spatial resolutions. Three potential routes were found and compared. The most novel element of the work was the use of CircuitScape software, which returned the likelihood that each cell in the raster data was a part of de Soto's route. This clearly illuminated areas where the estimated routes were more constrained and areas where de Soto would have been free to take alternate paths without increasing travel time. The two analysis methods, LCP and circuit theory, corroborate one another and provide insight into de Soto's journey.     

Multistate supernetwork approach to modelling multi-activity,multimodal trip chains

Least-costs path finding methods belong to the standard toolkit of geographical information science and allow one to assign trips with known origin and destination to a transport network. An extension of the network representation is proposed that allows one to model complete trip chains (tours) that may involve multiple transport modes and multiple activities, as a least-cost path through the network. The extension is based on the notion that link costs may change as a consequence of activity and vehicle choices during the tour. The extended network or supernetwork contains as many copies of the network as there are possible activity–vehicle states and additional state transition links to interconnect them. In this way, not only the generalized link cost function, but also the start and end points of a path can be defined state dependently. A least-cost path through a multistate network defines an optimal sequence of travelling, transferring, parking, conducting activities and dropping off products of activities. An application shows how a multistate network can be constructed and used to assess the impacts of network design variables on path choice.     

An efficient method for single-facility location and path-connecting problems in a cell map

This article presents an efficient method for simultaneously finding both the Weber cell and optimal connective paths in a grid. As numerous barriers of arbitrary shape and weighted regions are distributed in the cell map of this research, the problem scenario is similar to working out a real-life facility location selection and path-routing problems in a geographical map. In this study, the Weber problem of finding a single-facility location from an accumulation cost table is generated by a grid wave propagation method (higher-geometry maze router). After finding the Weber point (cell), optimal connective paths with minimum total weighted cost are backtracked between the Weber location cell and the demand cells. This new computation algorithm with linear time and space complexity can be integrated as a spatial analytical function within GIS.     

A study on DEM-derived primary topographic attributes for hydrologic applications: Sensitivity to elevation data resolution

Primary topographic attributes play a critical role in determining watershed hydrologic characteristics for water resources modeling with raster-based digital elevation models (DEM). The effects of DEM resolution on a set of important topographic derivatives are examined in this study, including slope, upslope contributing area, flow length and watershed area. The focus of the study is on how sensitive each of the attributes is to the resolution uncertainty by considering the effects of overall terrain gradient and bias from resampling. Two case study watersheds of different gradient patterns are used with their 10 m USGS DEMs. A series of DEMs up to 200 m grid size are produced from the base DEMs using three commonly used resampling methods. All the terrain variables tested vary with the grid size change. It is found that slope angles decrease and contributing area values increase constantly as DEMs are aggregated progressively to coarser resolutions. No systematic trend is observed for corresponding changes of flow path and watershed area. The analysis also suggests that gradient profile of the watershed presents an important factor for the examined sensitivities to DEM resolution.     

Propagating radial waves of travel cost in a grid

To calculate the minimum cost of travel to each location within a geographical area from a specified set of locations, most geographic information systems represent that area as a rectangular grid of discrete cells, each indicating the cost of traversing that cell's particular location. These increments of cost are then accumulated by proceeding from cell to adjacent cell in a manner that resembles the propagation of waves. Because this propagation is limited to the eight directions associated with each cell's eight neighbors, however, it is often misdirected, and travel costs are therefore often overestimated. This article discusses the context, precedent, design, implementation, performance, and implications of a new algorithm that eliminates such problems in a straightforward manner. It does so by retaining the octangular propagation mechanism of earlier algorithms while keeping track of the particular locations at which propagated waves of accumulating travel cost either refract or diffract. The approach also holds promise for significant improvement in areas ranging from dispersion modeling and shape analysis to interpolation and the delineation of cost-minimizing paths.     

基于耗费场的最优路径算法研究

在GIS中,有一类应用是基于连续分布耗费场的最优路径计算问题,如公路选线等。该文首先采用规则格网对耗费场进行建模,进而基于规则格网表现,分别建立网络实现模型和元胞自动机实现模型,并探讨了基于元胞自动机模型的最优路径算法,通过实例研究,说明了算法的正确性。     

基于GIS的社会统计数据空间化处理方法

社会统计数据的空间化是当前地理科学和社会科学共同研究的热点问题之一,根据社会统计数据的特点可以将其分为和值(extensive)变量型统计数据和均值(intensive)变量型统计数据两种类型.分析了这两类社会统计数据在区域拆分与合并时的特点,并尝试将网格单元面积权重内插(GCAWI)法引入社会统计数据的空间化的工作中,提出了确定网格单元大小的原则和采用图像平滑技术改进空问化结果的方法.以徐州市人均GDP数据(均值变量型统计数据)空间化为研究实例,采用网格单元面积权重内插法实现了徐州市人均GDP数据的空间化,而且运用图像平滑技术得到了比较满意的结果.     

A strategy for raster-based geocomputation under different parallel computing platforms

The demand for parallel geocomputation based on raster data is constantly increasing with the increase of the volume of raster data for applications and the complexity of geocomputation processing. The difficulty of parallel programming and the poor portability of parallel programs between different parallel computing platforms greatly limit the development and application of parallel raster-based geocomputation algorithms. A strategy that hides the parallel details from the developer of raster-based geocomputation algorithms provides a promising way towards solving this problem. However, existing parallel raster-based libraries cannot solve the problem of the poor portability of parallel programs. This paper presents such a strategy to overcome the poor portability, along with a set of parallel raster-based geocomputation operators (PaRGO) designed and implemented under this strategy. The developed operators are compatible with three popular types of parallel computing platforms: graphics processing unit supported by compute unified device architecture, Beowulf cluster supported by message passing interface (MPI), and symmetrical multiprocessing cluster supported by MPI and open multiprocessing, which make the details of the parallel programming and the parallel hardware architecture transparent to users. By using PaRGO in a style similar to sequential program coding, geocomputation developers can quickly develop parallel raster-based geocomputation algorithms compatible with three popular parallel computing platforms. Practical applications in implementing two algorithms for digital terrain analysis show the effectiveness of PaRGO.     

一种启发式A*算法和网格划分的空间可达性计算方法

本文提出了一个适用于研究城市内部的个体或商业区位的微观可达性计算方法,该方法的核心是将研究区域进行等距的网格划分,通过计算每个网格的可达性指标,来研究整个区域的可达性的空间分布特点。在可达性计算中,利用网格内的道路密度和土地利用状态这两个因素来模拟计算每个网格的交通成本,引入了启发式A ^*空间搜索算法来计算网格间路径的交通成本,并且加入适当的启发信息,提高了搜索效率,使搜索结果更符合实际需求。最后,基于本文提出的方法,利用GIS二次开发工具ArcEngine开发了计算程序,收集了多源数据,以广州市商务区的可达性作为计算对象,进行了商务区的可达性和易达性案例计算。     

A path that buys time to decide where to go

This paper considers the problem of planning a path in a circumstance where its origin is given, but its destination is not specified and is to be selected from among a set of candidate destinations during a trip. A situation like this may be experienced by a group of people who have different preferred destinations, as well as by an individual who is simply indecisive about where to go. To resolve such an uncertainty, one may stay at the origin until he decides on a destination, or choose to proceed on some path that does not overly deviate from a shortest path, whichever destination is eventually chosen, and make a decision on the way. The latter action is sensible when the risk of traveling longer is outweighed by the benefit of buying more time for a better destination decision. The problem of finding such a time-buying path is formulated and a simple algorithm is developed for its solution. Some extensions and applications are also discussed.     

On applying viewshed analysis for determining least-cost paths on Digital Elevation Models

The concept of computing least-cost paths has been proposed and discussed for a few decades but only in simplified form due to the limited computational resources in the past. With the advancement of computer technology in speed and data storage, it is now possible to implement least-cost path algorithms with realistic conditions. In this paper, we present our implementations of least-cost paths by integrating viewshed information computed from digital elevation models. Our implementations and analyses include four possible types of paths. They are scenic paths, strategic paths, hidden paths, and withdrawn paths. While possible applications of these least-cost paths include planning of civil engineering, military and environmental planning, other extensions can be formulated without much difficulty.     

基于矢量的城市扩张多智能体模拟——以广州市番禺区为例

运用自下而上的多智能体建模方法构建城市扩张模型,研究城市扩张的基本特征和规律,对新型城镇化建设具有重要的理论和现实意义。但传统的多智能体模拟大多是基于栅格数据构建,不同的格网大小、邻域形状及邻域大小将产生不同的模拟结果。为克服传统栅格数据受模拟尺度的影响,采用城市土地利用现状图,构建矢量多智能体城市扩张动态模型。智能体依据“宜居性”评价指标,并遵从个人偏好,选择合适区位,模拟城市扩张的时空动态过程。将模型应用于广州市番禺区,模拟了其2003-2008年城市扩张情况。最后将模拟结果与实际土地利用现状图进行对比,结果表明,地块的转化精度为63.09%,非转化精度为90.74%,总精度为85.83%,具有较好的模拟精度,可以为新型城镇化建设提供有效的决策支持。     

URBAN LIVEABILITY IN CONTEXT

The Census of Canada tells us much about dwellings but little about neighborhood environment. If we want to know just how many Canadians live in homogeneous, modern, low-density suburbs, the best that many scholars can do presently is to assign each Census Tract (CT) to a category of neighborhood environment, and then add up counts of households in all CTs that fit into a specified category. However, Statistics Canada also provides summary data at a finer geographic scale: the Enumeration Area (EA). This paper explores a measure of neighborhood environment derived using a circle of fixed radius drawn around each EA centroid. Each EA centroid is at the center of its own circle but also may lie within circles drawn around other EAs. In this paper, each circle is assigned to a category of neighborhood environment on the basis of housing found in EAs whose centroids lie within the circle. Categorization of neighborhood environment is based on principal type of dwelling and period of construction found within the circle, and the homogeneity of the stock. This paper finds significant differences in neighborhood characterizations when using EA circles compared to CTs. These differences are most marked in the case of larger urban areas. The paper considers why this is the case.