An Evolutionary Algorithm to Generate Real Urban Traffic Flows

An Evolutionary Algorithm to Generate Real Urban Traffic Flows Daniel H. Stolfi and Enrique Alba LCC, University of Malaga, Spain {dhstolfi,eat}@lcc.uma.es Abstract. In this article we present a strategy based on an evolutionary algorithm to calculate the real vehicle flows in cities according to data from sensors placed in the streets. We have worked with a map imported from OpenStreetMap into the SUMO traffic simulator so that the resulting scenarios can be used to perform different optimizations with the confidence of being able to work with a traffic distribution close to reality. We have compared the results of our algorithm to other competitors and achieved results that replicate the real traffic distribution with a precision higher than 90%. Keywords: Evolutionary algorithm, traffic simulation, SUMO, smart mobility, smart city 1 Introduction Road traffic related problems have been studied frequently in the last decades. Several published articles are based on traffic simulations and, if the city modeled is big enough, the need for not only real maps, but also real traffic distribution is obligatory in order to obtain valid conclusions. Therefore, a traffic flow study is an important aspect to be taken into account when modeling scenarios based on real maps. These maps can later be used to optimize traffic light cycles [12], to study the placement of LED Panels throughout the city [14], to reroute vehicles with the aim of reducing travel times [13], and for many other uses in smart mobility [1, 5, 6, 9]. Usually, local councils publish data about traffic (and other useful information about the city), under a smart city initiative: the so called Open Data. Within this information we can find origin-destination matrices, main vehicle flows, or the number of vehicles at specific measurement points. When these data are available they can be used to analyze drivers’ habits, predict traffic congestion, or model a real traffic distribution consisting of traffic flows that match the real values. The problem we are solving here consists in calculating the best vehicle flows on a real map so that the number of vehicles counted in several measurement points are as close as possible to the data available from the local council. Our proposal is a new strategy based on an evolutionary algorithm which is able to calculate several traffic flows based just on a few measurement points, so that 2 Daniel H. Stolfi and Enrique Alba it can reproduce the real traffic, which in addition to a real map imported from OpenStreetMap, achieves instances for traffic study which are close to reality. 2 Related Work There are many studies (see survey in [2]) which focus on the estimation of origin-destination matrix based on traffic counting locations. They can be static [7, 8] or dynamic [3, 10]. However, these algorithms assume that all link costs are available, which may not be true in practical situations such as our case study. Unfortunately, authors do not usually detail the scalability of their algorithms for larger networks, which is a key issue for the interest in their solutions. In [15] a Hopfield Neural Network (HNN) model is used to estimate the urban origin-destination distribution matrix. The author claims that due to the ability of quick computation, parallel distributed processing and hardware realization of neural networks, it is possible to overcome the difficulties of mathematical optimization models. He finds the global optimal solution to the problem and experiments on a graph made of just five nodes representing the same number of zones. To the contrary, our method focuses on individual streets rather than zones (finer grain, higher realism) and we need to route vehicles via individual streets. Consequently, there are several routes available between measurement points in which the vehicles are counted. Therefore, we need to use a different technique to calculate the flows. An open-source software, called TrafficModeler, is presented in [11]. This program implements a traffic definition model describing traffic via a set of traffic layers placed over a road network. By using those layers it is possible to represent specific traffic patterns associated with different attributes. Additionally, traffic flows can be obtained from virtual populations based on demographic data (i.e. transportation between home, school and work). This tool for modeling traffic flows differs from our proposal in that it cannot be applied when the only source of data is the number of vehicles measured by sensors. Finally, there are two utilities included in the SUMO [4] software package called ACTIVITYGEN and DFROUTER. The former computes the mobility wishes for a group of citizens matching a map, while the latter uses values from induction loops (sensors) to compute vehicle routes. ACTIVITYGEN is quite similar in some aspects to the aforementioned article, analyzed in this section, although it does not provide a graphic user interface. DFROUTER is a tool that may be used in the same way as the work we present in this article, however, it assumes that the map is completely covered by sensors, especially on its borders, and it requires the exact timestamp in which vehicles were detected and their speed in all the measurement points. None of these options are suitable for the problem we are solving as they cannot be applied to calculate the traffic flows in the city based on just the number of vehicles counted by each sensor. An EA to Generate Real Urban Traffic Flows 3 3 Problem Description The aim of this article is to present a new strategy to generate traffic distributions in a city by using the data previously collected from sensors which count vehicles in a few streets. It is based on an evolutionary algorithm especially adapted to work with the difficulties that are present in this problem, such as high complexity due to the high number of vehicles and large scenarios, long evaluation times, and the high probability of traffic jams occurring in an actual city scenario when the number of vehicles moving through its streets increases. Furthermore, as is the case in many cities of the world, we do not have access to the actual vehicle flows, as this information is often not known (or not published) by the city traffic authorities. However, our algorithm is capable of dealing with this drawback by modifying the number of vehicles in each flow, in order to match the number counted by the sensors at several points of the simulated city, increasing the realism of the simulation. Let v∗= (v∗ 1, . . . , v∗ N) be a vector containing the values collected from N sensors in the real city, and v= (v1, . . . , vN) a vector containing the values obtained from the evaluation of the city map. Our objective is to minimize the error ei=|v∗ i−vi|, i ∈ {1, . . . , N}by modifying the vehicle flows f= (f1, . . . , fM) in the city. In short, by looking for appropriate flows (decision variables) we compute estimated flows on a simulator with the goal that they match real measured ones in the city where they are available. Of course, the set of flows contain a subset of proposed ones for the streets where no measurements are available at all, thus allowing the researcher to further study the city by using existing and approximated flows for all streets. 4 Case Study In order to evaluate our proposal we have selected the downtown of Malaga, Spain, where several vehicle sensors have been installed by the local council. The geographical area under study is delimited to the north by San Bartolom´e Street and Ferr´andiz Street, to the west by the Guadalmedina River, to the east by Keromnes Street, and to the south by the Mediterranean Sea, which encompasses an area of about 3 km2. We imported the selected area from OpenStreetMap into SUMO [4] traffic simulator by using the program NETCONVERT included in the SUMO package so that we could work with a real road distribution consisting of the actual streets, traffic lights, roundabouts, and junctions. Then, we added the measurement points provided by the city council by using SUMO’s induction loops (logical resource) in order to collect the number of vehicles in each of these points and compare them to the real ones. In Fig. 1 the map from OpenStreetMap and a snapshot of the same map imported into SUMO are depicted. Note that the traffic sensors are located at the original positions in which the vehicles are counted. 4 Daniel H. Stolfi and Enrique Alba (a) OpenStreetMap (b) SUMO Fig. 1. Case study: Center of Malaga, Spain Finally, we generated estimated flows between the input streets to the area, output streets, and local sources by using the DUAROUTE program included in SUMO to calculate routes by using the travel time as the weight function. All in all, we defined 63 flows, which determined the length of the status vector. Note that each flow consists in a sorted list of streets describing a route between the origin and destination points in the city In all our results we analyzed the case study for one hour of traffic, as the values from the sensors correspond to this period of time. Additionally, we established a warm up period of 10 minutes so as not to start our analysis in an empty city, which is rather unrealistic. 5 Flow Generator Algorithm (FGA) We propose here for the first time a Flow Generator Algorithm (FGA) to find the flows which minimize the differences between the vehicles measured in the city by the sensors and the values obtained after the simulation of the map. Fig.2 shows the optimization process where we can see that FGA uses the available sensor data and the map from OpenStreetMap as inputs to evaluate individuals by using the SUMO traffic simulator. During the optimization process the algorithm generates and evaluates different individuals which represent the number of vehicles in each flow. Finally, when the optimization ends, the output produced is the number of vehicles in each flow plus the map of the city. FGA is based on a (10+2)-EA, a steady state EA with a population of ten individuals generating two new individuals at each step. We used Binary Tournament as the selection operator, Uniform Crossover as the recombination operator, and an elitist replacement policy. We used local search instead of mutation after applying the recombination operator because it is necessary to provide extra information to the algorithm to avoid saturating the streets with a number An EA to Generate Real Urban Traffic Flows 5 Fig. 2. Optimization Process. of vehicles so large that they will always provoke jams (not enough capacity in the streets). The local search is described later in Section 5.3. 5.1 Problem Representation In Fig.3 we can see the status vector containing flow values which are actually the number of vehicles that are following each flow. There are 63 flows (M= 63) in the case study we are optimizing, each one of the vector’s values consists of an integer which can take values of between 10 and 500. Fig. 3. Status vector containing the number of vehicles for the 63 flows. 5.2 Evaluation Function Our evaluation function (Equation 1) assigns a numeric value to a configuration representing the vehicle flows (an individual of the FGA). We calculate the absolute value of the difference between the real values (v?) measured in the city and the ones (v) collected during the simulation of the map using the flows represented by the individual under evaluation. The fitness value of an individual is calculated by applying the evaluation function so that the numeric value of F is the summation of the absolute values of the differences for all the Nsensors. This only happens if C(v)≤0.2, otherwise, we apply a penalization of a large constant value in the algorithm (infinite) because we are minimizing, so the lower, the better. F(v) = (PN i=1 |vi−v∗ i v∗ i|if C(v)≤0.2, ∞if C(v)>0.2.(1) C(v) = max vi−v∗ i v∗ i, i ∈ {1, . . . , N}(2) 6 Daniel H. Stolfi and Enrique Alba As we want to avoid traffic jams, we need to keep the number of vehicles in each street low while we target the real value as much as possible by adding vehicles to different flows. To do this, we set a limit of 20% (C(v)≤0.2) as the maximum percentage each sensor can exceed the desired one (we have seen that bigger values lead to traffic jams which the algorithm cannot detect). In Equation 2 we present the calculation of C(v) as the maximum difference between the vivalue and the v∗ ione, so that if one of the values obtained from the simulation is higher than 20% of the real one, the individual is invalidated. This threshold only affects high values while the lower ones are actually considered by the algorithm as we wish to match the desired number of vehicles by incrementing them progressively, preventing street congestions. 5.3 Operators As we have said, we used Binary Tournament as the selection operator, Uniform Crossover as the recombination operator, and an elitist replacement policy. After applying the recombination operator we applied the local search operator whose pseudocode is shown in Algorithm 1. Algorithm 1 Local Search procedure localsearch(individual,∆(t)) v←calculateSensorV alues(individual) f←getF lows(individual) for all fi∈fdo if random() ≤PLS then sensors ←getRelatedSensors(fi) s←selectSensorRND(sensors) if v[s]−sensors[s]<0then incrementV ehicles(fi, ∆(t)) else decrementV ehicles(fi, ∆(t)) end if end if end for return individual end procedure First, the algorithm obtains the number of vehicles measured in each sensor by simulating the scenario with the flow configuration provided by the individual and stores the values in the vector vso that it is able to decide whether the number of vehicles measured by each sensor is under or over the real value. Second, it obtains all the flows from the individual and stores them in the vector fto iterate over it. Third, it selects which flows are modified according to the PLS parameter. Then, all the sensors which depend on the selected flow fiare stored in the vector sensors, and just one of them is randomly selected and stored An EA to Generate Real Urban Traffic Flows 7 in s. This dependency data is available from the case study and depends on the positions of the sensors and the routes of the vehicles which do not change during the optimization process. If more vehicles are needed in the selected measurement point v[s], the number of vehicles in the flow fiis incremented by ∆(t), otherwise v[s] is reduced by the same amount ∆(t). Note that we have set a minimum value of 10 vehicles and a maximum of 500 for each flow, the former, to be sure that all the flows are in use and the latter, as a value sufficiently higher than the maximum obtained in our initial experiments. Finally, after the loop, the local search ends and the individual is returned in order to be evaluated by the fitness function. The value of ∆(t) is calculated based on the minimum fitness value of the population according to Equation 3 so that the lower the fitness value, the lower the variation the algorithm makes to the individual. This mechanism allows us to make big changes when the optimization begins (exploration) and lower ones when the values from the simulation are close to the real ones (exploitation). We have set αequal to 20 as this is the lower bound of ∆(t) and βequal to 3 in order to control the reduction pace of ∆(t) as the FGA converges. ∆(t) = dα∗e(min F itnessi(t))/βe, i ∈[1, λ], λ = 10 (3) In Fig. 4 we show and example of the local search performed on an individual. First, fiis selected to be modified. Second, one of the sensors (sj) whose value depends on the flow fiis randomly selected. Finally, the number of vehicles in fiis incremented or decremented according to the number of vehicles counted by sjin order to be closer to the real value vj. Fig. 4. Local search example. We have experimentally found the values of the crossover probability (PC= 0.9) and the local search probability (PLS = 1/L). The maximum number of generations was set to 3000, however, if the best individual does not change for more than 500 generations, the FGA execution ends. 8 Daniel H. Stolfi and Enrique Alba 6 Competitors for our FGA In order to evaluate our local search operator, we propose two different alternatives to configure the traffic flows in our case study: i) Random Search (RS) and ii) an Evolutionary Algorithm (EA). 6.1 Random Search (RS) We report the behavior of a pure random algorithm to perform a sanity check on the validity of our FGA. We have implemented Random Search (RS) to obtain configurations of the traffic flows by generating different random configurations, saving the best of them until a better one is found. We have set a limit of 3000 iterations for the search process, the same number as in the FGA. 6.2 Evolutionary Algorithm (EA) The Evolutionary Algorithm (EA) is exactly the same algorithm as the FGA but for the mutation operator that is used instead of the local search. This operator randomly selects flows according to the mutation probability (PM) and modifies them with a constant number of vehicles (Γ). However, unlike FGA, the current value of the flow is incremented or decremented with a probability of 0.5, as this operator does not have further knowledge of the sensors affected by each flow. The main idea here is to support our choice of local search operator instead of the mutation one, rather than compete against a basic EA which is clearly unfair. Moreover, the parameters of the EA are the same as the FGA, that is, PC= 0.9, PM= 1/L,Γ= 50, 3000 generations, and 500 generations as convergence criterion. 7 Results First, we have conducted the comparison between algorithms in order to analyze the performance of our proposal (FGA). We carried out 30 independent runs of each algorithm optimizing the same scenario and then collected and processed the results which are shown in Table 1. There, we present the average fitness value, the standard deviation, and the minimum (best) fitness solution. Additionally, we have calculated the Friedman Rank and the Wilcoxon p-value in order to know the statistical significance of our results. Table 1. Comparison between algorithm. Algorithm Fitness Friedman Wilcoxon Average StdDev Minimum Rank p-value RS 2.610 7.01% 2.117 3.00 0.00 EA 0.775 20.22% 0.541 2.00 0.00 FGA 0.224 32.53% 0.154 1.00 — An EA to Generate Real Urban Traffic Flows 9 (a) Fitness distributions. (b) Convergence curves. Fig. 5. Comparison between the RS, EA, and FGA. We show in the box plot the fitness distribution of the 30 runs of each algorithm on the left, and the convergence curve of the best of those runs on the right. We can see that FGA outperforms the rest of algorithms of this comparison as it achieves the lowest fitness (both absolute and on average). Moreover, FGA is the best ranked algorithm for this study, according to the Friedman Rank. Having calculated the Wilcoxon p-value, we can say that the values reported are statistically significant. As was to be expected, RS produces the worst solution because it searches in the solution space without any information of the problem’s characteristics. Additionally, the results achieved by EA indicate configurations of the flows far worse than the ones achieved by FGA, which better represents the real city traffic. This confirms that the local search operator proposed (FGA) performs much better than the ordinary mutation implemented in an EA as was expected. Using the data from the 30 runs performed we have drawn a box plot, shown in Fig. 5(a), to represent the fitness distribution of the algorithms. This figure confirms the differences between the algorithms and how the fitness values of FGA are the lowest ones. Furthermore, in Fig. 5(b) we present the fitness evolution during the best run of each algorithm where the more appropriate behavior of the FGA is clearly depicted. Second, we have tested the best solution achieved by the FGA by running the simulation of the city with the configuration of the flows according to that solution. In Table 2 we can see the names of the sensors, the same names as given by the local council of Malaga, the real number of vehicles (third four-month period of 2014), the number of vehicles measured in SUMO when we used the flow values calculated by the FGA, and the percentage difference. We can observe that the differences are under 1% except for sensor 16 (9.96%). Moreover, the number of vehicles measured by sensors 7 and 8 in the simulation are exactly the same as in the real world. We have analyzed the anomaly observed in sensor 16 and found that the main source of vehicles for the street in which sensor 16 is placed (see Fig. 1), includes a left-turn intersection controlled by a traffic light. We have observed that many vehicles are waiting at this traffic light so that they cannot reach the sensor during the simulation. We think that a modification of the light cycle of that traffic light is