Keywords

1 Introduction

One important aspect of smart cities is the intelligent traffic management. In this area, the fundamental role is played by intelligent traffic lights. Modern trend in the management and optimization of intelligent traffic tends toward merging vehicles in streams and their control [1]. One practical way is to synchronize the traffic lights located in the analyzed section of the road. Assuming that the phase times of traffic signals are fixed with not big distances between them, it is possible to aggregate traffic through the synchronization of traffic lights by changing the phase shift of the green signal for the next junctions [2]. Assuming that there is a preferred direction with priority in terms of travel time in the particular streets, it is possible to create the effect of the so-called “green wave’’ [3, 4]. Phase shift of successive cycles must therefore equal to the average travel time between this and previous traffic signal [5].

Numerous studies indicate that in conditions of high traffic (or due to intersecting slip roads) the problem emerges when vehicles wait before traffic lights and form queues at the next junctions [2]. This means that the aggregate stream of vehicles will be stopped and partly merged with a stream of vehicles that are about to move. This interferes with the idea of a green wave in traffic. For this reason, the idea of setting a reverse cycle - cycle offset of the next traffic lights is set so as to remove the queues formed at further junctions, and only later allowing in a controlled way new aggregated stream of vehicles to enter the road [6, 7].

An important role in optimizing traffic lights is played by evolution algorithms [8] that use the mechanisms of evolution known in the natural sciences. A variation of evolution algorithms are genetic algorithms. The aim of the article is make the comparative analysis of the effectiveness of selected genetic algorithms. For this purpose, the authors analyzed literature, defined the area of simulation, as well as evaluated the effectiveness of these strategies and algorithms. The article is completed by conclusions from the research.

1.1 Related Work

The literature presents different methods and technologies that enable more efficient control of traffic lights. In [9] the authors propose using Simultaneous Perturbation Stochastic Algorithm (SPSA) to calculate in real time the best set of traffic lights in order to minimize travel time through the junction. Proposal for a new controller (EOM-ANN Controller) of lights based on neural networks is presented in [10]. Quite a different concept is presented in [11]. The authors use the video stream from the cameras at junctions to calculate the volume of traffic in real time. The results obtained are used by switching algorithm of lights depending on the density of vehicles on the road, which aims to reduce congestion, thereby reducing the number of accidents. This area of research also describes the concept of self-organizing traffic lights. For example, in [12] the authors present a distributed algorithm to control traffic lights. Hybrid algorithms were developed in [13] that combines Fuzzy Logic Controller (FLC) and Genetic Algorithms (GA) and examined its effectiveness. The theory of distributed scheduling strategy based on Lagrangian relaxation and subgradient method is dealt by the authors in [14]. One last suggestion is the use of warning lights to support the traffic lights in order to avoid congestion [15].

An important place in the effective control of traffic lights is taken by genetic algorithms. There have been many attempts to apply them. An example would be [16], where he described the use of genetic algorithm to determine the durations of the successive phases of traffic signals and offsets. Another derivative algorithm, which can be classified as evolution algorithm, is particle swarm optimization (PSO). This algorithm was also applied in research on the development of an optimal fixed time traffic light program [17].

However, in the conclusions of the research authors clearly indicate the narrow nature of the results obtained as well as the need for improvement and rating of optimization algorithms in case of effective control of the traffic light cycles. This is also the motivation for the research of the authors of this article.

2 Research Environment

One of the first methods used to coordinate traffic network for junctions is TRANSYT, a method developed by the Transport Research Laboratory (TRL) in the United Kingdom. This method allows setting the maximum length of the queue in front of each signaling device in order to prevent the formation of queues affecting blocking of the previous junctions. The procedure for optimization is to change the operating parameters of traffic lights: offsets (i.e., the times between the start of the whole system and the start of particular traffic lights) and the durations of the phases. Subsequent modifications of TRANSYT method allow, for example, to take into account in the process of optimization the lines of public transport and the use of additional parameters such as fuel consumption [18, 19].

2.1 The Traffic Simulator

The research involved the use of the traffic simulator SUMO (Simulation of Urban Mobility) [20,21,22]. An important reason was the popularity of SUMO in similar research, for example [17, 23,24,25]. For the purpose of this article Python language software was prepared that was integrated with SUMO simulator via TraCi (Traffic Control Interface) [26]. The interface allows retrieving data about the current status of objects and changes in their status, e.g. reading of data from motion detectors, reading of vehicle information, reading and modification of the state of the traffic lights.

SUMO can put on the road three types of motion detectors: inductive loops, area detectors, detectors with multiple inputs and outputs.

2.2 Simulation Scenarios and Effectiveness Measurement

For the purposes of research on the optimization of control algorithms of traffic lights simulation scenario consisting of a artificial map of the road network (Fig. 1), arrangement of detectors and definitions of generated vehicles were developed. Every road (between nodes) has a length of 200 m. Simulation applies to passenger vehicles.

Fig. 1.
figure 1

Source: own research

