Transport network analysis

Short description: Spatial analysis tools for geographic networks

For transportation network mathematical graph theory, see Flow network.

For broader coverage of this topic, see Proximity analysis.

Network science

* Theory

* Graph
* Complex network
* Contagion
* Small-world
* Scale-free
* Community structure
* Percolation
* Evolution
* Controllability
* Graph drawing
* Social capital
* Link analysis
* Optimization
* Reciprocity
* Closure
* Homophily
* Transitivity
* Preferential attachment
* Balance theory
* Network effect
* Social influence

Network types

* Informational (computing)
* Telecommunication
* Transport
* Social
* Scientific collaboration
* Biological
* Artificial neural
* Interdependent
* Semantic
* Spatial
* Dependency
* Flow
* on-Chip

Graphs
|  Features

* Clique
* Component
* Cut
* Cycle
* Data structure
* Edge
* Loop
* Neighborhood
* Path
* Vertex
* Adjacency list / matrix
* Incidence list / matrix

Types

* Bipartite
* Complete
* Directed
* Hyper
* Multi
* Random
* Weighted

* Metrics
* Algorithms

* Centrality
* Degree
* Betweenness
* Closeness
* PageRank
* Motif
* Clustering
* Degree distribution
* Assortativity
* Distance
* Modularity
* Efficiency

Models
|  Topology

* Random graph
* Erdős–Rényi
* Barabási–Albert
* Fitness model
* Watts–Strogatz
* Exponential random (ERGM)
* Random geometric (RGG)
* Hyperbolic (HGN)
* Hierarchical
* Stochastic block
* Maximum entropy
* Soft configuration
* LFR Benchmark

Dynamics

* Boolean network
* agent based
* Epidemic/SIR

* Lists
* Categories

* Topics
* Software
* Network scientists

* Category:Network theory
* Category:Graph theory

* v
* t
* e

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

* 1 History
* 2 Network data
* 3 Analysis methods
* 3.1 Optimal routing
* 3.2 Location analysis
* 3.3 Service areas
* 3.4 Fault analysis
* 3.5 Transport engineering
* 3.6 Vertical analysis
* 4 See also
* 5 References

## 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:

* Capacity, measurements of any limitation on the volume of flow allowed, such as the number of lanes in a road, telecommunications bandwidth, or pipe diameter.
* Impedance, measurements of any resistance to flow or to the speed of flow, such as a speed limit or a forbidden turn direction at a street intersection
* Cost accumulated through individual travel along the edge or through the node, commonly elapsed time, in keeping with the principle of friction of distance. For example, a node in a street network may require a different amount of time to make a particular left turn or right turn. Such costs can vary over time, such as the pattern of travel time along an urban street depending on diurnal cycles of traffic volume.
* Flow volume, measurements of the actual movement taking place. This may be specific time-encoded measurements collected using sensor networks such as traffic counters, or general trends over a period of time, such as Annual average daily traffic (AADT).

## 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

Main articles: Shortest path problem and Dijkstra's algorithm

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

Main articles: Facility location problem and 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.[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

* Braess's paradox
* Flow network
* Heuristic routing
* Interplanetary Transport Network
* Network science
* Percolation theory
* Street network
* Rail network
* Highway dimension
* Multimodal transport
* Supply chain
* Logistics

## References

1. ↑ Barthelemy, Marc (2010). "Spatial Networks". Physics Reports 499 (1–3): 1–101. doi:10.1016/j.physrep.2010.11.002. Bibcode: 2011PhR...499....1B.
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". CATMOG (14). https://alexsingleton.files.wordpress.com/2014/09/14-graph-theoretical-methods-in-geography.pdf.
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?". Esri. https://pro.arcgis.com/en/pro-app/latest/help/analysis/networks/what-is-network-dataset-.htm.
7. ↑ "Network elements". Esri. https://pro.arcgis.com/en/pro-app/latest/help/analysis/networks/network-elements.htm.
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.). https://www.spatialanalysisonline.com/HTML/index.html?overview_-_network_analysis.htm.
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". Numerische Mathematik 1: 269–271. doi:10.1007/BF01386390. http://www-m3.ma.tum.de/twiki/pub/MN0506/WebHome/dijkstra.pdf.
11. ↑ "v.net.salesman command". OSGEO. https://grass.osgeo.org/grass78/manuals/v.net.salesman.html.
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.). https://www.spatialanalysisonline.com/HTML/index.html?larger_p-median_and_p-center_p.htm.
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.). https://www.spatialanalysisonline.com/HTML/index.html?service_areas.htm.
14. ↑ "v.net.alloc command". OSGEO. https://grass.osgeo.org/grass78/manuals/v.net.alloc.html.
15. ↑ Helbing, D (2001). "Traffic and related self-driven many-particle systems". Reviews of Modern Physics 73 (4): 1067–1141. doi:10.1103/RevModPhys.73.1067. Bibcode: 2001RvMP...73.1067H.
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.
17. ↑ Wolf, D E; Schreckenberg, M; Bachem, A (June 1996) (in en-US). Traffic and Granular Flow. WORLD SCIENTIFIC. pp. 1–394. doi:10.1142/9789814531276. ISBN 9789810226350.
18. ↑ Bednar, 2022, pp. 75–76

