Comparative Analysis of Route Planning Algorithms on Road Networks
Rajesh Kumar Yadav, Giriraj Kishor, H. Himanshu, Kishan Kashyap · 2020
It is merely impossible to know the history of Route Planning Algorithms. It can be imagined that from the very primitive era, animals have dedicated their time to find the shortest path to reach their food. This kind of algorithms is one of the most practised ones and forms the basis for solving many real-world problems. But like most of the graph algorithms, they were proposed in the mid-twentieth century. The applications of these algorithms are many, the most important one is its usage in Routing and Navigation based applications like Google Maps, Ola and, Uber. Here, the road network is resolved as a large graph with nodes as coordinates holding some meaning and edges as ways/paths connecting adjacent coordinates, then route planning algorithms are applied for finding the shortest path between two nodes in the graph created. A noteworthy application is in Routing data packets on the internet; the Open Shortest Path First (OSPF) routing protocol is based on the Dijkstra algorithm and is used in autonomous systems like Local Area Network (LAN). It is also being used in routing especially long-distance calls. Another interesting usage can be seen in the Currency Arbitrage strategy where currencies are bought and sold instantaneously from one market to another to make a profit from the exchange rate divergences. Due to applications in so many important fields, these algorithms are studied rigorously yet to come up with a more optimized version targeting certain scenarios or in general. It is in this understanding that this paper delves into the study and implementation of various route planning algorithms and portrays their performances based on efficiency, in comparison with each other when running on a graph obtained from real road network data. This paper will also deduce a set of parameters that affects the traffic flow and the evaluation metries that should be considered when applying those algorithms.