Abstract: To tackle insufficient convergence and exploration capability and time-consuming in solving the Capacitated Vehicle Routing Problem (CVRP),an adaptive large neighborhood search based artificial bee colony algorithm for CVRP was proposed.In this algorithm,five removal operators and two insertion operators were designed.Moreover,a distinct operator-using strategy,a careful scouter strategy and a loose update strategy were incorporated into the proposed method to improve its performance.As a result,the proposed algorithm could search efficiently for acceptable solutions,as it was able to converge to most of the best known solutions on the experimental datasets,and four best known exact solutions were updated.The results showed that the proposed approach had excellent comprehensive performance and all three optimization strategies were effective.

Key words: capacitated vehicle routing problem, artificial bee colony algorithm, adaptive large neighborhood search, distinct operator-using strategy, loose update strategy

摘要： 为解决带容量约束的车辆路径问题(CVRP)求解时收敛能力与探索能力不足、耗时长等问题,提出一种基于大邻域搜索的人工蜂群优化算法。设计了5个移除算子和2个插入算子,采用算子区别应用机制、仔细侦查蜂机制、更新策略宽松机制优化算法。所提算法能够快速搜索到可接受解,在实验数据集上能收敛到大部分已知最优解,并更新了4个已知最优精准解。实验结果表明,3种优化策略均能有效提升算法效率,算法具有较好的综合性能。

关键词: 带容量约束车辆路径问题, 人工蜂群算法, 自适应大邻域搜索, 算子区别应用机制, 宽松更新策略