M.MONICA BHAVANI 1 Dr.A.VALARMATHI 21 1(Department of CSE, AnnaUniversity,BIT Campus,Trichy,Tamilnadu,India)2(HOD,Department of MCA, AnnaUniversity,BIT Campus,Trichy,Tamilnadu,India)[email protected]
com, [email protected] ———————————————————————————————————————————————————————————————————————————————————————————————-Abstract The main aim of this Traffic route findersystem is to reduce the number of re-computations for finding optimised routeand alternate routes. This is to obtain less memory consumption & lesswastage of resources that results in minimal response times.On the developmentof Intelligent Transport System (ITS), this increasing intensive on- demand ofrouting guidance system in the real time coincides with increasing growth ofroads in the real world. This paper is about the values of the real-timetraffic data obtained for arrving at an optimal vehicle routing solution withina dynamic transportation networks.Our proposal is to implement an optimalvehicle routing algorithm in order to incorporate the dynamically changingtraffic flows.Thus we present a dynamic approach in selecting the paths for theimplementation of our proposed algorithm for the effective road traffictransportations routing system by providing dynamically changing traffic flowof information & the historical data using GIS. Keywords: shortestpath,Geographical Information System,optimal route,real time traffic——————————————————————————————————————————————————————————————————————————————————————————————–1.
Introduction T HIS paper gives theoptimal traffic routes for the road traffic using the Geographical InformatiobSyatem(GIS).The method has been determined for the calculation of shortest pathusing the modified Dijikstra’s algorithm with the usage of the fuzzy logic.Thedijikstra’s algorithm is the frequently used shortest path calculatingalgorithm so far.The fuzzy logic is usedwith the dijikstra’s algorithm in order to find out the various other paths ofthe source node to the destination node to be selected with the various weightsof the paths to be found. With the development ofgeographic information systems (GIS) technology this is much possible to calculatethe fastest route can be found with the assistance of GIS. Because a path on areal road network in a city tends to have various levels of traffic duringdifferent time periods of a day, and it is not an easy task to locate ashortest path. Hence, the fastest path can only be calculated in real time.
In some cases the fastest routehas to be calculated in a few other ways. Wherever the large area of roadnetworks are involved in the applications, the calculation of shortest paths ona large network can be computationally very tough because of the applicationsare involved are to find the shortest path over the road networks.With the geographicinformation systems (GIS), and the usage of GPS log of information,thereal-time & dynamically changing information that have been collected has becomea common practice in many of the applications. The application of this paper isto show that the real-time traffic information of the system combined with thehistorical data are used to develop the various routing strategies in order toimprove both the travel time & the fuel consumption of the travelling costmeasures.This paper is about to develop the new algorithm for to reduce thetravelling time and cost by providing an optimal routing path for every sourceand destination. We hereby propose anoptimal transportation routing algorithm called modified Dijkstra’s algorithmwith the fuzzy logic in order to select the various routing paths that catersto these constraints. We also present an approach to get the implementation ofour proposed algorithm for an optimal road transportation routing system whichcould be combined with a GIS providing real-time traffic flow of information.
Weconsider providing a shortest path problem on a road network with travel times wherethe paths are observed for traffic flow dynamically with the help of GIS.Theproposed algorithm is designed to provide the optimal path by the fuzzy logicin selecting the next shortest path to reach the destination. 2.
Related Work The shortest path problem finding with thelower or minimal cost and time from a source to a destination is the fundamentalproblem in the path finding in a road network.Most of the papers deals with thefinding of the shortest path with the algorithms like Bellmann ford,Dijkstra’setc for the traffic routing between source and destination.Our problem is tofind the shortest path with the more optimal algorithms like Dijkstra’s.Many ofthe literatures talk about the Dijkstra’s algorithm is best suited for theshortest path calculation.From the dijkstra’s algorithm,most of theadvantageous parts are obtained for creating this new algorithm called modifiedDijkstra’s algorithm with fuzzy logic for the decision making part of findingthe next shortest destination path to be selected as an optimal route to findthe destination by considering the dynamic traffic flows information and so on.Traffic congestion can be of two typesRecurring traffic and non-recurring traffic.
Recurring traffic is the placewhere the traffic occurs all the time and thus they can be easilypredictable.But the non-recurring traffic is the place where the traffic occursat sometimes which can not be predictable by most of these systems to providethe most optimal path slection in between a source and destination.The development of the communication hasbring the dynamic routing to a reality by providing the GeographicalPositioning System (GPS) for positioning the traffic flows and the GeographicalInformation System(GIS) to map the features of the traffic routing system.The paper 5 extended the work of the paper8 to examine the case where the network taffic status is available to the vehicledriver.
Systematic state space reduction techniques for dynamic stochasticshortest path problems with real-time traffic information were provided to efficientlyimprove computation and implementation processes. This paper is an extension ofthe paper5 and we determine the various issues integrating vehicle routingwith real-time traffic flow information from GIS.3.ProblemStatement The shortest path calculation is the mainproblem in the transportation network.Our aim is to create a shortest pathalgorithm which is more advantageous than the other algorithms for calculationof shortest path.This calculation contains various constraints. Some of themare real-time traffic information that is of the dynamic traffic flows andtime-dependent information that is available.
In the dynamic transportationnetwork, the network can be of dynamic traffic flow of information with thenetwork path weight changes can be of either deterministic or the stochasticdynamic network which is dynamic. The shortest path problem hasbeen immensely examined in the literature that. The paper 2 gives an optimalDijkstra’s type algorithm can be used to compute the minimum weight for theroute in a static network. The paper 3 showed that standard shortest pathalgorithms (such as Dijkstra’s algorithm 16) do not find the minimum expectedcost path on a non-stationary or dynamic stochastic network and that theoptimal route choice cannot be computed as a simple path but determined basedon a policy. This is because there are many dynamically varying parameters thatrequire policy-based decision making using the fuzzy logic systems.4.
Methodology The methodology deals with the variousconstraints and characteristics of the dynamic traffic flow of the informationlike the time dependent traffic flow of information which is dynamic and thehistorical informations which are the GPS datasets of the road trafficinformation.The methodology is to collect the GPSdatasets of the information from the vehicles which traverse through thevarious parts of the city.The routes of the whole city can be noted down for aweeks time. This traffic information is gathered from the GPS dataset which isnoted down with the timing constraints and it is transformed into a GISdatabase.From this GIS database, the traffic flow of information is gatheredwhich is able to detect the traffic in the peak hours and the weekends wherethe traffic values are high and low respectively.From this GIS database,the shortest path iscalculated with the various clustering techniques and with the proposedalgorithm which is Modified Dijkstra’s algorithm using fuzzy logic is used inorder to detect the traffic route from the source to destination. Theclustering techniques uses the time constraints and the distance of the traveltime of the vehicles and thus the optimal shortest path is calculated with themodified Dijkstra’s algorithm using fuzzy logic for the decision makingpurpose.
The shortest path calculated from thesetechniques and algorithm has to be mapped with the GIS softwares for thevisualization of the results of the specific regions.This methodology provides uswith the optimal traffic route. Fig.Methodology Diagram 5.
Conclusion This paper provides an approach for the implementation of an optimalrouting system for the transportation that is combined with GIS technology thatprovides real-time changing traffic flows.We observe that when the number ofpaths for the same source to destination increases with real-time traffic information, the finding of an optimalrouting path for the changing traffic flows is predictable based on thedecision making process using the fuzzy logic technique..
Hence,our algorithmbased on the shortest path calculation has been possible with the modifiedDijkstra’s algorithm with the fuzzy logic.Our conclusion is that real-timetraffic information from GIS which is incorporatedcan significantly reduce expected costs and usage of the vehicle during times of heavycongestion. 6. Future Work Our aim is to work on with the real-timetraffic flow of information to obtain the optimal traffic information using GISby dynamically changing values of information.This will be providing us onlywith the dynamic time to time varying dependent informations with the real timetraffic flows.
This scenario will be created as an application with the mostoptimal shortest path.References1 Bander, J. & White, C.
, “A heuristicsearch approach for a nonstationary stochastic shortest path problem with terminalcost”, Transportation Science, 2002, 36, 218 – 230.2 Fan,Y.; Kalaba, R. & Moore, I.
, “Shortest paths in stochastic networkswith correlated link costs”, Computers & Mathematics with Applications,Elsevier, 2005, 49, 1549-15643 Delling,D. & Wagner, D., ” Time-Dependent Route Planning”, Robust andOnline Large-Scale Optimization, Springer, 2009, 5868, 207-230.4 Hashemi,S.; Mokarami, S.
& Nasrabadi, E., “Dynamic shortest path problems withtime-varying costs”, Optimization Letters, Springer, 2010, 4, 147-156.5 Kim,S.; Lewis, M. & White III., “C. “State space reduction for nonstationary stochastic shortest path problems with real-time traffic information”,IEEE Transactions on Intelligent Transportation Systems, 2005, 6, 273-284.
6 Likhachev,M.; Ferguson, D.; Gordon, G.; Stentz, A. & Thrun, S., “Anytime searchin dynamic graphs”, Artificial Intelligence, Elsevier, 2008, 172,1613-1643.7 Opasanon,S. & Miller-Hooks, E.
, “Multicriteria adaptive paths in stochastic,time-varying networks”, European Journal of Operational Research,Elsevier, 2006, 173, 72-91.8 Psaraftis,H. & Tsitsiklis, J.
, “Dynamic shortest paths in acyclic networks withMarkovian arc costs”, Operations Research, JSTOR, 1993, 41, 91-101.9 Feldman,R. & Valdez-Flores, C., “Applied probability and stochasticprocesses”, Springer, 2010.10 Cherkassky, B.; Goldberg, A.
& Radzik,T., “Shortest paths algorithms: theory and experimentalevaluation”,Mathematical programming, Springer, 1996, 73, 129-174..11 Dial, R., “Algorithm 360: Shortest-pathforest with topological ordering H”, Communications of the ACM, ACM,1969, 12, 632-633.
12 Zeng, W., “Finding shortest paths onreal road networks: the case for A*”, International Journal of GeographicalInformation Science, Taylor & Francis, 2009, 23, 531-543.13 Amrita Sarkar, G.Sahoo, and U.C.
Sahoo “Application Of Fuzzy Logic InTransport Planning”, International Journal on Soft Computing (IJSC) Vol.3,No.2, May 2012.14 Sasikala K.
R., Petrou M., Kittler J “Fuzzy Classificationwith A GIS AsAn Aid To Decision Making”, University of Surrey,Guildford, Surrey GU2 5XH, U.K.15 Viswarani.C.
D,Vijayakumar.D,Subbaraj.L,S.Umashankar,Kathirvelan.J,”OptimizationOn Shortest Path Finding For Underground Cable Transmission Lines Routing UsingGIS”, Journal ofTheoretical and Applied Information Technology,31st July 2014. Vol.
65 No.316 Ammar Alazab, Sitalakshmi Venkatraman, Jemal Abawajy, and Mamoun Alazab”An Optimal Transportation Routing Approach using GIS-based Dynamic TrafficFlows” 2011 3rd International Conference on Information and FinancialEngineering,IPEDR vol.12 (2011) © (2011) IACSIT Press, Singapore 1 Dr.A.VALARMATHI,HOD,Department of MCA, Anna University,BIT Campus,Trichy,Tamilnadu,India