Local search heuristics for very large-scale vehicle routing problems (VRPs) have made remarkable advances in recent years. However, few local search heuristics have focused on the use of the spatial neighborhood in Voronoi diagrams to improve local searches. Based on the concept of a k-ring shaped Voronoi neighbor, we propose a Voronoi spatial neighborhood-based search heuristic and algorithm to solve very large-scale VRPs. In this algorithm, k-ring Voronoi neighbors of a customer are limited to building and updating local routings, and rearranging local routings with improper links. This algorithm was evaluated using four sets of benchmark tests for 200–8683 customers. Solutions were compared with specific examples in the literature, such as the one-depot VRP. This algorithm produced better solutions than some of the best-known benchmark VRP solutions and requires less computational time. The algorithm outperformed previous methods used to solve very large-scale, real-world distance constrained capacitated VRP.