International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 1
ISSN 2229-5518
Bio-inspired Neuro-Fuzzy Based Dynamic
Route Selection to Avoid Traffic Congestion
Sagheer Abbas, M. Saleem Khan, Khalil Ahmed, M.Abdullah and Umer Farooq
Abstract— this paper presents the bio-inspired neuro- fuzzy based route selection system to avoid traffic congestion. The proposed neuro-fuzzy system selects the best multi-parameters direction between two desired nodes: source and the endpoint. This research practices a mixture of neuro-fuzzy logic and ant colony system (ACS) algorithm for the principal routing to fulfill all the preferred requirements of the user using operational traffic data directly carried by the traffic control room and predicted by artificial neural networks for forthcoming minutes of the traffic.
Index Terms— Bio-inspired, Traffic congestion, Dynamic route selection, artificial neural networks, Bio-inspired Fuzzy based traffic system.
—————————— • ——————————
raffic congestion is becoming more alarming with every day as the number of vehicles on the roads is increasing rapidly. Route selection grounded on specifc desires is a foremost problem for city travelers. In route selection sys- tems, the source and the target are given. The objective of our system is to find out a route with the most favorable conditions satisfying all the needs and desires of a traveller. During the last decades, many researchers tried different approaches to find an optimized route, considering the important parameters that were the most advantageous for the city travellers. In theses systems, the distance and travel time were tried to minimize. Now-a-days many drivers are becoming concerned with not only these desires but also with rising fuel costs, to avoid traffic jamming and to adopt the route that satisfies their all desires like if users are fac- ing road-blocking on the way then it should be possible to adopt the next favorable route. It is a non-polynomial NP hard problem to find out the route that fulfills all prerequi- sites that force to enumerate all the possible routes. Pre- vious researchers have not spoken a fast, self-motivated and a applied except Salehinejad et al who tried a fuzzy
based dynamic route selection approach [1].
In 2007, Barth et al have mechanized some pleasant navi- gation based environmental systems. It consists of the fuzzy logic for pervasive and authoritative device for the
————————————————
Sagheer Abbas is with Computer Science department as research fellow at
NCBA&E Lahore, Pakistan (E- mail: sagheer@ncbae.edu.pk ).
Dr. M. Saleem Khan is with the Computer Science Department as Director in GC University Lahore, Pakistan (E-mail: mskgcu@yahoo.com ). Dr. Khalil Ahmed is with the School of Computer Science at NCBA&E Lahore, Pakistan, He is an expert academician and passionately engaged in research. (E-mail: drk@ncbae.edu.ok ).
Muhammad Abdullah is a PhD Scholar with Computer Science department at NCBA&E Lahore, Pakistan. (E-mail: abdullah_lahore@yahoo.com )
Umer Farooq is with Computer Science department as research fellow at
NCBA&E Lahore, Pakistan (E-mail: umer@ncbae.edu.pk ).
ideal routing [1] .
In 2011, Raghavendra et al used a new mechanism for
pheromones disappearance through a function based on
the convergance of the time. It shows a better peformace
as compared to all others traditional methodologies [4].
In this paper, Diogo et al attempted ADR algorithm for
the routing owing to enhance the efficiency of the system.
A new mechanism was used for the cost calculation based on the incentives [6].
In this paper, Saliba et al proposed the quality of ser- vice for internet traffic routing based on ants’ colony op- timization algorithm. The system’s performance was compared with the other traditional approaches and it was observed that the presentation of this model was much better as compared to all other methods [7]. In it three paramertes were used for the optimizations that are time, diatance and the no of vans. This work has much importantance regarding time-based palnning. Regarding digital image and tracks detection was proposed on ants based algorithms. [8]. Salehinejad et al. have proposed much for the route selection dased on the ACS [9].
In this paper, Attia et al suggested two algorithms for routing the network traffic. First got the inspiration by the multi-ant parametres, based on the reactive and proactive approaches to adopt the path and second was the mix-up with the QoS constraints. Its performance was excellent for the real time scenario [12].
In this paper, xiaamong et al attempted a quantum me- chanism for the travelling salesman problem, initializing the ants with the supeposition of qubit.this sytem shows the performance much better as compared to all other classical techniques [13]. Salehine jad et al introduced a fuzzy based route selection and ant colony system (ACS) based on “Distance”, “Incident Risk” and “Traffic” va- riables [1].
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 2
ISSN 2229-5518
This research work proposes a bio-inspired neuro-fuzzy based route selection system with six adjustable con- straints. This system uses a combination of ANNs, neuro- fuzzy logic and ant colony optimization algorithm to find out an optimum path based on the costs calculated with time, aimed at all possible directions for the user be- tween two nodes origin and the destination, valuing the user"s point of interests. An optimum route re- fers to a route that satisfies all the preferred parameters. In this paper, these parameters are “Distance”, “Traffic- flow”, “Environment monitoring”, “Width”, “Road con- dition”, “Traffic lights”. Due to the computational com- plexity six important parameters are taken else some more variables like “Incident risk” “Road condition” and the “View” (Home, building, park, river or any other scenic view the user wants to pass through). In this pro- posed system the present data is provided by the traffic control center and the coming traffic proceedings data is anticipated by artificial neural networks.
The arrangement of this research paper follows as: section II describes the overview of our suggested system, Artifi- cial Neural Network (ANN) and Ant colony optimization (ACO) algorithm. System and Parameters of the proposed system are discussed in section III, while in section IV the simulation results are discussed. Section V provides the conclusion and future work. Acknowledgement of this work is declared in Section VI.
The proposed system is a combination of ANNs and neuro-fuzzy inference engine. All six inputs to the proposed system are provided from the traffic control room TCR and the average speed of the vehicle is given from the user. The system comprises of the previous data, TCR indications that are being received continiously, the present time and the typical speed of the vehicle. Artifi- cial neural networks are casted for the forseen minutes of the traffic. Time delay estimation is used because time is required to move from base to destination. This estima- tion is done due to different loads of traffic among varied hours of day and night. This estimation is done as the system should be able to estimate the arrival time of the vehicle to the destination. This estimation is done on the basis of the average speed of the vehicle.
The system has the capability to avoid up coming traffic congestion as it is attentive to the up-to-date vehicle posi- tion system using GPS. Therefor, if congestion ensues the system recommends the user next direction according to the customized parametres. It is done by keep notifying the quantity of pheromones on the paths using ACS. The system has the flexibility for the customization of the pa- rametres that are being used in this system.
In the Fig. 1 main block diagram of our proposed scheme is shown, how the TCR, present time, Avg. speed, pre- vious data and the ANN collectively work to select the most favorable route using neuro-fuzzy system.
Fig. 1.Block diagram of the neuro-fuzzy based proposed sys- tem.
It is hybrid approach where neural and fuzzy advantages are combined for the paralle execution. The arrangement contains the structure of fuzzification and de-fuzzification. They both work with combined method.. The conforming grid has enhanced results as compared with the earlier work. The process of transforming crisp values into grades of membership for linguistic terms of fuzzy sets
Scheming and executing intellectual systems is a
complex factor for innovation and developments of en-
hanced products .Artificial neural networks are the ap-
proach that works higly parallel computations as com-
pared to our current machines. For a dynamic system,
these networks are highly attentionable and can resolve
problems that are not possible in linear computation. A
very atteactive attribute of these networks is, they are
adaptive in nature. If a dynamic application is required,
then these networks are considered most suitable due to
adaptive nature and decidedly parallelism.
Fig. 2 Feedfoward ANN for the upcoming minutes of traffic.
Neural networks are being engaged in various applica- tions including handwritten character recognition, human mind simulation and patterns appreciation [14]. ANNs
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 3
ISSN 2229-5518
have diffirents types and these networks are trained, grounded on the training data to perform a specific task.
Ant colony optimization (ACO) is a probalistics tech- nique that disentangles the cost for most favorable path selection. In ACO algorithm, artificial ants simulate intel- ligent behavior for discovering the optimized cost of the route selection. These anst are capable of solving complex problems like to find food using a chemical substance called pheromones. As a single ant moves between its nest and the source, it deposits some pheromones quanti- ty on that route. This pheromones quantity contains the path intensity to be adopted for other ants. As the phero- mones, quantity is being added frequently, becoming more noticeable for the ensuing ants.
An ant naturally adopts the way where the phero- mones quantity is higly concentrated. With the passage of the time, if ants are not following the higly concentrated path, the pheromones quantity start decreasing, causing the path to be less predicted. Those trails that are navi- gated (to food and back) most quickly soon become the trails with the highest intensity of pheromones, thus boosting the next ants to make choice of these routes.
It is not necessary that the ants are bound to follow the
route with the highest intensity of pheromones. Ants can
disregard the previous route and search food on all other
possible routes. If the ants are able to find a shortest path
towards food, then the current solution is swapped with
the previous one with highest pheromones quantity. As a
new shortest path is defined and updated, the phero-
mones quantity will start evaporation with time, causing
the path is less anticipated for the next ants and resulting
the longer path to be skipped.
Route selection based on the above mechanism is the
prime factor of ACO. The detailed description of ant be- havior as it narrates to ACO is provided by Dorigoet-al [15].
On the user defined parameters, for every single vehi- cel the proposed system is executed. In this system, the traffic indication is delivered by the TCR that contain- spresent traffic data and is updated dynamically. This system consists of average speed of vehicle, previous ve- hicles data, present time and the environment monitor- ing, no of lanes etc. ANNs are used for the future traffic minutes. The ANNs are trained as traffic predictor are used in this system causing helpful to the sytem with use of TCR and all other inputs to the system. The next sec- tion defines in details about the strategy algorithm of the system.
Initialize: it comprised of the initial values of the pa-
rameters such as number of ants and evaporation co-efficient etc.
During this phase, cost based probability for each route is calculated for all active ants. This probability is calcu- lated from the route souce to. For each ant, here it is elaborated with k.
Where, Tij denotes the pheromone intensity from source to destination ‘i’ and ‘j’ respectively. Constraint„a" is showing the the route [15, 16], tabu k is showing the all routes that are not suitable for all ants to be adopted in future. Bijl and ‘l’ are showing the cost of constraint l for route ij and the worth level of constraint l respectively. In this process list is consisted of all the jammed routes and the constainsts are the parametres for the user to adopt the route according to his customized way.. Currently the six most important parameters“Distance”, “Trafficflow”, “Environment monitoring”, “Width”, “Roadcondition”, and “Trafficlights” are used in this system. However, it can be enhanced by incorporating other parametress that are desiredable such as “Road Quality” and “other de- sired facilities like hospital” etc. [8-10].All these parame- ters have different significance impact from i to j; distance ij, road-condition ij, Env-monitoring ij, Traffic lights ij, Traffic flow ij, width ij.
source to target at time t.
source to target at a time t.
tion on the different routes from the source to target at a
time‘t’.
at a time‘t’ from the source to target.
routes from the source to target at a time‘t’.
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 4
ISSN 2229-5518
between ‘P’ and ‘p’ choices one from these.
a) If ‘p’ is larger than ‘P’ the ant adopts the route
with highest pheromones intensity.
b) If ‘p’ is smaller than ‘P’ or equal, then ant opts
the route with possibilities.
deactivated from the route for the following ants in order to provide the route reliability. More over its probability isnot considered any more.
Where, ‘hT’ is the amount of local pheromone updating. hT is the amount of pheromones of our neuro-fuzzy sys- tem. Six parameters of this system use three member functions that are taken by our systems and the phero- mone intensity was used between ‘0’ to ‘5’. If all parame- ters are in the most ideal situation then the pheromone intensity is maximum else varying between ‘0’ to ‘5’.
It is the final step of the algorithm to keep posted the global pheromone.
Where p is the evaporation constant and is usually set to
0.9.
In Table 1, some rules for the system are discussed. If
all the parameters are found at their ideal values then the
intensity of the pheromones is extraordinary. If three pa-
rameters comprised of maximum value and the other
three contained minimum value then the pheromones
intensity will be 3. If all the parameters have minimum degree then the pheromones intensity is minimum and the lowest probability to adopt that path. If the phero- mone intensity is high then it is decidedly observed to
adopt that route.
TABLE 1
PARAMETERS RELATIONAL TABLE OF THE SYSTEM
coust is suggested by the system.
According to the scheme of the neuro-fuzzy system for the route selection is designed and simulated on Matlab. All the parameters have significant effect on the system’s output. A neuro-fuzzy system is designed for the opti- mum route selection between two nodes, called the origin and the destination.
In the fig.3, six parameters are used as inputs to the Neuro-fuzzy system. The system makes three member functions of each parameter itself. The rules for the sys- tem are denser due to six inputs and three-member func- tion against each input as shown in the figure 3. The out- put member functions are also denser and the output is generated after all the computation is done.
Fig. 3 Neuro-Fuzzy System with 6 parameters
In the following table, we showed the relational parame- tric relational among all constratints of the sytem.
In the fig.4, Some data is given to the system for the work- ing out of the proposed neuro-fuzzy system. Total no of nodes 1503, participated during the training. In which there are 54 nonlinear parameters, 5103 linear parameters and 729 fuzzy rules are used.
Fig. 4 Training Error for the proposed Neuro-Fuzzy System.
ANFIS training using back propagation technique com- pleted at epoch 130 and the error is 0.56108, is too small.
Fig 5 shows blue circles for the data, offered for the testing purposes to the system and red stars are the outputs against the given inputs to the system. In the test- ing data fifteen pairs are randomly selected and pre- sented to the system. Red stars are the neuro-fuzzy out- puts of the testing data. The average testing error is
2.4827, remains too low and acceptable.
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 5
ISSN 2229-5518
Fig. 5 Testing Data results for proposed System.
In Fig 6 the checking data was presented to the system. Total no of pairs that are presented to the system, are 22 and the FIS output is shown against those pairs. Results against the checking data pairs are satisfied and the error is 0.54811.
Fig. 10 Surface graph between inputs width and road condi- tion against pheromones output
Fig. 11 Surface graph between inputs environment monitoring and road condition against pheromones output
Fig. 6 Checking Data results for the proposed System.
In fig 7 surface graph among inputs road condition and traffic flow against output is shown. When the road condition is at the ideal value the pheromones amount will be max against these inputs that will enhance the probability to adopt that route against two parameters,
Fig. 12 shows that Input variable traffic flow impact is directly relational to the pheromones intensity. Greater the intensity of the environment monitoring, the more impact will be on the pheromones intensity. Like this all others variables impact can be seen on the output varia- ble.
Fig. 7 Surface graph between inputs traffic flow and road condation against pheromones output
Fig. 12 Input variable traffic flow impact on the output variable pheromone
In figure 8,9,10 and 11 different parameters combination impact on the output is shown. These parameters impact on the pheromones are customizable.
Fig. 8 Surface graph between inputs traffic flow and envrion- ment Monitorning against pheromones output
Fig. 9 Surface graph between inputs traffic flow and width against pheromones output
5 CONCLUSION AND FUTURE WORK
In this proposed system, a neuro-fuzzy sytem is car- ried out to represent the characteristics of the constraints owing to select the most encouraging route according to the customized preferences of the driver who is utilizing this system. The proposed system is aware of changing the route dynamically when a congestion or obstructive traffic is perceived on the selected route. A route ranking can be provided to the user forecasting the decision mak- ing more adaptive and naturist. This work will reduce the cost handsomely in order to select the route according to the user’s customized preferences.
In this proposed sytem, costs of all the possible routes are studied to accept the favorable one. In conclusion, the route with the lowest cost is adopted using our system. This research can be continued for day-to-day life practic- es, by employing vehicle to vehicle (V2V) Communica- tion. In future microelectronics, state of the art technology can be used to develop the hardware of this sytem.
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 6
ISSN 2229-5518
This research work was carried out in the laboratories of GC University and NCBA&E, Lahore, Pakistan. We must acknowledge the support of fellows of research group and laboratories personals for their coordination to carry out this research work.
[1] Talebi, H. S. (2010). Dynamic Fuzzy Logic-Ant Colony System- Based. Applied Computational Intelligence and Soft Computing. Hindawi Publishing Corporation.
[2] Prasana Kumar and Raghavendra,(2011) “On the evaporation mechanism in the ant colony optimization,” Annals computer science series, pp. 51-56
[3] Diogo Alves, Jelmer van Ast, Zhe Cong (2010). Ant Colony Op- timization for Traffic Dispersion Routing, 13th International IEEE
[4] Annual Conference on Intelligent Transportation Systems, pp.
683-688
[5] Saliba, C. Farrugia, R.A (2010 quality of service aware Ant colo- ny optimization routing algorithm, 15th IEEE Mediterranean Electrotechnical Conference , 343 - 347
[6] A. Broggi, M. C. (2003). An evolutionary approach to visual sens- ing for vehicle navigation. IEEE Transactions on Industrial Elec- tronics, vol. 50, no. 1, pp. 18–29.
[7] H. Salehinejad, F. P. (2008). A new route selection system: multi- parameter ant algorithm based vehicle navigation approach. Vienna, Austria: in Proceedings of the International Conference on Computational Intelligence for Modeling, Control and Auto- matio, pp 1089-1094.
[8] Swann, S. A. (1979). Analysis of freeway traffic times-series data
by using Box Jenkins techniques. Transportation Research, no. 72, pp. 1–9.
[9] I. Ohe, H. K. (1995). A method for automatic detection of traffic incidents using neural networks. in Proceedings of the Vehicle Navigation and Information Systems Conference in Conjunction with the Pacific Rim TransTech Conference, A Ride into the Fu- ture, pp 231-235.
[10] Attia, R. Rizk, R. Mariee, M. . (2009). Wireless and Optical Communications Networks, 2009. WOCN '09. IFIP International Conference on ,pp, 1-5
[11] Meldrum, C. T. (1995). Freeway data prediction using neural networks. in Proceedings of the Vehicle Navigation and Informa- tion Systems Conference in Conjunction with the Pacific Rim TransTech Conference, A Ride into the Future, pp. 225–230.
[12] Xiaoming You Xingwai Miao Sheng Liu. (2009) .quantum compu- ting based ant colony optimization algorithm for travelling sales
man problem, pp,359-362
Sagheer Abbas is M.Phil. Scholar in the field of Computer Sciences at National College of Business Administration and Economics NCBA& E, Lahore, Pakistan . His research area includes Artificial Intelligence, Quantum Computing and Sparse Distributed Memory.
M. Saleem Khan is an Assistant Professor at GC University, Lahore, Pakistan. He is work- ing as director Computer Science Department in GC University, Lahore, Pakistan. He availed research fellowship at The School of Electron- ics & Engineering, University of Edinburgh, UK. and completed his Ph.D. thesis in the field of control systems: design, simulation and analysis in local and distributed environment.
He contributed his services on various projects in the field of Ad- vanced Electronics and Communication. His research interests include
control systems design and industrial applications. He promoted a large team of Electronics researchers and organized this field in his country. Mr. Khan had also been served as a senior scientific officer in a classified defense research organization in his country.
Khalil Ahmed is the Director School of Computer Science at National College of Business Administration and Economics (NCBA&E) Lahore, Pakistan. He is an expert academician and passionately engaged in research. His area of research is machine consciousness, A.I. and knowledge manage- ment. He completed his PhD in the fields of Computer Sciences and Robotics.
Muhammad Abdullah is Ph.D. Scholar in the field of Computer Sciences at National College of Business Administration and Economics
Lahore, Pakistan and his area of research is Artificial Intelligence, Machine Reflexes and Fuzzy Modeling.
.
Mr. UmerFarooq, is M.Phil scholar at School of Computer Science National College of Business administration & Economics(NCBA&E)Lahore, Pakistan and his area of research is Artificial Intelligence, Machine Reflexes and Fuzzy Modeling.
IJSER © 2011 http://www.ijser.org