Transport network analysis

Last updated

A transport network, or transportation network, is a network or graph in geographic space, describing an infrastructure that permits and constrains movement or flow. [1] 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.

Contents

History

The applicability of graph theory to geographic phenomena was recognized at an early date. 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. [2]

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. [3] The full implementation of network analysis algorithms in GIS software did not appear until the 1990s, [4] [5] but rather advanced tools are generally available today.

Network Data

Network analysis requires detailed data representing the elements of the network and its properties. [6] 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. [7]

Both the edges and nodes 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. [8] 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. [9] 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. [10]

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. [11] 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. [12]

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. [13] 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. [14]

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. [15] [16] [17]

Vertical Analysis

To ensure the railway system is as efficient as possible a complexity/vertical analysis should also be undertaken. This analysis will aid in the analysis of future and existing systems which is crucial in ensuring the sustainability of a system (Bednar, 2022, pp. 75–76). Vertical analysis will consist of knowing the operating activities (day to day operations) of the system, problem prevention, control activities, development of activities and coordination of activities. [18]

See also

Related Research Articles

<span class="mw-page-title-main">Geographic information system</span> System to capture, manage and present geographic data

A geographic information system (GIS) consists of integrated computer hardware and software that store, manage, analyze, edit, output, and visualize geographic data. Much of this often happens within a spatial database, however, this is not essential to meet the definition of a GIS. In a broader sense, one may consider such a system also to include human users and support staff, procedures and workflows, the body of knowledge of relevant concepts and methods, and institutional organizations.

Routing is the process of selecting a path for traffic in a network or between or across multiple networks. Broadly, routing is performed in many types of networks, including circuit-switched networks, such as the public switched telephone network (PSTN), and computer networks, such as the Internet.

<span class="mw-page-title-main">Minimum spanning tree</span> Least-weight tree connecting graph vertices

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph has a minimum spanning forest, which is a union of the minimum spanning trees for its connected components.

<span class="mw-page-title-main">Shortest path problem</span> Computational problem of graph theory

In graph theory, the shortest path problem is the problem of finding a path between two vertices in a graph such that the sum of the weights of its constituent edges is minimized.

<span class="mw-page-title-main">Mathematical optimization</span> Study of mathematical algorithms for optimization problems

Mathematical optimization or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfields: discrete optimization and continuous optimization. Optimization problems arise in all quantitative disciplines from computer science and engineering to operations research and economics, and the development of solution methods has been of interest in mathematics for centuries.

A* is a graph traversal and pathfinding algorithm, which is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path from source to goal.

<span class="mw-page-title-main">Graph drawing</span> Visualization of node-link graphs

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, linguistics, and bioinformatics.

<span class="mw-page-title-main">Pathfinding</span> Plotting by a computer application

Pathfinding or pathing is the plotting, by a computer application, of the shortest route between two points. It is a more practical variant on solving mazes. This field of research is based heavily on Dijkstra's algorithm for finding the shortest path on a weighted graph.

Friction of distance is a core principle of geography that states that movement incurs some form of cost, in the form of physical effort, energy, time, and/or the expenditure of other resources, and that these costs are proportional to the distance traveled. This cost is thus a resistance against movement, analogous to the effect of friction against movement in classical mechanics. The subsequent preference for minimizing distance and its cost underlies a vast array of geographic patterns from economic agglomeration to wildlife migration, as well as many of the theories and techniques of spatial analysis, such as Tobler's first law of geography, network routing, and cost distance analysis. To a large degree, friction of distance is the primary reason why geography is relevant to many aspects of the world, although its importance has been decreasing with the development of transportation and communication technologies.

<span class="mw-page-title-main">Vehicle routing problem</span> Optimization problem

The vehicle routing problem (VRP) is a combinatorial optimization and integer programming problem which asks "What is the optimal set of routes for a fleet of vehicles to traverse in order to deliver to a given set of customers?" It generalises the travelling salesman problem (TSP). It first appeared in a paper by George Dantzig and John Ramser in 1959, in which the first algorithmic approach was written and was applied to petrol deliveries. Often, the context is that of delivering goods located at a central depot to customers who have placed orders for such goods. The objective of the VRP is to minimize the total route cost. In 1964, Clarke and Wright improved on Dantzig and Ramser's approach using an effective greedy algorithm called the savings algorithm.

In business intelligence, location intelligence (LI), or spatial intelligence, is the process of deriving meaningful insight from geospatial data relationships to solve a particular problem. It involves layering multiple data sets spatially and/or chronologically, for easy reference on a map, and its applications span industries, categories and organizations.

In mathematics, a graph partition is the reduction of a graph to a smaller graph by partitioning its set of nodes into mutually exclusive groups. Edges of the original graph that cross between the groups will produce edges in the partitioned graph. If the number of resulting edges is small compared to the original graph, then the partitioned graph may be better suited for analysis and problem-solving than the original. Finding a partition that simplifies graph analysis is a hard problem, but one that has applications to scientific computing, VLSI circuit design, and task scheduling in multiprocessor computers, among others. Recently, the graph partition problem has gained importance due to its application for clustering and detection of cliques in social, pathological and biological networks. For a survey on recent trends in computational methods and applications see Buluc et al. (2013). Two common examples of graph partitioning are minimum cut and maximum cut problems.

