Keywords

13.1 Introduction

Nowadays, population growth seems to have a direct impact on daily life due mainly to society progress. Traffic jams, pollution and parking problems are some of the most common problems in relation to traffic networks. In this chapter, we present a methodology based on Optimization via Simulation (OvS) to select, from a group of nodes of a traffic network, the best alternative to increase the capacity of that network in the “Origin-Destiny Traffic Assignment Problem” (ODTAP), a subtype of the “Facility Location Problem” (FLP) and the “Network Traffic Design Problem” (NTDP) [17, 16]. Given a specific traffic network, which will suffer an increase in population, the main goal is to decide where to foment the installation of new urban infrastructure in order to minimize the cost of this and minimize the impact over the traffic system itself. In this context, we consider that the network already has a certain structure and a dynamic flow restricting possible configurations. To deal with the resolution of ODTAP, a Multi-Objective Particle Swamp Optimization Algorithm (MOPSO) was used together with Traffic Simulations (TS) in OvS based formalism.

The structure of this chapter goes as follow: in Sect. 13.1.1, a review of related works in the literature is presented; Sect. 13.2 explains the origin-destiny assignment problem and its formulation such as the optimisation problem; then, Sect. 13.3 shows an introduction to traffic simulation; Sect. 13.4 introduces the PSO algorithms for single and multi-objective problem; in Sect. 13.5, our optimisation approach is described; experiments and analysis of results are detailed in Sects. 13.6 and 13.7; finally, concluding remarks and future work are given in Sect. 13.8.

13.1.1 Literature Review

City growth reflects a progressive dynamic that is hardly ever planned, resulting in a decrease in the general performance of its sub-systems [41, 58]. In the case of the traffic sub-system, a population growth means more vehicles in the system, possible traffic jams, longer travel times, etc. [30, 41]. Even though this is not easy to control, it is possible to establish policies related to urbanization permits, to create industrial centers and to encourage activities in strategic zones, which will allow us to control the way the city grows and its associated traffic sub-system [18, 17, 28, 58]. In this line, the simulation [45, 40] revels itself as a useful tool to quantify the impact of a certain traffic network topology and the corresponding population assignment and, also, other problems related to traffic systems [56, 9, 29, 53, 26].

In this work, we present the problem of deciding where to foment the installation of urban, industrial and/or commercial complexes so that it has a minimum effect over the total traffic system with the minimum possible cost in infrastructure. We take into account that the network already has a certain structure and a dynamic flow restricting possible configurations. We name this proposed decision problem restatement of the traffic network and the underlying problem Origin-Destiny Traffic Assignment Problem (ODTAP). The ODTAP is an underlying problem of the “Network Traffic Design Problem” (NTDP). The NTDP is the NP-Hard problem [16] of building a traffic network in such a way that it minimizes the performing function of the system, i.e. the mean travel time in general [57]. In this context, several literature works exist in relation to NTDP, some of them related to the ODTAP issue and urban planning.

The metaheuristic approach has proven to be useful for different optimization problems [43, 6, 33, 42, 47, 25, 54, 1, 32, 36, 59, 27]. For the NTDP, there are some works for which the solution is obtained by heuristics and bio-inspired algorithms [24, 7, 19, 20, 10, 13, 44].

In this chapter, we explore the Optimization via Simulation (OvS) capacity to obtain good solutions for ODTAP considering that this tool has proved to be useful to solve a lot of problems that, due to their complexity, are difficult to mold analytically.

In [26] the authors apply OvS optimizing with Particle Swarm Optimization (PSO) and simulating with the SUMO- Simulated of Urban Mobility tool [5] to solve the scheduling of traffic lights cycle. Kalganova et al. [34] uses genetic algorithms in an OvS to solve the traffic lights synchronization problem. Finally, Horvat and Tosic [31] utilize OvS together with genetic algorithms for the design of non-restrictive traffic networks in pre-existing networks.

