Randomized Adaptive Spatial Decoupling for Large-Scale Vehicle Routing with Time Windows

Abstract

In recent years, the size of combinatorial applications and the need to produce high-quality solutions quickly have in-creased steadily, providing significant challenges for opti-mization algorithms. This paper addresses this issue for large-scale vehicle routing problems with time windows, a class of very difficult optimization problems involving com-plex spatial and temporal dependencies. It proposes a ran-domized adaptive spatial decoupling (RASD) scheme for ve-hicle routing with time windows in order to produce high-quality solutions quickly. Experimental results on hard in-stances with 1,000 customers and 90 vehicles show that the RASD scheme, together with large neighborhood search, sig-nificantly improves the quality of the solutions under time constraints. Interestingly, the RASD scheme, when allowed to run longer, also improves the best available solutions in almost all the tested instances.