Optimization of Ant Colony Algorithm in Traffic Light System with Constraint Delay Time

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

1. 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 two-dimensional 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 real-time 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 'real-time' 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.

2. GRAPH MODEL OF THE TRAFFIC LIGHT SYSTEM

   1. 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 two-way.

        The pseudo-code 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();

        }

   2. 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 multi-agent 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.

3. 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

4. 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

5. 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

1. Biham, O., Middleton, A. and Levine, D. Self-organization and a dynamical transition in traffic-flow models. Physical Review A. Vol.46 (1992), pp R6124-R6127.

2. DSouza, R.M. Geometric structure of coexisting phases found in the bihammiddleton-levine traffic model. Physical Review E. Vol.71 (2005), pp. 251-258.

3. Chen, Shiuan-Wen., Yang,Chang-Biau. and Peng, Yung-Hsing. Algorithms for the traffic light setting problem on the graph model. TAAI, National Sun Yat-Sen University, Kaohsiung, Taiwan, (2007).

4. 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).

5. Han, Chong. and Zhang, Qinyu. Real-time detection of vehicles for advanced traffic signal control. International Conference on Computer and Electrical Engineering, Vol. 17 (2008), pp 245-249.