Regarding what we have said, our work considers land use in the suburbs and cities in order to plan the urban expansion and predicts its growth considering its final impact on the traffic organization. The proposed methodology combines a popular traffic simulator SUMO [5] with “Speed-constrained Multi-objective Particle Swamp Optimization” (SMPSO) in a Optimization via Simulation context [22] in order to improve the traffic network. The propose methodology take advantage of the infrastructure in the urban sprawl. Our objectives are minimizes the impact on the landscape to obtain accessibility and mobility facilities. The experiments and comparisons with other techniques reveal that our proposed OvS approach obtains significant profits in terms of traffic network improvement. By its own nature, the OVS algorithm presented here can be easily adapted to solve different multi-objective problems [23, 21].

13.2 Origin-Destiny Traffic Assignment Problem

In this section, we define our case of study (traffic systems) and the ODTAP. Then, we expose the characteristics of the problem to be optimized.

13.2.1 Traffic Systems

A traffic system is a complex system made up of at least two elements: a traffic network and a traffic demand.

A traffic network is an oriented graph in which the edges represent the streets, and the nodes, the changing points of those streets. In Fig. 13.1, we can see a simple traffic network, composed of two one-way streets at each intersected at the corner. It is represented by a graph with 4 edges and 5 nodes, in which nodes “O” are traffic origins, nodes “D” are traffic destinations and nodes “I” are corners. As it can be observed in the previous figure, there are different types of nodes and edges in one traffic network. Each edge is anathematized by a group of parameters: its length, the number of tracks of the traffic route, maximum circulating speed, and so on. The nodes are also defined by certain features which determine their participation in the model: kind of node (origin, destiny, lane extension, corner, etc.) and spatial coordinates, and so on. In our case, we are interested in identifying origin nodes or demand destiny nodes, as they generate or receive traffic flow. This kind of nodes needs to have associated information about maximum capacity and its rate of emitting and receiving vehicles.

Fig. 13.1
figure 1

Representation of streets intersection

Full size image

Traffic demand, on the other hand, is the set of all circulating vehicles in the system (taking into account the routes they follow and their starting time). In a practical way, traffic demand is more difficult to deal with than the network structure. As it is, in a real implementation it is highly difficult not to say impossible to know the routes and starting points of the total number of vehicles of the system. Besides, generally, traffic studies normally imply having to determine how routes configuration can vary against changes in the system, turning the previous group useless. That is the reason why the demand tends to be characterized by a generating group, like traffic flows (which is the characterization used in this work). A traffic flow is a group of vehicles that in a specific time window circulating from a node i to a node j. The previous definition does not include the routes followed by the vehicles; so, flows tend to be invariable to most of the changes to be done in a traffic system. Changes which imply an alteration in the flows (as it is the case of ODTAP) turn to be easier to handle, because one only has to vary the number of vehicles associated to each flow. In order to evaluate a traffic system, it is necessary to generate the routes for the involved vehicles taking into account the flows, for which you have several mechanisms: proportional assignment, shorter paths, balancing assignments.

13.2.2 Origin-Destiny Traffic Assignment Problem

“Origin-Destiny Traffic Assignment Problem” (ODTAP) [4] tries to absorb the impact of a variation in the traffic demand (by increasing or redistributing flows) through a restructuration of the origin nodes and destinations of traffic flows. For instance, if you want to determine where to set a new shopping mall in the city. In this situation, it will not necessarily increase the number of vehicles, but it will modify the routes followed by the same vehicles at some particular times. The decision of where to set the new mall (regulated by the city hall through permits and authorizations) can be assimilated to vehicle reassignment to new traffic flows that have as one of their extremes the shopping mall (either the destiny or the origin, depending on the time frame). Another example can be the installation of an industrial depot (in this the city hall directly controls the location). Apart from redirecting vehicle routes already existing in the system, the installation of the industrial depot will probably generate new vehicle flows from an to other cities (increased by the total number of vehicles circulating). Once again, from a traffic point of view, this is translated in a restructuration of existing traffic flows and in the generation of new ones having the depot as origin and destiny. As a final example we can name the setting off a new neighborhood in town, which will have a similar effect as the previous of producing new traffic flows arriving and departing from and to the neighbor.

