nach oben

Soft Computing

Erschienen in:

01.02.2015 | Methodologies and Application

Combinatorial neighborhood topology bumble bees mating optimization for the vehicle routing problem with stochastic demands

verfasst von: Yannis Marinakis, Magdalene Marinaki

Erschienen in: Soft Computing | Ausgabe 2/2015

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The bumble bees mating optimization (BBMO) algorithm is a relatively new swarm intelligence algorithm that simulates the mating behavior that a swarm of bumble bees performs. 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, the proposed algorithm for the solution of the VRPSD, the combinatorial neighborhood topology bumble bees mating optimization, combines a BBMO algorithm, the variable neighborhood search algorithm and a path relinking procedure. The algorithm is evaluated on a set of benchmark instances (40 instances) from the literature and 16 new best solutions are found. The algorithm is compared with a number of algorithms from the literature (two versions of a particle swarm optimization algorithm, the classic one and the combinatorial expanding neighborhood topology particle swarm optimization algorithm, a differential evolution algorithm, a genetic algorithm and a honey bees mating optimization) and with the initial version of the BBMO algorithm.

Vorheriger Artikel An iterative fuzzy region competition algorithm for multiphase image segmentation

Nächster Artikel Artificial neural network weights optimization based on social-based algorithm to realize sediment over the river

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Abbass HA (2001a) A monogenous MBO approach to satisfiability. In: Proceeding of the international conference on computational intelligence for modelling, control and automation, CIMCA’2001, Las Vegas

Abbass HA (2001b) Marriage in honey-bee optimization (MBO): a haplometrosis polygynous swarming approach. In: The congress on evolutionary computation (CEC2001), Seoul, May 2001, pp 207–214

Afshar A, Haddad OB, Marino MA, Adams BJ (2007) Honey-bee mating optimization (HBMO) algorithm for optimal reservoir operation. J Frankl Inst 344:452–462CrossRefMATH

Baykasoglu A, Ozbakir L, Tapkan P (2007) Artificial bee colony algorithm and its application to generalized assignment problem. In: Chan FTS, Tiwari MK (eds) Swarm intelligence, focus on ant and particle swarm optimization. I-Tech Education and Publishing, Austria

Bent RW, Van Hentenryck P (2004) Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Oper Res 52(6):977–987CrossRefMATH

Bianchi L, Birattari M, Manfrin M, Mastrolilli M, Paquete L, Rossi-Doria O, Schiavinotto T (2006) Hybrid metaheuristics for the vehicle routing problem with stochastic demands. J Math Model Algorithms 5(1):91–110CrossRefMATHMathSciNet

Bianchi L, Dorigo M, Gambardella LM, Gutjahr WJ (2009) A survey on metaheuristics for stochastic combinatorial optimization. Nat Comput 8(2):239–287CrossRefMATHMathSciNet

Christiansen CH, Lysgaard J (2007) A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Oper Res Lett 35:773–781CrossRefMATHMathSciNet

Drias H, Sadeg S, Yahi S (2005) Cooperative bees swarm for solving the maximum weighted satisfiability problem. In: Proceeding of IWAAN international work conference on artificial and natural neural networks, LNCS 3512:318–325

Dror M, Laporte G, Louveaux FV (1993) Vehicle routing with stochastic demands and restricted failures. ZOR Methods Models Oper Res 37:273–283CrossRefMATHMathSciNet

Fathian M, Amiri B, Maroosi A (2007) Application of honey bee mating optimization algorithm on clustering. Appl Math Comput 190:1502–1513CrossRefMATHMathSciNet

Gendreau M, Laport G, Seguin R (1996) Stochastic vehicle routing. Eur J Oper Res 88:3–12CrossRefMATH

Glover F, Laguna M, Marti R (2003) Scatter search and path relinking: advances and spplications. In: Glover F, Kochenberger GA (eds) Handbook of metaheuristics. Kluwer Academic, Boston, pp 1–36

Goodson JC, Ohlmann JW, Thomas BW (2012) Cyclic-order neighborhoods with application to the vehicle routing problem with stochastic demand. Eur J Oper Res 217:312–323CrossRefMATHMathSciNet

Guo ZG, Mac KL (2004) A Heuristic algorithm for the stochastic vehicle routing problems with soft time windows. Congr Evolut Comput 2:1449–1456

Haddad OB, Afshar A, Marino MA (2006) Honey-bees mating optimization (HBMO) algorithm: a new heuristic approach for water resources optimization. Water Resour Manag 20:661–680CrossRef

Hansen P, Mladenovic N (2001) Variable neighborhood search: Principles and applications. Eur J Oper Res 130:449–467CrossRefMATHMathSciNet

