Transport network analysis: Difference between revisions

Revision as of 10:28, 22 August 2021

Latest revision as of 12:37, 27 June 2024

(18 intermediate revisions by 15 users not shown)

Line 1:

{{Short description|Spatial analysis tools for geographic networks}}

{{For|transportation network mathematical graph theory|Flow network}}

{{Broader|Proximity analysis}}

{{Network Science}}

A '''transport network''', or '''transportation network''', is a [[spatial network | network or graph]] in geographic space, describing an infrastructure that permits and constrains movement or flow.<ref name="Bart">{{Cite journal|arxiv=1010.0302|last1=Barthelemy|first1=Marc|title=Spatial Networks|journal=Physics Reports|volume=499|issue=1–3|pages=1–101|year=2010|doi=10.1016/j.physrep.2010.11.002|bibcode=2011PhR...499....1B|s2cid=4627021}}</ref>

Examples include but are not limited to [[road network]]s, [[railways]], [[Airway (aviation)|air routes]], [[Pipeline transport|pipelines]], [[Navigable aqueduct|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 system]]s, [[Public utility|public utilities]], and [[transport engineering]]. Network analysis is an application of the theories and algorithms of [[Graphgraph theory]] and is a form of [[proximity analysis]].

==History==

The applicability of [[graph theory]] to geographic phenomena was recognized asat an early date. In fact, manyMany 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.<ref>Euler, Leonhard (1736). "Solutio problematis ad geometriam situs pertinentis". ''Comment. Acad. Sci. U. Petrop'' 8, 128–40.</ref>

