A Bee Evolutionary Particle Swarm Optimization Algorithm for Vehicle Routing Problem

Abstract

Abstract: The vehicle routing problem (VRP) is discussed in this paper. There are studies that solve VRP by using particle swarm optimization (PSO) algorithm. However, with traditional PSO, it has slow convergence rate and a local optimum may be obtained. In order to improve the performance of PSO, an algorithm called bee evolutionary particle swarm optimization(BEPSO) is presented for VRP in this paper. By this algorithm, the best particle regarded as the queen crosses with the selected drones randomly. In this way, it takes the advantage of the best individuals information. At the same time, some drones are randomly generated and crossed with the queen such that diversity is enlarged. Experimental test shows that the proposed algorithm has better global search ability than the existing ones.

Key words: bee evolutionary, vehicle routing problem (VRP), particle swarm optimization (PSO)

Kou Mingshun， Ye Chunming， Chen Zihao. A Bee Evolutionary Particle Swarm Optimization Algorithm for Vehicle Routing Problem[J]. Industrial Engineering Journal , 2012, 15(1): 23-27.

References

［1］李军,郭耀煌.物流配送车辆优化调度理论与方法［M］.北京:中国物资出版社,2001. ［2］刘云忠,宣慧玉.车辆路径问题的模型及算法研究综述［J］.管理学报,2005,19(1):124-129. Liu Yunzhong, Xun Huiyu. Summarizing research on models and algorithms for vehicle routing problem［J］.Journal of Engineering/Engineering Management,2005,19(1):124-129. ［3］崔雪丽,马良,范炳全.车辆路径问题(VRP)的蚂蚁搜索算法［J］.系统工程学报,2004,19(4):418-422. Cui Xueli, Ma Liang, Fan Bingquan. Ant searching algorithm for vehicle routing problem［J］. Journal of Systems Engineering,2004,19(4):418-422. ［4］李宁，邹彤，孙德宝.车辆路径问题的粒子群算法研究［J］.系统工程学报.2004,19（6）：596-600. Li Ning, Zou Tong, Sun Debao. Particle swarm optimization for vehicle routing problem［J］. Journal of systems engineering, 2004, 19(6):596-600. ［5］肖健梅,李军军,王锡淮.求解车辆路径问题的改进微粒群优化算法［J］.计算机集成制造系统, 2005,11(4):577-581. Xiao Jianmei, Li Junjun, Wang Xihuai. Modified particle swarm optimization algorithm for vehicle routing probleml ［J］.Computer Integrated Manufacturing Systems,2005,11(4):577-581. ［6］邬开俊,鲁怀伟,杜三山.二进制粒子群优化算法在车辆路径问题中的应用［J］.西北民族大学学报:自然科学版，2010,31（4）：12-15. Wu Kaijun, Lu Huaiwei, Du Sanshan. Binary particle swarm optimization algorithm for the vehicle routing［J］. Journal of Northwest University for Nationalities:Natural Science,2010, 31(4): 1215. ［7］宁爱兵，马良.竞争决策算法及其在车辆路径问题中的应用［J］.管理科学学报，2005,8（6）：1018. Ning Aibing, Ma Liang. Competitive decision algorithm and its application to vehicle routing problem ［J］. Journal of Management Sciences In China, 2005,8(6):10-18. ［8］王斌,尚新春,李海峰.解决车辆路径问题的混合模拟退火算法［J］.计算机工程与设计,2009,30(3):651-653. Wang Bin, Shang Xinchun, Li Haifeng. Hybrid simulated annealing algorithm for solving vehicle routing problem［J］. Computer Engineering and Design,2009,30(3):651-653. ［9］杨进,马良.蜂群优化算法在车辆路径问题中的应用［J］.计算机工程与应用,2010,46(5):214-216. Yang Jin，Ma Liang. Wasp colony algorithm for vehicle routing problem. Computer Engineering and Applications［J］.Computer Engineering and Applications, 2010,46(5):214-216. ［10］Eberhart R C, Kennedy J. A new optimizer using particles swarm theory∥Proceeding of Sixth International Symposium on Micro Machine and Human Science［C］. Piscataway, NJ, USA: IEEE Service Center, 1995:39-43. ［11］Kennedy J, Eberhart R C. Particle swarm optimization: developments, applications and resources［C］∥Proc.Congress on Evolutionary Computation 2001. Piscataway, NJ: IEEE Press, 1999:1931-1938. ［12］Clerc M, Kennedy J. The particle swarm: explosion, stability, and convergence in a multidimensional complex space［DB/OL］.［2011 03 05］.http:∥www.cil.pku.edu.cn/resources/pso_paper/src/space_2002_CLERC.pdf.2011.3.15. ［13］刘伟,梁新兰,安晓龙.基于蜜蜂进化型粒子群算法的电力系统无功优化［J］.电力系统保护与控制, 2010,38(7):18-21. Liu Wei，Liang Xinlan，An Xiaolong. Power system reactive power optimization based on BEMPSO ［J］. Power System Protection and Control, 2010, 38(7): 18-21. ［14］刘伟莉,袁毅锐,蓝璐恺,等.改进的蜜蜂进化型遗传算法［J］.计算机工程与设计,2008,11(29):2863-2867. Liu Weili, Yuan Yirui, Lan Lukai, et al. Improved bee evolutionary genetic algorithms ［J］. Computer Engineering and Design, 2008,11(29):2863-2867. ［15］赵燕伟,吴斌,蒋丽,等.车辆路径问题的双种群遗传算法求解方法［J］.计算机集成制造系统, 2004, 10(3): 303-306. Zhao Yanwei, Wu Bin, Jiang Li, et al. Double populations genetic algorithm for vehicle routing problem ［J］. Computer Integrated Manufacturing Systems, 2004,10(3):303-306.

[1]	Xie Yang， Ye Chunming, Chen Junlan, Zhou Rong. Resource Constrained Project Scheduling Based on Chaos Particle Swam Optimization [J]. Industrial Engineering Journal , 2012, 15(3): 57-61.
[2]	Wang Nan，Li Shiqi，Wang Junfeng. Vehicle Routing with Time Windows in Material Delivery for Automobile General Assembly Line [J]. Industrial Engineering Journal , 2012, 15(2): 94-99.
[3]	Zhang Yongqian, Ding Kuixue. Layout Design in Cellular Manufacturing Based on Improved Particle Swarm Optimization [J]. Industrial Engineering Journal , 2012, 15(1): 125-130.