基于Spark的自适应蚁群算法对CVRP问题的求解

发布时间:2023-01-03 作者:徐涛, 孙鉴,刘陈伟 阅读量:

 

摘要:为解决大规模带容量限制的车辆路径问题(CVRP),提出一种基于Spark 平台的自适应蚁群算法。该算法利用改进的自适应状态转移规则和动态的信息素更新策略,减轻固定参数的弊端;结合2-opt进行局部搜索优化;在Spark集群上分布式并行实现该算法,利用Spark 提供的应用程序编程接口(API)实现对蚁群弹性分布式数据集(RDD)的各种操作,实现蚁群分布式计算。在标准数据集CVRPLib 的实验结果表明,该算法使得大规模算例问题求解速度有显著提升。

 

关键词:Spark;车辆路径问题;蚁群算法;2-opt;并行计算

 

Abstract: An adaptive ant colony algorithm based on Spark platform is proposed to solve the large-scale capacitated vehicle routing problem (CVRP). First, the algorithm uses improved adaptive state transfer rules and dynamic pheromone update strategy to alleviate the drawbacks of fixed parameters; then, it combines 2-opt for local search optimization; finally, the algorithm is implemented in distributed parallel on Spark cluster, using the application programming interface (API) provided by Spark to realize various operations on ant colony resilient distributed datasets (RDDs) to achieve ant colony distributed computation. The experimental results on the standard dataset CVRPLIB show that the algorithm has a significant improvement in the speed of solving the large-scale arithmetic problem.

 

Keywords: Spark; vehicle routing problem; ant colony algorithm; 2-opt; parallel computing

在线PDF浏览: PDF