 Open Access
 Total Downloads : 452
 Authors : Suhartono, Ahmadi, Turian Hasugian
 Paper ID : IJERTV3IS081057
 Volume & Issue : Volume 03, Issue 08 (August 2014)
 Published (First Online): 08092014
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Optimization of Ant Colony Algorithm in Traffic Light System with Constraint Delay Time
Suhartono, Ahmadi, Turian Hasugian Graduate School of Mathematics, University of Sumatera Utara
AbstractThe increasing number of vehicles and setting time of a traffic light system is the two main causes that need an optimization model due to the setting of waiting time vehicle. This paper is considered a specific constraint that affected the effectiveness of a traffic light system, delay time. The results obtained indicates that the greater the time delay on a traffic light system, the greater the required waiting time of each vehicle that affected the less number of vehicles that allowed crossing from one intersection to another intersection of the road.
Keywordstraffic light system, ant colony algorithm, delay time, optimization

INTRODUCTION
In statistical physics, the basic principles of traffic light flow system has been discussed for more than half of a century. The first model used is a model of automata that model Biham, Middleton and Levine (BML model) [1,2] which is formed by the sides of a simple twodimensional where each cell represents a lane of west and east bound of the vehicles. In this model there is only one traffic light to each cell where assumed that the cycle time of traffic lights is equal. [4] also have been developed a time optimization modeling of the traffic lights system.
In this paper, they used a strategy control traffic lights in realtime by using genetic algorithm in order to obtain the optimal performance traffic lights to some crossroads on a specific area. The used parameters are number of vehicles on the roads as well as the level of usage of a segment road at a particular intersection. Then, [5] successfully obtain an approach to detect and count the number of vehicles on a junction in 'realtime' so as to increase the efficiency of supervision over the traffic lights. The increasing number of vehicles as well as the timing of the traffic lights are less efficient and it becomes a factor when the need for a model of optimization with the goal of minimizing the waiting time of vehicles at a crossroads with the constraint of delay time.
This paper discussed a model of a traffic light with the delay constraint time. Section 2 discussed the graph model of the traffic light system that we used. Section 3 shows both of the methodology of ant colony algorithm and the mathematical model. The results of the discussion described in Section 4 and conclusions in Section 5.

GRAPH MODEL OF THE TRAFFIC LIGHT SYSTEM

Graph Model
This paper is using some notation of the graph model to represent the traffic light system as follows.

Each traffic light has three signs: Red, Yellow and Green;

Red and green lights have the same cycle time T, while the Yellow light has a cycle time for 5 seconds;

Each intersection had two phases, where the majority of vehicles through a phase of 'red light' and some other vehicles will experience a phase of 'green light' at the same time. And so on;

Each vehicle is not allowed to turn around to the right and to the left, and turn right and left;

If a vehicle reaches an intersection with a red light sign, then the vehicle must be stopped (the waiting period) until the green light is on
Under few assumptions above, we then modeling a traffic light system by a graph model G (V , E) with some definitions:

v V represents an intersection of a road;

(u, v) E represents the segment of the road between two vertices, u and v;

t(v) denoted the start time of green sign when
j 1 or the start time of red sign when j 0 ;

Thus, the time interval of a vehicle that allowed to cross the intersection road (green sign phase) is (t[v],t[v] T / 2 1) modT and time interval of
red sign phase is (t[v] T / 2 modT,t(v) 1] ;

