基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解

作者：李奕颖; 秦刚^*

来源：计算机系统应用, 2019, 28(07): 9-16.

DOI：10.15888/j.cnki.csa.007000

• 带时间窗车辆路径问题
• Spark平台
• 蚁群算法
• 邻域搜索

为应对大数据时代对带时间窗车辆路径问题(VRPTW)的实时求解要求,提出基于Spark平台的改进蚁群算法.在算法层面,利用改进的状态转移规则和轮盘赌选择机制构建初始解,结合k-opt邻域搜索进行路径构建优化,改进最大最小蚁群算法中的信息素更新策略;在实现层面,利用Spark提供的API对蚁群RDD进行操作,实现蚁群分布式并行求解.在标准算例Solomon benchmark和Gehring&Homberger benchmark的实验结果表明,该算法在大规模问题的求解精度和速度上有明显提升.

• 单位
  中国科学院计算机网络信息中心; 中国科学院大学