The objective of this paper is to cover the research in the area of adaptive traffic control with emphasis on applied optimization methods. A distinction can be made between classical systems, which operate with a common cycle time, and the more flexible ones, phasebased approaches, which are shown to be more suitable for adaptive traffic control. Classic optimization solutions for this problem result in a model which is relatively easy to represent but may be difficult to fit into the standard mixed-integer programming (MIP) scheme. We propose an alternative approach to find an optimal global solution for the green wave problem on hot routes, which consists of reducing it to a Job Shop Scheduler problem using the Webster Model to adapt the cycles to road characteristics and average traffic speed.
In recent years, there has been a significant increase in the number of systems with built-in GPS function. The proliferation of these devices allowed the collection of a large number of GPS trajectories. Many applications, such as route planners, route finders, and georeferenced social networks, began using GPS data information to provide new services that were not previously available.
Traffic congestion is one of the leading causes of productivity loss and decrease of living standards in urban settings. The data generated by smartphones with GPS provide rich datasets that can be mined to offer solutions to urban traffic problems. Our problem creates an optimization method to program traffic lights that encourages the creation of convoys of vehicles forming a green wave of routes with greater flow, using as input the flow variation estimated by GPS trajectories as input.
Traffic congestion causes delays that add significant costs to society and
business on a daily basis and also increases CO2 emissions and the risk of accidents.
The study [
In order to alleviate traffic congestion, there are basically two solutions:
improving public transportation or expanding road infrastructure. In urban areas,
the latter is often impossible due to residential areas adjacent to existing roads.
A more subtle way to improve network performance is to make better use of
existing roads, which can be achieved in part by proper configuration,
optimization of traffic signal parameters, increasing the overall flow efficiency of vehicles
and reducing losses.[
This paper is an extended version and clarify the novel scientific content
presented in the manuscript GPS2GR [
Mobility is one of the most significant concerns in the world’s largest cities. Due
to the growth vehicle fleet levels and the limitation of urban roads, It can be
assumed that the vast majority of vehicles exceed the flowing capacity of large
cities. Paper [
Another study [
Figure 1 has an illustration with an example of a graph with a vehicle in the space and time dimensions and the constraints for the green wave to occur. In this the vehicle must be maintained between a minimum and maximum average speed, thus maintaining the synchrony of displacement in the physical space of the track and the elapsed time
The definition of the problem consider the flow of vehicles passing through a finite series of traffic lights. Each vehicle moves at an average speed v, the path is not blocked by other vehicles and there are no non-synchronized traffic signals. We consider vehicle traffic in the one-dimensional network. It encourages the formation of vehicle trains through the orchestration of traffic lights where vehicles tend to travel together, all with the average speed of the v route. In synchronized strategy, all traffic lights change simultaneously from red to green, and vice versa over a fixed period of time. The sum of the times is called the cycle time.
In the green-wave strategy, the traffic light changes with a certain time delay t shifted between the semaphore phases of two successive intersections. The delay time is called the travel time. The change of traffic lights spreads backwards, like a green wave.
When a vehicle arrives at a traffic light and the light is red, the vehicle stops there. Then, when the traffic light changes from red to green, the vehicle moves on. On the other hand, when a vehicle reaches a traffic light and the light is green, it does not stop and keep moving without changing the speed (green wave). 2.2
Definition 1 (Hot Route) It is used to reveal the common behavior of a set
of paths in a given time window. The hot route in this context is the sequence of
adjacent edges that share the certain amount of traffic (minTraffic) defined as a
parameter. [
A lot of research has been done since the 1960s on offline traffic optimization systems. In order for the mathematical model to be solvable without an external evaluation tool, such as TRANSYT, it must contain functional constraints that relate, for example. the appropriate displacement for traffic lights along arterial parameters for the specific flow, such as the saturation flow rate and the vehicle convoy dispersion factor. Considering a typical optimization formulation involving a common cycle time, divisions and green compensations, even considering a discretization of time, the search space of a solution is very broad, especially when considering some form of simulation to obtain the target value. Systems that operate in this way are best suited for off-line use, because trial runs have resulted in very costly processes, typically of several hours, even for small networks. 2.3
The adaptive traffic control systems aim to coordinate the controlled
intersections by signal, controlling a performance index that indicates an optimized
solution, but possibly not optimal. They do this by dynamically adjusting cycle
times, phase sequences, and green time according to both detected and predicted
traffic, thus reacting to dynamic aspects of traffic that cannot be captured by
the static optimization routines used to generate time-of-day plans. Here we
cite three adaptive operating systems: RHODES [
This work [
The problem Job-Shop Scheduling is classified in the literature as NP-Hard, that is, it is a problem for which there are no algorithms that solve it at polynomial time. It is a combinatorial optimization problem (Souza, 2001), which is an explicit or implicit enumeration of all possible alternatives to search for satisfactory solutions or the search for the optimal solution, depending on the class of the optimization algorithm used.
The optimization algorithms can be classified into two classes: mathematical models (search for optimal solution) and heuristics (search for approximation).
Since the problem of optimizing green waves on public roads is of NP-Hard
complexity, the solutions have been adaptive methods [
Consider a set of n tasks (jobs) and a set of m machines, where each task is composed by a set of operations whose execution order is defined. For each operation, we want to know in which machine it must be executed and the necessary time for it to be completed. Each convoy becomes a task, which runs on multiple machines (traffic lights) synchronously.
– A task cannot be assigned to the same machine twice. – There is no order of execution in relation to different task operations. – An operation cannot be interrupted.
– Each machine can process only one task (operation) at a time. The purpose of JSSP is to distribute tasks among machines so that the processing time necessary to finish executing all of them (also known as makespan) is as small as possible. In other words, we want to determine the sequence of machines that minimize the makespan.
In our approach, we made a reduction of the problem of the green wave to a problem of Job Scheduler where the traffic lights are the processors and the convoys of vehicles are the tasks. 2.6
Simulation of Urban MObility (SUMO)[
In our work, we use the SUMO traffic simulation mechanism to compare the base-line with constant traffic times, but optimized against the traffic-light times produced by the GR algorithm.
Our approach provides a flow optimization solution on previously identified Hot Routes. We propose a method to optimize convoys of vehicles on hot routes. These clusters of vehicles will gain benefit from the green light exchange, when they are approaching an intersection. However, these convoys of vehicles need to have an average speed that matches the average speed of the hot route. We have concluded our approach by offering an alternative way to solve the optimization problem, reducing it to a job shop scheduler problem, and applying a branch & bound method to solve it.
In short, the proposed GR algorithm produces a green wave over predefined flows using combinatorial optimization approach to arrive at the best solution for an urban context. 3.1
According to the Webster model in the table 1 for urban semaphores [
Ty = Td + 2Va (1) For simplicity the standard defined in the table 2 is adopted for Ty.
The general red time Tgr, see table 3, of an approximation is a function of the following variables: – Velocity V of this approximation; – Width L of the track to be crossed (of the distance to be covered by the
Vehicle within approach); – Vehicle c length;
Street - 40Km/h 3s
Avenue - 60Km/h 4s Expressway - 80Km/h 5s
Table 2. Yellow time – Clearance time Tf (minimum time elapsed between the beginning of time of the transverse track and the moment of entry of a vehicle into Speed).
Considering the usual situations, the following parameters were adopted: – Secondary roads (streets) with a maximum width of 9 m, and speed of 40 km / h – Preferred routes (avenues) up to 30 m wide, and speed 60 km / h; – Vehicle of 5 m; – Clearance time Tf = 1.2s.
According to Webster’s model, we must adopt sub-multiple cycles of time or programming period, to enable any change of plans without cutting abruptly the time of green current, never adopt Tc less than 30 s and only in special cases accept Tc greater than 120 s
Tc = Tg + Ty + Tr + Tgr, 30 ≤ Tc ≤ 120
The concept of minimum green time Tg−min is associated with the concept of time-wasted of the Webster model and must be respected under the penalty of causing major traffic jams. In table 4, the usual values of Tg−min are shown:
To define the percentage of the cycle that corresponds to green, we adopted a proportion of traffic volume between the approach path and the secondary pathway, that is, where Fa is the approach path flow and Fb the secondary path flow, then
Tg = Tc − Ty − Tgr ∗ Ta/(Ta + Tb)
Tc = Tr + Ty + Tgr + Tg (2) (3)
Approaching pathway minimum green time Tg−min
Street - 40Km/h 12s
Avenue - 60Km/h 15s Expressway - 80Km/h 17s
Table 4. Minimum green time 3.2
The classic problem of optimizing [
T T (Ψ, q∗(Ψ )) =
L X ql · tj (Ψ, q∗(Ψ )) l=1 subject to : Cmin,n ≤ Cn ≤ Cmax,n,
0 ≤ θn ≤ Cn − 1 φmin,np ≤ φnp ≤ φmax,np
Cn =
Pn X(φnp + Inp) p=1
∀n, ∀n,p, ∀n (5)
We propose an optimized method that reduces the green-wave problem to
the Job-shop scheduler problem, allowing the use of Branch and Bound solver
[
We generate convoys on the hot routes and look for an optimal solution for
these convoys to travel on hot routes without colliding. Inspired by the work
[
Consider the following transformations from the original semaphore optimization problem to a JSSP: – Traffic lights are mapped to the processors – Convoys are formed to replicate the Webster cycle on the Hot Route – Convoys are mapped to the Jobs – Green time is the job run time – Webster model are problem constraints – We will use the branch and bound method to find an optimal solution that minimizes makespan – The solution generates a set of Jobs that can execute without conflicts in the processors, that is, a set of convoys of vehicles that travel at the average speed of the route and are able to pass in all the open semaphores In this way the JSSP variables are: – Job-shop(Jm): In a job shop with m machines (traffic lights), each job represents a car convoy that has a particular and predetermined route to follow (hot route) – Processing time (pij): The pij represents the processing time of the Job j on machine i. – Makespan (Cmax): The makespan (manufacturing time), defined as Max (C1, ..., Cn), the end time of the last job leaves the system. A minimum manufacturing time usually implies maximum use of the machine (s).
The whole implementation was done in C# language, because some of the
baseline algorithms were originally written in this language. The implemented code
is available in the GitHub repository. [
For testing purposes, we used real trajectory data extracted from Taxi Simples,
a taxi company based in Fortaleza, Brazil. [
ALGORITHM 1: GR - Green Way over Hot Route
Output: S set of scheduler for all traffic light 1 P rocessors ← {}; 2 Jobs ← {}; 3 w ←WebsterModel(R[]); 4 w.greentime ← w.mingreentime; 5 (w.greentime++ <= w.maxgreentime) P rocessors ← DTL(R[], w); 6 Jobs ← MC(R[], w); 7 s ←JSSP.Solver(Processors, Jobs); 8 if s!= null then 9 break; 10 end
/* repeats by increasing the green time, in search of a solution
11 return s;
/* s variable contains an optimal solution
*/
*/
ALGORITHM 2: MC-MakeConvoys
ALGORITHM 3: DTL-DiscoveryTrafficLights
frequency sampling rate, but was filtered down to reflect one with a low-sampling
character. Maps in OSM XML format were obtained from OpenStreetMap and
then parsed into a road network-like graph data structure using an XML parser
written in C# [
For the experiments, we used a Intel (R) Core (TM) i7-4770S CPU @ 3.10GHz with 16GB RAM memory, 256KB Cache L1, 1.0 MB Cache L2 and 8.0 MB Cache L3.
The trajectory data of the Taxi [
To demonstrate the effectiveness of our algorithms, we perform the sequence of the following steps on the raw data of GPS trajectories in the city of Fortaleza. 4.3
To evaluate the GR algorithm we used frequent routes obtained from the data
set of taxi trajectories mentioned above, using routes that contained traffic lights
in their route and where there were intersections. To extract the Hot routes we
use the Flowscan algorithm[
All the approaches used in this study showed very promising results and high applicability. Based on real-time trajectories of raw data we can obtain the city traffic behavior at each time slice where the behavior is linear. The query visualization can be used as a tool to discover the higher density flow (hot routes) and influence the creation of public policies for urban traffic.
In our experiments, we used the Simulation of Urban Mobility (SUMO) [
In each simulation, we isolated a fixed number of hot routes, using one in the first experiment, two in the second, and finally three on the third. In addition, for each hot route, we extracted its respective traffic lights, latitude and longitude positions. Furthermore, in order to execute the experiments, we had to calculate the rate of cars passing on each hot routes. For that, each hot route has an attribute called traffic segment, which tells us the number of vehicles in that specific segment. Therefore, by summing up all the traffic segments (on each hot route), we get the rate of cars.
On SUMO, for each simulation, we measured the average trip length (s), the average trip duration (s), and the average waiting time (s). For each simulation, we first performed it using the default traffic lights of the SUMO software, which are generated based on the common traffic of the route. Only after, we performed it again but then using our traffic lights configuration, in which we get it from our GR algorithm.
In Table 6, we present the results of the simulations for the first, second, and third scenarios. In the first line, we show the amount of vehicles loaded, then in the second line the number of hot routes, and finally on the third line the is show lane length (km). The remaining ones are the measures that we used throughout the simulation.
Listing 1.1. Part of scheduler file from GR <?xml v e r s i o n = " 1 . 0 " e n c o d i n g ="UTF−8"?> <s c h e d u l e r > < t r a f f i c −l i g h t i d ="0"> <g r e e n s t a r t = " 0 0 : 0 0 : 0 0 " end = " 0 0 : 0 0 : 1 7 " /> <g r e e n s t a r t = " 0 0 : 0 0 : 3 4 " end = " 0 0 : 0 0 : 5 1 " /> <g r e e n s t a r t = " 0 0 : 0 1 : 0 8 " end = " 0 0 : 0 1 : 2 5 " />
Second scenario % SUMO GPS2GR 6291 6291
3 3 653,26 653,26 % Simulation First scenario
SUMO GPS2GR loaded vehicles # 791 791 rot houtes # 1 1 total lane length (km) 84,94 84,94 Average time
Trip duration (s) Trip time loss (s)
We were able to complete an implementation and tests of the GR algorithms.
This algorithm converged and generated optimized solutions of the opening and
closing times of the traffic lights along the hot routes [
We prove by simulation that the solution obtained by the GR algorithm is optimal since its optimal solution is always better than the good solutions generated by heuristic methods. Optimization on rot route can solve classic vehicle containment problems at the end of a green wave, as it takes into account flow optimization, that is, green wave overflow, no matter what its path is.
As future work we can consider the application of GR algorithm on real time information streaming in order to reflect real time aspects of the flow such as accidents, road maintenance, etc.