REVIEW ON SHORTEST ROUTE PROBLEM IN URBAN NETWORK SYSTEM

The shortest path problem has been studied for over 40 years in diverse fields and transportation. It is one of the fundamental rules that is being used to find a minimum distance to reach the destination, with minimum time consumption in a cost effective manner. In the modern world, it is very useful in planning the efficient shortest routes that is essential for transportation, telephone network, electricity power supply network, gas pipeline network, water supply, drainage network system etc. The complexity of network, cost and time required for networking is increasing in different kinds of network systems and identification of shortest paths plays pivotal role. In graph theory, the number of algorithms can be applied for finding shortest paths in a graph based network system. It reduces complexity of network routes, cost and time to build and maintain network based systems. In this review of literature, some of the gateways in finding out the shortest path that have been developed in the past in different networks are highlighted. The goal of this study is to select a cross-section of approaches in identifying the shortest path in different fields of research usingGeographical Information System (GIS) and (Global Positioning Systems) GPS. Keywords—Shortest path, Algorithms, GIS


INTRODUCTION
Shortest path problem is very significant in the study of transportation and communication network. Travelling is important part of daily life. Therefore, the optimal shortest path (SP) to the particular destination becomes inevitable to reduce costs, losses in productivity, pollutions, and risks etc. An appropriate algorithm is used to find the shortest path between two known vertices is Dijkstra's algorithm, which waspresented by the famous Dutch computer scientist Edsger W. Dijkstra.This was recognized as the optimal algorithm that can be applied to obtain the shortest path from a vertex (node) to any other vertex.
In this paper, an improved Dijkstra algorithm will beused to constraint function and develop this algorithm by using priority queue and determine the source by GIS & GPS .This Application helps to find out the shortest path to road network system from user location along with time, distance and all roads related information. It is helpful in terms of reducing travel time, effort, and cost. GIS and GPS based route network system is considered as a guide for users from the origin to a destination in the Bengaluru city. There has been a surge of systematic investigation in shortestpath algorithms due to the problem's numerous and diverse applications. These applications include network routing protocols, route planning, traffic control, path finding in social networks, computer games, and transportation systems, to count a few. In recent years there has been an increasing interest in the shortest path problem for use in various transportation engineering applications. Generally, in order to represent the shortest route problem graphs are used. There are a number of transportation applications which require the use of a shortest path algorithm rather than one of the standard and most favourable optimal algorithms. The objective of this survey is to present a breakdown of the shortest-path with GIS and GPS through an appropriate classification. This classification aims to help researchers, practitioners, and application developers to understand how each shortest-path works and to help them decide, which type or category of shortest-path algorithms to use given a specific scenario or application domain.

II. GIS APPLICATION IN TRANSPORTATION:
GIS are becoming more widely used in transportation planning agencies, especially among metropolitan transportation organizations. In many developed countries, highway maintenance management and urban planning is becoming a critical issue. Many more authorities are now able to use GIS for Highways and transport management, due to falling price of GIS software and friendliness. A popular methodology of modelling road networks is in the form of a Geographical Information System (GIS). GIS is framework for gathering, managing, and analyzing data. A lot of transportation related applications are developed using Arc-GIS.Arc-GIS is the industry leader in modelling of complex road networks. However, lack of appropriate data for GIS remains a chronic problem. In our approach, we develop the road network system on GIS platform that can provide multiple route options given a start and end location. The key idea is to find a cost optimal solution for two locations using Dijkstra's algorithm and rerun the algorithm by increasing the travel cost of one segment or the whole path, forcing the search algorithm to an alternative solutions.