* v
* t
* e

Public transport

Bus service|

* Bus
* driver
* list
* Bus rapid transit
* Charabanc
* Express bus
* Guided bus
* Intercity bus
* driver
* Open top bus
* Public light bus
* Rail replacement bus
* Shuttle bus
* Transit bus
* Trolleybus

Rail|

* Cable car
* Commuter rail
* Elevated railway
* Funicular
* Heavy rail
* Heritage railway
* Heritage streetcar
* High-speed rail
* Higher-speed rail
* Horsecar
* Inter-city rail
* Interurban
* Light rail
* Maglev Train
* Medium-capacity rail system
* Monorail
* Narrow-gauge railway
* People mover
* Railbus
* Rapid transit
* Regional rail
* Rubber-tyred metro
* Street running
* Suspension railway
* Tram
* Tram-train
* Vactrain

Vehicles
for hire|

* Auto rickshaw
* Boda boda
* Combination bus
* Cycle rickshaw
* Dollar van
* Dolmuş
* Gondola
* Hackney carriage
* Jeepney
* Limousine
* Motorcycle taxi
* Marshrutka
* Nanny van
* Paratransit
* Personal rapid transit
* Pesero
* Public light bus
* Pulled rickshaw
* Share taxi
* Songthaew
* Taxicab
* Tuk tuk

Carpooling|

* Car jockey
* Flexible carpooling
* Real-time ridesharing
* Slugging
* Vanpool

Ship|

* Cable ferry
* Ferry
* Hovercraft
* Hydrofoil
* Ocean liner
* Water taxi

Other
transport|

* Aerial tramway
* Airline
* Airliner
* Carsharing
* Elevator
* Escalator
* Gondola lift
* Horse-drawn vehicle
* Hyperloop
* Micromobility
* Bicycle-sharing
* Scooter-sharing
* Moving walkway
* Trackless train

Locations|

* Airport
* Bus bulb
* Bus garage (bus depot)
* Bus lane
* Bus stand
* Bus station
* Bus stop
* Bus terminus
* Bus turnout (bus bay)
* Dry dock
* Ferry terminal
* Hangar
* Harbor
* Interchange station
* Kassel kerb
* Layover
* Metro station
* Park and ride
* Port
* Queue jump
* Taxicab stand
* Train station
* Tram stop
* Transit mall
* Transport hub

Ticketing
and fares|

* Automated fare collection
* Bus advertising
* Contract of carriage
* Dead mileage
* Exit fare
* Fare avoidance
* Fare evasion
* Farebox recovery ratio
* Free public transport
* Free travel pass
* Integrated ticketing
* Manual fare collection
* Money train
* Paid area
* Proof-of-payment
* Reduced fare program
* Smart cards
* Ticket machine
* Transfer
* Transit pass

Routing|

* Circle route
* Cross-city route
* Network length
* Non-revenue track
* Radial route
* Transport network

Facilities|

* Checked baggage
* First class
* Sleeper
* Standing passenger
* Travel class

Scheduling|

* Bus bunching
* Clock-face scheduling
* Headway
* On-time performance
* Public transport timetable
* Short turn

Politics|

* Airport security
* Rail subsidies
* Security
* Transit district
* Transit police
* Transit-oriented development (TOD)
* Transportation authority

Other topics|

* Boarding
* Bus rapid transit creep
* Crush load
* Destination sign
* Dwell time
* Hail and ride
* Prohibited activities
* Request stop
* Passenger load factor
* Transit map

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Transport network analysis. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Transport_network_analysis&oldid=4161920"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template