Cost Distance Analysis

From wiki.gis.com
Jump to: navigation, search
This map shows the results of a spatial model to calculate the least cost path between a stand of forest being cut and the nearest sawmill.[1]
Cost distance analysis, also known as Accumulated Cost Surface Analysis, is the analysis of movement over continuous space, in which the cost of moving through any location is variable, so that some paths of movement have higher costs than others. Although the notion of cost-based proximity analysis dates back to the 1950s[2], GIS has made such studies practical.[3][4] Most GIS software consists of several algorithms and tools for performing different kinds of cost distance analysis.

Network Analysis is also based on the notion of finding routes that minimize costs, but restrict the possible routes to a preexisting network. Cost Distance Analysis, on the other hand, evaluates costs over continuous space. These tools are most useful in applications for planning new routes for constructing linear infrastructure, like roads or utilities, or for modeling movements across the landscape that do not follow established routes, such as wildlife migration.

Cost Distance

cost distance is "the notion of an alternative family of distance metrics"[1]. There are many ways to measure the distance between two points that are relevant to GIS, including Euclidean distance (an unconstrained straight line), Geodesic distance (when travel is constrained to the surface of a sphere), and network distance (when travel is constrained to a linear network). Cost distance employs the geographic principle of Friction of Distance, which states that there is a cost or impedance associated with moving a unit distance over any location, and this cost varies over space (and can thus be conceptualized as a field). For example, if the cost of a person traveling over any space is measured as the amount of energy expended, then moving over water (i.e., swimming) has a far greater cost than moving over land (i.e., walking). If one wants to minimize this energy expenditure cost, then it may be better to walk around a body of water than swim straight through it, even though the actual distance is greater.

This cost can be measured in any number of ways. Although actual financial expenses can be part of it, the notion of "cost" is typically used for any negative impact of moving over a space. Depending on the particular application, these could include:

  • Travel time
  • Travel energy expenditure (e.g., vehicle fuel usage)
  • Property acquisition costs
  • Construction costs
  • Negative impacts to the natural environment (e.g., crossing wetlands or clearing forests)
  • Negative impacts to the human environment (e.g., destroying homes or historic structures)

Conceptually, one could "measure" the cost of a path crossing any unit area of space. For example, if one is planning a paved bicycling path, a location on a steep wooded slope would likely mean high construction costs, high negative impacts to the natural environment, and higher energy costs for riders trying to bicycle up the slope. Alternatively, a vacant lot in a flat suburban neighborhood would have a low cost in these three respects, but the land may be more expensive to purchase. Because these different costs use different units of measure or are not directly measurable in any quantitative way, an Index model is often used to build a "pseudo-measure" of total cost for use in a GIS.

As with many other fields, cost is typically represented in a GIS using a raster grid known as a Cost surface, in which the value of each cell represents the total cost of traveling in any direction across the square area it covers.[5] This raster grid is typically created by implementing an Index model using Map algebra to compute total cost from separate rasters representing individual elements of cost.

Thus the "distance" between two points along a given patch is the accumulation of all relevant costs over every point on the path. In the bike path example, a path over a hill may have the same cost distance as a path going around the hill, even though the former is a straight line on a map.

Analysis Tools

Most GIS software contains a number of tools for performing various tasks that depend on cost and cost distance into account. Most of these tools require one to first create a Cost surface using other GIS tools such as Map algebra.

Cost Distance

A cost distance raster showing the accumulated cost of traveling from the source cell in the lower left to each other cell.[6]
Cost Path

The cost distance tool is similar to Euclidean distance raster tools, but instead of calculating the actual distance from a given cell to the rest of the cells, the cost distance tools determine the shortest weighted distance (or accumulated travel cost) from each cell to the nearest source location. These tools apply distance in cost units, not in geographic units. The cost distance tool requires one or more source locations and a cost raster as input.[6] Each cell of the resultant cost distance grid contains the minimal total cost to travel from the given source location(s) to that cell.

Simultaneously, this tool creates a second raster grid known as a backlink raster that encodes, for each cell, the direction to the neighboring cell with the lowest cost (i.e., where a lowest-cost path would have come from to get to this cell). Usually the value is a coded direction, such as a number between 0-7.

The basic brute-force algorithm to compute cost distance is as follows, basically spreading out from the sources to fill the entire grid:

  1. Create a list of cells to evaluate, initially consisting of the cells corresponding to the given source locations.
  2. For each cell in the list:
    1. If it is a source cell, assign it a cost of 0
    2. Otherwise, look at its 8 neighbor cells and identify the neighbor with the lowest cost.
    3. Set the value of the cell in the backlink raster with a code for the lowest-cost neighbor
    4. Add the value for this cell in the cost raster to the neighbor's cost (multiply by 1.414 for diagonal neigbors)
    5. Identify any neighbors that have a higher value than this cell or no value at all and add them to the list

This algorithm is rather inefficient, in that many cells will be added to the list, and thus re-evaluated many times. Several more efficient algorithms have since been developed.[7][8]

Cost Path Analysis

After a cost distance and backlink raster have been created, A least-cost path can then be made between the source and one or more destinations, by tracing the backlink direction codes back from the destination back to the source.

Cost-Based Allocation

Cost Allocation creates a raster grid in which each cell is coded with which source (assuming many sources are provided to the tool) can be reached with the minimum cost. Thus, the resultant allocation raster consists of regions around each source. This tool is thus analogous to the Voronoi diagram for euclidean distance, and Location-allocation tools for networks.

Corridor Analysis

Corridor Analysis is similar to Cost Path Analysis, but instead of identifying the single optimal route between two points, it is able to identify all routes that fall below a given cost threshold. This usually takes the form of wide swaths of territory between the source and destination, as opposed to a path one cell wide. This approach is most useful for applications in which a single path does not need to be chosen, only a general area of acceptable paths, such as in wildlife migration modeling.

See Also

External Links

References

  1. 1.0 1.1 de Smith, Michael J., Michael Goodchild, and Paul Longley, "Cost Distance", Geospatial Analysis, 3rd Edition. Accessed 29 December 2016.
  2. Warntz, W., 1957. Transportation, social physics and the law of refraction. The Professional Geographer, 9 (4), 2–7
  3. Tomlin, C.D., 1983. Digital cartographic modeling techniques in environmental planning. Thesis (PhD). Yale University
  4. Douglas D H (1994) Least cost path in GIS using an accumulated cost surface and slope lines. Cartographica, 31, 37-51
  5. "Least-Cost Transportation Corridor Analysis Using Raster Data".GeoMedia Grid, Keigen Systems. Accessed 08 November 2012.
  6. 6.0 6.1 Understanding Cost Distance Analysis ArcGIS 10.0 Web Help. Esri. Accessed 08 November 2012
  7. Eastman J R (1989) Pushbroom algorithms for calculating distances in raster grids. Proceedings, Autocarto 9, 288-97.
  8. Dana Tomlin (2010) [http://dx.doi.org/10.1080/13658811003779152 Propagating radial waves of travel cost in a grid], International Journal of Geographical Information Science, 24:9, 1391-1413, DOI: 10.1080/13658811003779152