Haugland D, Ho SC, Laporte G (2007) Designing delivery districts for the vehicle routing problem with stochastic demands. Eur J Oper Res 180:997–1010CrossRefMATHMathSciNet

Hvattum LM, Lkketangen A, Laporte G (2004) A Heuristic solution method to a stochastic vehicle routing problem. In: Proceedings of TRISTAN V-The fifth triennial symposium on transportation analysis

Juan AA, Faulin J, Jorba J, Caceres J, Marques JM (2012) Using parallel and distributed computing for real-time solving of vehicle routing problems with stochastic demands. Ann Oper Res. doi:10.1007/s10479-011-0918-z

Juan A, Faulin J, Grasman S, Riera D, Marull J, Mendez C (2011) Using safety stocks and simulation to solve the vehicle routing problem with stochastic demands. Transp Res Part C 19:751–765CrossRef

Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Global Optim 39:459–471CrossRefMATHMathSciNet

Karaboga D, Basturk B (2008) On the performance of artificial bee colony (ABC) algorithm. Appl Soft Comput 8:687–697CrossRef

Karaboga D, Akay B (2009) A survey: algorithms simulating bee swarm intelligence. Artif Intell Rev 31:61–85CrossRef

Kenyon AS, Morton DP (2003) Stochastic vehicle routing with random travel times. Transp Sci 37:69–82CrossRef

Lei H, Laporte G, Guo B (2011) The capacitated vehicle routing problem with stochastic demands and time windows. Comput Oper Res 38:1775–1783CrossRefMATHMathSciNet

Li X, Tian P, Leung SCH (2010) Vehicle routing problems with time windows and stochastic travel and service times: models and algorithm. Int J Prod Econ 125:137–145CrossRef

Lourenco HR, Martin O, Stützle T (2002) Iterated local search. Handbook of metaheuristics. In: Operations research and management science, vol. 57, pp 321–353. Kluwer Academic, Boston

Marinakis Y, Marinaki M, Dounias G (2008a) Honey bees mating optimization algorithm for the vehicle routing problem. In: Krasnogor N, Nicosia G, Pavone M, Pelta D (eds) Nature inspired cooperative strategies for optimization—NICSO 2007. Springer, Berlin, pp 139–148 Studies in Computational Intelligence

Marinakis Y, Marinaki M, Matsatsinis N (2008b) A hybrid clustering algorithm based on honey bees mating optimization and greedy randomized adaptive search procedure. Learning and intelligence optimization—LION 2007, LNCS 5313. Springer, Berlin

Marinakis Y, Marinaki M, Matsatsinis N (2008c) Honey bees mating optimization for the location routing problem. In: Proceeding of IEEE international engineering management conference (IEMC—Europe 2008), Estoril, Portugal

Marinakis Y, Marinaki M (2009) A hybrid honey bees mating optimization algorithm for the probabilistic traveling salesman problem. In: Proceeding of IEEE congress on evolutionary computation (CEC 2009), Trondheim, Norway

Marinakis Y, Marinaki M, Matsatsinis N (2009) A hybrid bumble bees mating optimization—GRASP algorithm for clustering. In: Corchado E (ed) HAIS 2009, LN 5572. Springer, Berlin, pp 549–556

Marinakis Y, Marinaki M, Dounias G (2010a) Honey bees mating optimization algorithm for large scale vehicle routing problems. Nat Comput 9:5–27CrossRefMATHMathSciNet

Marinakis Y, Marinaki M, Matsatsinis N (2010b) A Bumble bees mating optimization algorithm for global unconstrained optimization problems. In: Gonzalez JR (ed) Nature inspired cooperative strategies for optimization—NICSO 2010. Springer, Berlin, pp 305–318 Studies in Computational Intelligence

Marinaki M, Marinakis Y, Zopounidis C (2010c) Honey bees mating optimization algorithm for financial classification problems. Appl Soft Comput 10:806–812CrossRef

Marinakis Y, Marinaki M (2011) Bumble bees mating optimization algorithm for the vehicle routing problem. In: Panigrahi BK, Shi Y, Lim M-H (eds) Handbook of swarm intelligence—concepts, principles and applications, aeries on adaptation, learning, and optimization 8. Springer, Berlin, pp 347–369

Marinaki M, Marinakis Y (2013a) A Honey bees mating optimization algorithm with path relinking for the vehicle routing problem with stochastic demands (submitted)

Marinakis Y, Marinaki M (2013b) Combinatorial neighborhood topology particle swarm optimization algorithm for the vehicle routing problem. In: Middendorf M, Blum C (eds) EvoCOP 2013, LNCS 7832, pp 133–144

Marinakis Y, Marinaki M (2013c) Combinatorial expanding neighborhood topology particle swarm optimization for the vehicle routing problem with stochastic demands. In: GECCO: 2013, genetic and evolutionary computation conference, 6–10 July 2013, Amsterdam, The Netherlands

