A hybrid method based on genetic algorithm and ant colony system for traffic routing optimization

or has two main 
algorithm, we suppose the number of iterations of components including a network component 
 and a vehicular traffic component. The network 
genetic algorithm is NL, then NLmin NL NLmax 
 component is responsible for simulating the 
with NLmin is the minimum iteration times of 
 behavior of a wireless network, while the 
genetic algorithm and NLmax is the maximum 
iteration times of genetic algorithm. The flowchart vehicular traffic component provides an 
 accurate mobility model for the nodes. Mobility 
of the proposed GACS algorithm showing a 
 models represent the velocity and the position 
hybridization of GA and ACS in traffic routing 
 of each vehicle at a given moment. This type of 
optimization is shown in Figure 1. In this 
6 T-H. Nguyen et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 36, No. 1 (2020) 1-10 
simulation is especially helpful to traffic appropriate set of parameter values and their 
routing problem. range of values are initially selected in our 
 The microscopic VANET simulator in experiments. With chromosome (m, , , q0, , 
traffic routing problem considers vehicles as , ) of GACS algorithm via experiments it 
distinct entities that could communicate and was shown that the appropriate range for , , 
share information on traffic density, speed, q0 is from 0 to 1, and  is between 1 and 5, and 
moving direction of vehicles, road and traffic , is between 1 and 10. At last, the initial ant 
light. The simulation on VANET with GACS number of system m is between 1 and 500. The 
framework we develop includes four modules fitness function is computed by Eq. (9) and the 
as shown in Figure 2. 
 stopping criteria are NLmin = 10 and NLmax = 55. 
 MAP module processes the map problem to The simulation experiments run on 
get and transform map from an open street map Windows 7 OS, Intel Core i7-6700 (3.4 Ghz, 
project, load and visualize agent activity. It also 8M Cache) processor, 16GB DDR3L RAM. 
establishes online changing traffic conditions Our simulation framework is developed using 
such as traffic light, road and traveling Open JDK Java 8 environment and VANETsim 
environment attributes. version 1.3. The types of vehicles include 
 motorbike, bicycle, car and bus, with total 
 number of them between 10 and 100. The 
 performance of the system is evaluated by 
 criteria such as the total length of vehicle from 
 starting point to destination, the time for this 
 trip and the time that is used for algorithm 
 processing. The results obtained from our 
 framework are then compared to A-Star and 
 ACS algorithms. 
 3.3. Results and analysis 
 Figure 2. VANET simulation system with In the first scenario, we evaluated on the city 
 routing algorithms. map of Berlin, Germany, in which the data is 
 loaded from open street map, then it randomized 
 AGENT module constructs agents from types the starting point A with coordinate as x = 582858 
of traffic vehicles with attributes on system, and y = 353950 on Holzmarktstrasse road and 
controlling agent behaviors and traffic conditions. destination B on Littenstrasse with coordinate as 
 GUI module processes visualization graphic x = 550418, y = 320967. The GACS framework 
information and provides interaction ability 
 selected the trip to travel from A to B as shown in 
between user and the system. 
 Figure 3(a). When the vehicles meet congestion at 
 ROUTING module processes the 
algorithms and returns the results to the system. the intersections between StralauerStrasse and 
In this module, beside the proposed GACS Littenstrasse, they reroute the path with updated 
algorithm, the A-Star and ACS algorithms are information. The new routing will be changed to 
also used for performance comparison. the Direksenstrasse road to complete their trip. 
 Experimental results are evaluated in terms of 
3.2. Experimental parameters three values including Length (the length of the 
 global best path), Time (the time of best path), 
 Based on the parameters analysis in [7, 11, Processed Time (the processing time of 
19, 20] which obtained remarkable results, the the system). 
 T-H. Nguyen et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 36, No. 1 (2020) 1-10 7 
 405 meters. The time for global best path of the 
 GACS is smaller than that of A-Star and ACS 
 6.76 seconds and 4.58 seconds respectively. 
 The performance of the GACS is improved 
 because the environment information is 
 integrated into nodes and ants could perceive 
 the suitable node on their path. Although the 
 processing time of the GACS algorithm is 
 longer due to the repetition in calculation of the 
 GA in ACS, it is still acceptable in practice. 
 Table 1. Simulation results on berlin map 
 Processed 
 Length Time 
 Algorithm Time 
 (meter) (seconds) 
 (milliseconds) 
 A-Star 1060 58.56 25 
 ACS 950 56.38 45 
 GACS 545 51.80 156 
 In second scenario, the framework is 
 evaluated by the same method on city map of 
 Hanoi, Vietnam with the starting point A in 
 Tran Thai Tong street at coordinate as x = 
 12971115, y = 10755648 and destination point 
 B in Tho Thap street at coordinate as x = 
 12991416, y = 10810560 as shown in Figure 
 3(b). The obtained results in this scenario are 
 shown in Table 2. Similar to the first scenario, 
 the GACS algorithm also outperforms the other 
 algorithms in terms of Length and Time. 
 However, Time value in this scenario is slightly 
 longer than that in the first scenario that is 
 because the traffic conditions of Berlin map are 
 better than that of Hanoi map. 
 Figure 3. Simulation GACCS framework on (a) Table 2. Simulation results on Hanoi map 
 Berlin Map, (b) Hanoi Map. 
 Processed 
 Length Time 
 Algorithm Time 
 The obtained results in this scenario are (meter) (seconds) 
