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.