A Voronoi neighborhood-based search heuristic for distance/capacity constrained very large vehicle routing problems

Abstract

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.

Keywords:

• graph theory
• large-scale optimization
• simulated annealing
• vehicle routing problem
• heuristics

Acknowledgments

This study was supported in part by the National Science Foundation of China (grants no. 40701153, no. 40971233, no. 40830530, and no. 60872132), the project from State Key Laboratory of Resources and Environmental Information Systems, CAS of China (no. 2010KF0001SA), LIESMARS Special Research Funding, and the Funding for Excellent Talents in Wuhan University.