工业工程 ›› 2012, Vol. 15 ›› Issue (1): 23-27.

• 专题论述 • 上一篇    下一篇

应用蜜蜂繁殖进化型粒子群算法求解车辆路径问题

  

  1. 上海理工大学 管理学院,上海 200093
  • 出版日期:2012-02-29 发布日期:2012-03-13
  • 作者简介: 寇明顺(1985-),男,山东省人,硕士研究生,主要研究方向为工业工程
  • 基金资助:

    上海市研究生创新基金资助项目(JWCXSL1022);教育部人文社会科学规划基金资助项目(10YJA630187);高等学校博士点基金资助项目(20093120110008);上海市重点学科建设资助项目(S30504)

A Bee Evolutionary Particle Swarm Optimization Algorithm for Vehicle Routing Problem

  1. College of Management,University of Shanghai for Science and Technology, Shanghai 200093,China
  • Online:2012-02-29 Published:2012-03-13
  • Supported by:

    上海市研究生创新基金资助项目(JWCXSL1022);教育部人文社会科学规划基金资助项目(10YJA630187);高等学校博士点基金资助项目(20093120110008);上海市重点学科建设资助项目(S30504)

摘要: 为了提高粒子群算法求解车辆路径问题时收敛速度和全局搜索能力,将蜜蜂繁殖进化机制与粒子群算法相结合,应用到CVRP问题的求解。该算法中,最优的个体作为蜂王与通过选择机制选择的雄蜂以随机概率进行交叉,增强了最优个体信息的应用能力;同时,随机产生一部分雄蜂种群,并将其与蜂王交叉增加了算法的多样性。实例分析表明该算法具有较好的全局搜索能力,验证了该算法的可行性。

关键词: 蜜蜂繁殖进化, 车辆路径问题, 粒子群算法

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)