shown in Table 1 and they show that the (milliseconds) 
proposed GACS algorithm outperforms the A-Star 1150 64.12 18 
other algorithms in terms of Length and Time. ACS 802 60.88 31 
In particular, Length of the GACS algorithm is GACS 601 58 162 
shorter than that of A-Star 515 meters and ACS 
 y 
8 T-H. Nguyen et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 36, No. 1 (2020) 1-10 
 Figure 5. Simulation on various 
 transportation conditions. 
 Therefore, the framework is applied in the 
 fourth scenario to simulate a situation of 
 transportation system in congestion condition. 
 In this scenario, the number of vehicles is 
 increasing from 0 to 1500 vehicles which 
 consist of cars, motorbikes and bicycles in 
 order to see when congestion happens due to 
 increase in the road density overtime. The 
 various types of vehicles travelling at different 
 speeds are visualized by different colored dots 
 on the map. These vehicles are randomly 
 distributed on the Nguyen Chi Thanh road, on 
 Figure 4. Online monitoring traffic light. 
 Hanoi map, travelling between the coordinate 
 In the third scenario, the framework is of the point A (x = 21.030053, y = 105.812800) 
deployed in online setting of traffic light and the coordinate of the point B (x = 
condition as shown in Figure 4. Figure 4(a) 21.014934, y = 105.804353) as shown in Figure 
shows the ability to update traffic light system 5. This road is chosen in this simulation 
on Caugiay district in Hanoi Map. The traffic because it is where the traffic jams often occur 
light is added and the delay time of traffic light at rush hours. Efficiency of the GACS 
is changed. Then the GACS system updated framework in solving congestion problem is 
and processed online information. By adding a estimated in various transportation situations: 
given delay time of traffic light, the fitness normal, light traffic jam and heavy traffic jam 
value of chromosome changes correspondingly which correspond to the situations that vehicles 
in finding the optimal parameters based on GA. can go with the speed being less than or equal 
Subsequently, the pheromone updating of ants the maximum, half, and 10% of the speed 
on the arcs is also changed to find the best path limitation respectively. The obtained results are 
based on ACS. The ants consequently choose a shown in Table 3. The normal transportation 
newly suitable path. It is really significant to situation is specified when the vehicles are 
apply our framework in practical cases, which travelling without any collision, while the light 
need to change traffic conditions to solve congestion is specified when collisions occur at 
congestion problem. intersections (nodes). The heavy congestion is 
 T-H. Nguyen et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 36, No. 1 (2020) 1-10 9 
specified when the vehicles start to be optimize parameter settings of ACS. We have 
unmovable due to collisions. demonstrated via simulation experiments that 
 the hybrid GACS algorithm outperforms 
Table 3. Simulation results on transportation conditions compared to A-star and ACS algorithms. 
 Light Heavy However, it took longer processing time than 
 Algorithm/ Normal 
 congestion congestion those algorithms. Moreover, the GACS 
 Status (minute) 
 (minute) (minute) framework can provide the ability for online 
 From 0 monitoring the condition of traffic lights. In the 
 From 17 
 to 16 future, we are planning to further improve the 
 minutes to To 25 
 A-Star minutes 
 24 minutes current framework in order to dynamically 
 30 
 minutes change the traffic lights and reduce the 
 seconds processing time. 
 From 0 From 35 
 To 45 
 ACS to 30 to 40 
 minutes 
 minutes minutes 
 From 0 From 47 Acknowledgements 
 To 60 
 GACS to 36 to 58 
 minutes 
 minutes minutes This research was funded by Vietnam 
 National University, Hanoi (VNU) under the 
 Thus, the efficiency of the path finding project no. QG 17.39. 
algorithm is proportional to the duration to 
maintain the normal status or the transition 
duration between statuses. The results in Table 
 References 
3 show that the proposed GACS algorithm can 
extend the normal status that is 6 minutes and [1] M. Dorigo, Ant colony optimization, Scholarpedia 
19.5 minutes longer than that of ACS and A- 2(3) (2007) 1461. 
Star algorithms respectively. The time period https://doi.org/10/4249/scholarpedia.1461. 
from the light traffic jam status to the heavy [2] M.V. Dorigo, Maniezzo, A. Colorni, Ant system: 
traffic jam status is also extended for the GACS Optimization by a colony of cooperating agents, 
algorithm. In particular, it is 15 minutes and 35 IEEE Transactions on Systems, Man and 
 Cybernetics, Part B (Cybernetics) 26(1) (1996) 