The three examples stated in the previous paragraph become new traffic origins and destinies. In general, if the change in the system is carried out in an organized way, it is possible to establish areas in which this new origins and destinies can establish themselves, either through regulations or plans encouraging its reside). This tend to have a meaningfully high infrastructure cost, since they demand zone paving, basic service supply, an improvement in the entrance, and so on. Therefore, the problem is now how to do this assignment (i.e. selecting the nodes of a traffic network which will function as the new origins and destinies) with the minor possible effect on current traffic, on the one hand, and using the less possible amount of money for infrastructure. Measuring the cost impact is quite simple, but evaluating the impact on the traffic system is much more complicated. It normally uses a mean time metric, thus, the size of the impact on traffic is estimated by time variations of mean time of all the system vehicles.

Formally, the ODTAP is defined on n nodes belonging to the set N = {1, …, n}, with arc (edges) set E, and weight costs w k with k = 1, …, m; associated with the arcs, then, the ODTAP can be resumed as follow:

$$\displaystyle{ \min Z_{1} =\sum (t_{ijp} \cdot (Pop_{ijp} + X_{ijp})) }$$
(13.1)
$$\displaystyle{ \min Z_{2} =\sum (c_{i} \cdot X_{i}) }$$
(13.2)

subject to

$$\displaystyle\begin{array}{rcl} \sum (X_{i} + Pop_{i}) \leq Max\mbox{ }Population\mbox{ }at\mbox{ }Origin\mbox{ }i& &{}\end{array}$$
(13.3)
$$\displaystyle\begin{array}{rcl}\sum (X_{j} + Pop_{j}) \leq Max\mbox{ }Population\mbox{ }at\mbox{ }Destination\mbox{ }j& &{}\end{array}$$
(13.4)
$$\displaystyle\begin{array}{rcl} \sum (X_{ijp}) = Increase\mbox{ }in\mbox{ }Population& &{}\end{array}$$
(13.5)

Where, i ∈ N are the origins, j ∈ N are the destinies, p are the paths that connect i with j, Pop ijp is the current population that needs to travel from i to j through the path p, X ijp is the new assignment of population that will need to travel from i to j through the path p, t ijp is the travel time from i to j in the path p of the population and c i infrastructure cost necessary to support a population growth X i in node i. It is important to note that this characterization of the ODTAP should be enough for small instances in simple models. However, there is not always accurate information available about traffic travel times associated with the land use in urbanization planning. The genuine function of traffic travel time depends on many uncontrollable factors such as the shape of the roads, the amount of the street, the velocity of the vehicles, etc. Moreover, traffic congestion can be an important factor in the total journey of the population. For these reasons, the total travel time can be reformulated in Eq. (13.6).

$$\displaystyle{ \min Z_{1} =\sum (t_{ijp}((Pop_{11} + X_{11}),\ldots,(Pop_{nn} + X_{nn})) \cdot (Pop_{ijp} + X_{ijp})) }$$
(13.6)

Hence, it is considered the impact between the origin-destiny assignments into the traffic network and how it affects the Land Use planning

13.3 Traffic Simulations

Because we want to represent correctly the effect of variations in vehicle flows have on mean travel time, we will test that assignation by doing a simulation of the traffic flow. There are several ways in which you can simulate traffic flow in a traffic network, but in this work we choose to use continuum microscopic simulations.

A microscopic traffic simulation is a type of simulation of discrete time in which each vehicle behavior is modeled and simulated individually. Each vehicle in the traffic system is characterized with an identification code (“id”), a group of constant parameters regulating the route to follow, the moment in which the trip starts, maximum speed and the rest of the vehicle circulation criteria, and a group of variables with vehicle and speed information (they are updated in every interval t). The behavior of each vehicle follows simple laws, represented in an equation of the type stimuli-response where the main factor that determines the behavior of vehicles is the vehicle situated in front. These kinds of logics are known as “Car-Following” [40]. An example of this logic for a vehicle i is the following:

  • If there is no car in front (from the vehicle position of vehicle i to a critical distance), accelerate until reaching maximum speed.

  • If there is one car in front and its speed is lower than that of vehicle i, slow down to equal the speed of that vehicle.

  • If there is a car front and its speed is higher or the same as that of vehicle i, accelerate to reach the same speed or to reach the maximum speed of vehicle i, whatever is lower.

Apart from interactions with other vehicles, interactions with the rest of the system elements are added, like the traffic lights system.

Taking into account each vehicle information, it is possible to obtain afterwards variables aggregated to the system, as average speed, maximum waiting time [11, 37].

