HoughtonlakeBoard.org

TIPS & EXPERT ADVICE ON ESSAYS, PAPERS & COLLEGE APPLICATIONS

 

Optimal Traffic Route Finder System

 

M.MONICA BHAVANI 1 Dr.A.VALARMATHI 2

We Will Write a Custom Essay Specifically
For You For Only $13.90/page!


order now

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 improvement in the
geographic information systems (GIS) technology it is much possible in order to
calculate the fastest & optimized route that can be found with the help of
GIS. This is because a path on a real road network in the city to have the various
different levels of the traffic at different time periods of  the day and it is not at all an easy task to
locate the shortest path. Thus, the fastest & optimal path can only be calculated
in the real time. In some of the cases, the fastest & optimal route has to
be calculated in a various other ways. Whenever the larger area of road
networks are involved in any of the application, the calculation of shortest
paths & optimal path on a larger network can be computationally very tough because
some of the applications are involved are to find the optimal path over the
road networks.

With the help of the geographic
information systems (GIS) and the GPS logs of information needed in the
real-time are dynamic, the changing information have been collected has become
a common practice in many of such applications.The usage of the application of
this paper is to provide that the real-time traffic information of the system
integrated with the historical data are used to develop various routing
strategies in order to provide both the travel time between the source to
destination & the fuel consumption of the travelling cost.This paper is to
develop the new algorithm for to reduce the travelling time and cost between
the every source & destination by providing an optimal routing path .

               

We therby likes to
propose a fastest & an optimal transportation path routing algorithm called
modified Dijkstra’s algorithm with the fuzzy logic in order to select the
various different routing paths that defines to these conditions. Thus, we present
an approach to provide the implementation of the proposed algorithm to an
optimal road transportation routing system where it will be integrated with GIS
providing real-time traffic flow of information.Thus,we consider getting a
shortest path problem on a road network with the various travel times where the
resultant paths are observed for traffic flow in a dynamical way with the help
of GIS.This proposed algorithm is designed in a manner to provide the optimal fastest
path by using the fuzzy logic in selecting the next shortest path for every
source to 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 which is the extended work of
the paper 8 to determine the special case where network taffic status updating
is completely available to all the vehicle drivers. The regular state space
compression technique for the dynamic & flexible stochastic optimal path
problems are with real-time traffic information which is provided to efficiently
increase the computational and the implementational processes. This paper is an
extended work of the paper5 and here to determine the different issues that
are combining the vehicle routing with the various real-time traffic flow
informations from Geographical Information System.

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 optimal path problem has been
immensely examined in the literature that this paper 2 gives an modified
Dijkstra’s algorithm is used to calculate the minimum cost for the route in a
network which is static.The paper 3 showed that standard shortest path
algorithms (such as Dijkstra’s algorithm 16) do not find the minimum expected
weight path on a non-stationary or a stochastic network which is dynamic and
that the optimal path chosen can’t be calculated as a simple path but examined
based on constraints.This is why because there are many dynamic parameters
which require constraint-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.

 

GPS datasets

GIS Database

Fuzzy Routing  Algorithm

Optimal Path  Selection

Route Mapping using
GIS

Real time Traffic

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                                                                                                                                                                                   Fig.Methodology Diagram

 

The working of this methodology is done with the help of the fuzzy
condition based modified Dijkstra’s   algorithm.The
methodology diagram above provides the implementation steps of the algorithm which
dynamically updates the real time traffic information with that of the
historical collection of the data (GPS logs) which can be  collected from the GPS enabled vehicles. The
new algorithm has been proposed which is the fuzzy based modified Dijkstra’s algorithm
as Fuzzy Routing Algorithm(FRA).

 

5.             Fuzzy
Routing Algorithm

The fuzzy based routing algorithm first calculate the intensity of the
road traffic within the city for every source and the destination.This can be
done with the help of the historical dataset which are GPS logs for a
particular city and the real time traffic information.The fuzzy logic is to
provide the details regarding the intensity estimation of every road segment.

ALGORITHM FRA(G,R,C, ingress,
egress, b)

 

Notation

G = G(N,L) = Input Graph. 

R
= Set of link residual bandwidth ri

C = Set of link capacities ci.           

ingress = Ingress node.

egress = Egress node.         

b = Bandwidth demand.

Pathy = Set of nodes in the path from ingress to node y

 

Begin

 

1.     
Remove all links which does not
satisfy bandwidth constraint “b” from
G

2.     
Run Dijkstra’s Algorithm to
calculate Hmin for each
node

3.     
P = {}, Pathy ={} ?y, mringress=1,
and mri = 0 ?i ? ingress.

Loop

4.                 Find x ? P such that mrx is maximum ?x? P;

5.                 P = P U {x}. If P contains egress then exit loop;

Loop

 

6.                 ?y? P having a link xy Update

 

test y  = ? × min ( pxy ,lxy ,hxy ) + (1- ?) ×1/3( pxy ,lxy ,hxy )

 

If testy > mry
then  Pathy = Pathx U {x};

m ry  = max(m ry ,test
) ; End If

y               y       y

 

End Loop

 

End Loop

7.     
Return Pathegress

8.     
End FRA

 

 

6.             Implementation

The implementation of this work is to provide the optimal and the
shortest path based on various kinds of conditions like traffic intensity
estimation, cost of the travelling path, shortest in time to reach the
destination and so on. This can be done with the help of the modified dijkstra’s
algorithm and the application of fuzzy logic. The modified dijkstra’s algorithm
based on fuzzy logic is to find the shortest and an optimal path to every
source and the destination.This  algorithm
is proposed as the Fuzzy Routing Algorithm(FRA).

 

·        
The various implementation steps
of this process are

·        
Collection of the datasets which
are the historical datasets from the GPS logs.

·        
Integration of the real time data
of traffic information

·        
Formation of the GIS database

·        
Execution of the fuzzy based routing
system which provides the traffic intensity estimation which is the application
of the fuzzy logic

·        
Finding an optimal route between
the source and the destination.

 

Fig. 1 . Shortest
path computation using Fuzzy Routing Algorithm (FRA).

 

 

5.             Conclusion

 

This paper gives an approach for providing an optimal routing in
transportation system and that is combined with GIS technology that provides the
real-time changing & dynamic traffic flows.We have observed that when there
are number of paths for the same source to same destination increased with
real-time dynamic traffic flow information, thus 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

 

Post Author: admin

x

Hi!
I'm Irvin!

Would you like to get a custom essay? How about receiving a customized one?

Check it out