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 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; heuristics; large-scale optimization; simulated annealing; vehicle routing problem
Document Type: Research Article
Affiliations: 1: State Key Laboratory of Information Engineering in Surveying, Mapping, and Remote Sensing, Wuhan University, Wuhan, PR, China 2: CEO, Guangzhou Augur Intelligent Technology Co. Ltd., Guangzhou, PR China 3: Engineering Research Center for Spatio-Temporal Data Smart Acquisition and Application, Ministry of Education of China, Wuhan, China
Publication date: 01 April 2013
- Editorial Board
- Information for Authors
- Subscribe to this Title
- Ingenta Connect is not responsible for the content or availability of external websites
- Access Key
- Free content
- Partial Free content
- New content
- Open access content
- Partial Open access content
- Subscribed content
- Partial Subscribed content
- Free trial content