A Fast Algorithm for Large Scale Vehicle Routing Optimization Based on Voronoi Neighbors

Logistic requires designing delivery plan intelligently and quickly.Traditional vehicle routing optimal algorithms can only solve vehicle routing problem no more than 2000 customers,and cost much computing efforts.This paper proposes a fast heuristic algorithm for large scale logistic vehicle routing optimization based on Voronoi neighbors.This algorithm creates an initial solution and improves it iteratively.The creation makes use of the Voronoi neighbors to cluster customers into groups from bottom to up,considering the vehicle capacity constraint.The route in each group is generated by the cheapest insertion algorithm.The improvement employs local search in k-order Voronoi neighbors to search the promising neighbor solution.The simulated annealing criterion is adopted to accept some bad solutions,escaping from local minima.The computational test has been done with a synthetic large scale vehicle routing problem dataset in Beijing.The result indicates the proposed algorithm could solve vehicle routing problem up to 12 000 customers in 4500 seconds.It costs few computational efforts,and has a quite stable performance.Comparison to other heuristics shows the proposed algorithm could provide high quality solution in a short time.The conclusion indicates the proposed algorithm is suitable for large scale logistic vehicle routing optimization.