12 - Spatial analysis: network analysis

Concepts

• Cost function

  The cost function can be simple: for instance, it can be defined as the length of a line. The cost function can also be more elaborate and take into account not only length of the lines but also their capacity, maximum transmission (travel) rate and other line characteristics, for instance to obtain a reasonable approximation of travel time. There can even be cases in which the nodes visited add to the cost of the path as well. These may be called turning costs, which are defined in a separate turning-cost table for each node, indicating the cost of turning at the node when entering from one line and continuing on another. This is illustrated in Figure below.

  

   

• Network

  A network is a connected set of lines representing some geographic phenomenon, typically to do with transportation. The “goods” transported can be almost anything: people, cars and other vehicles along a road network, commercial goods along a logistic network, phone calls along a telephone network, or water pollution along a stream/river network.

• Network Allocation

  In network allocation, we have a number of target locations that function as resource centres, and the problem is which part of the network to exclusively assign to which service centre.

  This may sound like a simple allocation problem, in which a service centre is assigned those line (segments) to which it is nearest, but usually the problem statement is more complicated. The additional complications stem from the requirements to take into account (a)the capacity with which a centre can produce the resources (whether they are medical operations, seats for school pupils, kilowatts or bottles of milk), and (b) the consumption of the resources, which may vary amongst lines or line segments. After all, some streets have more accidents, more children who live there, more industry in high demand of electricity or just more thirsty workers.

  The service area of any centre is a subset of the distribution network, in fact a connected part of the network. Various techniques exist to assign network lines, or their segments, to a centre.

• Network Analysis

  Computations on networks comprise a different set of analytical functions in GISs. Here, the network may consist of roads, public transport routes, high-voltage power lines, or other forms of transportation infrastructure. Analysis of networks may entail shortest path computations (in terms of distance or travel time) between two points in a network for routing purposes. Other forms are to find all points reachable within a given distance or duration from a start point for allocation purposes, or determination of the capacity of the network for transportation between an indicated source location and sink location. 

  Network analysis can be performed on either raster or vector data layers, but they are more commonly done on the latter, as line features can be associated with a network and hence can be assigned typical transportation characteristics, such as capacity and cost per unit. 

• Network Partitioning

  In network partitioning, the purpose is to assign lines and/or nodes of the network in a mutually exclusive way to a number of target locations. Typically, the target locations play the role of service centres for the network. This may be any type of service, e.g. medical treatment, education, water supply. This sort of network partitioning is known as a network allocation  problem. Another problem is trace analysis. Here, one wants to determine that part of a network that is upstream (or downstream) from a given target location. Such problems exist in tracing pollution along river/stream systems, but also in tracking down network failures in energy distribution networks.

• Optimal Path Finding

  Optimal-path finding techniques are used when a least-cost path between two nodes in a network must be found. The two nodes are called origin and destination. The aim is to find a sequence of connected lines to traverse from the origin to the destination at the lowest possible cost.

• Trace analysis

  Trace analysis is performed when we want to understand which part of a network is “conditionally connected” to a chosen node on the network, which is known as the “trace origin”. If a node or line is conditionally connected, this means that a path exists from the node/line to the trace origin, and that the connecting path fulfills the conditions set. What these conditions are depends on the application; they may involve the direction of the path, its capacity, its length, or resource consumption along it. The condition is typically a logical expression, as we have seen before:

  • the path must be directed from the node/line to the trace origin;

  • its capacity (defined as the minimum capacity of the lines that constitute the path) must be above a given threshold; and

  • the path’s length must not exceed a given maximum length.

  Tracing is the computation that the GIS performs to find the paths from the trace origin that obey the tracing conditions. It is a rather useful function for many network-related problems.