In the 1970s, the connection was reestablished by the early developers of [[geographic information system]]s, 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.<ref>{{cite journal |last1=Tinkler |first1=K.J. |title=An Introduction to Graph Theoretical Methods in Geography |journal=CATMOG |date=1977 |issue=14 |url=https://alexsingleton.files.wordpress.com/2014/09/14-graph-theoretical-methods-in-geography.pdf}}</ref> The full implementation of network analysis algorithms in GIS software did not appear until the 1990s,<ref>Ahuja R K, Magnanti T L, Orlin J B (1993) ''Network flows: Theory, algorithms and applications''. Prentice Hall, Englewood Cliffs, NJ, USA</ref><ref>Daskin M S (1995) ''Network and discrete ___location — models, algorithms and applications''. Wiley, NJ, USA</ref> but rather advanced tools are generally available today.

==Network Datadata==

Network analysis requires detailed data representing the elements of the network and its properties.<ref>{{cite web |title=What is a network dataset? |url=https://pro.arcgis.com/en/pro-app/latest/help/analysis/networks/what-is-network-dataset-.htm |website=ArcGIS Pro Documentation |publisher=Esri}}</ref> The core of a network dataset is a [[Vector graphics|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.<ref>{{cite web |title=Network elements |url=https://pro.arcgis.com/en/pro-app/latest/help/analysis/networks/network-elements.htm |website=ArcGIS Pro Documentation |publisher=Esri |access-date=17 March 2021}}</ref>

Line 19 ⟶ 21:

* ''Flow volume'', measurements of the actual movement taking place. This may be specific time-encoded measurements collected using [[sensor network]]s such as [[traffic counter]]s, or general trends over a period of time, such as [[Annual average daily traffic]] (AADT).

==Analysis Methodsmethods==

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.<ref>{{cite book |last1=deSmith |first1=Michael J. |last2=Goodchild |first2=Michael F. |last3=Longley |first3=Paul A. |title=Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools |date=2021 |edition=6th revised |chapter=7.2.1 Overview - network and locational analysis | chapter-url=https://www.spatialanalysisonline.com/HTML/index.html?overview_-_network_analysis.htm}}</ref> 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]].

Line 27 ⟶ 29:

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.<ref name="Worboys">{{cite book |last1=Worboys |first1=Michael |last2=Duckham |first2=Matt |title=GIS: A Computing Perspective |date=2004 |publisher=CRC Press |pages=211–218 |edition=2nd|chapter=5.7 Network Representation and Algorithms}}</ref> 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]].<ref name="Dijkstra1959">{{cite journal | author-link = Edsger W. Dijkstra | first1 = E. W. | last1 = Dijkstra | s2cid = 123284777 | url= http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf | title = A note on two problems in connexion with graphs | journal = Numerische Mathematik | volume = 1 | year = 1959 | pages = 269–271 | doi = 10.1007/BF01386390}}</ref>

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.<ref>{{cite web |title=v.net.salesman command |url=https://grass.osgeo.org/grass78/manuals/v.net.salesman.html |website=GRASS GIS manual |publisher=OSGEO |access-date=17 March 2021}}</ref> 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|"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===

{{main | Facility ___location problem |(disambiguation){{!}}Facility ___location problem|Location-allocation}}

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.<ref>{{cite book |last1=deSmith |first1=Michael J. |last2=Goodchild |first2=Michael F. |last3=Longley |first3=Paul A. |title=Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools |date=2021 |edition=6th revised |chapter=7.4.2 Larger p-median and p-center problems | chapter-url=https://www.spatialanalysisonline.com/HTML/index.html?larger_p-median_and_p-center_p.htm}}</ref>

Line 37 ⟶ 39:

===Service areas===

A network service area is analogous to a [[Buffer (GIS) | 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.<ref>{{cite book |last1=deSmith |first1=Michael J. |last2=Goodchild |first2=Michael F. |last3=Longley |first3=Paul A. |title=Geospatial Analysis: A Comprehensive Guide to Principles, Techniques, and Software Tools |date=2021 |edition=6th revised |chapter=7.4.3 Service areas | chapter-url=https://www.spatialanalysisonline.com/HTML/index.html?service_areas.htm}}</ref> 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]].<ref>{{cite web |title=v.net.alloc command |url=https://grass.osgeo.org/grass78/manuals/v.net.alloc.html |website=GRASS GIS documentation |publisher=OSGEO |access-date=17 March 2021}}</ref>

===Fault analysis===

Line 44 ⟶ 46:

===Transport engineering===

{{main | Transport engineering|Traffic flow}}

Traffic has been studied extensively&nbsp;using statistical physics methods.<ref>{{Cite journal|last=Helbing|first=D|date=2001|title=Traffic and related self-driven many-particle systems|journal=Reviews of Modern Physics|volume=73|issue=4|pages=1067–1141|arxiv=cond-mat/0012229|bibcode=2001RvMP...73.1067H|doi=10.1103/RevModPhys.73.1067|s2cid=119330488}}</ref><ref>{{Cite book|title=The Physics of Traffic : Empirical Freeway Pattern Features, Engineering Applications, and Theory|last=S.|first=Kerner, Boris|date=2004|publisher=Springer Berlin Heidelberg|isbn=9783540409861|___location=Berlin, Heidelberg|oclc=840291446}}</ref><ref>{{Cite book|last1=Wolf|first1=D E|last2=Schreckenberg|first2=M|last3=Bachem|first3=A|title=Traffic and Granular Flow|date=June 1996|journal=Traffic and Granular Flow|pages=1–394|language=en-US|publisher=WORLD SCIENTIFIC|doi=10.1142/9789814531276|isbn=9789810226350}}</ref>

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.

<ref>{{Cite journal|last1=Li|first1=Daqing|last2=Fu|first2=Bowen|last3=Wang|first3=Yunpeng|last4=Lu|first4=Guangquan|last5=Berezin|first5=Yehiel|last6=Stanley|first6=H. Eugene|last7=Havlin|first7=Shlomo|date=2015-01-20|title=Percolation transition in dynamical traffic network with evolving critical bottlenecks|journal=Proceedings of the National Academy of Sciences|language=en|volume=112|issue=3|pages=669–672|doi=10.1073/pnas.1419185112|issn=0027-8424|pmid=25552558|bibcode=2015PNAS..112..669L|pmc=4311803|doi-access=free}}</ref>

Critical exponents characterizing the cluster size distribution of good traffic are similar to those of percolation theory.<ref>Switch between critical percolation modes in city traffic dynamics,

G Zeng, D Li, S Guo, L Gao, Z Gao, HE Stanley, S Havlin,

Proceedings of the National Academy of Sciences 116 (1), 23-28 (2019)

</ref> 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.<ref>{{cite journal |last1=G. Zeng, J. Gao, L. Shekhtman, S. Guo, W. Lv, J. Wu, H. Liu, O. Levy, D. Li, ... |title=Multiple metastable network states in urban traffic |journal=Proceedings of the National Academy of Sciences |date=2020 |volume=117 |issue=30 |pages=17528–17534|doi=10.1073/pnas.1907493117 |pmid=32661171 |pmc=7395445 }}</ref>

===Vertical analysis===

An empirical study regarding the size distribution of traffic jams has been performed recently by Zhang et al.<ref>Scale-free resilience of real traffic jams,

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.&nbsp;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.<ref>Bednar, 2022, pp. 75–76</ref>

Limiao Zhang, Guanwen Zeng, Daqing Li, Hai-Jun Huang, H Eugene Stanley, Shlomo Havlin,

Proceedings of the National Academy of Sciences 116(18), 8673-8678 (2019)</ref> 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.<ref>{{cite journal |last1=Nimrod Serok, Orr Levy, Shlomo Havlin, Efrat Blumenfeld-Lieberthal |title=Unveiling the inter-relations between the urban streets network and its dynamic traffic flows: Planning implication |journal=SAGE Publications |date=2019 |volume=46 |issue=7 |pages=1362}}</ref> G. Li et al.<ref>{{cite journal |last1=G. Li, S.D.S. Reis, A.A. Moreira, S. Havlin, H.E. Stanley, J.S. Andrade Jr. |title=Towards Design Principles for Optimal Transport Networks |journal=Phys. Rev. Lett. |date=2010 |volume=104 |issue=1 |pages=018701|doi=10.1103/PhysRevLett.104.018701 |pmid=20366398 |arxiv=0908.3869 |bibcode=2010PhRvL.104a8701L |s2cid=119177807 }}</ref> developed a method to design an optimal two layer transportation network in a city.

[[File:Percolation traffic networks.png|500px|center|alt=Percolation traffic networks|thumb|Fig. 1: Percolation of traffic networks in a typical day in Beijing. '''A''' Shows the high speed clusters. In '''B''' one can see the clusters at the critical threshold, where the giant component breaks. '''C''' Shows the low speed case where one can reach the whole city. In '''D''', one can see the percolation behavior of the largest (green) and second largest (orange) components as a function of relative speed. '''E''' Shows the critical threshold, q<math>c</math>, during the day for working days and weekends. High q<math>c</math> means good global traffic while low q<math>c</math> is bad traffic—during rush hour.

]]

===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.<ref>{{cite journal |last1=Y. Shida, H. Takayasu, S. Havlin, M. Takayasu |title=Universal scaling laws of collective human flow patterns in urban regions |journal=Scientific Reports |date=2020 |volume=10 |issue=1 |page=21405 |doi=10.1038/s41598-020-77163-2 |pmid=33293581 |pmc=7722863 }}</ref>

==See also==

Line 75 ⟶ 60:

*[[Street network]]

*[[Rail network]]

*[[Highway dimension]]

*[[Multimodal transport]]

*[[Supply chain]]

*[[Logistics]]

==References==

{{reflistReflist}}

{{Public transport |collapsed}}

{{Authority control}}

{{DEFAULTSORT:Transport Network}}