A novel membrane algorithm for capacitated vehicle routing problem

详细信息    查看全文

• 作者：Yunyun Niu (1)
  Shuo Wang (2)
  Juanjuan He (2)
  Jianhua Xiao (3)
  
  1. School of Electronic Engineering and Computer Science ; Peking University ; Beijing ; 100871 ; China
  2. Key Laboratory of Image Processing and Intelligent Control ; Department of Control Science and Engineering ; Huazhong University of Science and Technology ; Wuhan ; 430074 ; China
  3. The Research Center of Logistics ; Nankai University ; Tianjin ; 300071 ; China
  
• 关键词：Membrane algorithm ; Ant colony optimization ; Max鈥搈in ant system ; Capacitated vehicle routing problem
• 刊名：Soft Computing - A Fusion of Foundations, Methodologies and Applications
• 出版年：2015
• 出版时间：February 2015
• 年：2015
• 卷：19
• 期：2
• 页码：471-482
• 全文大小：692 KB
• 参考文献：1. Baker BM, Ayechew MA (2003) A genetic algorithm for the vehicle routing problem. Comput Oper Res 7:301鈥?17
  2. Chen AL, Yang GK, Wu ZM (2006) Hybrid discrete particle swarm optimization algorithm for capacitated vehicle routing problem. J Zhejiang Univ Sci A 7:607鈥?14 CrossRef
  3. Colorni A, Dorigo M, Maniezzo V (1991) Distributed optimization by ant colonies. Proc First Eur Conf Artif Life 1991:134鈥?42
  4. Colorni A, Dorigo M, Maniezzo V (1992) An investigation of some properties of ant algorithm. Elsevier Publishing, Brussels
  5. Dantzig G, Ramser JH (1959) The truck dispatching problem. Manag Sci 6:80鈥?1 CrossRef
  6. Dorigo M, Di Caro G, Gambardella LM (1999) Ant algorithms for discrete optimization. Artif Life 5:137鈥?72 CrossRef
  7. Gendreau M, Laporte G, Musaraganyi C, Taillard ED (1999) A tabu search heuristic for the heterogeneous fleet vehicle routing problem. Comput Oper Res 41:421鈥?51
  8. Gendreau M, Iori M, Laporte G, Martello S (2008) A tabu search heuristic for the vehicle routing problem with two-dimensional loading constraints. Networks 1:4鈥?8 CrossRef
  9. Lawrence B, Bruce G (1981) Classification of vehicle routing and scheduling. Networks 11:97鈥?08 CrossRef
  10. Lin S, Kernighan BW (1973) An effective heuristic algorithm for the TSP. Oper Res 21:498鈥?16 CrossRef
  11. Nishida TY (2005) Membrane algorithm: an approximate algorithm for NP-complete optimization problems exploiting P-systems. In: Proceedings of 6th international workshop on membrane computing, pp 26鈥?3
  12. Osman IH, Abo-Sinna MA, Mouse AA (2005) An effective genetic algorithm approach to multiobjective routing problems. Appl Math Comput 162:769鈥?81 CrossRef
  13. P膬un Gh (2000) Computing with membranes. J Comput Syst Sci 61(1):108鈥?43 CrossRef
  14. P膬un Gh (2002) Membrane computing: an introduction. Springer, Berlin CrossRef
  15. P膬un Gh, Rozenberg G, Salomaa A (2010) The Oxford handbook of membrane computing. Oxford University Press, Oxford CrossRef
  16. St眉tzle T, Hoos H (1996) Improving the ant-system: a detailed report on the MAX鈥揗IN ant system. Technical Report AIDA-96-12, FG Intellektik, TH Darmstadt
  17. St眉tzle T, Hoos H (1997) MAX鈥揗IN ant system and local search for the traveling salesman problem. Int Conf Evol Comput 1997:308鈥?13
  18. St眉tzle T, Hoos H (2000) MAX鈥揗IN ant system. Futur Gener Comput Syst 16:889鈥?14 CrossRef
  19. Tarasewich P, McMullen PR (2002) Swarm intelligence: power in numbers. Commun ACM 45(8):62鈥?7 CrossRef
  20. Tavakkoli-Moghaddam R, Safaei N, Gholipour Y (2006) A hybrid simulated annealing for the capacitated vehicle routing problems with the independent tour length. Appl Math Comput 176:445鈥?54 CrossRef
  21. Zachariadis E, Tarantilis C, Kiranoudis C (2009) A guided tabu search for the vehicle routing problem with two-dimensional loading constraints. Eur J Oper Res 195:729鈥?43 CrossRef
  22. Zhang G, Gheorghe M, Wu C (2008) A quantum-inspired evolutionary algorithm based on P systems for knapsack problem. Fundam Inform 87:93鈥?16
  23. Yu B, Yang Z, Ya B (2009) An improved ant colony optimization for vehicle routing problem. Eur J Oper Res 196:171鈥?76 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

文摘

This study is focused on solving the capacitated vehicle routing problem (CVRP) by applying a novel membrane algorithm based on ant colony optimization (MA_ACO). The effect of non-determinism on the performance of the membrane algorithm is also studied in this work. In this approximate approach model, a membrane system is considered to be a non-deterministic distributed parallel framework, and ant colony optimization (ACO) is used as a sub-algorithm of elementary membranes. With the purpose of maintaining balance between the convergence rate and the population diversity, MA_ACO supports sub-algorithms for elementary membranes based on two types of ACO. The elementary membranes send their best solutions to the skin membrane. In the next step, the best one in the skin membrane is sent back to every inner membrane with a fixed probability. All of the elementary membranes have thus a chance to receive the best result and make changes to the current search direction. Thirty benchmark problems of CVRP are utilized to confirm the effectiveness of the proposed membrane algorithm. Experimental results show that compared with other algorithms proposed in the previous literature, our algorithm is very competitive. The new best solutions for seven instances are also listed.