Transport network analysis: Difference between revisions

Revision as of 08:23, 17 March 2021

Revision as of 23:47, 24 May 2021

Line 25:

{{main | Shortest path problem | 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.<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-218211–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 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.