Screenshot of SUMO simulator with open map of tested area marked with identifiers of junctions.

Full size image

Each of the traffic lights is based on a two-phase program: the first phase allows for the movement of vehicles in the direction north-south and south-north, while the second - the west-east and east-west.

The authors defined the movement of vehicles. Depending on the needs the following types traffic configuration were used: vehicles can go straight or turn right one time; vehicles can only go straight; vehicles can only go straight, the traffic on roads in the west-east direction is set to fixed high value for all such files, and the traffic on roads in the north-south direction is set for the specific file. According to [18] effectiveness of a specific algorithm of traffic light control is measured using the following criteria: throughput, probability of traffic relieve, etc.

In order to compare the tested algorithms, the number of vehicles that passed through the entire network of roads and vehicles stopping time (the time when the vehicle is stopped before the traffic lights or another vehicle) were used.

2.3 Methods of Testing the Efficiency of Algorithms for Fixed Time Traffic Lights

Evolution algorithms are a popular method for optimizing used to determine fixed time traffic light program. For this reason, this publication involved carrying out experiments designed to compare several selected types of evolution algorithms. These algorithms start from generating random parameters and strive with every step (generation) to find the parameters for which the rating function (also called adaptation function) returns closer value, the so-called optimum value.

For each of the algorithms the same number of units in a population was used: 25 and the same number of generations - 100. In the research configuration files were used, in which each of the vehicles can drive through the map straight or turn right one time. The traffic (the probability of generating a vehicle on each of the possible roads) is set to 0.282. The results of each unit are the arithmetic average of four ratings. The rating of a single simulation was calculated as a weighted average of the components such as the inverse of the sum of stopping times of vehicles and the number of vehicles that have reached their destination. Used components of the rating function have been normalized so that on the start with the default configuration generated by SUMO their values were close to 1. The aim of optimizing algorithms was to minimize the rating function. After the results were obtained, the algorithm with the best value of the rating function was selected and subject to a further test. This experiment consisted of simulation with the same settings of phase durations, but with files with the vehicle configuration for different traffic.

Figure 2 shows the structure of units that was used in the genetic algorithm. “F1” and “f2” are respectively the length of the first and second phase, “o” in the version with the offset is the length of the offset. Vector of a unit value in a version without offset consisting of 16 elements – two phase durations for each of the eight junctions, while in the version with offset 24 elements - offset and durations of the two phases for each junction. For each element of unit vector from which it can take values the range was set to [1; 50].

Fig. 2.
figure 2

Source: own research

Structure of a unit containing phase durations of traffic lights in the evolution algorithms, (a) version without the offset optimization, (b) version with the offset optimization.

Full size image

Settings of genetic algorithm: crossover probability - 0.95, the probability of mutation - 0.02 elitism – yes, applied mutation - a Gaussian function with a standard deviation of 0.1, the selection algorithm - roulette.

Settings of particle swarm optimization: the weight of inertia - 0.7298, \( \varphi_{1} \) - cognitive component - 2.05, \( \varphi_{2} \) - social component - 2.05. The rest of this article involved the differential evolution, the Monte Carlo method and PSO algorithm [17] as methods to be compared with strategies proposed in this publication. The use of evolution strategies involving the adaptation of the covariance matrix and archipelago consisting of four islands in the optimization of the phase durations of traffic lights is a new solution.

Differential Evolution (DE).

The algorithm of differential evolution [27] - similarly to the genetic algorithm - involves the steps consisting in crossover and mutation, but these operations are carried out for a randomly chosen unit elements, and do not depend (as in the case of crossover in a genetic algorithm) on mixing together the units.

This research involved the following parameters of differential evolution algorithm: the amplification factor - 0.8, the crossover probability - 0.9.

Covariance Matrix Adaptation Evolution Strategy (CMA-ES).

Evolution strategy involving the adaptation of the covariance matrix is a special kind of evolution strategies, in which instead of the vector variance [28] for the individual variables covariance matrix representing the relationship between the pairs of values is used, and instead of the one-dimensional normal distribution a multi-dimensional distribution is applied. Its big advantage highlighted by the creator of this method is no need for parameter selection by the user - all parameters used in the method are automatically selected by itself [29]. In this publication it was the first time when evolution strategy involving the adaptation of the covariance matrix was used to optimize the length of the phases.

Monte Carlo Algorithm.

The algorithm based on the draw of phase durations and checking the best result for the random sets of times. In the experiment, 2500 iterations involving drawing new times were conducted.

Archipelago.

This is a method of connecting a group of algorithms. In such a model representation of a single algorithm is called an island. When creating the archipelago one should define the list of islands belonging to it and the topology of connections between them. For each connection you can optionally assign a weight indicating the likelihood of migration. Sample topologies are presented in [30]. The idea of the algorithm is so that each island performs optimization according to predetermined algorithm. Then, the migration process is performed, which means the transfer of solutions between interconnected islands. After migration, re-optimization is started, however, the first step of migrating random units is omitted (units used are those, which were on the island as a result of migration) [30] (Fig. 3).