The main advantage this type of simulations offers is that modeling all its elements is comparatively easier than in the rest of the simulations, without the need of making assumptions about global system behavior. In fact, global behavior emerges as a consequence of interactions between each of its components.

13.4 Multiobjective Particle Swamp Optimization

As it was previously mentioned, with the objective of optimizing the ODTAP we use a multi-objective version of the “Particle Swamp Optimization” (PSO). In this section, we make an introduction to this metaheuristic and its adaptation to solve multi-objective problems.

13.4.1 Particle Swamp Optimization

The PSO algorithm first appeared in 1995 [35] and since then it has been used in a high number of problems [15, 2, 52, 3, 51]. PSO is based on bird flock behavior when they go searching for their food. In a flock, you can observe individual and group behavior. PSO algorithm is a population optimization algorithm where in each iteration we have a group of potential solutions (particles expressed in PSO terminology) that function as the birds of the flock. Every particle is defined based on their position p and its speed v in a space n − dimensional. Interaction after interaction, each one of them evolve according to the historic individual information recollected and to global historic information of the whole flock, updating its position and speed. This evolution is regulated by Eqs. (13.7) and (13.8):

$$\displaystyle{ v_{i,j}(t + 1) = w \cdot v_{i,j}(t) + c_{1} \cdot r_{1} \cdot (p_{i,j}(t) - x_{i,j}(t)) + c_{2} \cdot r_{2} \cdot (p_{g,j}(t) - x_{i,j}(t)) }$$
(13.7)
$$\displaystyle{ x_{i,j}(t + 1) = x_{i,j}(t) + v_{i,j}(t + 1) }$$
(13.8)

Where w is the inertia factor (which regulates the updating parameters speed), v i, j is the component of particle i in dimension j, c 1 and c 2 are the importance of individual and global information in each update, r 1 y r 2 ∼ U(0, 1) represent the differential acceleration of each particle, p i is the best value found by particle i (pbest) and p g is the best solution found in the neighborhood (gbest). During each interaction, the speed value is updated first, and then the position value of each particle.

Even though it is a kind of evolutionary algorithm, PSO presents the distinctive feature that the individuals belonging to the population do not compete with each other to monopolize the following interactions, but they even cooperate to find the global optimum.

13.4.2 Multi-Objective Particle Swamp Optimization

The original definition of PSO was thought to deal with mono-objective problems. However, there are several adaptations to deal with problems in which it is required to optimize several objectives simultaneously [50, 48, 38, 46].

In a multi-objective problem, the focus is no longer finding the global optimum but to obtain the best approximation to the Pareto Frontier of the system. For each point in the “Decision Space” there is an associated point in the “Objective Space”, being the latter a m-dimensional space with m equal to the number of objectives of the problem. Given that it exists several “Trade-Off” possible among the different objectives, the function of the optimization algorithm is finding the section in the frontier of the “Objective Space” where these “Trade-Off” are better than any other belonging to that space. In multi-objective optimization terminology, a solution i dominates a solution j if it is at least better in one of their objectives and better or the same in the rest. The aim of a multi-objective optimization algorithm is, then, to find the group of all solutions that are not dominated by any other solution of the space (thus, they are better than the rest) [38].

In this work, we decided to use the “Speed-constrained Multi-objective PSO” (SMPSO). This algorithm was presented in [14] and it is an adaptation of “Optimized Multi-Objective PSO” (OMOPSO) presented in [49]. Both have proven to have a good performance in comparison to other versions of the multi-objective PSO, and even compared to NSGA-II [14, 8]. The main problem in any multi-objective alteration based on Pareto Frontiers of the PSO consists in how to select the leader of each interaction (gbest). Both algorithms handle the leader selection with a fix size list of leader solutions, selected from the group of non-dominated solutions. In each interaction, solutions are added or eliminated from the list following the non-dominating criteria. To all the leaders, a “Crowding Factor”is calculated. In case the size of the list increases, the solutions with the worst “Crowding Factor” value are eliminated; this value performing as second classificatory factor of solutions. To estimate the speed v t of each swarm particle, a leader is chosen through a binary tournament based on the crowding value of the leaders.

