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

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

Solving Vehicle Routing Problem with Time Window Based on Spark's Improved Ant Colony Algorithm

In order to cope with the real-time solution requirements of the Vehicle Routing Problem with Time Window (VRPTW) in the era of big data, this study proposed an improved parallel ant colony algorithm based on Spark platform. At the algorithm level, the improved state transition rule and roulette selection mechanism are used to construct the initial solution, and the k-opt local search is used to optimize the path construction. In addition, the improved pheromone update strategy of max-min ant colony algorithm is applied. At the implement level, the ant colony is encapsulated into RDD, which is operated by Spark API to realize distributed construction solution. The experimental results of the Solomon benchmark and Gehring & Homberger benchmark show that the proposed algorithm can improve the accuracy and speed of large-scale problems.