Figure 1. Genetic Algorithm Flowchart for the Traffic Control System
Adaptive Traffic Control System (ATCS) serves as a main element in the constituents with which traffic control flow is achieved in fast developing, and developed urban areas. ATCS, however causes more delays on vehicles due to the fact that it is made up of intersecting points. Ensuring maximum efficiency at intersections has remained a challenge due to its dynamic nature of traffic. Additionally, a number of different methods that can be used to achieve higher performance at road traffic intersections have been recently proposed to engineers. In this study, a new and different method based on modified round robin scheduling algorithm through genetic algorithm technique to optimize the performance (in terms of timing) of a signalized intersection in one of the busiest and most crowded roads of Minna, Niger State - Nigeria (at Obasanjo shopping complex area). The technique uses an initial timing pattern to generate newer offspring (in terms of delay duration) to analyze cost function and to check if a global optimum is reached. This technique outweighs current techniques because the data upon which the nature of the system is built is relatively more phenomenal, as it puts into consideration the exact nature of the lane in many possible occurrences. In this work, a global optimum was reached at only a few number of iterations on the whole Genetic Algorithm process.
The continuous rise in the growing number of automobiles on the road has necessitated the need to have a control system that can better manage the population upsurge experienced in the traffic domain (Vahedha & Jyothi, 2017), which is an efficient way to optimize the utilization of road capacities. Exorbitant fuel costs, road accidents, nonchalant attitude of road users, and environmental concerns have necessitated the provision of a traffic system with minimized traffic delay timings. In this disposition, computer technology and its paradigms have been largely and widely used to curtail road excess and to come forth with optimized traffic control system with better timing system to enhance traffic transitions.
Gündoğan et al., (2014) analyzed the performance of an adaptive traffic control system in one of the busy road networks in Turkey. The traffic control system was based on the fuzzy logic, and genetic algorithm, which handled traffic exceptions and signalized optimization, respectively. It was observed that the performance of the adaptive control system was 10% improved as concerned with cycle time and also, an improvement of 15% was recorded in terms of travel time.
Also, (Hasan, Saha, Hoque, & Majumder, 2014; Pandit, Doshi, Mehta, Mhatre, & Janardhan, 2014) worked on proposing a technique that can be used in determining congestions in traffic through the application of image processing. A model that can be used for the control of traffic signals as a function of traffic data received from video camera was developed. Traffic density extraction of the road was based on the area occupied by the vehicles in the pixels of acquired image. Two parameters were used as output in the proposed model such as traffic cycle and time for every lane in terms of how dense the traffic is.
With a view to create an even swift movement access to emergency vehicles, Kabir and Salam, (2016) have proposed a system for reducing the delay times and providing quicker paths for emergency vehicles. A combination of field programming gate array - System on Chip (SoC) and infrared radio frequency identification sensor was used to implement the system. The system during the simulation stage was observed to respond almost immediately when emergency vehicles were added to lane for which it paved a least delay time of exit (Kabir & Salam, 2016; Mahajan, Atiwadkar, Patil, Lande, & Choudhari, 2016).
(Mishra & Singh, 2015; Ou & Wang, 2016) proposed a framework for optimizing the traffic control system dynamically. According to the model, infrared sensors were introduced on either side of the road. The presence of vehicles was thus detected and sent to a centralized microcontroller, which determined the delay and movement times.
It was with the view of improving the movement of emergency vehicles that (Vahedha & Jyothi, 2017) proposed a system for the intelligent control of traffic, whereby every vehicle gets to carry a Radio Frequency Identification (RFID) at all time. The signal conditions are studied by the RFID reader after which, an exit pathway is created for the exit of the emergency vehicles.
Round robin scheduling algorithm has been broadly used to describe the basic nature of a signalized road traffic intersection (Nipa & Islam, 2015). Round robin is a starvation free computer scheduling algorithm, which implies that every process waiting on the queue for access to some resources would get their fair share once processing gets to their turn.
Genetic algorithm has been widely used to solve optimization problems that rather seem unsolvable. It is very ideal for problems involving series of objective functions governed by certain constraints. Genetic algorithm is able to start with an initial population, perform a crossover function, analyze new generation for presence of better offspring, do mutation and selection all with the view to be achieving a global optimal result (Carr, 2015).
In this study, data were collected from the signalized road intersection point (Obasanjo shopping complex area, Bosso road) and critically analyzed using a round robin and genetic algorithm. A mathematical model was deduced and inferences were drawn from the model. The study aimed at reducing the travel time and the experienced delays posed by the current traffic control system through the application of modified round robin and genetic algorithm.
Optimization of multi objectives based system can be easily handled by Genetic algorithm. Vehicle lengths in terms of density, vehicle delay lengths, and other constraints in terms of driver behaviours with respect to obedience to traffic control system can all be modeled into genetic algorithm according to the period; undersaturated and over-saturated dynamics. This set of concepts is adopted in this work and used in data capture, representation, and interpretation.
The inspiration of Genetic algorithm was derived after evolution of life itself (Carr, 2015). Three major stages denote its searching space:
Figure 1 shows the GA for the traffic system. Taking the average of extra delay caused by take off, size and other unstructured behaviours of vehicles plying the road intersection arrived at a resulting constraint value of 5.
Figure 1. Genetic Algorithm Flowchart for the Traffic Control System
In this work, the modification implemented on the normal traditional round robin scheduling algorithm is based on the logic gate of NOR. When two vertically connected lanes are of no activity in terms of vehicles, instead of the traffic system to switch the movement to them, it instead switches to the other lanes with at least one vehicle waiting to ply the road. The round robin upon recipient of two nulls, processes the two 0s inputs as 1 using the alternative logic gate, NOR and therefore skips the two vertical lanes providing such inputs.
The motivation behind this technique is derived from the phenomenal occurrences of two opposite lanes being empty at the same time. This occurrence, according to the data gathered from the traffic analysis occurs twice everyday.
The modification on Round Robin would exceptionally help to prevent waste of time as no allocation of service time is given to two parallel lanes without at least a waiting vehicle. The impatient attitude of motorists would be curbed in this technique as it signifies that no one waits for nothing.
In Figure 2, the modified round robin scheduling algorithm comes into play when no activity in terms of vehicles are waiting to ply the road on points A0 and correspondingly parallel A01. The control thereby switches movement permission to the same A1 and correspondingly parallel A11 and vice versa. Figure 3 shows the lights at the intersection points.
Figure 2. The Concept of Modified Round Robin Scheduling Algorithm
Figure 3. Traffic Light Display at the Road Intersection Point
The location of the adaptive traffic control system to be optimized is in the heart of Minna, Niger State - Nigeria. It is one of the busiest road intersections in the city due to existence of banks, shopping malls, a hospital, and other business enterprises set up along the road. The road also serves as the main route to schools. Obasanjo shopping complex area's signalized traffic control system is shown in Figure 4.
Figure 4. Obasanjo Shopping Area Intersection Location
To capture the traffic flow and delay at each of the four lanes of the junction, a set of traffic counts were carried out at three specific periods (morning, afternoon, and evening). These counts lasted 20 minutes for each (of the three periods).
For Lane A, at morning peak period (from 7:00 am - 9:00 am), an average of 1210 vehicles were observed to be moving per 20 minutes. An average of 38 vehicles were noticed to accumulate at the stop point with delay duration of 103 seconds.
For Lane B, at morning peak period (from 7:00 am - 9:00 am), an average of 872 vehicles were observed to be moving per 20 minutes. An average of 34 vehicles were noticed to accumulate at the stop point with delay duration of 103 seconds.
For Lane C, at morning peak period (from 7:00 am – 9:00 am), an average of 452 vehicles were observed to be moving per 20 minutes. An average of 31 vehicles were noticed to accumulate at the stop point with delay duration of 97 seconds.
For Lane D, at morning peak period (from 7:00 am - 9:00 am), an average of 456 vehicles were observed to be moving per 20 minutes. An average of 27 vehicles were noticed to accumulate at the stop point with delay duration of 97 seconds.
During peak period at noon (from 12:00 – 1:00 pm) on Lane A, it was recorded that an average of 1245 vehicles ply the road per 20 minutes, 27 vehicles at stop point and a delay duration of 96 seconds.
During peak period at noon (from 12:00 – 1:00 pm) on Lane B, it was recorded that an average of 1103 vehicles ply the road per minute, 24 vehicles at stop point and a delay duration of 96 seconds.
During peak period at noon (from 12:00 – 1:00 pm) on Lane C, it was recorded that an average of 392 vehicles ply the road per minute, 15 vehicles at stop point and a delay duration of 80 seconds.
During peak period at noon (from 12:00 - 1:00 pm) on Lane D, it was recorded that an average of 508 vehicles ply the road per minute, 15 vehicles at stop point and a delay duration of 80 seconds.
The peak evening period of the road intersection was taken a between 4:15 - 6:30 pm.
Averagely, it was observed that 858 vehicles ply Lane A of which a build-up of 37 vehicles was noticed with stop duration of 109 seconds.
Averagely, it was observed that 933 vehicles ply Lane B of which a build-up of 41 vehicles was noticed with stop duration of 109 seconds.
Averagely, it was observed that 285 vehicles ply Lane C of which a build-up of 24 vehicles was noticed with stop duration of 109 seconds.
Averagely, it was observed that 330 vehicles ply Lane D of which a build-up of 21 vehicles was noticed with stop duration of 109 seconds.
Considering a single lane L1 that stops for the time STL1 of red light and moves for duration of time MTL1 of the green light, if the average arrival time of vehicle in L1 is λ1 and the service time for vehicle is S1 (time between departure of vehicles in the queue), then that R1 will last until the green light of the remaining three lanes, i.e.
Total delay TD1 in L1 is the sum of delay D1i of all vehicles in the queue, ie:
where,
N is the number of vehicles in the queue
D1i is the delay of ith vehicle in L1, i=1,2,3,…
Average delay per vehicle is:
Number of vehicles:
The TD1 can be expressed as the sum of an arithmetic progression:
where:
i.e.
Then
By induction average delay per vehicle of the second lane L2, ADV2 is:
By induction average delay per vehicle of the second lane L3, ADV3 is:
By induction average delay per vehicle of the fourth lane L4, ADV4 is:
The objective function F, therefore implies:
Hence, the task to use Genetic Algorithm to minimize the functions, F1, F2, F3, F4. i.e.:
Minimize F1 (G1,G2,G3,G4)
Minimize F2 (G1,G2,G3,G4)
Minimize F3 (G1,G2,G3,G4)
Minimize F4 (G1,G2,G3,G4)
Before the optimization of the road traffic network, the following was observed as the traffic behaviour as shown in Table 1. During the optimization initialization phase, the Morning, Afternoon, and Evening peak periods were set at 10 seconds each. A dummy value of 5 was added to each of the periods to provide for flexibility. This therefore, brings the initial population to 15 seconds for each of the periods. Each of these timing units gets evaluated with respect to the cost function, which in this case is the minimum amount of time it requires to have vehicles exit the lanes across all connected lanes. The mutation operator running at the background of the algorithm increases the exploration of the process. A new set of optimized timing plan gets created, and again, gets evaluated by a cost function to check if it meets a global optimum. This iteration continued and it was observed that the Genetic Algorithm converged at a value less than 10-6. At the end of the optimization, the obtained results are presented in the tables below (Tables 1 - 8):
Table 1. Traffic Analysis of Lane A before Optimization
Table 2 shows the analysis of the traffic after optimization.
Based on the achieved results, it is not outlandish realizing that it is very feasible to reduce the travel time experienced by motorists plying Obasanjo shopping complex road through the adjustment of the timing delay pattern as presented in Figures 5, 6, 7, and 8.
Table 2. Traffic Analysis for Lane B before Optimization
Table 3. Traffic Analysis for Lane C before Optimization
Table 4. Traffic Analysis for Lane D before Optimization
Table 5. Traffic Analysis for Lane A after Optimization
Table 6. Traffic Analysis for Lane B after Optimization
Table 7. Traffic Analysis for Lane C after Optimization
Table 8. Traffic Analysis for Lane D after Optimization
Figure 5. A Chart of Lane A showing the Traffic Delay before and after Optimization
Figure 6. A Chart of Lane B showing the Traffic Delay after and after Optimization
Figure 7. A Chart of Lane C showing the Traffic Delay after and after Optimization
Figure 8. A Chart of Lane D showing the Traffic Delay after and after Optimization
As judged from the optimization route, a combination of modified round robin and genetic algorithm has revealed new timing plan for the Obasanjo shopping area intersection. The plan has proposed a decrease in the delay time experienced by motorists while plying the road. The delay durations at morning, noon and evening peak periods have been cut down to 40%, 35%, and 50%, respectively.
Combination of modified round robin and genetic algorithm to optimize Adaptive traffic control system is the contribution of the work.
The research has also proved that to increase the efficiency of a signalized traffic control system, a reduction in the service time can help in the actualization of such efficiency. This is in the case that an accumulation of service time contributes directly to the delay experienced by connected lanes in the traffic.
This work only puts into consideration the behaviour of the traffic on Mondays, Tuesdays, Wednesdays, and Thursdays. Further work to ascertain and optimize the behaviour of the traffic system is encouraged for Fridays, Saturdays, and Sundays. It would be very interesting to see how the optimization of the traffic system would look like for Fridays, considering the fact that there exists a central mosque, (which greatly contributes to the traffic flow) just few meters away from the signalized intersection.
Further works could focus on the simulation of the achieved results in the work with the purpose of fine-tuning uprising bottlenecks.