-Genetic and heuristics algorithms are suitable for finding solutions where classical methods fails. In this paper, clonal selection algorithm was discussed as a efficient solution for the vehicle routing problem with time windows. Moreover, variability of parameters has been tested, analyzed and discussed. CVRP (Capacitated Vehicle Routing Problem) - vehicles have a defined volume, MDVRP (Multi Depot Vehicle Routing Problem) - there are many warehouses, PVRP (Periodic Vehicle Routing Problem) - deliveries are spread over a number of days, SDVRP (Split Delivery Vehicle Routing Problem) - customers can be served by several vehicles, VRPTW (Vehicle Routing Problem with Time Windows) - customers have a defined time windows when they should be served.
Vehicle Routing Problem is a combinatorial optimization problem with practical applications in logistics. It is an extension of the classic traveling salesman problem. The basic version involves the determination of optimal route passes to a group of customers for whom the demand and location are known. Delivery is carried out by a certain number of available vehicles of the same capacity route starting and finishing in the same store.
This problem occurs in several varieties. Here is a sample of its variants:
In this study, a variant of vehicle routing problem with time windows (VRPTW) will be examined.
Vehicle Routing Problem with Time Windows (VRPTW) is a multi-criteria combinatorial optimization problem belongs to the class of NP-hard problems. The problem involves three criteria the number of available vehicles, the maximum capacity of vehicles, time window in which each of the clients must be served. In addition, each customer orders varying quantity of goods, have an established individual service time and should be served exactly once. The vehicle can reach to the customer before the start of the time window in which the client should be served. However, in this case, the driver must wait until the time interval begins. The duration is also defined and it is 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 and do not alter any of the accepted limits. At the same time minimize the number of used cars what is the basic criterion for optimization, and minimize the total distance traveled by all vehicles (secondary criterion optimization).
A practical example of a routing problem with time windows can be a distribution center that distributes goods to retail chains. The distribution center has its own fleet of delivery vehicles at a specified equal capacity, and individual stores have specific hours of receiving the goods. The problem is to reduce the number of required vehicles carrying the shipment of goods to the shops and to minimize the length of the route.
Heuristics are called methods of finding solutions to problems in acceptable time with no guarantee of finding the optimal solution. Heuristic methods are typically used to solve difficult problems for which classical approach is not able to find optimal solution in finite time. Heuristic algorithms often are inspired by the processes from different scientific fields. Evolutionary algorithms are inspired by genetics and evolution, simulated annealing algorithm was inspired by the annealing process used in metallurgy, immune algorithms are inspired by the processes occurring in the natural immune system.
Heuristic approach found numerous practical applications
such as position traffic in NoSQL database systems [
CLONALG algorithm is an algorithm of the general
purpose, which means that various problems can be solved by this
approach, among others optimization problems [
VRPTW is a multi-criteria combinatorial optimization problem. It has a practical application in transport. In the problem, three constraints are highlighted: the number of available vehicles, the maximum capacity of vehicles and the time windows in which each customer should be served. VRPTW is NP-hard problem and that is why heuristic approaches are used. In this paper, clonal selection algorithm as a tool for solving VRPTW is described.
II. ASSUMPTIONS OF THE THEORY OF CLONAL SELECTION
Clonal selection is a process of specific immune response. It is the activation of only those B cells which can produce antibodies against the pathogen. Activated B cells rapidly begins to divide. The resulting clones are go through a process of somatic hypermutation, the aim of which is to produce the most relevant antibodies. Then, mutant clones are subjected to evaluation of their the degree of adaptation to a particular antigen. Clones with a high degree adaptation are converted into memory cells, or plasma, whereas clones with low degree of adjustment undergo apotheosis Plasma cells produce antibodies which combine the antigen phagocytic cells indicate that it should be absorb. The memory cells are used in the secondary immune response.
Clonal selection algorithms is a group of immune
algorithms, whose principles of operation was inspired by the
theory of clonal selection in the immune system of human. There
are many algorithms modeled on the theory of clonal selection,
such as CLONALG, opt-IA, MOCSA, RCSA [
CLONALG is characterized by few rules. The first is the number of clones resulting from each antibody - the value is directly proportional to the degree of adaptation of the antibody. Whereas the resulting clones were subjected to mutation are inversely proportional to the degree of adaptation of their parents. In addition, the least matched antibodies are replaced with newly generated. Replacing the least adapted new antibodies allows you to increase the diversity of pool. In the case of optimization function allows to escape from local in order to find global extreme.
CLONALG algorithm is available in two versions. The first version is designed for pattern recognition and machine learning. The second version is adapted to optimization problems. Version of CLONALG algorithm is designed for pattern recognition and machine learning which operates on two main sets.
The first set is a set of antigens Ag which contains patterns for recognition. The second set is marked as Ab contains antibodies representing the solution to problem. Version of CLONALG algorithm for machine learning and pattern recognition can be described in a following way 1) Initiation of pool Ab of size N divided into two subsets.
The first subset Abm of size m contains the potential of antibody memory. The second one Abr of size r contains other antibodies for the diversity of the population. 2) Random selection of antigen Agj for the purposes of recognition. 3) Calculating the degree adaptation of each antibody to the antigen Agj . 4) The choice of n fittest antibodies. 5) Cloning of selected antibodies directly proportional to the degree of adaptation. 6) Maturation of set of clones by mutation inversely proportional to the degree of adaptation. 7) Determination of the affinity of each clone relative to the preselected antigen. 8) Selection of the mature clone with the highest adaptation to the antigen Agj as a candidate for a set of memory. If its degree of adaptation with respect to the Agj is better than the weakest one in the set memory, it is replaced. 9) Replacement d antibodies from a pool Abr with the lowest adaptation to the antigen Agj by new antibodies.
Steps 2-9 are performed by a predetermined number of iterations specified by Ngen. Each iteration is synonymous with a new generation of antibodies. The algorithm returns a set of memory Abm.
Version of CLONALG algorithm, designed to optimize tasks is slightly different from the version used for pattern recognition and machine learning. These differences are as follows
In the first step, the two subsets Abm and Abr are not created. The entire population is a set of memory, and each antibody represents a part of the input space. In the second step, the population of antigen recognition is replaced by the objective function, which is subject to optimization. The degree of adaptation of the antibody corresponds to the value of the objective function. In the eight step, instead of a single antibody, n antibodies are chosen to the set Ab.
The basic parameters of CLONALG algorithm are N - size of the pool of antibodies Ab, n - the number of selected best-fit antibodies, d - the number of the least adapted of antibodies that will be replaced by new ones,
- coefficient of cloning, Ngen - number of generations of antibodies (iteration of the algorithm).
The number of clones that will be created from each of n selected antibodies for cloning is defined as
Nc = round (1) where i is the index of antibody inversely proportional to the degree of adaptation (antibodies are ordered with respect to descending adaptation).
The number of all created clones for mutations Nt is calculated as n Nt = X Nc: i=1 i
N Nc = + 0:5 :
The formula for the number of clones may be presented in other way like
In addition, when the optimization process applies to multimodal function it is recommended that N = n and changing the mathematical formula for the number of clones that will be created from each of n chosen antibodies. The modified formula is as follows
Nc = round (
N ) :
In CLONALG algorithm, antibodies are subjected to mutation inversely proportional to the degree of their adaptation. One possibility for the implementation of such a mutation is to introduce mutation rate . The best-known formula for the mutation are determined as follows or
= e = 1 f ; e f where – mutation rate, — aspect of ratio distribution, f — the value of the relevance of a given antibody normalized to the interval h0; 1i.
The number of mutations that will be performed on the antibody is defined as where L is the length of antibody that describes a certain number of attributes. For example, the traveling salesman problem the length of antibodies will be equal to the number of cities that must be visited.
Version of CLONALG adapted to optimization problems
is presented in Fig. 1. There are also modifications of
algorithm, CLONALG such as parallel version (called. parallel
CLONALG) or CLONCLAS (CLONal selection algorithm for
CLASsification). These versions have been described in detail
in [
IV. RESEARCH ON THE INFLUENCE OF DIFFERENT
PARAMETERS ON THE OBTAINED RESULTS
In order to compare the quality of the results obtained by clonal selection in the problem VRPTW with other algorithms, a set of test data must be selected. The kit should be chosen so that the best solutions are known and publicly available.
Nm = b
Lc (7)
(2) (3) (4) (5) (6)
One of these data sets has been prepared by Marius Solomon. Solomon prepared three different data sets for 25, 50 and 100 clients. For the purposes of the experiment, a set composed of 100 clients was used. This set includes 56 test problems that have been divided into six distinct groups C1, C2, R1, R2, RC1 and RC2. In addition, groups are diverse in terms of the capacity of vehicles and the width of the time windows. Particular groups differ in the arrangement of clients. In the group C1, customers make explicit distinct of clusters, the group C2, the boundaries of clusters are less clear. The groups R, the distribution of customers is random throughout the area. In contrast, the group RC groups are a combination of C and R.In addition, groups are diverse in terms of the vehicles capacity and the width of time windows.
In groups C1, R1 and RC1 vehicles have a relatively low capacity and time windows are narrow. In the groups C2, R2 and RC2 capacity vehicles are larger, and the time windows are wider.
The distance between two customers x1 and x2 is measured by Euclidean metric defined as
vu 2 d(x1; x2) = tuX(x1;i i=0 x2;i)2: (8) Speed of vehicles is set as 1 what means that the travel time between two clients is equal to the Euclidean distance between them. Visualization of the position of all customers located in the file that describes the RC201 test problem is presented in Fig. 2. The store is marked in red.
Experimental research relied on measurements and evaluation of influence each parameters CLONALG algorithm in terms of execution time and quality of the results. For research purposes, six tests were selected from the Solomon’s set, one from each group: C1, C2, R1, R2, RC1, RC2. Selected tests are: C106, C203, R101, R210, RC107 and RC204. Testing kits were selected in a random way in order to maximize their differing levels of difficulty.
The number of iterations of the algorithm is equivalent to the number of generations of antibodies in the clonal selection algorithms. It is determined by the parameter Ngen.
The tests carried out showed that with increasing number of iterations, the quality of solutions is greater. At the same time, execution time is longer. Increasing the number of iterations, at the same time we increase the number of attempts to improve the solutions represented by antibodies. Any attempt to improve the solutions require additional operations that directly extends the execution time.
Size of the pool in the algorithm CLONALG is defined by a parameter N .
On the basis of experiments, increasing the size of the pool of antibodies N clearly improves the quality of results, while prolonging the performance time. The execution time increases Fig. 1: The algorithm of the proposed method.
Fig. 2: Visualization of customers distribution in problem RC201 almost linearly. The impact of N is in line with expectations. Each antibody represents a solution to the problem. The more different antibodies is the pool, the greater the number of different possible solutions. This increases the probability that at least one of the available antibodies will be improved causing that it will be better than the best current solution.
The number of best-fit antibodies chosen for the cloning of the pool of all the antibodies determines the parameter n.
The parameter n has a smaller impact on the quality of obtained results than the parameters Ngen and N . In the case of increasing value of n, the execution time is higher. A smaller impact of n on the obtained results, can be explained by the fact that antibodies are selected in relation to the value of their adaptation. That is why the increasing of n causes selection of the worst antibodies.
The number of the least matched antibodies that will be overwritten is determined by the parameter d.
For the test configuration of algorithm, the parameter d had no significant effect on the results, as well the execution time of the algorithm. Replacing the least adapted antibodies on new allows to increase diversity in the pool of antibodies. In the case of function optimization, parameter allows to escape from local extreme in order to find global. At the same time, the probability of generating a new antibody with better adjustment than the current one is low. Therefore, setting the rate parameter d on 10 20% N seems to be a reasonable solution.
Coefficient of cloning antibodies is determined by the parameter . It has a direct impact on the number of clones that will be created for each antibody subjected to cloning operation.
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.
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 test configuration of the algorithm has an impact on the quality 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 formula (5) – the higher is value of , the fewer mutations is carried out on a clone of an antibody, which reduces execution time.
The conducted experimental research indicate that the greatest impact on the quality of the solutions returned by clonal selection algorithm implemented in the problem of vehicle routing with time windows have Ngen, N and . The parameters n and have much smaller impact than other parameters. The smaller has d. Moreover, parallel instructions have the greatest impact on the execution time of a given algorithm, but the impact is dependent on the number of available processors in the computer - the more threads, the shorter execution time is.
Minimizing the number of vehicles is the main criterion for optimization. In the 39 to 56 test problems, the algorithm equalized best known result in terms of vehicles number. In the remaining 17 problems, the number has always been only one more than the best known solution to solve that problem. The total length of the routes is an average of 10% longer. In addition, the total length of the route is shorter than the known solutions, although the number of vehicles is slightly higher in R103, RC101 and RC105.
To improve the obtained results, the clonal selection algorithm can be combined with local Search algorithms, thereby forming a hybrid algorithm. Another possibility is to use evolutionary strategies occurring in evolutionary algorithms.
Another possibility for improvement it is to use parallelism.
The implemented algorithm uses multi-threading to improve
execution time. The use of multi-threading in a manner similar
to what has been applied in [
VI. CONCLUSIONS
In this paper, clonal selection algorithm called CLONALG was presented and used to solve the problem of vehicle routing problems with time windows (VRPTW). The effect of various parameters of the algorithm has been tested in terms of execution time and the quality of the results obtained in the described problem. The results can be considered as good, although they are different than the known solutions considered to be the best. However, in this study, the classical approach was analyzed without modification described in Sec. III. Further research on this topic may include modifications of the algorithm that would allow to obtain better solutions. It is a good idea to use other solutions, what is planned for future research.