Apart from this leader selection mechanism, the OMOPSO and the SMPSO have other features. The calculation of non-dominance follows non-strict dominance criteria o ε-dominance. is considered to be dominant with respect to a solution s if for all objectives f(q)∕(1 + ε) ≤ f(s) and to at least one objective f(q)∕(1 + ε) < f(s). Also, to avoid bias, the parameters c 1 and c 2 are selected randomly. Finally, mutation process of solutions is incorporated, taken from the namesake process used in Genetic Algorithms.

Unlike OMOPSO, SMPSO also adds a speed calculation restriction; with the goal of avoiding particles positioning varies from its feasible extremes without evaluating intermediate points. To do this, speeds are restricted according to the Eqs. (13.9) and (13.10).

$$\displaystyle{ -delta_{j} \leq v_{i,j}(t) \leq delta_{j} }$$
(13.9)
$$\displaystyle{ delta_{j} = \frac{upperLimit_{j} - lowerLimit_{j}} {2} }$$
(13.10)

13.5 Optimization Framework

In this section we explain the OvS Procedure developed to solve the Multi-Objective version of ODTAP.

13.5.1 General Procedure

In order to solve the ODTAP, we have chosen a formalism based on OvS [23]. In the OvS, the evaluation of the goodness of solutions is done by the execution of a simulator, which functions as the generator of necessary values to calculate the objective function. Both the optimizer and the simulator are independent from each other, connecting themselves in a black box way, having a system functioning as a controller between the two (Fig. 13.2). Apart from regulating the process, the controller has the function of translating the resulting solutions brought by the optimizers to configuration parameters for the simulator, at the same time it converts this last one outputs (data samples) into a value the optimizer can accept as an aptitude or fitness function. In this context, SUMO is used for simulation purpose [5] and the SMPSO to the optimization part. This framework is adapted from a framework used to solve the mono-objective version of the ODTAP, presented in [4], in which it replaces the use of Genetic Algorithms by the PSO. The OvS procedure was implemented in the popular software R  [39, 55] with the library RSUMO (http:www.modelizandosistemas.com.ar/p/rsumo).

Fig. 13.2
figure 2

OvS procedure as black box

Full size image

Figure 13.3 shows the interrelations between the R language, SUMO package and the PSO Procedure. Defined current traffic net and current traffic density, in order to absorb population growth and restrictions on the capacity increase in the nodes, the procedure generates SMPSO solutions to assess, in the form of increases in capacity per node. These solutions are translated into traffic flows and used to run the simulation. When the simulation process ends, the travel time statistics are consolidated in an average value of travel time and reentered the SMPSO to determine the quality of each solution and generate new solutions in the next iteration.

Fig. 13.3
figure 3

OvS procedure

Full size image

13.5.2 Solution Evaluation

In our model, SMPSO algorithm only assigns values to variables X i, j . That is to say, it defines the population growth (or decrease) in each origin-destiny pair of the potential origin-destiny pair group in which to invest on infrastructure. Based on this assignation, we can calculate each traffic flow Pop i, j + X i, j (keeping Pop i, j constante durante todas las evaluaciones). constant during all evaluation). With the group of traffic flows, SUMO con estimate the distribution of that flow among every path p that link i with j, and then assign starting moments to each of the vehicles involved in the routes. Once each vehicle is programmed, simulations starts and statistics are recollected about mean travel time.

The evaluation of the objective cost is much simpler. You only have to compute the number of vehicles assigned to each node and multiply it with the infrastructure cost. In case it is requested, you can modify the calculation by assuming the non-linearity of these costs, making them vary step by step with respect to the number of assigned vehicles, without altering the optimization model.

13.6 Experiments

In this section, we detail the experiments carried out to evaluate the quality of the solutions of the proposed optimization algorithm.

13.6.1 Scenarios

Building scenarios can be divided in two stages: construction of traffic networks and generation of initial traffic flows. To test the quality of the algorithm, a group of ten scenarios was designed based on traffic network like the “grid” type. Its network presents the peculiarity of having a great number of possible routes between two nodes, whichever they are. Doing small variations in this network, you can get traffic networks similar to those of various urbanization types. Summarizing, the transformation operations carried out were:

  1. 1.

    Given a grid network of size m ⋅ n, we determined a number of changes equals to \(\sqrt{min(m, n)}\).

  2. 2.

    For each change to be done, we set their type: “edge change” or “node change”.

    If the kind of change is “edge change”, we select a random edge from the network and we eliminate it.

    If the king of change is a “node change”, we select a random node from the network and we eliminate it and all the edges attached to it.

