Page 55 - Fister jr., Iztok, Andrej Brodnik, Matjaž Krnc and Iztok Fister (eds.). StuCoSReC. Proceedings of the 2019 6th Student Computer Science Research Conference. Koper: University of Primorska Press, 2019
P. 55
ther important class is Graph, which is responsible for Table 2. Test results of solving the example pr04
drawing different graphs and connecting nodes of customers and
depots on it with paths. Each customer and depot object have its Algorithm Fitness Run time
own coordinate pair x and y, which is then plotted on a graph and (unit of distance) (seconds)
connected to paths, obtained from the current result object. The GA 3906.96
final graph thus illustrates all the paths made by vehicles between ES 13282.01 3808.14
all the customers and depots. The class can also draw a final bar DE 13640.05
graph of all fitness values across generations, received through the PSO 3713.49
objects of all solutions. Image Class on the other hand, captures HS 13476.95 3714.37
an image from a drawn graph and saves it to the appropriate 13603.86 3865.54
directory. It can also use previously stored images to generate 13573.96
animated gifs that show the composition of the found route.
PSO achieved the second-best fitness value when solving the third
The program itself starts in its main function, where we specify MDVRP case - pr08 (6 depots/vehicles and 144 customers),
desired parameters, such as population size, number of
generations to be made, number of instances inside one which is interesting because the example was a bit easier that he
generation, seed value and genotype to phenotype conversion. previous one. It also solved the problem as the fastest
Results are displayed on the console at the end of the solving. optimization algorithm of all tested. Overall, the algorithm proved
to be a good choice for solving the specific case. Test results are
4. RESULTS OF THE EXPERIMENT recorded in Table 3.
The experiment we conducted was performed on five MDVRP Table 3. Test results of solving the example pr08
cases and with five competitive evolutionary algorithms (Particle
Swarm Optimization PSO, Evolutionary Strategy ES, Genetic Algorithm Fitness Run time
Algorithm GA, Differential Evolution DE and Harmony Search (unit of distance) (seconds)
HS), using settings of 10 generations, 5 instances and 20 units of GA 3906.96
distance as the penalty value. Each of five test cases was run with ES 13282.01 3808.14
a random seed value between 1.000 and 10.000 and with first DE 13640.05
genotype to phenotype conversion. Unfortunately, the testing was PSO 3713.49
only performed once due to poor hardware capabilities, which HS 13476.95 3714.37
were processor Intel Core i5-6267U 3.300Ghz, graphic card Intel 13603.86 3865.54
Iris Graphics 550, Kingston 8Gb RAM and Liteon 250Gb SSD. 13573.96
The experiment was performed on the Linux operating system
Ubuntu 18.04. The fourth MDVRP case pr14 (4 depots/vehicles and 192
customers) was similar in complexity to the second, but with one
The exact NiaPy algorithms, which were used in the testing are depot less. PSO solved the problem well again, with its fitness
GeneticAlgorithm for GA, EvolutionStrategyMpL for ES,
DifferentialEvolution for DE, ParticleSwarmAlgorithm for PSO result reaching second place, and ES reaching last place. With
and HarmonySearch for HS. Settings of individual evolutionary 3709.32 seconds, PSO solved the problem fastest once again. All
algorithm were left at default values from the NiaPy framework. the results can be seen in Table 4.
When testing on the first and simplest example of the problem Table 4. Test results of solving the example pr14
pr00 (2 depots/vehicles and 10 customers), PSO fund the fourth
best route, which is not exactly good. It was overtaken by all the Algorithm Fitness Run time
algorithms except the ES, which achieved an even worse fitness (unit of distance) (seconds)
result. Comparing on the execution time of the algorithms, the GA 3896.00
PSO achieved the best value, although it was quite like the DE ES 13723.88 3732.49
and HS values. All the results described are shown in Table 1. DE 13885.56 3755.60
PSO 13494.85
Table 1. Test results of solving the example pr00 HS 3709.32
13500.67 3950.66
13873.96
Algorithm Fitness Run time The toughest test case pr20 (6 depots/vehicles and 288 customers)
(unit of distance) (seconds) was with 21085.43 units of distance best resolved by PSO – the
GA rest of the algorithms were left behind by about 200 units of
ES 688.02 168.59 distance or more. It achieved the third-best computing time, and
DE interestingly GA achieved first, although its fitness value wasn’t
PSO 774.52 155.93
HS 711.88 148.61 very good. All the test results are shown in Table 5.
749.02 148.43
679.10 148.78
GA achieved the best fitness value in solving the second MDVRP Table 5. Test results of solving the example pr20
case pr04 (4 depots/vehicles and 192 customers). Again, the PSO
found the fourth best route with 13603.86 units of distance, and Algorithm Fitness Run time
the worst path was found by the ES. This time, PSO solved the (unit of distance) (seconds)
problem with the second fastest time, as it was overtaken by the GA 7341.09
DE for only one second. Results are shown in Table 2. ES 21610.55
DE 7345.13
21397.89
7487.69
21224.04
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 55
Koper, Slovenia, 10 October
drawing different graphs and connecting nodes of customers and
depots on it with paths. Each customer and depot object have its Algorithm Fitness Run time
own coordinate pair x and y, which is then plotted on a graph and (unit of distance) (seconds)
connected to paths, obtained from the current result object. The GA 3906.96
final graph thus illustrates all the paths made by vehicles between ES 13282.01 3808.14
all the customers and depots. The class can also draw a final bar DE 13640.05
graph of all fitness values across generations, received through the PSO 3713.49
objects of all solutions. Image Class on the other hand, captures HS 13476.95 3714.37
an image from a drawn graph and saves it to the appropriate 13603.86 3865.54
directory. It can also use previously stored images to generate 13573.96
animated gifs that show the composition of the found route.
PSO achieved the second-best fitness value when solving the third
The program itself starts in its main function, where we specify MDVRP case - pr08 (6 depots/vehicles and 144 customers),
desired parameters, such as population size, number of
generations to be made, number of instances inside one which is interesting because the example was a bit easier that he
generation, seed value and genotype to phenotype conversion. previous one. It also solved the problem as the fastest
Results are displayed on the console at the end of the solving. optimization algorithm of all tested. Overall, the algorithm proved
to be a good choice for solving the specific case. Test results are
4. RESULTS OF THE EXPERIMENT recorded in Table 3.
The experiment we conducted was performed on five MDVRP Table 3. Test results of solving the example pr08
cases and with five competitive evolutionary algorithms (Particle
Swarm Optimization PSO, Evolutionary Strategy ES, Genetic Algorithm Fitness Run time
Algorithm GA, Differential Evolution DE and Harmony Search (unit of distance) (seconds)
HS), using settings of 10 generations, 5 instances and 20 units of GA 3906.96
distance as the penalty value. Each of five test cases was run with ES 13282.01 3808.14
a random seed value between 1.000 and 10.000 and with first DE 13640.05
genotype to phenotype conversion. Unfortunately, the testing was PSO 3713.49
only performed once due to poor hardware capabilities, which HS 13476.95 3714.37
were processor Intel Core i5-6267U 3.300Ghz, graphic card Intel 13603.86 3865.54
Iris Graphics 550, Kingston 8Gb RAM and Liteon 250Gb SSD. 13573.96
The experiment was performed on the Linux operating system
Ubuntu 18.04. The fourth MDVRP case pr14 (4 depots/vehicles and 192
customers) was similar in complexity to the second, but with one
The exact NiaPy algorithms, which were used in the testing are depot less. PSO solved the problem well again, with its fitness
GeneticAlgorithm for GA, EvolutionStrategyMpL for ES,
DifferentialEvolution for DE, ParticleSwarmAlgorithm for PSO result reaching second place, and ES reaching last place. With
and HarmonySearch for HS. Settings of individual evolutionary 3709.32 seconds, PSO solved the problem fastest once again. All
algorithm were left at default values from the NiaPy framework. the results can be seen in Table 4.
When testing on the first and simplest example of the problem Table 4. Test results of solving the example pr14
pr00 (2 depots/vehicles and 10 customers), PSO fund the fourth
best route, which is not exactly good. It was overtaken by all the Algorithm Fitness Run time
algorithms except the ES, which achieved an even worse fitness (unit of distance) (seconds)
result. Comparing on the execution time of the algorithms, the GA 3896.00
PSO achieved the best value, although it was quite like the DE ES 13723.88 3732.49
and HS values. All the results described are shown in Table 1. DE 13885.56 3755.60
PSO 13494.85
Table 1. Test results of solving the example pr00 HS 3709.32
13500.67 3950.66
13873.96
Algorithm Fitness Run time The toughest test case pr20 (6 depots/vehicles and 288 customers)
(unit of distance) (seconds) was with 21085.43 units of distance best resolved by PSO – the
GA rest of the algorithms were left behind by about 200 units of
ES 688.02 168.59 distance or more. It achieved the third-best computing time, and
DE interestingly GA achieved first, although its fitness value wasn’t
PSO 774.52 155.93
HS 711.88 148.61 very good. All the test results are shown in Table 5.
749.02 148.43
679.10 148.78
GA achieved the best fitness value in solving the second MDVRP Table 5. Test results of solving the example pr20
case pr04 (4 depots/vehicles and 192 customers). Again, the PSO
found the fourth best route with 13603.86 units of distance, and Algorithm Fitness Run time
the worst path was found by the ES. This time, PSO solved the (unit of distance) (seconds)
problem with the second fastest time, as it was overtaken by the GA 7341.09
DE for only one second. Results are shown in Table 2. ES 21610.55
DE 7345.13
21397.89
7487.69
21224.04
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 55
Koper, Slovenia, 10 October