Fig. 3.
figure 3

Source: own research

The topology of the archipelago used to optimize the traffic light operation.

Full size image

Another new aspect of the experiment conducted in this publication is the creation of archipelago consisting of four islands in the following order: the particle swarm optimization (PSO), differential evolution (DE), genetic algorithm (GA), evolution strategy (CMA ES). It involved a use of a ring topology with non-directed edges (possible migration at each edge in both directions). Each algorithm works on a population of 25 units and creates 10 generations in each step of migration in the number of 20.

3 The Results of Experiment

The authors present the results of algorithms for selecting optimal durations of the phases of traffic lights on the test road network, without selecting the offset values (all traffic lights began to work at the same time from the same phase - the green light for the north-south direction and red for the west-east) - Table 1, and with offset (Table 2).

Table 1. Results of the fixed time traffic lights optimization with zero offset
Full size table
Table 2. Results of the fixed time traffic lights optimization with offset subject to optimization
Full size table

Both tables show the minimum value of the evaluation function reached, and the durations of the light phases at every junction (marked ‘‘j’’ with the number of junction) that were generated as optimal by the algorithm. In Table 2 first offset, and then phase durations were given for each junction.

Symbols algorithms used in the table involve: CMA-ES - evolution strategy involving the adaptation of the covariance matrix, DE - differential evolution, MC - Monte Carlo method, GA - genetic algorithm, PSO - particle swarm optimization, Archipelago - a combination of algorithms in the model based on the islands.

Figure 4 presents a graph of the evaluation function for the test algorithms with and without offset optimization. Black dashed line shows selected the value of the evaluation function calculated on the basis of the simulation with time settings taken from the map editor available in SUMO package.

Fig. 4.
figure 4

Source: own research

A graph showing the value of the evaluation function for the best result of each algorithm

Full size image

Analysis of the results shows that all algorithms except Monte Carlo, managed to generate a solution rated better than the initial settings from the map editor. Evolution algorithms achieved better results, and among them was the best algorithm was evolution strategy with covariance matrix adaptation (CMA-ES).

In the presented results it can be seen that in most solutions the duration of the first phase is shorter than in the second phase. The reason why evolution of solutions has led to selection of such units is the fact that the map used in the simulation has two roads towards the west-east directions and four of them crossing the road in a north-south direction. The car passing the entire map straight in a single case has to drive through four junctions, and in the other only two. There is a risk that the car designed to drive through more junctions will have to stop completely more times (which would increase the main component of the evaluation - total stopping times). Therefore, probably algorithms developed in the evolution a solution to minimize this risk - longer phase with the green light for these cars.

One of the test procedures included the comparison of the effectiveness of algorithms tested only for the times and for the offsets and times. For most algorithms, the result obtained for the optimization of offset proved to be better than the result for the solution without offset. However, for CMA-ES algorithm solution without offset achieved better (lower) value of the evaluation function. The reason is the increase in the dimensionality (the number of elements of the vector solution) from 16 (two phases for each of the eight junctions) to 24 (two phases and offset for each junction) without changing the algorithm parameters - the number of generations, and the number of units.

A little disappointment is the result of the archipelago, which is combination of many algorithms. Despite the use of the four algorithms in it, including the best CMA-ES, the value of the evaluation function was lower than the value of a single CMA-ES algorithm. In this case, the poor result can be the reason for the use of the low number of generations between migration. For example, migration to the island representing PSO algorithm from the island representing any other algorithm must involve the assigning of new velocity vectors to migrating unit, since they are only part of the PSO algorithm. The migration of units between selected algorithms every 10 generations could interfere with the operation of different algorithms, which resulted in a weaker result of the entire archipelago of CMA-ES algorithm.

4 Summary

The aim of the article was to compare the effectiveness of selected algorithms to optimize the length of the phase in fixed time traffic lights with two new approaches: evolution strategy involving the adaptation of the covariance matrix and topology archipelago consisting of four islands. To achieve the set goal, software extension of SUMO simulator was developed.

To conduct optimization studies of the durations of the individual phases and offsets of fixed time traffic lights a group of selected evolution algorithms was applied: genetic algorithm, particle swarm optimization (PSO), the differential evolution and the Monte Carlo method. Evolution strategy involving the adaptation of the covariance matrix was applied, which had not been done for such tasks before. In addition to single algorithm, the research involved a model combining them in order to work together on a solution called a model based on the islands (each algorithm is represented by an island that is part of the archipelago). For a test case of certain traffic all the evolution algorithms reached better solutions than the original program of fixed time traffic lights generated by the editor supplied with SUMO simulator. The best result was obtained using evolution strategy involving the adaptation of the covariance matrix.

Further research on the algorithms to optimize traffic lights will include the creation of new algorithms, modification of existing ones, and the selection of appropriate parameters to allow the best efficiency. It is possible to carry out experiments using methods presented in this article, including the use of other test scenarios.