An example of a network construction can be seen in Fig. 13.4.

Fig. 13.4
figure 4

(a) Grid net. (b) Elimination of one arc. (c) Elimination of one node

Full size image

On the other hand, once it is defined the traffic network, it is necessary to generate the traffic demand associated to the situation previous to the population increase to be dealt with (every Pop ijp ). To do that, starting from the traffic networks previously created, an initial number of vehicles circulating during an hour of a simulated time in a random value between 100 ⋅ max(m, n) and 10 ⋅ m ⋅ n was fixed. Having the total number of vehicles, the origin and destiny of each one are randomly raffled from the network nodes through a non-repository sampling

Regarding the maximum capacity and cost of each node, the first one was fixes in a value similar to its current population assignation increased by a random factor contained between 1. 01 and 2. 00. The unitary costs of increased capacity were randomly fixed too, taking some range value [10: 100].

In total, we worked with 3 initial traffic networks, sized 10 ⋅ 10, 25 ⋅ 50 and 50 ⋅ 75, from which we generated 3 other daughter networks, according to the previously described technique. Afterwards, for each of these 9 networks, 3 random flows were created, leaving a total of 27 traffic scenarios. To every scenario a maximum capacity of every node and increase costs were randomly assigned. Every traffic scenario was evaluated with a population growth of 1. 05 and 1. 15, leaving 54 cases of study defined in total.

13.6.2 Tests

To evaluate how well our algorithm approximates to the problem Pareto frontier, for each scenario 10 runs were carried out. To create the Pareto frontier associated to the scenario, all generated solutions by each 10 run were consolidates and the Pareto frontier of this new data was calculated. This gave us a Global Estimated Pareto frontier for the total scenario, made up by the non-dominance solutions found in every run. That global estimated Pareto frontier is the one used as a pattern to measure the quality of the found solutions en each individual run.

Two solution quality indicators were measured: “Convergence” and “Uniformity” “Convergence” is calculated by averaging the minimum Euclidean distance of each point of the Pareto frontier obtained in one run of the algorithm with the Global Estimated Pareto frontier. This method of estimating the convergence is called “Generational Distance”. The complete index is shown in Eq. (13.11):

$$\displaystyle{ generational\text{ }distance = \frac{\sqrt{\sum _{i=1 }^{N }d_{i }^{2}}} {N} }$$
(13.11)

Where N is the number of solutions to be compared with the Pareto Frontier and d i is the minimum distance from solution i to the Pareto Frontier.

Moreover, the “uniformity” is calculated by Eq. (13.12).

$$\displaystyle{ uniformity = \frac{d_{f} + d_{l} +\sum _{ i=1}^{N-1}\vert d_{i} -\bar{ d}\vert } {d_{f} + d_{l} +\bar{ d}(N - 1)} }$$
(13.12)

Where d f and d l are the minimum Euclidean distances between the ends of the Global Estimated Pareto Frontier and the estimated Pareto Frontier in current run, d i is the distance between the solution i and the solution i + 1 from the estimated Pareto Frontier in current run, \(\bar{d}\) is the average of N − 1 distances d i and N is the number of points in the estimated Pareto Frontier in current run.

For a further comparison, we have studied the performance of the NSGA-II [12] for the same experimental procedure as our proposal.

13.6.3 Algorithm Parameters

The parameters under which the SMPSO was executed are the following:

  • Probability of Mutation = 0. 5

  • w = 0. 4

  • ε = 0. 05

  • Swarm Size = 50

  • Max Number of Generations = 100

On the other hand, the simulation time to evaluate each solution was set in 1. 200 s.

13.7 Results

In this section, we present the results of the experiments done.

13.7.1 Convergence

