Page 54 - 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. 54
ertain payload, travel a certain distance and must eventually programming language, installation is possible on all systems,
return to its starting depot [3], [11]. If any of the restrictions is which have the support for the language and installed PIP package
violated, penalty function is used to punish the vehicle with a manager. Due to further development, new algorithms are being
certain mark-up value. Because MDVRP is represented as a added to the framework and the previously implemented
directed graph, every node of customer and depot has its own x algorithms are being further improved [13].
and y coordinate pair [4], [5]. When looking for a solution to the
problem, we usually divide it into three phases, collectively One of the algorithms implemented in NiaPy is also PSO, which
referred to as decision making or decision hierarchy in MDVRP. is a population stochastic optimization algorithm and belongs to
We call them the merging phase, the routing phase and the the EA group. The algorithm, which is based on the behavior of
scheduling phase. In the first phase, we try to allocate customers the swarms of animals such as fish and birds was first developed
to the individual depots according to the distance, which is present by James Kennedy and Russel Eberhart in the mid-90s of the 20th
between them. The second phase, with previously divided century. It was created as a by-product of the desire to graphically
customers, draws up several routes, which vehicles will take. represent various flight patterns of animals [6], [8], [14], [15].
After that, each path is sequenced in the third phase [3], [11].
The PSO population is referred to as a swarm and instances inside
Figure 1 is an example of MDVRP problem, where letters A and of it flying particles, which are constantly moving inside of a
B represent depots or vehicles with a maximum capacity of 10 hyperdimensional search space. The position between particles is
units of weight, and circles with numbers represent different determined with social-psychology tendency to be better and to
customers. There are four paths between depots and customers, imitate other, closer instances [6], [8]. Each particle is moving
based on genotype numbers that are converted to phenotype with its own speed, knows its previous locations and never goes
numbers by the first conversion method. The routes were extinct, because there is no selection, mutation or recombination
determined according to the previously mentioned MDVRPs [10]. Velocity is changed in every generation/iteration. For
decision hierarchy. changing velocity, we have three different parts, namely previous
velocity, cognitive component and social component
Figure 1. MDVRP example.
First component represents the memory of the previous direction
2.1 Particle Swarm Optimization for MDVRP motion and prevents the current flight direction from drastically
changing. Second component expresses the performance of the
The system we developed for experiment purposes, supports current particle with respect to past results. Lastly, third
importing any EA from the library or microframework called component expresses the performance of the current particle with
NiaPy. It was developed by researches from the Faculty of respect to some group of particles or neighbors around it [8].
Electrical Engineering and Computer Science and the Faculty of
Economics and Business from University of Maribor. Main During the operation, we need to store some other information
purpose for developing the framework was lack of easy and fast like information about the best found location of each particle
use of EA, since the own implementation of a single algorithm is (pbest), information about the best found location of the currently
often difficult and time-consuming. The library architecture is selected part of the swarm (lbest) and information about the best
divided into two parts, which we call algorithms and benchmarks. found location of the particle of any swarm (gbest). When finding
In addition to the developed normal EA versions, we can also find new top locations, current values need to be updated [6], [8]. The
hybrid variants, such as hybrid bat algorithm and self-adaptive PSO algorithm uses fitness function for guidance of the search
differential evolution algorithm. The framework supports EA over the search space. When the stopping condition is meet,
startup and testing with predefined and generated comparisons, algorithms returns global best solution found [10].
while also allowing the export of results in three different formats,
which are LaTeX, JSON and Excel [13]. 3. IMPLEMENTATING PSO FOR MDVRP
Although some similar frameworks for managing nature-inspired
algorithms already exist, NiaPy differs mainly in minimalism and For the purpose of the experiment we used programming language
ease of use. Its main functions are weak coupling, good Python to develop a system, which allows application of any EA
documentation, user friendliness, fair comparison of algorithms, from NiaPy library to the different MDVRP examples. The
quick overview of results and friendly support community. NiaPy system can handle CSV cases of VRP made by Cordeau [12].
project is designated as open source and licensed under an MIT
license. Because the framework is developed in Python The system consists of several different classes, one of which is
class Evaluation, which is responsible for solving the problem. In
the class we firstly convert given genotype from imported EA to
an appropriate phenotype, which can be then used to tackle the
problem. First genotype to phenotype conversion assigns
ascending index number to each gene, according to its value in the
array. Second conversion assigns genes, representing nodes or
customers, to specific vehicles based on the value scale, made of
number of depots.
The fitness function of the program itself is quite simple, since it
only adds up all the paths made to the total distance. This then
represents the fitness value of the current instance. It is also
important to add penalty to the result, if solution violated any of
the limitations of the MDVRP. This is done by checking the limits
during the program operation and in case of a violation, send the
current result into the penalty function, which then adds a certain
distance unit to the distance already completed.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 54
Koper, Slovenia, 10 October
return to its starting depot [3], [11]. If any of the restrictions is which have the support for the language and installed PIP package
violated, penalty function is used to punish the vehicle with a manager. Due to further development, new algorithms are being
certain mark-up value. Because MDVRP is represented as a added to the framework and the previously implemented
directed graph, every node of customer and depot has its own x algorithms are being further improved [13].
and y coordinate pair [4], [5]. When looking for a solution to the
problem, we usually divide it into three phases, collectively One of the algorithms implemented in NiaPy is also PSO, which
referred to as decision making or decision hierarchy in MDVRP. is a population stochastic optimization algorithm and belongs to
We call them the merging phase, the routing phase and the the EA group. The algorithm, which is based on the behavior of
scheduling phase. In the first phase, we try to allocate customers the swarms of animals such as fish and birds was first developed
to the individual depots according to the distance, which is present by James Kennedy and Russel Eberhart in the mid-90s of the 20th
between them. The second phase, with previously divided century. It was created as a by-product of the desire to graphically
customers, draws up several routes, which vehicles will take. represent various flight patterns of animals [6], [8], [14], [15].
After that, each path is sequenced in the third phase [3], [11].
The PSO population is referred to as a swarm and instances inside
Figure 1 is an example of MDVRP problem, where letters A and of it flying particles, which are constantly moving inside of a
B represent depots or vehicles with a maximum capacity of 10 hyperdimensional search space. The position between particles is
units of weight, and circles with numbers represent different determined with social-psychology tendency to be better and to
customers. There are four paths between depots and customers, imitate other, closer instances [6], [8]. Each particle is moving
based on genotype numbers that are converted to phenotype with its own speed, knows its previous locations and never goes
numbers by the first conversion method. The routes were extinct, because there is no selection, mutation or recombination
determined according to the previously mentioned MDVRPs [10]. Velocity is changed in every generation/iteration. For
decision hierarchy. changing velocity, we have three different parts, namely previous
velocity, cognitive component and social component
Figure 1. MDVRP example.
First component represents the memory of the previous direction
2.1 Particle Swarm Optimization for MDVRP motion and prevents the current flight direction from drastically
changing. Second component expresses the performance of the
The system we developed for experiment purposes, supports current particle with respect to past results. Lastly, third
importing any EA from the library or microframework called component expresses the performance of the current particle with
NiaPy. It was developed by researches from the Faculty of respect to some group of particles or neighbors around it [8].
Electrical Engineering and Computer Science and the Faculty of
Economics and Business from University of Maribor. Main During the operation, we need to store some other information
purpose for developing the framework was lack of easy and fast like information about the best found location of each particle
use of EA, since the own implementation of a single algorithm is (pbest), information about the best found location of the currently
often difficult and time-consuming. The library architecture is selected part of the swarm (lbest) and information about the best
divided into two parts, which we call algorithms and benchmarks. found location of the particle of any swarm (gbest). When finding
In addition to the developed normal EA versions, we can also find new top locations, current values need to be updated [6], [8]. The
hybrid variants, such as hybrid bat algorithm and self-adaptive PSO algorithm uses fitness function for guidance of the search
differential evolution algorithm. The framework supports EA over the search space. When the stopping condition is meet,
startup and testing with predefined and generated comparisons, algorithms returns global best solution found [10].
while also allowing the export of results in three different formats,
which are LaTeX, JSON and Excel [13]. 3. IMPLEMENTATING PSO FOR MDVRP
Although some similar frameworks for managing nature-inspired
algorithms already exist, NiaPy differs mainly in minimalism and For the purpose of the experiment we used programming language
ease of use. Its main functions are weak coupling, good Python to develop a system, which allows application of any EA
documentation, user friendliness, fair comparison of algorithms, from NiaPy library to the different MDVRP examples. The
quick overview of results and friendly support community. NiaPy system can handle CSV cases of VRP made by Cordeau [12].
project is designated as open source and licensed under an MIT
license. Because the framework is developed in Python The system consists of several different classes, one of which is
class Evaluation, which is responsible for solving the problem. In
the class we firstly convert given genotype from imported EA to
an appropriate phenotype, which can be then used to tackle the
problem. First genotype to phenotype conversion assigns
ascending index number to each gene, according to its value in the
array. Second conversion assigns genes, representing nodes or
customers, to specific vehicles based on the value scale, made of
number of depots.
The fitness function of the program itself is quite simple, since it
only adds up all the paths made to the total distance. This then
represents the fitness value of the current instance. It is also
important to add penalty to the result, if solution violated any of
the limitations of the MDVRP. This is done by checking the limits
during the program operation and in case of a violation, send the
current result into the penalty function, which then adds a certain
distance unit to the distance already completed.
StuCoSReC Proceedings of the 2019 6th Student Computer Science Research Conference 54
Koper, Slovenia, 10 October
