Abstract: A heuristic algorithm integrating simulated annealing and Voronoi long edge guided optimization is proposed for large scale vehicle routing problem. The simulated annealing strategy is employed to accept some bad neighborhood solutions in local search. Voronoi long edge guides to improve the unreasonable local structure in routes. A large scale vehicle routing benchmark instances is designed to test the proposed algorithm. The results show that the proposed algorithm can provide high quality solution in a short time.