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

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