Decomposition techniques are an important component of modern heuristics for large instances of vehicle routing problems. The current literature lacks a characterisation of decomposition strategies and a systematic investigation of their impact when integrated into state-of-the-art heuristics. This paper fills this gap: we discuss the main characteristics of decomposition techniques in vehicle routing heuristics, highlight their strengths and weaknesses, and derive a set of desirable properties. Through an extensive numerical campaign, we investigate the impact of decompositions within the Hybrid Genetic Search of Vidal et al.~(2012) for the capacitated vehicle routing problem. We evaluate the quality of popular decomposition techniques from the literature and propose new strategies that outperform existing methods. Our results also confirm the validity of the desirable properties identified in the analysis of the literature.
Citation
Submitted to the INFORMS Journal on Combinatorial Optimisation (2022)