Arc routing problems (ARP) are a category of general routing problems (GRP), which also includes node routing problems (NRP). The objective in ARPs and NRPs is to traverse the edges and nodes of a graph, respectively. The objective of arc routing problems involves minimizing the total distance and time, which often involves minimizing deadheading time, the time it takes to reach a destination. Arc routing problems can be applied to garbage collection, school bus route planning, package and newspaper delivery, deicing and snow removal with winter service vehicles that sprinkle salt on the road, mail delivery, network maintenance, street sweeping, police and security guard patrolling, and snow ploughing. Arc routings problems are NP hard, as opposed to route inspection problems that can be solved in polynomial-time.

In geographic information systems (GIS) and spatial analysis, buffer analysis is the determination of a zone around a geographic feature containing locations that are within a specified distance of that feature, the buffer zone. A buffer is likely the most commonly used tool within the proximity analysis methods.

Proximity analysis is a class of spatial analysis tools and algorithms that employ geographic distance as a central principle. Distance is fundamental to geographic inquiry and spatial analysis, due to principles such as the friction of distance, Tobler's first law of geography, and Spatial autocorrelation, which are incorporated into analytical tools. Proximity methods are thus used in a variety of applications, especially those that involve movement and interaction.

In applied mathematics, branch and price is a method of combinatorial optimization for solving integer linear programming (ILP) and mixed integer linear programming (MILP) problems with many variables. The method is a hybrid of branch and bound and column generation methods.

A geometric network is an object commonly used in geographic information systems to model a series of interconnected features. A geometric network is similar to a graph in mathematics and computer science, and can be described and analyzed using theories and concepts similar to graph theory. Geometric networks are often used to model road networks and public utility networks. Geometric networks are called in recent years very often spatial networks.

<span class="mw-page-title-main">Geospatial topology</span> Type of spatial relationship

Geospatial topology is the study and application of qualitative spatial relationships between geographic features, or between representations of such features in geographic information, such as in geographic information systems (GIS). For example, the fact that two regions overlap or that one contains the other are examples of topological relationships. It is thus the application of the mathematics of topology to GIS, and is distinct from, but complementary to the many aspects of geographic information that are based on quantitative spatial measurements through coordinate geometry. Topology appears in many aspects of geographic information science and GIS practice, including the discovery of inherent relationships through spatial query, vector overlay and map algebra; the enforcement of expected relationships as validation rules stored in geospatial data; and the use of stored topological relationships in applications such as network analysis. Spatial topology is the generalization of geospatial topology for non-geographic domains, e.g., CAD software.

In spatial analysis and geographic information systems, cost distance analysis or cost path analysis is a method for determining one or more optimal routes of travel through unconstrained (two-dimensional) space. The optimal solution is that which minimizes the total cost of the route, based on a field of cost density that varies over space due to local factors. It is thus based on the fundamental geographic principle of Friction of distance. It is an optimization problem with multiple deterministic algorithm solutions, implemented in most GIS software.

References

  1. ↑ Barthelemy, Marc (2010). "Spatial Networks". Physics Reports. 499 (1–3): 1–101. arXiv: 1010.0302 . Bibcode:2011PhR...499....1B. doi:10.1016/j.physrep.2010.11.002. S2CID   4627021.
  2. ↑ Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". Comment. Acad. Sci. U. Petrop 8, 128–40.
  3. ↑ Tinkler, K.J. (1977). "An Introduction to Graph Theoretical Methods in Geography" (PDF). CATMOG (14).
  4. ↑ Ahuja R K, Magnanti T L, Orlin J B (1993) Network flows: Theory, algorithms and applications. Prentice Hall, Englewood Cliffs, NJ, USA
  5. ↑ Daskin M S (1995) Network and discrete location — models, algorithms and applications. Wiley, NJ, USA
  6. ↑ "What is a network dataset?". ArcGIS Pro Documentation. Esri.
  7. ↑ "Network elements". ArcGIS Pro Documentation. Esri. Retrieved 17 March 2021.
  8. ↑ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.2.1 Overview - network and locational analysis". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).
  9. ↑ Worboys, Michael; Duckham, Matt (2004). "5.7 Network Representation and Algorithms". GIS: A Computing Perspective (2nd ed.). CRC Press. pp. 211–218.
  10. ↑ Dijkstra, E. W. (1959). "A note on two problems in connexion with graphs" (PDF). Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390. S2CID   123284777.
  11. ↑ "v.net.salesman command". GRASS GIS manual. OSGEO. Retrieved 17 March 2021.
  12. ↑ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.4.2 Larger p-median and p-center problems". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).
  13. ↑ deSmith, Michael J.; Goodchild, Michael F.; Longley, Paul A. (2021). "7.4.3 Service areas". Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools (6th revised ed.).
  14. ↑ "v.net.alloc command". GRASS GIS documentation. OSGEO. Retrieved 17 March 2021.
  15. ↑ Helbing, D (2001). "Traffic and related self-driven many-particle systems". Reviews of Modern Physics. 73 (4): 1067–1141. arXiv: cond-mat/0012229 . Bibcode:2001RvMP...73.1067H. doi:10.1103/RevModPhys.73.1067. S2CID   119330488.
  16. ↑ S., Kerner, Boris (2004). The Physics of Traffic : Empirical Freeway Pattern Features, Engineering Applications, and Theory. Berlin, Heidelberg: Springer Berlin Heidelberg. ISBN   9783540409861. OCLC   840291446.{{cite book}}: CS1 maint: multiple names: authors list (link)
  17. ↑ Wolf, D E; Schreckenberg, M; Bachem, A (June 1996). Traffic and Granular Flow. WORLD SCIENTIFIC. pp. 1–394. doi:10.1142/9789814531276. ISBN   9789810226350.
  18. ↑ Bednar, 2022, pp. 75–76
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.