The average of generational distance between found solutions by the algorithm and the global estimated Pareto frontier is kept in low values, with a deviation coefficient oscillating between 0. 27 and 0. 41. In Table 13.1 it can be observe convergence values for one of the scenarios of size 10 ⋅ 10 with an increase in vehicle population of 1. 15. The convergence average of this group is of 0. 40384 and the desviation coefficient is 0. 38759. It can be noticed that the majority of the runs were kept in the same generational distance range, except two atypical observations in one of which we can see the effect of the presence of local optimum (item 4). The lower generational distance in item 3 is because a group of solutions kept a low mean travel time with a low infrastructure cost. For this specific scenario, the algorithm was run once more with a swarm size of 250 individuals. The convergence results are shown in Table 13.2. An improvement in the indicators can be noticed.

Table 13.1 Convergence and Uniformity of grid 10 ⋅ 10 and population increase of 1. 15
Full size table
Table 13.2 Convergence and Uniformity of grid 10 ⋅ 10 and population increase of 1. 15 (swarm size = 250)
Full size table

13.7.2 Uniformity

Uniformity finds its average in low values, but with a higher desviation coefficient than in convergence (oscillates between 0. 33 and 0. 46). Table 13.1 shows uniformity values for the presented case in Sect. 13.7.1. It can be observed that the behavior here is different, with a significant number of solutions with good uniformity values, and some solutions with a high uniformity. Once it was run again the algorithm with a swarm size of 250, it was impossible to observe significant improvements in this indicator.

13.7.3 Evolution of the Solutions Generated by the Algorithm

In Figs. 13.5 and 13.6 you can see the solutions from iterations 25 and 100 for one run of the algorithm, compared with the Pareto Frontier. The adjustment in the iteration 100 is very good, with almost all solutions belonging to the Pareto Frontier. It further notes that while there is not a great diversity of solutions, the Pareto frontier is swept almost entirely. At iteration 25 can see that while convergence of the solutions is very low, the algorithm found several individuals who belong to the frontier. Moreover, in Figs. 13.7 and 13.8 you can see the evolution of the population and the Estimated Pareto Frontier in iterations 25, 50, 75 and 100. In the earlier iterations, the dispersion of solutions is big and there are few solution in the estimated Pareto Frontier. In the last iterations, the dispersion is lesser and the majority of solutions are near to the estimated Pareto Frontier.

Fig. 13.5
figure 5

Iteration 25. The line is the Pareto Frontier, points are the individual of the iteration

Full size image
Fig. 13.6
figure 6

Iteration 100. The line is the Pareto Frontier, points are the individual of the iteration

Full size image
Fig. 13.7
figure 7

Evolution of population

Full size image
Fig. 13.8
figure 8

Evolution of estimated Pareto Frontier

Full size image

It’s interesting see that the convergence to the Pareto Frontier is faster for the combination of “low cost-high travel time” than the “high cost-low travel time”. This is a consequence of the structure of the problem: the infrastructure costs are constant, but the mean speed is a dynamic function of the vehicles assignation in the origins and destination of traffic flows.

13.7.4 Comparison with NSGA-II Metaheuristic

The same set of experiments were running under a NSGA-II metaheuristics, in order to check the quality of SMPSO solution. In Table 13.3 are shown the result of 10 runs for the same scenario that is shown in Table 13.2.

Table 13.3 Convergence and Uniformity of grid 10 ⋅ 10 and population increase of 1. 15 (swarm size = 250)
Full size table

According to the “Wilcoxon Signed Rank” the convergence of solution founded by the SMPSO algorithm are better than the NSGA-II, but for a low margin (\(p\text{-}value\cong 0.03\)). The uniformity is similar for both algorithms.

13.8 Conclusions

In this chapter, we presented an algorithm that combines SMPSO with a traffic simulation to solve a multi-objective version of the ODTAP. The obtained results show a good performance, being able to find a great approximation to the problem Pareto frontier with a swarm size not so big. The results get better when the swarm size increases, scarifying an increase in the computation time. The SMPSO also showed a slightly better performance than the NGSA-II for this problem.

Using simulation as an evaluating function of the optimization algorithm lets us faithfully represent the effect of policies to be implemented in the system, without the distorting effects of an analytical simplification. The algorithm has showed a fast convergence rate for the “low cost-high travel time” side of the Pareto Frontier. This is consequence of the dynamic nature of the speed of cars in the system, which varies in function of the assignments in the origins and destinations. The use of simulations allows us to evaluate this dynamic in a easy way.