Reproduce “Edge-Selector Model Applied for Local Search Neighborhood for Solving Vehicle Routing Problems” on OpenResearch

About this paper

Bachtiar Herdianto, Romain Billot, Flavien Lucas, Marc Sevaux, Daniele Vigo

Researchers from IMT Atlantique, IMT Nord Europe, Université Bretagne Sud, and University of Bologna developed a hybrid optimization framework that employs a Graph Neural Network (GNN) based "edge selector" to guide local search in metaheuristics for Vehicle Routing Problems. This approach statistically improved solution quality on large-scale CVRP and CVRPTW instances, reducing the average gap to the Best Known Solution for HGS by 0.015% on X instances and for HGS-TW by 0.093% on large Gehring & Homberger instances, while demonstrating generalizability across problem variants and metaheuristics.

Key insights

• Machine learning models, particularly GNNs, can effectively learn to identify specific solution components (edges) that are unlikely to be part of high-quality improvements, thereby intelligently pruning the local search space.
• The proposed GNN-based edge selector exhibits strong generalizability, enabling a single trained model to enhance diverse metaheuristic structures and VRP variants (e.g., CVRP to CVRPTW) without problem-specific re-training.
• Integrating ML guidance "in-loop" with state-of-the-art metaheuristics can achieve statistically significant improvements in solution quality, pushing performance beyond traditional highly-tuned solvers.

Summary by alphaXiv.