M.MONICA BHAVANI 1 Dr.A.VALARMATHI 21

1(Department of CSE, Anna

University,BIT Campus,Trichy,Tamilnadu,India)

2(HOD,Department of MCA, Anna

University,BIT Campus,Trichy,Tamilnadu,India)

[email protected], [email protected]

———————————————————————————————————————————————————————————————————————————————————————————————-

Abstract

The main aim of this Traffic route finder

system is to reduce the number of re-computations for finding optimised route

and alternate routes. This is to obtain less memory consumption & less

wastage of resources that results in minimal response times.On the development

of Intelligent Transport System (ITS), this increasing intensive on- demand of

routing guidance system in the real time coincides with increasing growth of

roads in the real world. This paper is about the values of the real-time

traffic data obtained for arrving at an optimal vehicle routing solution within

a dynamic transportation networks.Our proposal is to implement an optimal

vehicle routing algorithm in order to incorporate the dynamically changing

traffic flows.Thus we present a dynamic approach in selecting the paths for the

implementation of our proposed algorithm for the effective road traffic

transportations routing system by providing dynamically changing traffic flow

of information & the historical data using GIS.

Keywords: shortest

path,Geographical Information System,optimal route,real time traffic

——————————————————————————————————————————————————————————————————————————————————————————————–

1.

Introduction

T

HIS paper gives the

optimal traffic routes for the road traffic using the Geographical Informatiob

Syatem(GIS).The method has been determined for the calculation of shortest path

using the modified Dijikstra’s algorithm with the usage of the fuzzy logic.The

dijikstra’s algorithm is the frequently used shortest path calculating

algorithm so far.The fuzzy logic is used

with the dijikstra’s algorithm in order to find out the various other paths of

the source node to the destination node to be selected with the various weights

of the paths to be found.

With the development of

geographic information systems (GIS) technology this is much possible to calculate

the fastest route can be found with the assistance of GIS. Because a path on a

real road network in a city tends to have various levels of traffic during

different time periods of a day, and it is not an easy task to locate a

shortest path. Hence, the fastest path can only be calculated in real time. In some cases the fastest route

has to be calculated in a few other ways. Wherever the large area of road

networks are involved in the applications, the calculation of shortest paths on

a large network can be computationally very tough because of the applications

are involved are to find the shortest path over the road networks.

With the geographic

information systems (GIS), and the usage of GPS log of information,the

real-time & dynamically changing information that have been collected has become

a common practice in many of the applications. The application of this paper is

to show that the real-time traffic information of the system combined with the

historical data are used to develop the various routing strategies in order to

improve both the travel time & the fuel consumption of the travelling cost

measures.This paper is about to develop the new algorithm for to reduce the

travelling time and cost by providing an optimal routing path for every source

and destination.

We hereby propose an

optimal transportation routing algorithm called modified Dijkstra’s algorithm

with the fuzzy logic in order to select the various routing paths that caters

to these constraints. We also present an approach to get the implementation of

our proposed algorithm for an optimal road transportation routing system which

could be combined with a GIS providing real-time traffic flow of information. We

consider providing a shortest path problem on a road network with travel times where

the paths are observed for traffic flow dynamically with the help of GIS.The

proposed algorithm is designed to provide the optimal path by the fuzzy logic

in selecting the next shortest path to reach the destination.

2. Related Work

The shortest path problem finding with the

lower or minimal cost and time from a source to a destination is the fundamental

problem in the path finding in a road network.Most of the papers deals with the

finding of the shortest path with the algorithms like Bellmann ford,Dijkstra’s

etc for the traffic routing between source and destination.Our problem is to

find the shortest path with the more optimal algorithms like Dijkstra’s.Many of

the literatures talk about the Dijkstra’s algorithm is best suited for the

shortest path calculation.From the dijkstra’s algorithm,most of the

advantageous parts are obtained for creating this new algorithm called modified

Dijkstra’s algorithm with fuzzy logic for the decision making part of finding

the next shortest destination path to be selected as an optimal route to find

the destination by considering the dynamic traffic flows information and so on.

Traffic congestion can be of two types

Recurring traffic and non-recurring traffic.Recurring traffic is the place

where the traffic occurs all the time and thus they can be easily

predictable.But the non-recurring traffic is the place where the traffic occurs

at sometimes which can not be predictable by most of these systems to provide

the most optimal path slection in between a source and destination.

The development of the communication has

bring the dynamic routing to a reality by providing the Geographical

Positioning System (GPS) for positioning the traffic flows and the Geographical

Information System(GIS) to map the features of the traffic routing system.

The paper 5 extended the work of the paper

8 to examine the case where the network taffic status is available to the vehicle

driver. Systematic state space reduction techniques for dynamic stochastic

shortest path problems with real-time traffic information were provided to efficiently

improve computation and implementation processes. This paper is an extension of

the paper5 and we determine the various issues integrating vehicle routing

with real-time traffic flow information from GIS.

3.Problem

Statement

The shortest path calculation is the main

problem in the transportation network.Our aim is to create a shortest path

algorithm which is more advantageous than the other algorithms for calculation

of shortest path.This calculation contains various constraints. Some of them

are real-time traffic information that is of the dynamic traffic flows and

time-dependent information that is available.In the dynamic transportation

