Abstract
The Clonal Selection Algorithm is the most known algorithm inspired from the Artificial Immune Systems and used effectively in optimization problems. In this paper, this nature inspired algorithm is used in a hybrid scheme with other metaheuristic algorithms for successfully solving the Vehicle Routing Problem with Stochastic Demands (VRPSD). More precisely, for the solution of this problem, the Hybrid Clonal Selection Algorithm (HCSA) is proposed which combines a Clonal Selection Algorithm (CSA), a Variable Neighborhood Search (VNS), and an Iterated Local Search (ILS) algorithm. The effectiveness of the original Clonal Selection Algorithm for this NP-hard problem is improved by using ILS as a hypermutation operator and VNS as a receptor editing operator. The algorithm is tested on a set of 40 benchmark instances from the literature and ten new best solutions are found. Comparisons of the proposed algorithm with several algorithms from the literature (two versions of the Particle Swarm Optimization algorithm, a Differential Evolution algorithm and a Genetic Algorithm) are also reported.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bianchi, L., Birattari, M., Manfrin, M., Mastrolilli, M., Paquete, L., Rossi-Doria, O., Schiavinotto, T.: Hybrid metaheuristics for the vehicle routing problem with stochastic demands. J. Math. Model. Algorithms 5(1), 91–110 (2006)
Bianchi, L., Dorigo, M., Gambardella, L.M., Gutjahr, W.J.: A survey on metaheuristics for stochastic combinatorial optimization. Nat. Comput. 8(2), 239–287 (2009)
Brabazon, A., O’Neill, M.: Biologically Inspired Algorithms for Financial Modeling. Natural Computing Series. Springer, Berlin (2006)
Christiansen, C.H., Lysgaard, J.: A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Oper. Res. Lett. 35, 773–781 (2007)
Cuevas, E., Osuna-Enciso, V., Wario, F., Zaldvar, D., Pérez-Cisneros, M., : Automatic multiple circle detection based on artificial immune systems. Expert Syst. Appl. 39, 713–722 (2012)
Dabrowski, J.: Clonal selection algorithm for vehicle routing. In: Proceedings of the 2008 1st International Conference on Information Technology, IT 2008 19–21 May 2008, Gdansk, Poland (2008)
Dasgupta, D. (ed.): Artificial Immune Systems and their Application. Springer, Heidelberg (1998)
Dasgupta, D., Niño, L.F.: Immunological Computation: Theory and Applications. CRC Press, Taylor and Francis Group, Boca Raton (2009)
De Castro, L.N., Timmis, J.: Artificial Immune Systems: A New Computational Intelligence Approach. Springer, Heidelberg (2002)
De Castro, L.N., Von Zuben, F.J.: The clonal selection algorithm with engineering applications. In: Workshop on Artificial Immune Systems and Their Applications (GECCO00), Las Vegas, NV, pp. 36–37 (2000)
De Castro, L.N., Von Zuben, F.J.: Learning and optimization using the clonal selection principle. IEEE Trans. Evol. Comput. 6(3), 239–251 (2002)
Engelbrecht, A.P.: Computational Intelligence: An Introduction, 2nd edn. Wiley, New York (2007)
Flower, D., Timmis, J. (eds.): In Silico Immunology. Springer, New York (2007)
Forrest, S., Perelson, A. Allen, L., Cherukuri, R.: Self-nonself discrimination in a computer. In: Proceedings of the 1994 IEEE Symposium on Research in Security and Privacy, pp. 202–212. IEEE Computer Society Press, Los Alamitos (1994)
Gong, M., Jiao, L., Zhang, L.: Baldwinian learning in clonal selection algorithm for optimization. Inf. Sci. 180, 1218–1236 (2010)
Goodson, J.C., Ohlmann, J.W., Thomas, B.W.: Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand. Eur. J. Oper. Res. 217, 312–323 (2012)
Hansen, P., Mladenovic, N.: Variable neighborhood search: principles and applications. Eur. J. Oper. Res. 130, 449–467 (2001)
Li, F., Gao, S., Wang, W., Tang, Z.: An adaptive clonal selection algorithm for edge linking problem. IJCSNS Int. J. Comput. Sci. Netw. Secur. 9(7), 57–65 (2009)
Lourenco, H.R., Martin, O., Stützle, T.: Iterated local search. In: Glover, F., Kochenberger, G. (eds.) Handbook of Metaheuristics. Operations Research and Management Science, vol. 57, pp. 321–353. Kluwer Academic Publishers, Dordrecht (2002)
Ma, J., Shi, G., Gao, L.: An Improved immune clonal selection algorithm and its applications for VRP. In: Proceedings of the IEEE International Conference on Automation and Logistics Shenyang, China, August 2009 (2009)
Marinakis, Y., Iordanidou, G.R., Marinaki, M.: Particle swarm optimization for the vehicle routing problem with stochastic demands. Appl. Soft Comput. 13, 1693–1704 (2013)
Marinakis, Y., Marinaki, M.: Combinatorial expanding neighborhood topology particle swarm optimization for the vehicle routing problem with stochastic demands. In: GECCO: 2013, Genetic and Evolutionary Computation Conference, Amsterdam, The Netherlands, 6–10 July 2013
Marinakis, Y., Marinaki, M., Spanou, P.: A memetic differential evolution algorithm for vehicle routing problem with stochastic demands. In: Fister, I., Fister, I. Jr. (eds.) Adaptation in Computational Intelligence, Adaptation Learning and Optimization (2014). (accepted)
Martin, O., Otto, S.W., Felten, E.W.: Large-step Markov chains for the traveling salesman problem. Complex Syst. 5(3), 299–326 (1991)
Panigrahi, B.K., Yadav, S.R., Agrawal, S., Tiwari, M.K.: A clonal algorithm to solve economic load dispatch. Electr. Power Syst. Res. 77, 1381–1389 (2007)
Stewart, W.R., Golden, B.L.: Stochastic vehicle routing: a comprehensive approach. Eur. J. Oper. Res. 14, 371–385 (1983)
Talbi, E.-G.: Metaheuristics : From Design to Implementation. Wiley, New York (2009)
Timmis, J., Neal, M.: A resource limited artificial immune system for data analysis. In: Timmis, J., Neal, M. (eds.) Research and Development in Intelligent Systems, vol. 14, pp. 19–32. Springer, London (2000)
Ulutas, B.H., Islier, A.A.: A clonal selection algorithm for dynamic facility layout problems. J. Manuf. Syst. 28, 123–131 (2009)
Ulutas, B.H., Kulturel-Konak, S.: An artificial immune system based algorithm to solve unequal area facility layout problem. Expert Syst. Appl. 39(5), 5384–5395 (2012)
Yang, W.H., Mathur, K., Ballou, R.H.: Stochastic vehicle routing problem with restocking. Transp. Sci. 34, 99–112 (2000)
Yang, J.-H., Sun, L., Lee, H.P., Qian, Y., Liang, Y.-C.: Clonal selection based memetic algorithm for job shop scheduling problems. J. Bionic Eng. 5, 111–119 (2008)
Zhu, Y., Gao, S., Dai, H., Li, F., Tang, Z.: Improved clonal algorithm and its application to traveling salesman problem. IJCSNS Int. J. Comput. Sci. Netw. Secur. 7(8), 109–113 (2007)
http://www.coin-or.org/SYMPHONY/branchandcut/VRP/data/Vrp-All.tgz
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Marinakis, Y., Marinaki, M., Migdalas, A. (2014). A Hybrid Clonal Selection Algorithm for the Vehicle Routing Problem with Stochastic Demands. In: Pardalos, P., Resende, M., Vogiatzis, C., Walteros, J. (eds) Learning and Intelligent Optimization. LION 2014. Lecture Notes in Computer Science(), vol 8426. Springer, Cham. https://doi.org/10.1007/978-3-319-09584-4_24
Download citation
DOI: https://doi.org/10.1007/978-3-319-09584-4_24
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-09583-7
Online ISBN: 978-3-319-09584-4
eBook Packages: Computer ScienceComputer Science (R0)