A Novel Spatial-Temporal Voronoi Diagram-Based Heuristic Approach for Large-Scale Vehicle Routing Optimization with Time Constraints

ISPRS International Journal of Geo-Information

Wei Tu³  Qingquan Li¹  Zhixiang Fang²  Baoding Zhou¹ 

[1] Shenzhen Key Laboratory of Spatial Information Smart Sensing and Services, College of Civil Engineering, Shenzhen University, Shenzhen 518060, China; E-Mail:;State Key Laboratory of Information Engineering in Surveying, Mapping, and Remote Sensing, Wuhan University, Wuhan 430079, China; E-Mail:;College of Information Engineering, Shenzhen University, Shenzhen 518060, China

关键词: spatial decision support system;    vehicle routing problem;    Voronoi diagram;    heuristics;    local search;    distance decay;   

DOI  :  10.3390/ijgi4042019

来源: mdpi

【 摘 要 】

Vehicle routing optimization (VRO) designs the best routes to reduce travel cost, energy consumption, and carbon emission. Due to non-deterministic polynomial-time hard (NP-hard) complexity, many VROs involved in real-world applications require too much computing effort. Shortening computing time for VRO is a great challenge for state-of-the-art spatial optimization algorithms. From a spatial-temporal perspective, this paper presents a spatial-temporal Voronoi diagram-based heuristic approach for large-scale vehicle routing problems with time windows (VRPTW). Considering time constraints, a spatial-temporal Voronoi distance is derived from the spatial-temporal Voronoi diagram to find near neighbors in the space-time searching context. A Voronoi distance decay strategy that integrates a time warp operation is proposed to accelerate local search procedures. A spatial-temporal feature-guided search is developed to improve unpromising micro route structures. Experiments on VRPTW benchmarks and real-world instances are conducted to verify performance. The results demonstrate that the proposed approach is competitive with state-of-the-art heuristics and achieves high-quality solutions for large-scale instances of VRPTWs in a short time. This novel approach will contribute to spatial decision support community by developing an effective vehicle routing optimization method for large transportation applications in both public and private sectors.

【 授权许可】

CC BY   
© 2015 by the authors; licensee MDPI, Basel, Switzerland.