A Voronoi neighborhood-based search heuristic for distance/capacity constrained very large vehicle routing problems |
| |
| Authors: | Zhixiang Fang Shih-Lung Shaw Shunqing Chen Bi Yu Chen |
| |
| Institution: | 1. State Key Laboratory of Information Engineering in Surveying, Mapping, and Remote Sensing , Wuhan University , Wuhan , PR , China zxfang@whu.edu.cn;3. State Key Laboratory of Information Engineering in Surveying, Mapping, and Remote Sensing , Wuhan University , Wuhan , PR , China;4. Department of Geography , University of Tennessee , Knoxville , TN , USA;5. CEO, Guangzhou Augur Intelligent Technology Co. Ltd. , Guangzhou , PR China;6. Engineering Research Center for Spatio-Temporal Data Smart Acquisition and Application , Ministry of Education of China , Wuhan , China |
| |
| 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 |
|
|
