Transport network analysis

A transport network, or transportation network is a network or graph in geographic space, describing an infrastructure that permits and constrains movement or flow.
Examples include but are not limited to road networks, railways, air routes, pipelines, aqueducts, and power lines. The digital representation of these networks, and the methods for their analysis, is a core part of spatial analysis, geographic information systems, public utilities, and transport engineering. Network analysis is an application of the theories and algorithms of Graph theory and is a form of proximity analysis.
History.
The applicability of graph theory to geographic phenomena was recognized as an early date. In fact, many of the early problems and theories undertaken by graph theorists were inspired by geographic situations, such as the Seven Bridges of Königsberg problem, which was one of the original foundations of graph theory when it was solved by Leonhard Euler in 1736.
In the 1970s, the connection was reestablished by the early developers of geographic information systems, who employed it in the topological data structures of polygons (which is not of relevance here), and the analysis of transport networks. Early works, such as Tinkler (1977), focused mainly on simple schematic networks, likely due to the lack of significant volumes of linear data and the computational complexity of many of the algorithms. The full implementation of network analysis algorithms in GIS software did not appear until the 1990s, but rather advanced tools are generally available today.
Network Data.
Network analysis requires detailed data representing the elements of the network and its properties. The core of a network dataset is a vector layer of polylines representing the paths of travel, either precise geographic routes or schematic diagrams, known as "edges". In addition, information is needed on the network topology, representing the connections between the lines, thus enabling the transport from one line to another to be modeled. Typically, these connection points, or "nodes", are included as an additional dataset.
Both the edges and notes are attributed with properties related to the movement or flow:
Analysis Methods.
A wide range of methods, algorithms, and techniques have been developed for solving problems and tasks relating to network flow. Some of these are common to all types of transport networks, while others are specific to particular application domains. Many of these algorithms are implemented in commercial and open-source GIS software, such as GRASS GIS and the Network Analyst extension to Esri ArcGIS.
Optimal routing.
One of the simplest and most common tasks in a network is to find the optimal route connecting two points along the network, with "optimal" defined as minimizing some form of cost, such as distance, energy expenditure, or time. A common example is finding directions in a street network, a feature of almost any web street mapping application such as google maps. The most popular method of solving this task, implemented in most GIS and mapping software, is Dijkstra's algorithm.
In addition to the basic point-to-point routing, "composite routing problems" are also common. The Traveling salesman problem asks for the optimal (least distance/cost) ordering and route to reach a number of destinations; it is an NP-hard problem, but somewhat easier to solve in network space than unconstrained space due to the smaller solution set. The Vehicle routing problem is a generalization of this, allowing for multiple simultaneous routes to reach the destinations. The Route inspection or "Chinese Postman" problem asks for the optimal (least distance/cost) path that traverses every edge; a common application is the routing of garbage trucks. This turns out to be a much simpler problem to solve, with polynomial time algorithms.
Location analysis.
This class of problems aims to find the optimal location for one or more facilities along the network, with "optimal" defined as minimizing the aggregate or mean travel cost to (or from) another set of points in the network. A common example is determining the location of a warehouse to minimize shipping costs to a set of retail outlets, or the location of a retail outlet to minimize the travel time from the residences of its potential customers. In unconstrained (cartesian coordinate) space, this is an NP-hard problem requiring heuristic solutions such as Lloyd's algorithm, but in a network space it can be solved deterministically.
Particular applications often add further constraints to the problem, such as the location of pre-existing or competing facilities, facility capacities, or maximum cost.
Service areas.
A network service area is analogous to a buffer in unconstrained space, a depiction of the area that can be reached from a point (typically a service facility) in less than a specified distance or other accumulated cost. For example, the preferred service area for a fire station would be the set of street segments it can reach in a small amount of time. When there are multiple facilities, each edge would be assigned to the nearest facility, producing a result analogous to a Voronoi diagram.
Fault analysis.
A common application in public utility networks is the identification of possible locations of faults or breaks in the network (which is often buried or otherwise difficult to directly observe), deduced from reports that can be easily located, such as customer complaints.
Transport engineering.
Traffic has been studied extensively using statistical physics methods.
Recently a real transport network of Beijing was studied using a network approach and percolation theory.
The research showed that one can characterize the quality of global traffic in a city at each time in the day using percolation threshold, see Fig. 1.
In recent articles, percolation theory has been applied to study traffic congestion in a city. The quality of the global traffic in a city at a given time is by a single parameter, the percolation critical threshold. The critical threshold represents the velocity below which one can travel in a large fraction of city network. The method is able to identify repetitive traffic bottlenecks.
Critical exponents characterizing the cluster size distribution of good traffic are similar to those of percolation theory. It is also found that during rush hours the traffic network can have several metastable states of different network sizes and the alternate between these states.
An empirical study regarding the size distribution of traffic jams has been performed recently by Zhang et al. They found an approximate universal power law for the jam sizes distribution.
A method to identify functional clusters of spatial-temporal streets that represent fluent traffic flow in a city has been developed by Serok et al. G. Li et al. developed a method to design an optimal two layer transportation network in a city.
Flow patterns of traffic.
River-like patterns of traffic flow in urban areas in large cities during rush hours and non rush hours have been studied by Yohei Shida et al.