A meta-analysis of set partitioning/set covering based matheuristics for vehicle routing problems

The Vehicle Routing Problem (VRP) is a cornerstone of operations research with broad real-world relevance. As variants increase in complexity, researchers increasingly adopt metaheuristics and matheuristics to find high-quality solutions. We focus on set partitioning (SP) and set covering (SC) formulations as enhancement mechanisms in matheuristics for VRPs. These methods exploit previously generated routes by decomposing and recombining solutions, either as a post-optimization step or iteratively. We conducted a meta-analysis of 30 implementations, selected from 54 eligible studies identified via systematic review of Web of Science and Scopus, complemented by backward snowballing. Using a random-effects model, we quantified the effect of SP/SC enhancements on solution quality. On average, SP/SC improved solutions by 0.51% (95% CI: 0.41%–0.61%). Although the numerical gains are modest, they are consistent and significant, highlighting the practical value of these classical formulations in hybrid heuristic frameworks. • Set Partitioning/Set covering enhances Vehicle Routing Problems heuristics. • Meta-analysis of 30 implementations quantifies impact on solutions. • Methods effective across diverse Vehicle Routing Problems variants. • Improves solutions by average 0.51% (95% interval: 0.41%–0.61%).