network, the network can be of dynamic traffic flow of information with the

network path weight changes can be of either deterministic or the stochastic

dynamic network which is dynamic.

The shortest path problem has

been immensely examined in the literature that. The paper 2 gives an optimal

Dijkstra’s type algorithm can be used to compute the minimum weight for the

route in a static network. The paper 3 showed that standard shortest path

algorithms (such as Dijkstra’s algorithm 16) do not find the minimum expected

cost path on a non-stationary or dynamic stochastic network and that the

optimal route choice cannot be computed as a simple path but determined based

on a policy. This is because there are many dynamically varying parameters that

require policy-based decision making using the fuzzy logic systems.

4.Methodology

The methodology deals with the various

constraints and characteristics of the dynamic traffic flow of the information

like the time dependent traffic flow of information which is dynamic and the

historical informations which are the GPS datasets of the road traffic

information.

The methodology is to collect the GPS

datasets of the information from the vehicles which traverse through the

various parts of the city.The routes of the whole city can be noted down for a

weeks time. This traffic information is gathered from the GPS dataset which is

noted down with the timing constraints and it is transformed into a GIS

database.From this GIS database, the traffic flow of information is gathered

which is able to detect the traffic in the peak hours and the weekends where

the traffic values are high and low respectively.

From this GIS database,the shortest path is

calculated with the various clustering techniques and with the proposed

algorithm which is Modified Dijkstra’s algorithm using fuzzy logic is used in

order to detect the traffic route from the source to destination. The

clustering techniques uses the time constraints and the distance of the travel

time of the vehicles and thus the optimal shortest path is calculated with the

modified Dijkstra’s algorithm using fuzzy logic for the decision making

purpose.

The shortest path calculated from these

techniques and algorithm has to be mapped with the GIS softwares for the

visualization of the results of the specific regions.This methodology provides us

with the optimal traffic route.

Fig.Methodology Diagram

5. Conclusion

This paper provides an approach for the implementation of an optimal

routing system for the transportation that is combined with GIS technology that

provides real-time changing traffic flows.We observe that when the number of

paths for the same source to destination

increases with real-time traffic information, the finding of an optimal

routing path for the changing traffic flows is predictable based on the

decision making process using the fuzzy logic technique..Hence,our algorithm

based on the shortest path calculation has been possible with the modified

Dijkstra’s algorithm with the fuzzy logic.Our conclusion is that real-time

traffic information from GIS which is incorporated

can significantly reduce expected costs and usage of the vehicle during times of heavy

congestion.

6. Future Work

Our aim is to work on with the real-time

traffic flow of information to obtain the optimal traffic information using GIS

by dynamically changing values of information.This will be providing us only

with the dynamic time to time varying dependent informations with the real time

traffic flows.This scenario will be created as an application with the most

optimal shortest path.

References

1

Bander, J. & White, C., “A heuristic

search approach for a nonstationary stochastic shortest path problem with terminal

cost”, Transportation Science, 2002, 36, 218 – 230.

2

Fan,

Y.; Kalaba, R. & Moore, I., “Shortest paths in stochastic networks

with correlated link costs”, Computers & Mathematics with Applications,

Elsevier, 2005, 49, 1549-1564

3

Delling,

D. & Wagner, D., ” Time-Dependent Route Planning”, Robust and

Online Large-Scale Optimization, Springer, 2009, 5868, 207-230.

4

Hashemi,

S.; Mokarami, S. & Nasrabadi, E., “Dynamic shortest path problems with

time-varying costs”, Optimization Letters, Springer, 2010, 4, 147-156.

5

Kim,

S.; Lewis, M. & White III., “C. “State space reduction for non

stationary 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 search

in 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 with

Markovian arc costs”, Operations Research, JSTOR, 1993, 41, 91-101.

9

Feldman,

R. & Valdez-Flores, C., “Applied probability and stochastic

processes”, Springer, 2010.

10 Cherkassky, B.; Goldberg, A. & Radzik,

T., “Shortest paths algorithms: theory and experimental

evaluation”,Mathematical programming, Springer, 1996, 73, 129-174..

11 Dial, R., “Algorithm 360: Shortest-path

forest with topological ordering H”, Communications of the ACM, ACM,

1969, 12, 632-633.

12 Zeng, W., “Finding shortest paths on

real road networks: the case for A*”, International Journal of Geographical

Information Science, Taylor & Francis, 2009, 23, 531-543.

13

Amrita Sarkar, G.Sahoo, and U.C.Sahoo “Application Of Fuzzy Logic In

Transport 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 As

An 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,”Optimization

On Shortest Path Finding For Underground Cable Transmission Lines Routing Using

GIS”, Journal of

Theoretical and Applied Information Technology,31st July 2014. Vol. 65 No.3

16

Ammar Alazab, Sitalakshmi Venkatraman, Jemal Abawajy, and Mamoun Alazab

“An Optimal Transportation Routing Approach using GIS-based Dynamic Traffic

Flows” 2011 3rd International Conference on Information and Financial

Engineering,IPEDR vol.12 (2011) © (2011) IACSIT Press, Singapore

1 Dr.A.VALARMATHI,HOD,Department of MCA, Anna University,BIT Campus,Trichy,Tamilnadu,India