Learning to Prune: A Reduce-then-Optimize Approach for the Capacitated Vehicle Routing Problem

Abstract

Recent advances in mathematical programming have enabled exact solutions of the Capacitated Vehicle Routing Problem (CVRP) for hundreds of customers, while metaheuristics scale to thousands. A defining property of CVRP solutions is their sparsity: optimal solutions use only a small fraction of edges in the complete graph. We exploit this through a reduce-then-optimize pipeline in which a Graph Neural Network predicts which edges are likely to appear in the optimal solution, pruning the graph before solving. On 100-customer benchmark instances, retaining just 20% of edges yields optimal solutions within 1% of optimality while cutting runtime by up to 40%. Graph reduction further enables exact solution of 15% of test instances otherwise intractable on the complete graph. On instances with up to 2,000 customers, GNN-guided candidate lists improve metaheuristic efficiency by 40% without quality loss. The approach extends naturally to the CVRP with Time Windows, showing consistent gains across both solver types.