III. RELATED WORK
Here an attempt has been made to review the literatures related to finding shortest path in various applications. There are number of works carried out. An effort has been made to bring the advanced and up to date review articles / papers published in the journals and books. Several methods have been developed in transportation engineering applications to find an optimal path. These methods could be mathematical model computations or classical algorithms (Bellman, 1958;Dijkstra, 1959). Dijkstra algorithm (1959) is one of the most famous methods to find the shortest path for a deterministic network. Many research works considered the road network as a deterministic network where the travel time is a constant value. Typically, there are two types of short path problems: the single shortest path problem which aims to find the shortest path from a given source to all other vertex in the graph, and all-pairs shortest path to find out the shortest path from every source in a network to every other destination in the graph (Baras and Theodorakopoulos, 2010). A conceptual architecture of a traveller information system for a metropolitan city in India was proposed by Pal, Sarvjeet (2011). This web GIS based system, namely Computerized Traveller Information and Decision Support System (CTIDSS) will not only assist travellers in route butalso provide prevailing roadway and traffic condition and schedule of operation of public transportation in real time. A path finding algorithm for transit network is proposed to handle the special characteristics of transit networks, e.g., time-dependent services, common bus lines on the same street, and no symmetric routing with respect to an origin/destination pair. The resulted path is a schedule coordinated fastest path for given constraints including origin and destination with a planned departure time or an expected arrival time. A GIS based information analyses and system was created by Amrapali C (2014) tosolve the traffic problem so that patients can find out the information about necessary treatment in a hospital based on a specialist service provided. The main objective of this paper was to integrate information on the actual position of health centres in Aurangabad city with the service and facilities provided. Further, the author demonstrated the function of the shortest path in a network analysis for finding out the nearest health facilities from patient's location. The base map of the study area is collected while the coordinates of the health care centres obtained in the field using Global Positioning System (GPS). These data incorporated into GIS environment and analyzed using Arc-GIS 10.0 software. Kumar (2014) discussed the network analysis tool to measure the efficiency of services in terms of time and distance. In his study, the optimal service area such as hospitals, schools and fire stations were defined based on the time and distance and analyzed the gap that exists in the allocation of these services in city area. So, this study had used GIS tools which are more relevant for different type of network analysis especially for transport planning for different purposes like shortest path, closest facility, service area and also for the best recourses allocation and for the creating of emergency route services, so this type of analysis is very crucial for the transport based planning.  (2015). This is particularly relevant for active commuting, where actual routes travelled may show high levels of agreement with modelled shortest routes. However, the predictability of the commute route clearly depends on the mode of travel used. Demirel (2016) demonstrated the opportunities of spatio-temporal analyses within dynamic urban road network management, where the concepts are supported with a case study from Istanbul Metropolitan Area. In the proposed methodology, the speed information retrieved from detectors was associated with the Open Street Map and quickest paths were simulated within determined time intervals. Different shortest routes are proposed to users in various time spans via incorporated speed information and network analyses. For the same origin and destination, 2.5 minutes difference is observed within the study area. The results were promising, where the added value of this study is presenting an approach for integrating various spatio-temporal data to aid dynamic urban road network management. In a study Idhoko K.E (2016) appliedGIS tool is applied to answer basic generic questions on how accessible one location is to another. The geospatial datasets were geo-referenced and link with attribute database using the Arc-GIS software. Analysis such as; spatial search for a particular road; the shortest route between two locations by applying concept of road network analysis was employed for effective emergency response services as well as solving travel salesman problem and improving the standard of life within the study area. Shortest path from the user location to the University to minimize the travelling distance was analysed by Saeed (2017)analyzed the. The author implemented Arc-GIS and Dijkstra's algorithm that find the shortest path between two points depend on the route length. The useof GIS Cloud Publisher for Arc-Map extension enables to publish the maps from Arc-Map to GIS Cloud. Amoako (2017) dealt with the problem of finding shortest paths in traversing some locations within the Kumasi Metropolis in the Ashanti Region of Ghana using Dijkstra's algorithm. The updated route was sent via a dynamic routing system for all vehicles in urban road communication system to vehicle driver to change his network has some special considerations which are the route. School bus routing and scheduling could be treated as a multiobjective Vehicle Routing Problem (VRP) that helps to transport the students in the safest, most economical and convenient way was proposed by Hashi(2017). The result of this research helps the Transport Management to design a dynamic shortest and fastest route for the vehicles. The GIS helps to identify the real-world pickup stops according to the concentration of the students in a particular area as well as to visualize the current optimum route and pickup points. Zhu (2017) proposed a mathematical model for mini-bus stop spacing based on Voronoi Diagrams to minimize the passengers' total travel time. In the optimization model, the Cartesian coordinate system was defined to calculate the travel time from origins or destinations to mini-bus stops. The model was a non-linear and constrained programming problem, which is modified WilsonHan-Powell Sequential Quadratic Programming (SQP) technique with properties of global convergence and stability used to solve this problem. However, the optimal mini-bus spacing calculated by the model was relatively ideal. The results have shown that there was an optimal minibus stop spacing of 330 m, which was used to locate minibus stops with the proposed modification methods, proving simple and practical. Babiker (2017) illustrated that GIS based network analysis was more helpful tool for solving transportation problems, road congestion and terrific jam. It was being dominant in most planning and transportation sector, and provides effective cost for agencies even small ones. Further, the study showed that the high resolution IKONOS image provided an cost effective and less time consuming as data source to find out the best and short route between locations, determine the closest facility depended on arrival time and the car speed, determine the area serviced by certain facility which helped in the future planning and support decision makers to determine the area needed for new facilities to build and compare alternatives. Ride-Sharing is an efficient way to improve the traffic situation by lowering the number of necessary vehicles when people travel together was proposed by Paul Czioska (2017). However, in a real city environment, it is necessary to consider the local situation to determine convenient meeting points, enabling a secure parking and boarding and making the waiting time as comfortable as possible. The evaluation shows that the user satisfaction as well as the amount of matched participants is dependent on the amount and spatial distribution of meeting points. However, a saturation effect can be observed, showing that a limited amount of labelled meeting points in a city is sufficient to meet the demand. Locations with facilities like light, shelter and seating can further improve the overall satisfaction of the user. An assessment of characteristics, spatial arrangements, and impedance of the roads through digital road map and database was discussed by Chigbu(2017). Data analysis included layers and database creation, link impedances that indicate area with low, moderate and high efficiency route and proximity analysis that indicate areas with difficulty accessibility due to poor planning of infrastructures. The use of geo-database, digital road map for the evaluation of road transportation and infrastructure planning such as electricity was recommended which will help to solve long lasting problem of light within the area. Fitro(2018)presented the problem-solving technique in the shortest path search based on Geographic Information Systems using combination of methods that are node combination algorithm and Dijkstra's algorithm. Based on the results of tests that have been carried out the technique succeeded in finding the optimal route in the case study route in Taman Sub district, Sidoarjo Regency, East Java, Indonesia. The results presented can be the distance traveled and travel time from the starting point to the end point. The neutrosophic shortest path (NSP), where edge weights were represented by IVNS was described by Broumi1 (2019). The advantage of using IVNSs in NSP has been discussed in this paper. The classical Bellman's algorithm has been modified by incorporating the uncertainty using IVNSs for NPP between source and destination nodes. The main goal of this work was to describe an algorithm for NSP in the neutrosophic environment using IVNS as edge weight. The algorithm proposed in the study is very effective for real-life problem.

