Computer Engineering and Applications ›› 2016, Vol. 52 ›› Issue (7): 35-42.

Previous Articles     Next Articles

Double evolutional artificial bee colony algorithm for solving vehicle routing problem

MAO Sheng1,2, XIE Wenjun1, ZHANG Jianye1, ZHAO Xiaolin1   

  1. 1.School of Aeronautics and Astronautics Engineering, Air Force Engineering University, Xi’an 710038, China
    2.Key Laboratory of Science and Technology on Avionics Integration Technologies, Shanghai 200233, China
  • Online:2016-04-01 Published:2016-04-19

车辆路径问题的双重进化蜂群算法求解研究

毛  声1,2,谢文俊1,张建业1,赵晓林1   

  1. 1.空军工程大学 航空航天工程学院,西安 710038
    2.航空电子系统综合技术重点实验室,上海 200233

Abstract: Aimed at the flaws of traditional exploitation search of low efficiency, randomness and prone to be run into local optimum, a Double Evolutional Artificial Bee Colony(DEABC) algorithm is proposed. The half stochastic optimal searching strategy is used to improve traditional exploitation search operators, and the search efficiency and fitness guidance are improved. Two different half stochastic optimal searching operators are adopted in exploitation search to constitute the double evolutional process, and the exploration search is improved for different optimizing objectives. Experimental results demonstrate that the algorithm can increase convergence speed, improve the solutions and promote timeliness under reasonable termination threshold.

null

Key words: Artificial Bee Colony(ABC) algorithm, optimization, vehicle routing problem

摘要: 针对传统人工蜂群算法局部搜索的低效性,提出了双重进化人工蜂群算法。在需要两点进行操作的搜索过程中,采用一点随机选取,另一点通过遍历可行解,以其中最优解确定位置的半随机式搜索策略。用该策略改进插入点算子和逆转序列算子,分别在两对以及三对城市间距离之和的解空间维度上交叉搜索,并应用到局部搜索中构成双重进化过程,提高了搜索效率和适应值引导性。实验结果表明,该算法较已有方法提高了收敛速度,优化了目标解,并可通过合理设置终止阈值提高时效性。

关键词: 人工蜂群算法, 优化, 车辆路径问题