=Paper=
{{Paper
|id=Vol-1853/p13
|storemode=property
|title=The use of clonal selection algorithm for the
vehicle routing problem with time windows
|pdfUrl=https://ceur-ws.org/Vol-1853/p13.pdf
|volume=Vol-1853
|authors=Marcin Ogiołda
|dblpUrl=https://dblp.org/rec/conf/system/Ogiolda17
}}
==The use of clonal selection algorithm for the
vehicle routing problem with time windows
==
https://ceur-ws.org/Vol-1853/p13.pdf
The use of clonal selection algorithm for the
vehicle routing problem with time windows
Marcin Ogiołda
Faculty of Automatic Control, Electronics and Computer Science
Silesian University of Technology
Akademicka 16, 44-100 Gliwice, Poland
Email: m.ogiolda@gmail.com
Abstract—Genetic and heuristics algorithms are suitable for before the start of the time window in which the client should
finding solutions where classical methods fails. In this paper, be served. However, in this case, the driver must wait until
clonal selection algorithm was discussed as a efficient solution the time interval begins. The duration is also defined and it is
for the vehicle routing problem with time windows. Moreover,
variability of parameters has been tested, analyzed and discussed. determined individually for each client.
The solution to problem thus defined is a set of closed tracks
(road vehicles) that contain all the customers exactly once
I. I NTRODUCTION and do not alter any of the accepted limits. At the same time
Vehicle Routing Problem is a combinatorial optimization minimize the number of used cars what is the basic criterion
problem with practical applications in logistics. It is an ex- for optimization, and minimize the total distance traveled by
tension of the classic traveling salesman problem. The basic all vehicles (secondary criterion optimization).
version involves the determination of optimal route passes to A practical example of a routing problem with time win-
a group of customers for whom the demand and location are dows can be a distribution center that distributes goods to retail
known. Delivery is carried out by a certain number of available chains. The distribution center has its own fleet of delivery
vehicles of the same capacity route starting and finishing in vehicles at a specified equal capacity, and individual stores
the same store. have specific hours of receiving the goods. The problem is to
This problem occurs in several varieties. Here is a sample reduce the number of required vehicles carrying the shipment
of its variants: of goods to the shops and to minimize the length of the route.
• CVRP (Capacitated Vehicle Routing Problem) – vehicles B. Related works
have a defined volume,
Heuristics are called methods of finding solutions to prob-
• MDVRP (Multi Depot Vehicle Routing Problem) – there
lems in acceptable time with no guarantee of finding the
are many warehouses,
optimal solution. Heuristic methods are typically used to solve
• PVRP (Periodic Vehicle Routing Problem) - deliveries
difficult problems for which classical approach is not able
are spread over a number of days,
to find optimal solution in finite time. Heuristic algorithms
• SDVRP (Split Delivery Vehicle Routing Problem) – cus-
often are inspired by the processes from different scientific
tomers can be served by several vehicles,
fields. Evolutionary algorithms are inspired by genetics and
• VRPTW (Vehicle Routing Problem with Time Windows)
evolution, simulated annealing algorithm was inspired by the
– customers have a defined time windows when they
annealing process used in metallurgy, immune algorithms are
should be served.
inspired by the processes occurring in the natural immune
In this study, a variant of vehicle routing problem with time system.
windows (VRPTW) will be examined. Heuristic approach found numerous practical applications
A. Vehicle Routing Problem with Time Windows such as position traffic in NoSQL database systems [1]. This
is a very important topic because of the growth of Internet
Vehicle Routing Problem with Time Windows (VRPTW) access and the creation of various queues. Another application
is a multi-criteria combinatorial optimization problem belongs is signal processing like sound [2], [3] and image [4]–[8]
to the class of NP-hard problems. The problem involves three where the idea to use a specific heuristic technique for feature
criteria selection were presented. Moreover, in [9], heuristic showed
• the number of available vehicles, the application of heuristic to maze creation. Furthermore,
• the maximum capacity of vehicles, optimization is important approach in engineering [10], [11],
• time window in which each of the clients must be served. physics [12] or medicine [13] where it is used to optimize
In addition, each customer orders varying quantity of goods, certain parameters.
have an established individual service time and should be CLONALG algorithm is an algorithm of the general pur-
served exactly once. The vehicle can reach to the customer pose, which means that various problems can be solved by this
approach, among others optimization problems [14], problems The first set is a set of antigens Ag which contains patterns
of pattern recognition [15], as well as it can be applied to for recognition. The second set is marked as Ab contains
machine learning [16], [17]. As part of this work CLONALG antibodies representing the solution to problem. Version of
algorithm was used to solve the vehicle routing problems with CLONALG algorithm for machine learning and pattern recog-
time windows (VRPTW). nition can be described in a following way
VRPTW is a multi-criteria combinatorial optimization prob- 1) Initiation of pool Ab of size N divided into two subsets.
lem. It has a practical application in transport. In the problem, The first subset Abm of size m contains the potential of
three constraints are highlighted: the number of available antibody memory. The second one Abr of size r contains
vehicles, the maximum capacity of vehicles and the time other antibodies for the diversity of the population.
windows in which each customer should be served. VRPTW 2) Random selection of antigen Agj for the purposes of
is NP-hard problem and that is why heuristic approaches are recognition.
used. In this paper, clonal selection algorithm as a tool for 3) Calculating the degree adaptation of each antibody to
solving VRPTW is described. the antigen Agj .
4) The choice of n fittest antibodies.
II. A SSUMPTIONS OF THE THEORY OF CLONAL SELECTION
5) Cloning of selected antibodies directly proportional to
Clonal selection is a process of specific immune response. the degree of adaptation.
It is the activation of only those B cells which can produce 6) Maturation of set of clones by mutation inversely pro-
antibodies against the pathogen. Activated B cells rapidly portional to the degree of adaptation.
begins to divide. The resulting clones are go through a process 7) Determination of the affinity of each clone relative to
of somatic hypermutation, the aim of which is to produce the the preselected antigen.
most relevant antibodies. Then, mutant clones are subjected 8) Selection of the mature clone with the highest adaptation
to evaluation of their the degree of adaptation to a particular to the antigen Agj as a candidate for a set of memory. If
antigen. Clones with a high degree adaptation are converted its degree of adaptation with respect to the Agj is better
into memory cells, or plasma, whereas clones with low degree than the weakest one in the set memory, it is replaced.
of adjustment undergo apotheosis Plasma cells produce anti- 9) Replacement d antibodies from a pool Abr with the
bodies which combine the antigen phagocytic cells indicate lowest adaptation to the antigen Agj by new antibodies.
that it should be absorb. The memory cells are used in the Steps 2-9 are performed by a predetermined number of
secondary immune response. iterations specified by Ngen . Each iteration is synonymous
III. C LONAL SELECTION ALGORITHM with a new generation of antibodies. The algorithm returns a
set of memory Abm .
Clonal selection algorithms is a group of immune algo- Version of CLONALG algorithm, designed to optimize
rithms, whose principles of operation was inspired by the the- tasks is slightly different from the version used for pattern
ory of clonal selection in the immune system of human. There recognition and machine learning. These differences are as
are many algorithms modeled on the theory of clonal selection, follows
such as CLONALG, opt-IA, MOCSA, RCSA [18], [19]. In this
• In the first step, the two subsets Abm and Abr are not
paper, CLONALG (CLONal selection ALGorithm) was used
created. The entire population is a set of memory, and
to solve the problem of vehicle routing with time windows
each antibody represents a part of the input space.
was used. It was presented by de Castro and Von Zubena in
• In the second step, the population of antigen recognition
[19]. This algorithm can be applied to optimization problems,
is replaced by the objective function, which is subject to
pattern recognition, and machine learning.
optimization. The degree of adaptation of the antibody
CLONALG is characterized by few rules. The first is the corresponds to the value of the objective function.
number of clones resulting from each antibody - the value • In the eight step, instead of a single antibody, n antibodies
is directly proportional to the degree of adaptation of the are chosen to the set Ab.
antibody. Whereas the resulting clones were subjected to
The basic parameters of CLONALG algorithm are
mutation are inversely proportional to the degree of adaptation
• N - size of the pool of antibodies Ab,
of their parents. In addition, the least matched antibodies are
• n - the number of selected best-fit antibodies,
replaced with newly generated. Replacing the least adapted
• d - the number of the least adapted of antibodies that will
new antibodies allows you to increase the diversity of pool. In
the case of optimization function allows to escape from local be replaced by new ones,
• β - coefficient of cloning,
in order to find global extreme.
• Ngen - number of generations of antibodies (iteration of
CLONALG algorithm is available in two versions. The
first version is designed for pattern recognition and machine the algorithm).
learning. The second version is adapted to optimization prob- The number of clones that will be created from each of n
lems. Version of CLONALG algorithm is designed for pattern selected antibodies for cloning is defined as
recognition and machine learning which operates on two main
β·N
sets. Nc = round (1)
i
where i is the index of antibody inversely proportional to the One of these data sets has been prepared by Marius Solomon.
degree of adaptation (antibodies are ordered with respect to Solomon prepared three different data sets for 25, 50 and 100
descending adaptation). clients. For the purposes of the experiment, a set composed
The number of all created clones for mutations Nt is of 100 clients was used. This set includes 56 test problems
calculated as n
that have been divided into six distinct groups C1, C2, R1,
Nt =
X
Nc . (2) R2, RC1 and RC2. In addition, groups are diverse in terms of
i=1
the capacity of vehicles and the width of the time windows.
Particular groups differ in the arrangement of clients. In the
The formula for the number of clones may be presented in group C1, customers make explicit distinct of clusters, the
other way like group C2, the boundaries of clusters are less clear. The groups
β·N
Nc = + 0.5 . (3) R, the distribution of customers is random throughout the area.
i In contrast, the group RC groups are a combination of C
In addition, when the optimization process applies to mul- and R.In addition, groups are diverse in terms of the vehicles
timodal function it is recommended that N = n and changing capacity and the width of time windows.
the mathematical formula for the number of clones that will In groups C1, R1 and RC1 vehicles have a relatively low
be created from each of n chosen antibodies. The modified capacity and time windows are narrow. In the groups C2, R2
formula is as follows and RC2 capacity vehicles are larger, and the time windows
are wider.
Nc = round (β · N ) . (4) The distance between two customers x1 and x2 is measured
In CLONALG algorithm, antibodies are subjected to muta- by Euclidean metric defined as
tion inversely proportional to the degree of their adaptation. v
u 2
One possibility for the implementation of such a mutation is uX
d(x1 , x2 ) = t (x1,i − x2,i )2 . (8)
to introduce mutation rate α. The best-known formula for the
i=0
mutation are determined as follows
Speed of vehicles is set as 1 what means that the travel time
α = e−ρ·f , (5) between two clients is equal to the Euclidean distance between
or them. Visualization of the position of all customers located in
1 −f the file that describes the RC201 test problem is presented in
α= e (6)
ρ Fig. 2. The store is marked in red.
Experimental research relied on measurements and evalu-
where
ation of influence each parameters CLONALG algorithm in
• α – mutation rate,
terms of execution time and quality of the results.
• ρ — aspect of ratio distribution,
For research purposes, six tests were selected from the
• f — the value of the relevance of a given antibody
Solomon’s set, one from each group: C1, C2, R1, R2, RC1,
normalized to the interval h0, 1i. RC2. Selected tests are: C106, C203, R101, R210, RC107 and
The number of mutations that will be performed on the RC204. Testing kits were selected in a random way in order
antibody is defined as to maximize their differing levels of difficulty.
Nm = bα · Lc (7) A. The number of iterations
where L is the length of antibody that describes a certain The number of iterations of the algorithm is equivalent to
number of attributes. For example, the traveling salesman the number of generations of antibodies in the clonal selection
problem the length of antibodies will be equal to the number algorithms. It is determined by the parameter Ngen .
of cities that must be visited. The tests carried out showed that with increasing number of
Version of CLONALG adapted to optimization problems iterations, the quality of solutions is greater. At the same time,
is presented in Fig. 1. There are also modifications of algo- execution time is longer. Increasing the number of iterations,
rithm, CLONALG such as parallel version (called. parallel at the same time we increase the number of attempts to
CLONALG) or CLONCLAS (CLONal selection algorithm for improve the solutions represented by antibodies. Any attempt
CLASsification). These versions have been described in detail to improve the solutions require additional operations that
in [18]. directly extends the execution time.
IV. R ESEARCH ON THE INFLUENCE OF DIFFERENT B. The size of pool
PARAMETERS ON THE OBTAINED RESULTS Size of the pool in the algorithm CLONALG is defined by
In order to compare the quality of the results obtained by a parameter N .
clonal selection in the problem VRPTW with other algorithms, On the basis of experiments, increasing the size of the pool
a set of test data must be selected. The kit should be chosen of antibodies N clearly improves the quality of results, while
so that the best solutions are known and publicly available. prolonging the performance time. The execution time increases
Fig. 1: The algorithm of the proposed method.
Coefficient of cloning β has a significant impact on the
quality of results returned by the algorithm. At the same time,
the increasing of β extends the execution time of the algorithm
in a linear way. This happens because of β. larger the value
of β. The higher is value, the more clones will be created
from each of the antibodies. Thus, the probability is higher
that at least one of the clones resulting from mutations will
be improved. This will make that solution will be better than
a result from which the clone was created.
F. The aspect of ratio distribution
The aspect of ratio distribution ρ directly affects the value
of mutation α, which specifies the number of mutations that
will be performed on the clone of antibody.
The results show that the aspect of ratio distribution ρ for the
Fig. 2: Visualization of customers distribution in problem test configuration of the algorithm has an impact on the quality
RC201 of the obtained solutions, but this effect is smaller than in the
case of the parameters Ngen , N or β. Increasing the value of
ρ, execution time is shorter. What is the consequence of the
almost linearly. The impact of N is in line with expectations.
formula (5) – the higher is value of ρ, the fewer mutations is
Each antibody represents a solution to the problem. The more
carried out on a clone of an antibody, which reduces execution
different antibodies is the pool, the greater the number of
time.
different possible solutions. This increases the probability that
at least one of the available antibodies will be improved G. Analysis of the results
causing that it will be better than the best current solution.
The conducted experimental research indicate that the great-
C. The number of selected best-fit antibodies est impact on the quality of the solutions returned by clonal
The number of best-fit antibodies chosen for the cloning of selection algorithm implemented in the problem of vehicle
the pool of all the antibodies determines the parameter n. routing with time windows have Ngen , N and β. The parame-
The parameter n has a smaller impact on the quality of ters n and ρ have much smaller impact than other parameters.
obtained results than the parameters Ngen and N . In the case The smaller has d. Moreover, parallel instructions have the
of increasing value of n, the execution time is higher. A greatest impact on the execution time of a given algorithm, but
smaller impact of n on the obtained results, can be explained the impact is dependent on the number of available processors
by the fact that antibodies are selected in relation to the value in the computer - the more threads, the shorter execution time
of their adaptation. That is why the increasing of n causes is.
selection of the worst antibodies. V. T HE OBTAINED RESULTS
D. The number of the least matched antibody replaced with Minimizing the number of vehicles is the main criterion
new for optimization. In the 39 to 56 test problems, the algorithm
The number of the least matched antibodies that will be equalized best known result in terms of vehicles number. In
overwritten is determined by the parameter d. the remaining 17 problems, the number has always been only
For the test configuration of algorithm, the parameter d had one more than the best known solution to solve that problem.
no significant effect on the results, as well the execution time The total length of the routes is an average of 10% longer. In
of the algorithm. Replacing the least adapted antibodies on addition, the total length of the route is shorter than the known
new allows to increase diversity in the pool of antibodies. solutions, although the number of vehicles is slightly higher
In the case of function optimization, parameter allows to in R103, RC101 and RC105.
escape from local extreme in order to find global. At the same To improve the obtained results, the clonal selection algo-
time, the probability of generating a new antibody with better rithm can be combined with local Search algorithms, thereby
adjustment than the current one is low. Therefore, setting the forming a hybrid algorithm. Another possibility is to use
rate parameter d on 10 − 20% ∗ N seems to be a reasonable evolutionary strategies occurring in evolutionary algorithms.
solution. Another possibility for improvement it is to use parallelism.
The implemented algorithm uses multi-threading to improve
E. Coefficient of cloning execution time. The use of multi-threading in a manner similar
Coefficient of cloning antibodies is determined by the to what has been applied in [20], [21] (in simulated annealing
parameter β. It has a direct impact on the number of clones algorithm), in which the parallel running processes periodi-
that will be created for each antibody subjected to cloning cally send the best obtained solutions between each other. Such
operation. a solution should improve the accuracy of obtained solution.
(a) (b)
(c) (d)
(e)
(f)
(g) (h)
Fig. 3: Graphs of the obtained results for selected problems.
Another possibility is to make improvement in every thread, [13] R. Damaševičius, “Optimization of svm parameters for recognition of
and then choose the best from among the obtained solutions. regulatory dna sequences,” Top, vol. 18, no. 2, pp. 339–353, 2010.
[14] P. Čisar, S. M. Čisar, and B. Markoski, “Implementation of immuno-
However, improvement in the quality of solutions extends time logical algorithms in solving optimization problems,” Acta Polytechnica
of the algorithm. Hungarica, vol. 11, no. 4, 2014.
[15] J. A. White and S. M. Garrett, “Improved pattern recognition with
VI. C ONCLUSIONS artificial clonal selection?” in International Conference on Artificial
Immune Systems. Springer, 2003, pp. 181–193.
In this paper, clonal selection algorithm called CLONALG [16] J. Brownlee, “Clonal selection theory & clonalg-the clonal selection
was presented and used to solve the problem of vehicle classification algorithm (csca),” Swinburne University of Technology,
2005.
routing problems with time windows (VRPTW). The effect [17] I. Aydin, M. Karakose, and E. Akin, “A multi-objective artificial im-
of various parameters of the algorithm has been tested in mune algorithm for parameter optimization in support vector machine,”
terms of execution time and the quality of the results obtained Applied Soft Computing, vol. 11, no. 1, pp. 120–129, 2011.
[18] B. Jason, “Clonal selection algorithms,” Technical Report 070209A,
in the described problem. The results can be considered as 2007.
good, although they are different than the known solutions [19] F. J. V. Z. Leandro N. de Castro, “Learning and optimization using the
considered to be the best. However, in this study, the classical clonal selection principle,” vol. 6, no. 3, pp. 239–251, 2002.
[20] S. W. Mahfoud and D. E. Goldberg, “Parallel recombinative simulated
approach was analyzed without modification described in Sec. annealing: a genetic algorithm,” Parallel computing, vol. 21, no. 1, pp.
III. Further research on this topic may include modifications 1–28, 1995.
of the algorithm that would allow to obtain better solutions. [21] Z. J. Czech and P. Czarnas, “Parallel simulated annealing for the
vehicle routing problem with time windows,” in Parallel, Distributed
It is a good idea to use other solutions, what is planned for and Network-based Processing, 2002. Proceedings. 10th Euromicro
future research. Workshop on. IEEE, 2002, pp. 376–383.
R EFERENCES
[1] M. Woźniak, M. Gabryel, R. K. Nowicki, and B. A. Nowak, “An
application of firefly algorithm to position traffic in nosql database
systems,” in Knowledge, Information and Creativity Support Systems.
Springer, 2016, pp. 259–272.
[2] D. Połap, “Neuro-heuristic voice recognition,” in Computer Science and
Information Systems (FedCSIS), 2016 Federated Conference on. IEEE,
2016, pp. 487–490.
[3] M. Woźniak and D. Połap, “Voice recognition through the use of gabor
transform and heuristic algorithm,” International Journal of Electronics
and Telecommunications, vol. 63, no. 2, pp. 159–164, 2017.
[4] D. Połap, M. Woźniak, C. Napoli, E. Tramontana, and R. Damaševičius,
“Is the colony of ants able to recognize graphic objects?” in International
Conference on Information and Software Technologies. Springer, 2015,
pp. 376–387.
[5] M. Woźniak and Z. Marszałek, “An idea to apply firefly algorithm in 2d
image key-points search,” in International Conference on Information
and Software Technologies. Springer, 2014, pp. 312–323.
[6] M. Woźniak, D. Połap, M. Gabryel, R. K. Nowicki, C. Napoli, and
E. Tramontana, “Can we process 2d images using artificial bee colony?”
in International Conference on Artificial Intelligence and Soft Comput-
ing. Springer, 2015, pp. 660–671.
[7] M. Woźniak, D. Połap, C. Napoli, and E. Tramontana, “Graphic object
feature extraction system based on cuckoo search algorithm,” Expert
Systems with Applications, vol. 66, pp. 20–31, 2016.
[8] M. Wozniak, C. Napoli, E. Tramontana, G. Capizzi, G. L. Sciuto, R. K.
Nowicki, and J. T. Starczewski, “A multiscale image compressor with
rbfnn and discrete wavelet decomposition,” in Neural Networks (IJCNN),
2015 International Joint Conference on. IEEE, 2015, pp. 1–7.
[9] D. Połap, “Designing mazes for 2d games by artificial ant colony algo-
rithm,” in Proceedings of Symposium for Young Scientists in Technology,
Engineering and Mathematics, 2016, pp. 63–70.
[10] F. Bonanno, G. Capizzi, S. Coco, C. Napoli, A. Laudani, and G. L.
Sciuto, “Optimal thicknesses determination in a multilayer structure
to improve the spp efficiency for photovoltaic devices by an hybrid
fem—cascade neural network based approach,” in Power Electronics,
Electrical Drives, Automation and Motion (SPEEDAM), 2014 Interna-
tional Symposium on. IEEE, 2014, pp. 355–362.
[11] F. Bonanno, G. Capizzi, A. Gagliano, and C. Napoli, “Optimal man-
agement of various renewable energy sources by a new forecasting
method,” in Power Electronics, Electrical Drives, Automation and Mo-
tion (SPEEDAM), 2012 International Symposium on. IEEE, 2012, pp.
934–940.
[12] C. Napoli, G. Pappalardo, E. Tramontana, and G. Zappalà, “A cloud-
distributed gpu architecture for pattern identification in segmented
detectors big-data surveys,” The Computer Journal, vol. 59, no. 3, pp.
338–352, 2016.