A Parallel Metaheuristic Based On Spark Framework For Capacitated Vehicle Routing Problem

The vehicle routing problem is a classic NP-hard problem,which has a high scientific and applied.The research of the vehicle routing problem is beneficial to the reasonable planning of the transportation path,and the reasonable path planning in reality can improve the efficiency,reduce the cost and save the resources.This paper does research for the capacitated vehicle routing problem.Since being proposed,this question has been a hot issue studied by a lot of scholars,and a series of excellent algorithms has been put forward for many years.Based on the previous works,this paper studies and proposes a parallel heuristic algorithm based on the Spark framework.The goal is to find a feasible solution with high quality in a short time.The research covers three main tasks:First,we implement the classic Tabu search algorithm including five kinds of neighborhood structures,and the Granular neighborhood is used to reduce the search time;Second,a parallel algorithm is proposed that can be executed parallelly in multiple TS nodes.The nodes are divided into two categories,TS Nodes cooperate mutually through a Solution Pool,each node sends the best solution found by itself to the Solution Pool and receives the solution from Solution Pool.Solutions in the Solution Pool form a different population according to similarity;Third,a parallel algorithm is implemented on the Spark framework and tested by two different data generated by Christofides and Golden respectively.The experiment results show that the Tabu search is feasible and the parallel algorithm can achieve good results in a short time.