minutes longer than the ACS and A-Star 29-41. 
algorithms respectively. This extension is [3] M. Dorigo, L.M. Gambardella, Ant colony 
resulted by dynamic adjustment of information system: A cooperative learning approach to the 
updating in the GACS framework that is useful traveling salesman problem, IEEE Transactions 
in traffic routing optimization. This simulation on evolutionary computation 1(1) (1997) 53-66. 
allows the managers and planners to evaluate [4] M. Dorigo, T. St¨utzle, Ant Colony Optimization. 
 MIT Press, Cambridge, MA, 2004. 
the transportation system based on the data [5] D. Favaretto, E. Moretti, P. Pellegrini, On the 
collected from personal devices to reduce the explorative behavior of MAX-MIN Ant 
traffic congestion through changing transport System, In: St¨utzle T, Birattari M, Hoos HH 
conditions such as adding the traffic lights and (eds) Engineering Stochastic Local Search 
adjusting the delay time of traffic light. Algorithms, Designing, Implementing and 
 Analyzing Effective Heuristics. SLS 2009, LNCS, 
 Springer, Heidelberg, Germany 5752 (2009) 
 115-119. 
4. Conclusion [6] F. Lobo, C.F. Lima, Z. Michalewicz (eds), 
 Parameter Setting in Evolutionary Algorithms, 
 In this paper, we proposed a hybrid Springer, Berlin, Germany, 2007. 
framework, named GACS to solve traffic [7] T. Stützle, Manuel López-Ibáñez, Paola 
routing problem in terms of distance and time. Pellegrini, Michael Maur, Marco Montes de Oca, 
The proposed GACS framework uses GA to Mauro Birattari, Marco Dorigo, Parameter 
10 T-H. Nguyen et al. / VNU Journal of Science: Comp. Science & Com. Eng., Vol. 36, No. 1 (2020) 1-10 
 adaptation in ant colony optimization in Light Control System with a Pedestrian Crossing, 
 Autonomous search, Springer, 2011, pp. 191-215. In: Wen P., Li Y., Polkowski L., Yao Y., Tsumoto 
 [8] Z. Cai, H. Huang, Ant colony optimization S., Wang G. (eds) Rough Sets and Knowledge 
 algorithm based on adaptive weight and volatility Technology, RSKT 2009, Lecture Notes in 
 parameters in Intelligent Information Technology Computer Science, Springer, Berlin, Heidelberg 
 Application, 2008. IITA'08, Second International 5589 (2009) 512-519. 
 Symposium IEEE, 2008. [16] Y.R.B. Al-Mayouf, Mahamod Ismail1, Nor 
 [9] J. Liu, Shenghua Xu, Fuhao Zhang, Liang Wang, Fadzilah Abdullah, Salih M. Al-Qaraawi, Omar 
 A hybrid genetic-ant colony optimization Adil Mahdi, Survey On Vanet Technologies And 
 algorithm for the optimal path selection, Simulation Models, 2006. 
 Intelligent Automation & Soft Computing, 2016, [17] S.A. Ben Mussa, M. Manaf, K.Z. Ghafoor, 
 pp. 1-8. Z. Doukha, "Simulation tools for vehicular ad hoc 
[10] D. Gaertner K.L. Clark, On Optimal Parameters networks: A comparison study and future 
 for Ant Colony Optimization Algorithms, In IC- perspectives", 2015 International Conference on 
 AI, 2005. Wireless Networks and Mobile Communications 
[11] X. Wei, Parameters Analysis for Basic Ant (WINCOM), Marrakech, 2015, pp. 1-8. 
 Colony Optimization Algorithm in TSP, Reason [18] V. Cristea, Victor Gradinescu, Cristian Gorgorin, 
 7(4) (2014) 159-170. Raluca Diaconescu, Liviu Iftode, Simulation of 
[12] J.H. Holland, Adaptation in natural and artificial vanet applications, Automotive Informatics and 
 systems: An introductory analysis with Communicative Systems, 2009. 
 applications to biology, control and artificial [19] L. Liang, J. Ye, D. Wei, Application of improved 
 intelligence, U Michigan Press, 1975. ant colony system algorithm in optimization of 
[13] K.D.E. Sastry, Goldberg, G. Kendall, Genetic irregular parts nesting, In 2008 Fourth 
 algorithms, In Search methodologies, Springer, International Conference on Natural Computation, 
 2014, pp. 93-117. IEEE, 2008. 
[14] S.M. Odeh, Management of an intelligent traffic [20] X. Yan, Research on the Hybrid ant Colony 
 light system by using genetic algorithm, Journal Algorithm based on Genetic Algorithm. 
 of Image and Graphics 1(2) (2013) 90-93. International Journal of Signal Processing, Image 
[15] A.M. Turky, M.S. Ahmad, M.Z.M. Yusoff, B.T. Processing and Pattern Recognition 9(3) (2016) 
 Hammad, Using Genetic Algorithm for Traffic 155-166.
 H 
 h