A Supervised Learning Framework for Accelerating Solvers and Metaheuristics in Routing Problems

Abstract

Routing problems such as the traveling salesman problem (TSP) and the capacitated vehicle routing problem (CVRP) are computationally challenging due to the exponential growth of their feasible solution spaces with increasing instance size. Established optimization approaches, including exact algorithms and (meta)heuristics, often face scalability limits as instance size increases. In this study, we introduce a supervised machine learning (ML) framework that assigns a confidence score to each edge, indicating the likelihood of appearing in high‐quality solutions. Using these predictions, we develop systematic strategies to reduce the search space by pruning low‐relevance edges. We integrate the ML‐based edge classifier into a mathematical optimization solver and a metaheuristic as a preprocessing step and evaluate its effectiveness in a comprehensive numerical study on instances with up to 1,000 nodes. On the tested instances, the proposed ML‐based preprocessing removed approximately up to 90% of candidate edges and reduced solver runtimes, while preserving the baseline‐optimal solution in all or nearly all cases for conservative parameter settings. For instances not solved to optimality within the time limit, average optimality gaps decrease by up to 1.7% (TSP) and over 7% (CVRP). Within a state‐of‐the‐art metaheuristic, learned pruning decreases the time required to reach solutions of equal or better quality by up to 20–25 s under a 60‐second time limit, and improves average solution quality by up to 0.75% (TSP) and 0.86% (CVRP) on large‐scale instances.