Adaptive Large Neighborhood Search (ALNS) remains a dominant metaheuristic for vehicle routing, yet the design of its destroy and repair operators relies heavily on manual engineering. Although Neural Combinatorial Optimization with Deep Reinforcement Learning (DRL) offers automation, it introduces severe computational overhead. We challenge this paradigm by proposing novel ALNS operators based on Unsupervised Learning. Our approach employs dynamic K-Means clustering applied to both raw feature spaces and latent PCA projections to identify spatial groups and guide solution reconstruction. Evaluating on the Orienteering Problem (OPSWTW) and the Capacitated Vehicle Routing Problem (CVRP), we demonstrate that a classical adaptive ALNS equipped with these operators significantly outperforms a state-of-the-art DRL baseline. We report substantial gains on large-scale instances with competitive execution times, suggesting that employing smarter and more robust heuristic operators at the execution level impacts performance more significantly than the sophistication of DRL-based control.
To use DR-ALNS for solving COPs, follow these steps:
- Install uv!
- Install dependencies:
uv sync - Unzip the data file:
DR-ALNS/cluster_alns/rl/environments/data.7z - Copy the data files to the paper_reproduction directories:
DR-ALNS/paper_reproduction/tsp/dataDR-ALNS/paper_reproduction/cvrp/data
- Configure experiment configuration in the config file (e.g., in 'DR-ALNS/paper_reproduction/tsp/configs/tsp_rl.yml')
- Go to the example directory of the problem you want to solve (e.g., 'DR-ALNS/paper_reproduction/tsp/')
- Run DR-ALNS algorithm:
uv run python rl_tsp.py