IV. CONCLUSION AND SUMMARY
This literature review has shown that GIS is a broad field which covers many applications of scientific knowledge for practical purposes and it they plays a significant role in the technology era. The large growth of technology and GIS applications help people in daily life in various domains. Theshortest path solution will be considered as an excellent guide for users to benefit from its services by decrease time, cost, and effort in finding out the shortest path to the various transportation services from user locations, most appropriate roads, time and distance. The improved Dijkstra algorithm is better than traditional algorithm because it reduces nodes number and consuming time. Apart from this, the application of GIS will have the possibility to offer the following benefits: improved safety, efficiency, mobility, accessibility and intermodal connections. The beneficiaries' areas are optimal path, emergency service, data collection, environmental issues and traveller information. This paper has presented a wide range of GIS technique where in research journals in this field were collected, classified and interpreted result. Further, this review addresses the use of GIS in Sustainable Urban Transport performance, particularly on traffic and road network studies. In addition, this review enables researchers to understand the overview of application of GIS in finding all shortest route and also provides researchers with information on GIS areas in which further detailed investigation may be needed.

V. RECOMMENDATIONS
There is an urgent need for transportation planning and management in urban network by the application of Geographic Information System, because the number of vehicles on roads at certain peak periods of the day leads to lot of traffic congestion. The time periods between 7.30 am to 10.30 am and 3.30pm to 8.30pm in the major cities of India e.g. Bengaluru, Chennai, Hyderabad, Delhi etc., require alternative routes to overcome traffic jams. This problem can be resolved by the application of GIS, which help the users to decide the best possible routes from his own place. Government should ensure free flowingtraffic for people's safety and easy mobility.

VI. ACKNOWLEDGEMENT
The support from Dr.A.M. Ramesh, Chief Executive Officer from Karnataka Science and Technology is gratefully acknowledged.