Transport network analysis: Difference between revisions

Revision as of 07:15, 17 March 2021

Revision as of 07:21, 17 March 2021

Line 15:

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

Line 22:

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]].<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 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===