On the model, each edge (u, v) E is twoway.
The pseudocode of the traffic light network to both phase (green and red sign) as follows.
class Traffic {//implements Runnable{
// traffic control center
Vector v=new Vector(); // main traffic Vector v2[]; // other traffics
car c;
int w=10,h=5,y0,w2=w/2; Graphics g;
static double a=10.;
static private double a2=a/6.; int minDx=3,xMax,Dx,Dx2,minDx2; Light L;
int passed=0,passed2=0; int ymax,ymin,y1; Traffic(Light Li){ L=Li;
v2=new Vector[L.count];
for(int i=0;i<L.count;i++)v2[i]=new Vector();
}


Ant Colony Algorithm
Ant Colony algorithm working with a substance of living things called Pheromone. Pheromone is a chemical substance that comes from endocrine glands and used by ant to recognize same types. Pheromone process is known as Stigmergy. Ant Colony optimization using a multiagent system where each ant colony moves as a single agent.
B. Input Data
We use some notation as input data in our traffic light model as follows.

cycle time of the traffic light is T;

delay time of the traffic light is W;

distance matrix, where
d(u,v) D , is a distance of each
edge (u, v) E
takes to pass;
that denoted total of time that vehicle

traffic network flow matrix, where
f(u,v) f (u, v)
Fig 2. Simulation of Ant Colony framework
denoted the number of vehicles from u to v in a cycle;

Boolean coloring matrix B with
b(u,v)b(u, v) {0,1}
that
Assume that we have  V  4 with V {v1, v2 , v3 , v4} of a
i
denoted the traffic light color at time t(v);
traffic graph model where each route or intersection has three
vertices,
l1, l2
and l3 , where li
shows
t
(v
i1
) t(v ) . Then, we
In this traffic model, the goal is to obtain a model that minimize the waiting time of a vehicle with the constraint delay time as the optimal solution to the model.


METHODOLOGY
can formulate the probability as follows.
[ (i, j)(t) ][(i, j)] prk (i, j) T 1 [ (i, j)(t) ][(i, j)]u0
(3.2)
A. Branch & Bound Algorithm
This traffic light system is represented by a tree searching that show the traffic flow from u to v. Therefore, we can estimate the distance or the time that takes a vehicle passing from u toward v. First, given the form of simple heuristic for setting the traffic light system at the next crossroads called wave setting [3], namely
with
prk (i, j)
(i, j)(t)
(i, j)
: probability of Pheromone k to choose edge j at vertex li , 0 j T 1
: iteration t at Pheromone concentration
: weighted of edge j at li
t(vi ) t(vi1) d(vi1,vi ) modT
(3.1)
Pheromone concentration of traffic light system model can be
formulated as follows.
The solution of wave setting is an upper limit of optimal solution and the lower bound is the sum of total root value on a tree to the specific node. It shows the adjacently
(i, j)(t 1) (1 ) (i, j)(t) 1 (i, j)k (t)
q
k
with
(3.3)
intersection, u and v. If t(u) and t(v) and traffic flow from u to
v, Pu,v , can be obtained with a traffic simulation from u to v.
Thus, the simulation will be continued from v to another intersection.
: evaporation rate of Pheromone with
0 1
q : total number of ant
(i, j)k (t) : Pheromone ant k at edge j in li

RESULTS
Our traffic light system model was implemented by Java Programming by using software Netbeans 6.9. Fig 3. shows the Graphical User Interface (GUI) of our program.
Fig 3. Simulation of green sign
Fig 4. Simulation of yellow sign
Fig 5. Simulation of red sign
Here is Table 1 that shows the result of our program with constraint delay time to each intersection of the road.
d.Time
(1)
d. Time
(2)
Waiting
time
Total
vehicles
0.00
0.00
26.10
13
1.00
0.00
27.46
11
0.00
1.00
25.24
9
1.00
1.00
26.48
10
Table 1. Results of our program

CONCLUSIONS
This paper represents a traffic light system model of traffic flow by using both of algorithm, Branch & Bound and Ant Colony. The aim of this study is to obtain the minimum waiting time of each vehicles with considering the constraint delay time. From our results, Ant Colony algorithm need a lot of running time in traffic light system problem. With constraint delay time to our program, we can choose the feasible algorithm to reduce the risk of traffic jam. This model then can be implemented in a sensor system of a traffic light, therefore perform of the efficiency of time is increasing.
REFERENCES

Biham, O., Middleton, A. and Levine, D. Selforganization and a dynamical transition in trafficflow models. Physical Review A. Vol.46 (1992), pp R6124R6127.

DSouza, R.M. Geometric structure of coexisting phases found in the bihammiddletonlevine traffic model. Physical Review E. Vol.71 (2005), pp. 251258.

Chen, ShiuanWen., Yang,ChangBiau. and Peng, YungHsing. Algorithms for the traffic light setting problem on the graph model. TAAI, National Sun YatSen University, Kaohsiung, Taiwan, (2007).

Singh, Leena., Tripathi, Sudhanshu. and Arora, Himakshi. Time optimization for traffic signal control using genetic algorithm. International Journal of Recent Trends in Engineering, Vol.2. New Delhi, India. November, (2009).

Han, Chong. and Zhang, Qinyu. Realtime detection of vehicles for advanced traffic signal control. International Conference on Computer and Electrical Engineering, Vol. 17 (2008), pp 245249.