Abstract: Vehicle routing problem is one of the most popular researches.The basic Ant Colony Optimization (ACO) algorithm  is easy to trap into the local optimum.Aiming at this shortcoming,three points of improvement was proposed.In pheromone update  stage,the pheromone on the current optimal path was updated only,which could reduce the accumulation speed of pheromone,add a reward value to ensure the quality of the early search and set a limit interval  for the value of pheromone.As the number of iterations increase,the pheromone volatility coefficient was dynamically adjusted.The optimal paths obtained in each iteration was optimized by adding the 2-optimization (2-opt) algorithm,sequential exchange strategy and sequential insertion strategy.The improved algorithm was applied to the Solomon benchmark problem of the Vehicle Routing Problems with Time Window (VRPTW) and compared with the basic ACO.The experimental results showed that the improved algorithm had better performance.

Key words: ant colony optimization algorithm, pheromone volatilization factor, reward value, 2-optimization algorithm

摘要： 车辆路径规划问题是当下发展和研究的热门问题之一,针对传统蚁群算法容易陷入局部最优的问题提出了3个改进方案。首先,在更新信息素阶段,只更新当前最优路径的信息素,降低信息素在路径上的积累速度,并增加一个奖励值保证前期迭代搜索的质量,同时为信息素的值设置了上下限。其次,随着迭代次数的增加,同时调整信息素挥发因子,逐步增大以适应蚁群搜索的信息素浓度变化。最后,加入了2-opt(2-optimization)算法、顺序交换策略、顺序插入策略来改进蚁群算法优化每次迭代得到的最优路径。将改进的算法应用在带时间窗的车辆路径问题(VRPTW )上,通过在Solomon Benchmark算例上进行实验,对比算法改进前后的路径最优解,从而证明改进后的算法性能更好。

关键词: 蚁群算法, 信息素挥发因子, 奖励值, 2-optimization算法