Search papers, labs, and topics across Lattice.
The paper introduces AILS-AHD, a novel Adaptive Iterated Local Search method for the Capacitated Vehicle Routing Problem (CVRP) that uses Large Language Models (LLMs) to automatically design and optimize ruin heuristics. This approach addresses the computational challenges of large-scale CVRP instances by dynamically generating heuristics within an evolutionary search framework and incorporating an LLM-based acceleration mechanism. Empirical results demonstrate that AILS-AHD outperforms state-of-the-art solvers like AILS-II and HGS, establishing new best-known solutions for 8 out of 10 large-scale CVRPLib benchmark instances.
LLMs can automatically design better heuristics for combinatorial optimization, leading to state-of-the-art results on large-scale CVRP instances.
The Capacitated Vehicle Routing Problem (CVRP), a fundamental combinatorial optimization challenge, focuses on optimizing fleet operations under vehicle capacity constraints. While extensively studied in operational research, the NP-hard nature of CVRP continues to pose significant computational challenges, particularly for large-scale instances. This study presents AILS-AHD (Adaptive Iterated Local Search with Automatic Heuristic Design), a novel approach that leverages Large Language Models (LLMs) to revolutionize CVRP solving. Our methodology integrates an evolutionary search framework with LLMs to dynamically generate and optimize ruin heuristics within the AILS method. Additionally, we introduce an LLM-based acceleration mechanism to enhance computational efficiency. Comprehensive experimental evaluations against state-of-the-art solvers, including AILS-II and HGS, demonstrate the superior performance of AILS-AHD across both moderate and large-scale instances. Notably, our approach establishes new best-known solutions for 8 out of 10 instances in the CVRPLib large-scale benchmark, underscoring the potential of LLM-driven heuristic design in advancing the field of vehicle routing optimization.
