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

详细信息    查看全文

• 作者：Yannis Marinakis (1)
  Magdalene Marinaki (2)
  
  1. Decision Support Systems Laboratory ; School of Production Engineering and Management ; Technical University of Crete ; University Campus ; 73100聽 ; Chania ; Crete ; Greece
  2. Computational Mechanics and Optimization Laboratory ; School of Production Engineering and Management ; Technical University of Crete ; University Campus ; 73100聽 ; Chania ; Crete ; Greece
  
• 关键词：Vehicle routing problem with stochastic demands ; Bumble bees mating optimization ; Combinatorial neighborhood topology
• 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：19
• 期：2
• 页码：353-373
• 全文大小：349 KB
• 参考文献：1. Abbass HA (2001a) A monogenous MBO approach to satisfiability. In: Proceeding of the international conference on computational intelligence for modelling, control and automation, CIMCA鈥?001, Las Vegas
  2. 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鈥?14
  3. Afshar A, Haddad OB, Marino MA, Adams BJ (2007) Honey-bee mating optimization (HBMO) algorithm for optimal reservoir operation. J Frankl Inst 344:452鈥?62 CrossRef
  4. 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
  5. Bent RW, Van Hentenryck P (2004) Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Oper Res 52(6):977鈥?87 CrossRef
  6. 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鈥?10 CrossRef
  7. Bianchi L, Dorigo M, Gambardella LM, Gutjahr WJ (2009) A survey on metaheuristics for stochastic combinatorial optimization. Nat Comput 8(2):239鈥?87 CrossRef
  8. Christiansen CH, Lysgaard J (2007) A branch-and-price algorithm for the capacitated vehicle routing problem with stochastic demands. Oper Res Lett 35:773鈥?81 CrossRef
  9. 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鈥?25
  10. Dror M, Laporte G, Louveaux FV (1993) Vehicle routing with stochastic demands and restricted failures. ZOR Methods Models Oper Res 37:273鈥?83 CrossRef
  11. Fathian M, Amiri B, Maroosi A (2007) Application of honey bee mating optimization algorithm on clustering. Appl Math Comput 190:1502鈥?513 CrossRef
  12. Gendreau M, Laport G, Seguin R (1996) Stochastic vehicle routing. Eur J Oper Res 88:3鈥?2 CrossRef
  13. 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鈥?6
  14. 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鈥?23 CrossRef
  15. Guo ZG, Mac KL (2004) A Heuristic algorithm for the stochastic vehicle routing problems with soft time windows. Congr Evolut Comput 2:1449鈥?456
  16. 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鈥?80 CrossRef
  17. Hansen P, Mladenovic N (2001) Variable neighborhood search: Principles and applications. Eur J Oper Res 130:449鈥?67 CrossRef
  18. Haugland D, Ho SC, Laporte G (2007) Designing delivery districts for the vehicle routing problem with stochastic demands. Eur J Oper Res 180:997鈥?010 CrossRef
  19. 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
  20. 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
  21. 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鈥?65 CrossRef
  22. Karaboga D, Basturk B (2007) A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. J Global Optim 39:459鈥?71 CrossRef
  23. Karaboga D, Basturk B (2008) On the performance of artificial bee colony (ABC) algorithm. Appl Soft Comput 8:687鈥?97 CrossRef
  24. Karaboga D, Akay B (2009) A survey: algorithms simulating bee swarm intelligence. Artif Intell Rev 31:61鈥?5 CrossRef
  25. Kenyon AS, Morton DP (2003) Stochastic vehicle routing with random travel times. Transp Sci 37:69鈥?2 CrossRef
  26. Lei H, Laporte G, Guo B (2011) The capacitated vehicle routing problem with stochastic demands and time windows. Comput Oper Res 38:1775鈥?783 CrossRef
  27. 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鈥?45 CrossRef
  28. Lourenco HR, Martin O, St眉tzle T (2002) Iterated local search. Handbook of metaheuristics. In: Operations research and management science, vol. 57, pp 321鈥?53. Kluwer Academic, Boston
  29. 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鈥擭ICSO 2007. Springer, Berlin, pp 139鈥?48 Studies in Computational Intelligence
  30. 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鈥擫ION 2007, LNCS 5313. Springer, Berlin
  31. 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鈥擡urope 2008), Estoril, Portugal
  32. 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
  33. Marinakis Y, Marinaki M, Matsatsinis N (2009) A hybrid bumble bees mating optimization鈥擥RASP algorithm for clustering. In: Corchado E (ed) HAIS 2009, LN 5572. Springer, Berlin, pp 549鈥?56
  34. Marinakis Y, Marinaki M, Dounias G (2010a) Honey bees mating optimization algorithm for large scale vehicle routing problems. Nat Comput 9:5鈥?7 CrossRef
  35. 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鈥擭ICSO 2010. Springer, Berlin, pp 305鈥?18 Studies in Computational Intelligence
  36. Marinaki M, Marinakis Y, Zopounidis C (2010c) Honey bees mating optimization algorithm for financial classification problems. Appl Soft Comput 10:806鈥?12 CrossRef
  37. 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鈥攃oncepts, principles and applications, aeries on adaptation, learning, and optimization 8. Springer, Berlin, pp 347鈥?69
  38. Marinaki M, Marinakis Y (2013a) A Honey bees mating optimization algorithm with path relinking for the vehicle routing problem with stochastic demands (submitted)
  39. 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鈥?44
  40. 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鈥?0 July 2013, Amsterdam, The Netherlands
  41. Marinakis Y, Iordanidou GR, Marinaki M (2013a) Particle swarm optimization for the vehicle routing problem with stochastic demands. Appl Soft Comput 13:1693鈥?704 CrossRef
  42. Marinakis Y, Marinaki M, Spanou P (2013b) A Memetic differential evolution algorithm for vehicle routing problem with stochastic demands and customers (submitted)
  43. Martin O, Otto SW, Felten EW (1991) Large-step markov chains for the traveling salesman problem. Complex Syst 5(3):299鈥?26
  44. 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鈥?898 CrossRef
  45. 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鈥?1 CrossRef
  46. Novoa C, Storer R (2009) An approximate dynamic programming approach for the vehicle routing problem with stochastic demands. Eur J Oper Res 196:509鈥?15 CrossRef
  47. Pham DT, Ghanbarzadeh A, Koc E, Otri S, Rahim S, Zaidi M (2006) The bees algorithm鈥攁 novel tool for complex optimization problems. In: IPROMS 2006 proceeding 2nd international virtual conference on intelligent production machines and systems, Oxford, Elsevier
  48. 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鈥?76
  49. 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鈥?69
  50. Secomandi N (2000) Comparing neuro-dynamic programming algorithms for the vehicle routing problem with stochastic demands. Comput Oper Res 27:1201鈥?225 CrossRef
  51. Shen Z, Dessouky M, Ordonez F (2005) The stochastic vehicle routing problem for large-scale emergencies. Technical Report 2005鈥?6, Department of Industrial and Systems Engineering, University of Southern California
  52. Stewart WR, Golden BL (1983) Stochastic vehicle routing: a comprehensive approach. Eur J Oper Res 14:371鈥?85 CrossRef
  53. Talbi E-G (2009) Metaheuristics: from design to implementation. Wiley, USA CrossRef
  54. Tan KC, Cheong CY, Goh CK (2007) Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation. Eur J Oper Res 177:813鈥?39 CrossRef
  55. 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鈥?11 CrossRef
  56. Teodorovic D, Dell鈥橭rco M (2005) Bee colony optimization鈥攁 cooperative learning approach to complex transportation problems. In: Advanced OR and AI methods in transportation, Proceedings of the 16th mini鈥擡URO conference and 10th meeting of EWGT, pp 51鈥?0
  57. Tillman F (1969) The multiple terminal delivery problem with probabilistic demands. Transp Sci 3:192鈥?04 CrossRef
  58. 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鈥?4 CrossRef
  59. Yan S, Chi CJ, Tang CH (2006) Inter-city bus routing and timetable setting under stochastic demands. Transp Res Part A 40:572鈥?86
  60. Yang JM, Alvarez JR (eds) (2005) Engineering optimizations via nature-inspired virtual bee algorithms. IWINAC 2005, LNCS 3562. Springer, Berlin, pp 317鈥?23
  61. Yang WH, Mathur K, Ballou RH (2000) Stochastic vehicle routing problem with restocking. Transp Sci 34:99鈥?12 CrossRef
  
• 刊物类别：Engineering
• 刊物主题：Numerical and Computational Methods in Engineering
  Theory of Computation
  Computing Methodologies
  Mathematical Logic and Foundations
  Control Engineering
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1433-7479

文摘

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.