Algorithm for scheduling traffic lights

[rany11]

The subject of scheduling traffic lights has been studied in many articles. Each has different assumptions on the data the traffic lights can gather, and different practical results. Most of the algorithms are tested with the SUMO simulator, and get a speedup with respect to the static scheduling and previous algorithms.

My research was to find the best algorithm for us that will be the best for our problem. The solution is based on the article:

An Intelligent Traffic Light Scheduling Algorithm Through VANETs By Maram Bani Younes, Azzedine Boukerche

The idea is to maximize the throughput of the traffic under the junction and in addition, to prevent starvation to lanes with less traffic. In order to achieve that the traffic lights are scheduled in a round-robin way.

Before the algorithm itself we need several definitions and notations:

• We define a cycle for traffic light i as the time between two consecutive times i became green.
• In addition, an epoch is one iteration of the round-robin scheduling.
• f_i is the rate of cars arriving to the ith lane in the junction.
• fe_i is the rate of cars exiting the ith lane. (when the lane is green).
• T_i is the cycle length of the ith traffic light.
• M is a mapping between a traffic light i and the other traffic lights that can be green with i at the same time.

The scheduling algorithm:

1. epoch <-- {all traffic lights}
2. find the traffic light with maximal f_i in epoch. If f_i = 0, return to (1).
3. search in M[i] another traffic light with the maximal f_j.
4. schedule i, j for T_i * (f_i / fe_i) time units. (turn the other lights to red, and then i, j to green).
5. epoch <-- epoch \ {i,j}. If epoch is empty then, epoch <-- {all traffic lights}
6. return to (2).

• Note that in (4) we don't necessarily turn i, j to red after T_i * (f_i / fe_i) seconds but only in the case that there is another traffic light in the current epoch with f > 0. (This is because scheduling is also turning the previous traffic lights to red).

• T_i * (f_i / fe_i) is the time will take for all cars that arrived to the ith lane to cross the junction. The time units are depends on the units of f_i, fe_i, T_i.

• Note that this could be a relatively long time because the goal is to maximize the throughput and not to minimize the maximal waiting time (which is a different problem). So, although no lane is starved, a car in a lane can wait for quite a lot of time in theory. In this case, it is possible to limit the scheduled time to a certain constant T_max. This constant can be set empirically by the simulation results.

[rany11]

Changes due to implementation limitations: The implemented algorithm is slightly different then the algorithm previously presented. The new algorithm is called at small time gaps and needs to decide who to schedule now.

The way this is done is using E2 detectors: long detectors on the road that can tell the percentage of occupancy and average speed.

The algorithm looks for the most busy queue using this information and decide whether to change the scheduling or keep with the current one. If two traffic lights could be scheduled at the same time, the algorithm will do it. Starvation prevention and context switch overhead are considered as well.

[EylonSho]

As it seems in 35b9529, are you assuming that the simulator will initialize an instance of Scheduler, and will call method schedule for each junction? Isn't it better that the scheduler will handle the scheduling of all of the junctions internally? In that way, the scheduler could be extended later to a smarter version which is based on the traffic in all of the junctions, something beyond micro-scheduling for a single junction.

[TomPalny]

35b9529540ac5504c24f3376e13d950d484f3726

[tomerkay]

@rany11 pls pay notice there are accidents in the simulation. I understood that @yairf11 should change his "green light changer" function with orange at the middle because at the moment it moves from green to red in a brief.