Reducing Vehicle Emissions and Fuel Consumption in the City by Using Particle Swarm Optimization

Reducing Vehicle Emissions and Fuel Consumption in the City by Using Particle Swarm Optimization A. Carolina Olivera 1,∗ Departamento de Ciencias e Ingenier´ıa de la Computaci´on, Universidad Nacional del Sur, Av. Alem 1253, 8000, Bah´ıa Blanca, Argentina J. Garc´ıa-Nieto, E. Alba Dept. de Lenguajes y Ciencias de la Computaci´on, University of Malaga, ETSI Inform´atica, Campus de Teatinos, Malaga - 29071, Spain Abstract Nowadays in current cities the increasing levels of pollution emissions and fuel consumption derived from the road traffic directly affect to the air quality, the economy, and specially the health of citizens. Therefore, improving the traffic flow is a mandatory task in order to mitigate such critical problems. In this work, we propose a Swarm Intelligence approach for optimizing signal light timing programs in metropolitan areas. In this way, we can improve the traffic flow of vehicles with the global target of reducing their fuel consumption and gas emissions (CO and NOx). In this article we optimize the timing programs of signal lights and analyze their effect in pollution by following the standard HBEFA as traffic emission model. In concrete, we are focused here on two large and heterogeneous urban instances located in the cities of Malaga and Seville (in Spain). In comparison with timing programs of signal lights predefined by experts (close to real ones), our proposal obtains significant reductions in terms of the emission rate and the total fuel consumption. Key words: Traffic Signal Timing, Particle Swarm Optimization, SUMO Microscopic Simulator of Urban MObility, HBEFA Traffic Emission Model. ∗Corresponding author. Email addresses: [email protected], {jnieto,eat}@lcc.uma.es (J. Garc´ıa-Nieto, E. Alba). 1Authors acknowledge funds from the CICE of the Junta de Andalucia, under contract P07-TIC- 03044 (DIRICOM http://diricom.lcc.uma.es) and Spanish Ministry of Sciences and Innovation (MICINN) and FEDER under contracts TIN2011-28194 (RoadMe http://roadme.lcc.uma.es) and TIN2008-06491-C04-01 (M* http://mstar.lcc.uma.es). Jos´e Garc´ıa-Nieto is supported by grant BES-2009-018767 from the MICINN. Ana 1. Introduction In current metropolitan areas, the increasing levels of air contamination and fuel consumption derived from the urban road traffic have become highly serious problems that directly affect to the C. Olivera acknowledges CONICET, the ANPCyT for Grant PICT 2011 Category I-B and SeCyT (UNS) for Grant PGI 24/N026. Preprint submitted to Elsevier Science July 2, 2012 air quality, the economy, the building/structure maintenance, and especially to the health of citizens. Improving the traffic flow of vehicles is a mandatory task in order to mitigate such critical issues. Traditionally, traffic congestion has been dealt with changes in urban infrastructures (e.g. sense of traffic in streets or roundabouts), although this is usually not possible and always expensive. Recently, a number of works in the literature proposed the optimization of timing programs of signal lights as one of the most influent methods to improve the flow of vehicles [20,22,23,28]. In this sense, the use of automatic intelligent methods have demonstrated their usefulness to the optimization of timing programs of traffic lights [3,23]. However, authors in general have addressed specific cases of study with few intersections and small number of signal lights [5], and most of them apply ad-hoc algorithms designed only for one specific instance [3,23]. The use of artificial intelligent techniques for large and heterogeneous urban areas is still an open issue. Moreover, the optimization of timing programs from the perspective of the reduction of gas emission and hydrocarbons consumption have not ever been dealt, to the best of our knowledge. All this motivated us to propose in this work an optimization strategy, based in a Particle Swarm Optimization (PSO) algorithm [16], to find successful signal light timing programs with regards to two main factors: emissions of CO and NOx, plus the global amount of fuel consumed by vehicles. Several features led us to use PSO instead of other evolutionary methods: – First of all, using a Fitness Cloud preliminary analysis [31], we tested that PSO is able to tackle the signal light timing problem (SLTP) efficiently. A description of this analysis is given in Section 5.3. – Second, the PSO is a well-known algorithm shown to perform a fast converge to quasioptimal solutions [8]. This is a highly desirable feature for the optimal timing program of traffic lights, where new adaptive (and automatically computed) schedules should be required to face updating events in traffic scenarios. – Third, the Standard PSO is easy to implement, and requires few tuning parameters [8,16]. – Fourth, PSO is a kind of Swarm Intelligence algorithm that can inform us on future issues to deal with this problem by using independent agents for online adaptation (a promising line of research). Coupled with PSO, we use in our optimization strategy the microscopic simulator SUMO (Simulator of Urban Mobility) [4] for the evaluation of optimized timing programs codified as vector solutions. Such timing programs are used in signal lights that control the flow of vehicles through a given scenario (urban instance). As done in other similar initiatives [13,14,21], we use a traffic simulator since it provides an immediate and continuous source of information about the vehicles flow. In the case of SUMO, we can also work with the traffic emission model HBEFA (HandBook Emission FActors) [15] for road transport in order to recollect information about the emission rates and the fuel consumption. This information is used by PSO to evaluate the timing programs of signal lights. As main contributions of this work, we can mention the following ones: – We propose an optimization strategy for the reduction of emissions in large and heterogeneous urban areas with hundreds of vehicles and signal lights (high dimensionality and complexity). – We use real information: we have modeled two urban scenarios located in the cities of Seville and Malaga, in Spain. Our optimization strategy has been then evaluated on realistic instances. – In comparison with predefined (by experts) timing programs close to real ones, our PSO will be shown to obtain quantitative improvements in terms of the two main objectives: reducing the emission rates and the global fuel consumption. – We consider for the first time the use of a swarm intelligent approach coupled with the traffic emission model HBEFA [9], for the reduction of pollution and fuel consumption in urban areas. The structure of this article is as follows. In Section 2, a review of related works in the literature is presented. Section 3 explains the SUMO simulation tool and the HBEFA emission model. Then in Section 4, our optimization approach is described. Experiments and analysis of results are detailed in Section 5. Finally, concluding remarks and future work are given in Section 6. 2 2. State of the Art In the last decade, a number of works can be found in the related literature that deal with the traffic congestion problem by means of accurate signal lights timing programs [6,18,23,24,26,29]. In all these approaches, global trip times and waiting times of vehicles in traffic lights are optimized, although none of them considered the influence of solutions on emissions and fuel consumption factors. On the contrary, a few of works can be found that incorporated emission/consuming factors into the traffic control strategies by enhancing the traffic flow [11,20] with different results. In [11], just for one intersection (crossroad), the improvement of traffic lights timing programs and their impact on the final emission rates were examined. In [20], the authors proposed a signal time model that reduce the vehicles’ delays, the fuel consumption, and the gas emissions by considering the cycle length and the green time of traffic lights in one intersection in Nanking city (China). In [7], a microscopic simulator was used for the evaluation of traffic control strategies in a sub-network selected from the Haidian district of Beijing. This last work was focused on analyzing the relation between vehicles’ emissions and their instantaneous speeds/accelerations, although traffic signal optimization was not considered and only two control strategies were studied. At the same time, advanced algorithms have emerged as accurate techniques for solving traffic lights scheduling and traffic control problems [23,26]. However, the environmental impact of the traffic flow is ignored or partially considered. An example of this can be found in [32] where a Genetic Algorithm (GA) was used for the air pollution reduction considering the optimization of traffic signals in one intersection. In [33], the authors showed how the cycle programs of traffic lights affect the gas concentrations on a given road intersection by using Neural Networks. Concerning Swarm Intelligence approaches, few of them can also be found for the schedule of traffic lights. One of the most representative was proposed in [6], where the authors applied a PSO for training a fuzzy logic controller located in each intersection by determining the effective time of green for each phase of the traffic lights. Peng et al. [25] presented a PSO with isolation niches to the schedule of traffic lights. In that work, a purely academic small instance with a restrictive one-way road with two intersections was used to test the PSO. More recently, an Ant Colony Optimization (ACO) [12] has been proposed to the signal light timing. In this work, two interesting uncertainty and convergence analysis were performed, although in the scope of one simple traffic intersection. In these last works, environment factors were not considered at all, and only academic instances were studied. All these approaches focused on different aspects of the traffic light scheduling. As a summary, four limitations can be found in general: – They tackled limited vehicular networks with very few traffic lights and a small number of other elements (roads, intersections, directions, etc.). In contrast, our PSO can find optimized timing programs for large scenarios with hundreds of traffic lights, vehicles, and other city elements. – They were designed for only one specific scenario. Some of them studied the influence of the traffic density. Our approach can be easily adapted to different scenario topologies and cities. – In most of the cases, existing works were not compared against other techniques. Our PSO is compared here against two different approaches: a Random Search algorithm (to show that it is intelligent), and the cycle program generator provided by SUMO (that uses human expert knowledge). – Previous works did not consider the optimization of environmental factors. Our approach considers a series of factors (CO,NOx, and fuel consumption) that, coupled with pure traffic flow indicators (vehicles arriving at destinations, global trip times, etc.), provide the expert with optimized signal light timing programs: a small step to the future smart city. 3 … … … … … … 40 5 40 10 36 6 22 … … … … … … … intersection id=“i+1” intersection id=“i” phaseduration=“36” Solution:a particle position for the PSO algorithm Current state of intersection i=“rrrr GGr rrrr GGr” Figure 1. Timing program (phase duration) of signal lights within intersections. Integer codification inside a PSO solution 3. SLTP: Timing and Emission Models A urban traffic scenario is basically composed by: intersections, traffic lights, roads, directions, and vehicles moving through their own different routes. The traffic lights are located in intersections and control the flow of vehicles by following their programs of color states, and timing cycles or phase durations. In this context, all traffic lights located in the same intersection are governed by a common program, since they have to be necessarily synchronized for traffic security. In addition, for all the traffic lights in an intersection, the combination of color states during a cycle period is always kept valid [19] and it must follow the specific traffic rules of intersections, in order to avoid vehicle collisions and accidents. In this sense, we work only with valid combinations of color states for each intersection, which are kept feasible during the optimization process. This avoids invalid combinations of color states and restricts the optimization approach to work only with feasible states. From an environmental point of view, since different timing programs lead to different flow of vehicles, their underlying speeds, accelerations, and decelerations potentially result in different levels of emissions [33]. In short, decelerations occur before red lights, whereas green lights cause the acceleration of vehicles. Therefore, traffic emissions are likely influenced by timing program of traffic lights [7]. In this context, timing and emission models are detailed in the following subsections. 3.1. Timing Model Our main objective is to find optimized timing programs (TP) for all the signal lights located in a given urban area with the aim of reducing the emissions and the fuel consumption of vehicles. Specifically, timing programs are refereed to the time span that a set of signal lights (in a junction) keep their color states. At the same time, these programs have to coordinate signal lights in adjacent intersections with the aim of improving the global flow of vehicles circulating according to traffic regulations. For this reason, we have focused on a microscopic view of the management of traffic agents but, at the same time, we want to evaluate the behavior of all the vehicles in the complete urban scenario during a given time interval (macroscopic analysis). An example of this mechanism can be observed in Figure 1, where the intersection with id="i" contains seven phases with durations 40, 5, 40, 10, 36, 6, and 22 seconds (simulation steps). In these phases, the states have twelve signals (colors), corresponding each one of them to one of the twelve signal lights located in the studied intersection. These states are the valid ones generated by SUMO (Simulation of Urban Mobility) [4] attending to real traffic rules. In this instance, the fifth phase contains the state “Grrr GG Grrr GG” meaning that six traffic lights are in green (G), and the six others are in red (r) during 36 seconds. The following phase changes the state of the four traffic lights to other valid combination, for example, 4 “yGGG rr yGGG rr” (ymeans yellow) during 6 seconds, and so on. The last phase is followed by the first one, and this cycle (timing) is repeated during all the analysis time. All the intersections in the complete scenario perform their own timing cycles of phases at the same time, hence conforming the global schedule of signal lights. As commented before, computing TP consists in optimizing the combination of phase durations of all traffic lights (in all intersections) with the aim of improving the global flow of vehicles. A final indication in this sense concerns the behavior of the vehicles involved in a SUMO simulation, that depends on both road directions and speed. SUMO employs a space-discrete extended model as introduced by Krauß et al. [17]. In this model, the streets are divided into cells and the vehicles circulating through the streets go from one cell to another if both, the sense and the direction are allowed. The speed of each vehicle depends on its distance to the vehicle in front of it, with a preestablished maximum speed typical of urban areas (50 km/h in our study). 3.2. HBEFA: Road Traffic Emission Model Many research efforts have attempted to develop emission of road transportation models. Due to their simplicity, a macroscopic point of view has become very popular [2] in this sense. This kind of model computes fuel consumption (FC) and emissions factor (EF) based on average link speeds in a global way. That is, changes of vehicle’s speed and accelerations levels are computed as mean values for the whole network. For this reason, many microscopic models have been proposed. In particular, HBEFA (Handbook of Emission Factors for Road Transport) provides emission factors for all current vehicle categories: PC (Passenger Car), LDV (light delivery vehicles), HDV (heavy duty vehicles), urban buses, motor cycles, and for a wide variety of traffic situations. The HBEFA allows experts to select different types of emission factors (EFs). These EFs depend on many variables of vehicles such as: size, type, cylinder capacity, fuel mode of the vehicle (gasoline or diesel), type of exhaust technology (with/without catalytic converter), driving style (acceleration and speed), road gradient, and the maintenance [9]. SUMO version 0.12.0 [4] allows us to simulate vehicular environmental factors based on HBEFA. Therefore, it is possible to define vehicles with information about acceleration, deceleration times, maximum velocity, and even their HBEFA-based emission class (PC, LDV, HDV, etc). Then, after a simulation procedure with SUMO, we can obtain information about CO,NOx, fuel consumption, and other pollutant agents to evaluate the obtained timing programs by our PSO. For this study, we retrieve the information about CO and NOxemissions, and fuel consumption. 4. Optimization Strategy This section describes our optimization approach to compute the optimal timing programs of traffic lights. It details the solution encoding, the fitness function, and finally the global optimization procedure. 4.1. Solution Encoding In our approach, the optimal TP is encoded by means of a vector of integers (see Figure 1) following the SUMO structure of programming cycles (timing), where each element represents a phase duration of one state of the signal lights involved in a given intersection. In spite of its simplicity, this solution representation allows our PSO to take into account the dependency of variables (epistasis), not only between phase durations of a state of traffic lights in an intersection, but also between traffic lights in adjacent ones. 4.2. Fitness Function In order to evaluate each timing program solution (s) generated by our PSO, the following fitness function is minimized, which considers the information obtained from the events happening during the traffic flow analyzed: 5 Ftp(s) = (CO+NOx+F u)(s)+ω·(Gtt(s)+(C(s)×St) V2(s) + P) (1) The main objective is to maximize the number of vehicles that reach their destinations (V) and minimize both, emission levels (CO and NOx) and fuel consumption (Fu), during the simulation time (St). The global trip time of all the vehicles (Gtt) has to be also minimized. The number of vehicles that arrive to their destinations is squared (V2(s)) in order to prioritize it over the other terms and factors. Obviously, the number of vehicles that do not reach their destinations and remain circulating C(s) after the simulation has to be minimized. The global trip time concerns an aggregation of the trip time of vehicles that reach their destinations during the simulation process. On the contrary, vehicles with uncompleted travels C(s) consume all the simulation time St and then, an additional penalization is induced by multiplying these two factors. It is worth mentioning that terms in Equation 1 are in the range of values [1e+ 0 · · · 5e+ 2] and therefore, additional weighting values were not considered in this formulation. Only the value ω which is set to 0.5 is considered in order to enhancing environmental terms in the overall fitness computation. Finally, the balanced proportion of colors in the phase duration of the states should promote those states with more traffic lights in green located in streets with a high number of vehicles circulating, and traffic lights in red located in streets with a low number of vehicles moving. The proportion of colors in each phase (ph) of all the tl intersections can be formulated as follows: P= tl ∑ k=0 ph ∑ j=0 sk,j ·(Gk,j rk,j ),(2) where Gk,j is the number of traffic lights in green, and rk,j is number of traffic lights in red in the phase state j(with duration sk,j) and in the intersection k. The minimum value of redk,j is 1 in order to avoid division by 0. 4.3. Optimizing Timing Programs with PSO The optimization strategy is composed by two main parts: the Particle Swarm Optimizer (PSO), and the simulation procedure with the SUMO traffic microsimulator. The PSO algorithm [16] is a population-based metaheuristic inspired by the social behavior of birds within a flock, and was initially designed for continuous optimization problems. In PSO, each potential solution to the problem is called particle position and the population of particles is called the swarm. We have followed the specification of the Standard PSO 2011 [10]. In this algorithm, each particle position xiis updated each iteration gby means of the Equation 3. xi g+1 =xi g+vi g+1 (3) where term vi g+1 is the velocity of the particle, given by the Equation 4. vi g+1 =w·vi g+Gri g−xi g+HS(Gr, ∥Gr −xg∥) (4) with Gri g=xi g+p′i g+l′i g 3(5) and p′i g=xi g+c·(pi g−xi g) (6) l′i g=xi g+c·(li g−xi g) (7) In this formula, pi gis the best solution that the particle ihas seen so far, li gis the best particle of a neighborhood of kother particles (also known as the social best) randomly (uniform) selected from the swarm, and wis the inertia weight of the particle (it controls the trade-off between exploration and exploitation). The acceleration coefficient c > 1 is a normal (Gaussian) random value with µ= 1/2 and ρ= 1/12. This coefficient is sampled anew for each component of the velocity vector. Finally, HS is a distinctive element of the Standard PSO 2011 with regards to the previous ones. It is basically a random number generator within a Hypersphere space, with Gr as center of gravity. That is, Gr is calculated as the equidistant point to p′ g,l′ g, and xg. This is a new rotation invariance mechanism provided by the Standard PSO 2011 to (pos- 6 sibly) avoid the intrinsic coordinate dependence showed by all previous versions of PSO [10]. Since the optimal SLTP requires solutions encoded with a vector of integers (representing phase durations), we have used the quantisation method provided in the standard specification of PSO 2011 [10]. This quantisation is applied to each new generated particle (in Equation 3), and transforms the continuous values of particles to discrete ones. It consists of a Mid-Thread uniform quantiser method as specified in Equation 8. The quantum step is set here to ∆ = 1. Q(x)=∆· ⌊x/∆+0.5⌋(8) Algorithm 1 Standard PSO 2011 for the SLTP 1: initializeSwarm() 2: while g < maxIterations do 3: for each particle xi gdo 4: bn g=bestNeighbourSelection(xi g, n) 5: vi g+1=updateVelocity(w, vi g, xg, φ1, pg, φ2, bn g) 6: xi g+1=Q(updatePosition(xi g, vi g+1)) 7: evaluate(xi g+1) //SUMO Simulation and Eq. 1 8: pi g+1=update(pi g) 9: end for 10: end while Algorithm 1 describes the pseudo-code of the Standard PSO 2011 for the optimal SLTP. The algorithm starts by initializing the swarm (Line 1). The corresponding elements of each particle (solutions) are initialized with random values representing the phase durations. These values are within the time interval [5,60] ∈Z+, and constitute the range of possible time spans (in seconds) a traffic light can kept a signal color (only green or red, the time for yellow is a constant value set in sumo to 5 seconds). Then, for a maximum number of iterations, each particle flies through the search space updating its velocity and position (Lines 4, 5, and 6), it is then evaluated (Line 7), and its personal best position piis also updated (Line 8). Finally, the best particle found so far is returned. The simulation procedure is then used for assigning a quantitative quality value (fitness) to the solutions, thus leading to optimized timing programs tailored to a given urban scenario instance. This task is tackled by the SUMO microscopic traffic simulator, which accepts new timing programs of traffic lights and compute the required values in Equation 1. When our PSO generates a new solution, it is used for updating the timing program. Then, SUMO is started to simulate the instance with streets, directions, obstacles, traffic lights, vehicles, speed, routes, etc., under the new defined schedule of timing programs. After the simulation, SUMO returns the global information necessary to compute the fitness function. Each solution evaluation (Line 7 at Algorithm 1) requires a simulation procedure since vehicle routes in SUMO are generated deterministically. Each new timing program is then loaded for each simulation procedure. In this sense, what real traffic light human schedulers actually demand are constant timing programs for specific areas and for preestablished time periods (rush hours, nocturne periods, etc.), which led us to take this focus. 5. Experiments and Results In this section we present the experimental framework followed to assess the performance of our PSO algorithm for creating optimized TPs. First, we describe the scenario instances, the implementation details of our approach, and the parameter settings. Later, results and comparisons to other techniques are presented. A study of the resulting timing programs is also carried out in order to show the actual benefits of using our proposal and their impact into the living environment of urban areas. 5.1. Urban Scenario Instances As we are interested in developing an optimization solver capable of dealing with close-to-reality generic urban areas, we have generated two scenarios by extracting actual information from real digital maps. These two scenarios cover similar areas of approximately 0.75 km2, and they are physically located in the cities of Malaga and Seville, in Spain. The information used concerns: traffic rules, traffic element locations, buildings, road directions, streets, intersections, etc. Moreover, we 7 Figure 2. Process of creation of real-world instances for study. Urban centre of Malaga (36◦43’01”N 4◦25’58”O) and Seville (37◦38’14”S 5◦97’23”O) instance views. After selecting the area of interest (Google Earth view), it is interpreted by means of the OpenStreetMap tool, and then exported to SUMO format have set the number of vehicles circulating, as well as their speeds by following current specifications available in the Mobility Delegation of the City Hall of Malaga (http://movilidad.malaga.eu/). This information was collected from sensorized points in certain streets obtaining a measure of traffic density in several time intervals. In the case of Seville we consulted the Mobility Delegation of Seville Council (http://www.trajano.com/). In Figure 2, the selected areas of the two cities are shown with their corresponding snapshots of Google Earth, OpenStreetMap, and SUMO. This figure illustrates the process of generating the traffic network instances. The specific features of these areas are as follows: (i) Malaga. In the zone between the city center and the harbor. This second scenario (Figure 2, top) is composed by streets with different widths and lengths, and several roundabouts. It contains junctions including from 4 to 16 traffic lights each one. The main avenues found in this area are: Andaluc´ıa, Am´ericas and Aurora avenues, Hilera, and Lehmberg Ruiz streets. (ii) Seville. Located in the popular district of Nervi´on in the city center of Seville (Figure 2, bottom), it is made up of intersections between streets including each one from 4 to 17 traffic lights. The complete area shows a representative organization with almost all the junctions connecting between three and four streets. The main avenues crossing this neighborhood are: Men´endez Pelayo, Eduardo Dato, San Francisco Javier, Montoto, Galv´an, and Buhar´ıa. We have chosen these two scenarios since they constitute different metropolitan areas with heterogeneous structures and traffic organizations. The number of studied intersections is 70 for the two instances, with 250 circulating (PC and LDV types) vehicles through each one of them. We have to notice that in spite of having in both instances a similar number of intersections (70), the number of signal lights is not exactly the same, since they contain different intersection shapes (304 traffic lights in Malaga and 368 ones in the case of Seville). In the study, each vehicle performs its own route from its own origin to destination circulating with a maximum speed of 50 km/h (typical in urban areas). The routes were previously generated by following random paths. The simulation time was set 8 Table 1 SUMO and PSO parameters Solver Phase Parameter Value Simulation Time (steps) 500 s Area 0.75 km2 SUMO Details Number of Vehicles 250 Vehicle Speed 0-50 km/h Vehicles Types PC/LDV N. of Studied Intersections 70 Max. N. of Evaluations 9,000 Swarm Size 30 Particle Size (N. Traffic Lights) 368 304 PSO Parameters Local Coefficient (φ1) 2.0 Social Coefficient (φ2) 2.0 Maximum Inertia (wmax ) 0.5 Minimum Inertia (wmin ) 0.1 Velocity Truncation Factor (λ) 0.5 to 500 seconds (iterations of microsimulation) for each instance. This time was determined as a maximum time for a car to complete its route, even if it must stop in all the traffic lights along its way. Vehicles are located in their own origins and they move from the initial simulation steps. When a vehicle leaves the scenario network, it reaches its destination and it will not appear again. 5.2. Experimental Setup We have used the implementation in C++ of the PSO algorithm provided by the MALLBA [1] framework. The simulation phase is carried out by executing (for the evaluation of particles) the traffic simulator SUMO release 0.12.0 for Linux. The experiments were performed in the computing facilities of the Department of Computer Science of the University of Malaga (Spain). Most of them are equipped with modern dual core processors, 1GB RAM, and Linux Debian O.S. They operate under a Condor [30] middleware platform that acts as a distributed task scheduler (each task dealing with one independent run of PSO). For each scenario instance we have carried out 30 independent runs of our PSO. The swarm size was set to 30 particles performing 300 iteration steps, hence resulting a number of 9,000 solution evaluations (SUMO simulations) per run and instance. As previously mentioned, the particle size directly depends on the number of traffic lights of each in- Algorithm 2 Pseudocode of RANDOM 1: generate(x) //initial solution 2: i←0 3: while i < Max Number of Evaluations do 4: generate(xi) //new solution 5: if f(x)≥f(xi)then 6: x←xi 7: end if 8: i←i+ 1 9: end while stance. The remaining parameters are summarized in Table 1. These parameters were set after preliminary executions. Specific parameters of PSO were selected as recommended in the study about the convergence of this algorithm in [8]. Additionally, we have implemented a Random Search algorithm, also in the scope of the MALLBA library, with the aim of establishing comparisons against our PSO. Thus, by performing the same experimentation procedure with PSO and Random Search algorithm we expect to obtain some insights into the power of our proposal (how much intelligent it is). The pseudocode of the Random Search algorithm (RANDOM from now on) is shown in Algorithm 2. The maximum number of evaluations was set to 9,000, as for PSO. SUMO provides a deterministic algorithm for generating cycle programs (SCPG). Then we also compare the cycle programs obtained by our PSO against the ones obtained by SUMO. This last algorithm basically consists in assigning to the phase durations of the traffic logics fresh values in the range of [6,31], according to three different factors: (i) the proportion of green states in the phases, (ii) the number of incoming lanes to the intersection, and (iii) the braking time of the vehicles approaching to their traffic lights. Further information about this algorithm can be found in [4]. 5.3. Evolvability of PSO on the SLTP Landscape Previous to the performance experimentation, we have carried out a Fitness-Cloud analysis [31] with the aim of verifying whether our optimization strategy with PSO is able to successfully tackle the signal light timing problem or not, for the scenario 9 [19] J. Leung, L. Kelly, and J. H. Anderson. Handbook of Scheduling: Algorithms, Models, and Performance Analysis. CRC Press, Inc., Boca Raton, FL, USA, 2004. [20] X. Li, G. Li, S. Pang, X. Yang, and J. Tian. Signal timing of intersections using integrated optimization of traffic quality, emissions and fuel consumption: a note. Transportation Research Part D: Transport and Environment, 9(5):401 – 407, 2004. [21] G. Lim, J. Jin Kang, and Y. Hong. The optimization of traffic signal light using artificial intelligence. In FUZZ-IEEE, pages 1279–1282, 2001. [22] J. McCrea and S. Moutari. A hybrid macroscopicbased model for traffic flow in road networks. European Journal of Operational Research, In Press, Corrected Proof:–, 2010. [23] J. S´anchez Medina, M. Gal´an Moreno, and E. Rubio Royo. Applying a traffic lights evolutionary optimization technique to a real case: “Las Ramblas” area in Santa Cruz de Tenerife. Evolutionary Computation, IEEE Transactions on, 12(1):25 –40, feb. 2008. [24] T. Nagatani. Effect of speed fluctuation on greenlight path in 2d traffic network controlled by signals. Physica A: Statistical Mechanics and its Applications, In Press, Accepted Manuscript:–, 2010. [25] L. Peng, M. Wang, J. Du, and G. Luo. Isolation niches particle swarm optimization applied to traffic lights controlling. In 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference, pages 3318 –3322, dec. 2009. [26] N. M. Rouphail, B. B. Park, and J. Sacks. Direct signal timing optimization: Strategy development and results. Technical report, In XI Pan American Conference in Traffic and Transportation Engineering, 2000. [27] D. J. Sheskin. Handbook of Parametric and Nonparametric Statistical Procedures. Chapman & Hall/CRC, 2007. [28] J. C. Spall and D. C. Chin. Traffic-responsive signal timing for system-wide traffic control. Transportation Research Part C: Emerging Technology, 5(3-4):153 – 163, 1997. [29] F. Teklu, A. Sumalee, and D. Watling. A genetic algorithm approach for optimizing traffic control signals considering routing. Computer-Aided Civil and Infrastructure Engineering, 22:31–43, 2007. [30] D. Thain, T. Tannenbaum, and M. Livny. Distributed computing in practice: the condor experience. Concurrency - Practice and Experience, 17(2-4):323– 356, 2005. [31] L. Vanneschi, M. Clergue, P. Collard, M. Tomassini, and S. Vrel. Fitness clouds and problem hardness in genetic programming., 2004. [32] S. Zhou, X. Yan, and C. Wu. Optimization model for traffic signal control with environmental objectives. In Proceedings of the 2008 Fourth International Conference on Natural Computation - Volume 06, pages 530–534, Washington, DC, USA, 2008. IEEE Computer Society. [33] P. Zito. Influence of coordinated traffic lights parameters on roadside pollutant concentrations. Transportation Research Part D: Transport and Environment, 14(8):604 – 609, 2009. 16