Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Algorithm Portfolios for Noisy Optimization: Compare Solvers Early Read chapter Read first chapter

2014 | OriginalPaper | Chapter

A Hybrid Clonal Selection Algorithm for the Vehicle Routing Problem with Stochastic Demands

Authors : Yannis Marinakis, Magdalene Marinaki, Athanasios Migdalas

Published in: Learning and Intelligent Optimization

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

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.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter A Novel Hybrid Dynamic Programming Algorithm for a Two-Stage Supply Chain Scheduling Problem
next chapter Bayesian Gait Optimization for Bipedal Locomotion
Literature
1.
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)MATHMathSciNetCrossRef
2.
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)MATHMathSciNetCrossRef
3.
Brabazon, A., O’Neill, M.: Biologically Inspired Algorithms for Financial Modeling. Natural Computing Series. Springer, Berlin (2006)
4.
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)MATHMathSciNetCrossRef
5.
Cuevas, E., Osuna-Enciso, V., Wario, F., Zald https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-09584-4_24/MediaObjects/328771_1_En_24_Figb_HTML.gif var, D., Pérez-Cisneros, M., : Automatic multiple circle detection based on artificial immune systems. Expert Syst. Appl. 39, 713–722 (2012)
6.
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)
7.
Dasgupta, D. (ed.): Artificial Immune Systems and their Application. Springer, Heidelberg (1998)
8.
Dasgupta, D., Niño, L.F.: Immunological Computation: Theory and Applications. CRC Press, Taylor and Francis Group, Boca Raton (2009)
9.
De Castro, L.N., Timmis, J.: Artificial Immune Systems: A New Computational Intelligence Approach. Springer, Heidelberg (2002)
10.
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)
11.
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)CrossRef
12.
Engelbrecht, A.P.: Computational Intelligence: An Introduction, 2nd edn. Wiley, New York (2007)CrossRef
13.
Flower, D., Timmis, J. (eds.): In Silico Immunology. Springer, New York (2007)
14.
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)
15.
Gong, M., Jiao, L., Zhang, L.: Baldwinian learning in clonal selection algorithm for optimization. Inf. Sci. 180, 1218–1236 (2010)CrossRef
16.
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)MATHMathSciNetCrossRef
17.
18.
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)
19.
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)
20.
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)
21.
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)CrossRef
22.
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
23.
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)
24.
Martin, O., Otto, S.W., Felten, E.W.: Large-step Markov chains for the traveling salesman problem. Complex Syst. 5(3), 299–326 (1991)MATHMathSciNet
25.
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)CrossRef
26.
Stewart, W.R., Golden, B.L.: Stochastic vehicle routing: a comprehensive approach. Eur. J. Oper. Res. 14, 371–385 (1983)MATHCrossRef
27.
Talbi, E.-G.: Metaheuristics : From Design to Implementation. Wiley, New York (2009)CrossRef
28.
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)
29.
Ulutas, B.H., Islier, A.A.: A clonal selection algorithm for dynamic facility layout problems. J. Manuf. Syst. 28, 123–131 (2009)CrossRef
30.
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)CrossRef
31.
Yang, W.H., Mathur, K., Ballou, R.H.: Stochastic vehicle routing problem with restocking. Transp. Sci. 34, 99–112 (2000)MATHCrossRef
32.
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)CrossRef
33.
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)
34.
Metadata
Title
A Hybrid Clonal Selection Algorithm for the Vehicle Routing Problem with Stochastic Demands
Authors
Yannis Marinakis
Magdalene Marinaki
Athanasios Migdalas
Copyright Year
2014
Book
Learning and Intelligent Optimization

Print ISBN: 978-3-319-09583-7

Electronic ISBN: 978-3-319-09584-4

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-09584-4_24

Premium Partner

    Image Credits