The results of the work simulations of both systems are combined in the following figure:
Figure 11.Results of the simulations of loads
Each of the first four columns demonstrates the oscillations in the outputs of the systems simulations, that are the minimum, maximum and average values calculated from one hundred annual simulations.
Firstly, it is possible to analyze the accuracy and validity of simulation techniques, based on the inverseCDFmethod. The results are presented by the third and fourth columns of the bar charts, where the left column represents the system where each day some number of cars has not arrived due to the unforeseen circumstances. The fifth (yellow) columns, that represents the annual real average amount of garbage for each area, are used as the item to compare with in this case. Based on the graphs, it is possible to conclude that de-spite the insignificant variability in the results due to the stochastic nature of the models, the outputs of the simulation are very close to the averaged values. Moreover, the addition of the realism to the model through the daily dropping of some number of cars does not cause significant changes in the simulation results, which shows the relative stability of the system to the uncertain situations. These facts prove the accuracy and reliability of constructed models as well as the validity of the application of simulation techniques in this case.
The analysis of the simulation results of the system based on the assumption about max-imum loads for cars provides less optimistic conclusions. The first and second columns of the bar charts, which represents the outputs of the system with the additional condition about daily change in the number of cars and the classical system, can be compared with the fifth columns representing assumed annual transported amount of garbage for each area. Despite the relatively small influence of additional conditions on the system, which indicates its resistance to uncertain situations, for some areas, the results of the
simula-tions significantly differ from the expected loads. Moreover, the difference has a different character for each area, that is, for some areas the values of the simulation results are higher than the expected loads, and for other areas, they are lower. The natural conclu-sion is that this system has to be optimized and, moreover, the optimized model has to consider individual features of the loads generation for each area.
6 OPTIMIZATION
In order to optimize both problems, it was decided to use the algorithm of differential evo-lution (DE), which is a method of multi-dimensional mathematical optimization related to the class of stochastic optimization algorithms. Its advantage is that it does not require the computation of derivatives of objective functions, unlike classical optimization meth-ods, such as gradient descent and quasi-newton methods. DEworks just with values of multidimensional real-valued functions, that is very convenient for the current case. DE is a population-based optimizer, where the population is the set of a predefined number Np of D-dimensional vectors. DE handles three population vectors xg, vg, ug for each generation g, wherexg is a current population at the beginning of each generation, i.e. a population before any changes;vg is the intermediate population of mutant vectors;ug is a population of mutant vectors after the application of crossover step. The size of popu-lationsNp and vector dimensionDremains unchanged for all generations. Considering example where the current population consists of vectors xg = (xj,i,g)j=1,...,D, i=1,...,Np, wherej denotes the vector component index andithe population member, the evolution steps can be described by following stages:
1. Initialization. For the first generation (g = 0) the initial population is usually generated by the following set: (xj,i,g) = rj · (bj,U − bj,L) + bj,L where rj ∼ U(0,1), bj,U andbj,Lare upper and lower boundaries for the corresponding dimen-sion j. For other populations initial generation is the population survived after previous step.
2. Mutation. The most popular way to calculate mutant vector is: vi,g = xr1,g + F ·(xr2,g−xr3,g), wherexr1,g, xr2,g, xr3,g are mutually different randomly chosen members of current population andF > 0is a scaling factor.
3. Crossover. The process of acceptance of the mutations for the trial populationug is based on crossover probabilityCr ∈[0,1]:
ui,j,g=
4. Selection. The algorithm of selection of a new population is based on the values of the cost functionf
xi,g+1 =
ui,g, ifui,g ≤f(xi,g) xi,g, otherwise .
Thus, one can see that the selection algorithm is similar to the process of evolution where only the strongest representatives of the old generation and children who surpass their parents survive in new generation.
The sequence of steps described above will be repeated until the population will satisfy the required criteria or a specified number of generations is reached [31].
Thus, the algorithm does not require strict mathematical formulation of the cost function.
It is enough just to define the way of the calculation of its output value and its parameters.
To demonstrate the operation of the algorithm, it can be used to find the minimum of a simple two-parameter function
x2+xy+y2+x−y+ 1 =z
This function has an extremum at the pointx=−1, y = 1, which is the minimum of the function andz(−1,1) = 0. The application ofDEalgorithm is presented in the following table:
Table 5. DEalgorithm: simple case without noise
x initial y initial z(x,y) → x final y final z(x,y)
0.6521 1.7927 4.6675 → -1.0000 1.0000 1.0e-15·0.1110 0.6897 1.9200 5.2562 → -1.0000 1.0000 1.0e-15·0 1.0559 0.9099 4.0496 → -1.0000 1.0000 1.0e-15·0 0.8733 0.8703 3.2831 → -1.0000 1.0000 1.0e-15·0 1.4336 1.4895 7.3531 → -1.0000 1.0000 1.0e-15·0 1.3928 1.1540 6.1178 → -1.0000 1.0000 1.0e-15·0 0.9142 0.5648 3.0204 → -1.0000 1.0000 1.0e-15·0 1.3835 1.5268 7.2143 → -1.0000 1.0000 1.0e-15·0 1.1588 0.5970 3.9527 → -1.0000 1.0000 1.0e-15·0.1110 1.3209 0.5284 4.5143 → -1.0000 1.0000 1.0e-15·0.1110 0.9858 1.8117 6.2144 → -1.0000 1.0000 1.0e-15·0 0.5245 1.8193 4.2441 → -1.0000 1.0000 1.0e-15·0.2220 0.5664 0.0158 1.8807 → -1.0000 1.0000 1.0e-15·0 1.4127 0.7700 5.3192 → -1.0000 1.0000 1.0e-15·0.1110 1.3336 1.3507 6.3870 → -1.0000 1.0000 1.0e-15·0 1.1322 0.4052 3.6317 → -1.0000 1.0000 1.0e-15·0 0.5917 0.5482 2.0184 → -1.0000 1.0000 1.0e-15·0 1.4162 1.4214 7.0336 → -1.0000 1.0000 1.0e-15·0 0.9926 1.8848 6.5165 → -1.0000 1.0000 1.0e-15·0
This table presents the initial generation (from the left side) where each population was randomly generated and the generation generated on 100th algorithm iteration (from the right side). As can be seen from the table the optimizer coped well with his task. However, this case is quite artificial and usually cost functions may have a stochastic character. And DEalgorithm is supposed to cope with searching for minimum within this conditions as well. This phenomenon can be illustrated by the application of the algorithm to the pre-vious example with modernized cost function where instead Instead of the last operation of adding +1 some small random noise will be added. The table below represents the results of the algorithm for the case described above, where two objective functions with stronger and weaker noise were used.
Table 6. DEalgorithm: simple case without noise
x1 final y1 final z1(x1,y1) ↔ x2 final y2 final z2(x,y) -0.9967 1.0268 -0.9975 ↔ 0.0317 0.0081 0.0234 -0.9761 0.9781 -0.9986 ↔ -1.5377 0.9318 -0.6685 -0.9870 1.0153 -0.9980 ↔ -1.0861 1.2945 -0.9324 -0.9889 0.9991 -1.0010 ↔ -1.4768 0.9390 -0.7418 -1.0195 1.0344 -1.0008 ↔ -1.7041 1.1206 -0.5754 -0.9936 0.9846 -1.0011 ↔ -0.7759 0.5003 -0.8123 -1.0002 0.9998 -0.9997 ↔ -2.7427 1.4991 1.4178 -0.9932 0.9941 -0.9998 ↔ -0.7825 1.4400 -0.6638 -1.0054 1.0101 -1.0002 ↔ -0.8345 1.3807 -0.7641 -0.9669 0.9857 -0.9989 ↔ -1.1633 0.6282 -0.7752 -1.0473 1.0261 -0.9975 ↔ -0.5629 -0.4204 0.5884 -0.9993 0.9780 -0.9992 ↔ -1.5567 1.6031 -0.6610 -0.9853 0.9822 -1.0009 ↔ -0.6880 1.1531 -0.8310 -1.0266 1.0326 -0.9989 ↔ -1.1173 0.9875 -0.9836 -0.9997 1.0225 -0.9985 ↔ -2.3992 1.8536 0.4914 -1.0177 1.0022 -0.9993 ↔ -2.0944 1.9560 0.0646 -1.0308 1.0066 -0.9979 ↔ -0.0664 1.3294 0.2879 -1.0085 0.9817 -1.0019 ↔ -1.8162 1.1249 -0.4202 -0.9932 1.0075 -0.9998 ↔ -0.7466 1.5760 -0.4587 -0.9969 1.0104 -1.0012 ↔ -1.4248 1.4393 -0.8136
The left part represents the results of searching for the minimum for cost function with slight noise generated as normally distributed random numbers with zero mean and unit variance scaled by multiplication by 0.001. The right part, respectively, is the result of the optimizer for the cost function with stronger noise generated as normally distributed random numbers with zero mean and unit variance. Based o the results of simulation it is possible to make several conclusions. Firstly, DEalgorithm is able to optimize the objective function under uncertainty. However, the more stochastic the cost function, the less accurate the results of the algorithm work.
6.1 Optimization of the traffic system
For the calculation of the cost function in case of traffic simulation, it was decided to consider the total number of cars from all areas which were not serviced during annual simulation. The parameters of cost function under optimization are the mean valueµand standard deviationσof the normal distribution which is used for generation of the service time initially where determined as µ = 30andσ = 5 for all variants of noise. The op-timal parameters were defined separately for each variant of noise. Taking into account the physical aspects of the real service process, some limitations were introduced into the optimization algorithm. Thus, theµparameter was set to be no less than ten and the de-pendences betweenµandσwere also considered. Consequentially, If the new candidate does not meet the boundary conditions described above, the value of the corresponding parameter increases significantly. This action automatically excludes him from the set of potential candidates for a new generation.
The traffic simulation system is stochastic, with both the service time and the arrival time being indeterminate. For this reason, the result of the algorithm is also not accurate and it strongly depends on the generated noise. Thus, there is no possibility to identify the opti-mal value of each parameter as a unit number. As an inference, we can only determine the confidence interval for the parameters and demonstrate how the cost function oscillates within the frameworks described above.
In case of exponential noise in the arrival time, the optimal parameters for noisy service time distribution fluctuate within the following intervals: µfrom10,04to21,96 and σfrom0,34to4,31. The change in the cost function, representing the total annual num-ber of cars from all areas that were not serviced, is presented in the following graph:
Figure 12.Optimized service time in case of ATN1
The blue square in down part represents the confidence interval for theµandσparameters and green square presents changes in the cost function under these constraints.
Considering the average values of the parameters which were calculated after running of the optimization multiple times, it is also possible to estimate how the waiting time in the queue has changed. The average parameters areµ= 13.52andσ = 1.84.
Figure 13. Optimized daily average amount of waiting time in queue for one car from each area in case of ATN1
As it can be seen from the pictures, in case if the approximate normal service time varies from 10 to 21 minutes and the random approximate deviations are from 1 to 13 minutes, the waiting time does not exceed three minutes for each area in contrast to the original case when it was around seven. And the number of not served cars, which is annually from 54 to 92, decreased approximately twice as compared to the initial simulation. These facts indicate successful optimization.
Considering the case of normal arrival time noise, the optimal parameters for noisy service time distribution fluctuate within approximately the same intervals:µfrom10,02to20,78 and σfrom0,23to3,34. The graphical illustration of the work of optimizer is presented be-low:
Figure 14. Optimized daily average amount of waiting time in queue for one car from each area in case of ATN2
if, similarly with the previous case, the averaged values of the parameters when simulating the waiting time will be considered, which are µ = 13.6 andσ = 1.37, then the graph will be as follows:
Figure 15. Optimized daily average amount of waiting time in queue for one car from each area in case of ATN2
Thus, in case of ATN2 and service time fluctuating from 10 to 21 minutes with inaccura-cies from 1 to 10 minutes, the number of annually unserviced cars variates from 3 to 22 which is significantly less than it was with non-optimized parameters. And the waiting time decreased from 4 to maximum 1 minute. Thus, in this case, the optimization also served well.
The confidential interval in case of uniform distribution of the noise in the service time is following: µfrom11,33to19,95 andσfrom0,23to4,25. The representative graph is located below:
Figure 16. Optimized daily average amount of waiting time in queue for one car from each area in case of ATN3
The averaged waited time with averaged optimal parametersµ= 14.3andσ = 1.5is the following:
Figure 17. Optimized daily average amount of waiting time in queue for one car from each area in case of ATN3
Thus, in case of uniformly distributed fluctuations in arrival time from 0 to 30 minutes and service time between 11 and 20 minutes with the delays approximately from 1 to 13
minutes, just maximum 20 cars will be not serviced during the year instead of 140 before optimization. At the same time, the waiting time will not exceed 1,5 minutes for each car in contrast with averaged 5 minutes of waiting in the non-optimized system.