Marinakis Y, Iordanidou GR, Marinaki M (2013a) Particle swarm optimization for the vehicle routing problem with stochastic demands. Appl Soft Comput 13:1693–1704CrossRef

Marinakis Y, Marinaki M, Spanou P (2013b) A Memetic differential evolution algorithm for vehicle routing problem with stochastic demands and customers (submitted)

Martin O, Otto SW, Felten EW (1991) Large-step markov chains for the traveling salesman problem. Complex Syst 5(3):299–326

Mendoza JE, Castaniera B, Guereta C, Medagliab AL, Velascob N (2010) A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands. Comput Oper Res 37:1886–1898CrossRefMATHMathSciNet

Minis I, Tatarakis A (2011) Stochastic single vehicle routing problem with delivery and pick up and a predefined customer sequence. Eur J Oper Res 213:37–51CrossRefMATHMathSciNet

Novoa C, Storer R (2009) An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. Eur J Oper Res 196:509–515CrossRefMATH

Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S, Zaidi M (2006) The bees algorithm—a novel tool for complex optimization problems. In: IPROMS 2006 proceeding 2nd international virtual conference on intelligent production machines and systems, Oxford, Elsevier

Protonotarios M, Mourkousis G, Vyridis I, Varvarigou T (2000) Very large scale vehicle routing with time windows and stochastic demand using genetic algorithms with parallel fitness evaluation. HPCN 2000, LNCS 1823, pp 467–476

Reimann M (2005) Analyzing a vehicle routing problem with stochastic demands using ant colony optimization. In: Jaszkiewicz A, Kaczmarek M, Zak J, Kubiak M (eds) Advanced OR and AI methods in transportation. Publishing House of Poznan University of Technology, Poland, pp 764–769

Secomandi N (2000) Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Comput Oper Res 27:1201–1225CrossRefMATH

Shen Z, Dessouky M, Ordonez F (2005) The stochastic vehicle routing problem for large-scale emergencies. Technical Report 2005–06, Department of Industrial and Systems Engineering, University of Southern California

Stewart WR, Golden BL (1983) Stochastic vehicle routing: a comprehensive approach. Eur J Oper Res 14:371–385CrossRefMATH

Talbi E-G (2009) Metaheuristics: from design to implementation. Wiley, USACrossRef

Tan KC, Cheong CY, Goh CK (2007) Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. Eur J Oper Res 177:813–839CrossRefMATH

Teo J, Abbass HA (2003) A true annealing approach to the marriage in honey bees optimization algorithm. Int J Comput Intell Appl 3(2):199–211CrossRef

Teodorovic D, Dell’Orco M (2005) Bee colony optimization—a cooperative learning approach to complex transportation problems. In: Advanced OR and AI methods in transportation, Proceedings of the 16th mini—EURO conference and 10th meeting of EWGT, pp 51–60

Tillman F (1969) The multiple terminal delivery problem with probabilistic demands. Transp Sci 3:192–204CrossRef

Wedde HF, Farooq M, Zhang Y (2004) BeeHive: an efficient fault-tolerant routing algorithm inspired by honey bee behavior. In: Dorigo M (ed) Ant colony optimization and swarm intelligence, LNCS 3172. Springer, Berlin, pp 83–94CrossRef

Yan S, Chi CJ, Tang CH (2006) Inter-city bus routing and timetable setting under stochastic demands. Transp Res Part A 40:572–586

Yang JM, Alvarez JR (eds) (2005) Engineering optimizations via nature-inspired virtual bee algorithms. IWINAC 2005, LNCS 3562. Springer, Berlin, pp 317–323

Yang WH, Mathur K, Ballou RH (2000) Stochastic vehicle routing problem with restocking. Transp Sci 34:99–112CrossRefMATH

Titel: Combinatorial neighborhood topology bumble bees mating optimization for the vehicle routing problem with stochastic demands
verfasst von: Yannis Marinakis
Magdalene Marinaki
Publikationsdatum: 01.02.2015
Verlag: Springer Berlin Heidelberg
Erschienen in: Soft Computing / Ausgabe 2/2015
Print ISSN: 1432-7643
Elektronische ISSN: 1433-7479
DOI: https://doi.org/10.1007/s00500-014-1257-1

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 2/2015

A fuzzy logic-based system for the automation of human behavior recognition using machine vision in intelligent environments

Calculus of fuzzy functions on time scales (I)

An adaptive particle swarm optimization method based on clustering

Combine particle swarm optimization algorithm and canonical sign digit to design finite impulse response filter

Robust classifier using distance-based representation with square weights

A new study on first-order fuzzy Fredholm–Volterra integro-differential equations by Jacobi polynomials and collocation methods