LLM-Driven Neighborhood Search for Efficient Heuristic Design

Handcrafting heuristics often demands extensive domain knowledge and significant development effort. Recently, heuristic search powered by large language models (LLMs) has emerged as a new approach, offering enhanced automation and promising performance. Existing methods rely on an evolutionary computation (EC) framework with carefully designed prompt strategies. However, the large heuristic search space poses significant challenges for these EC-based methods. This paper proposes a simple yet effective LLM-driven Heuristic Neighborhood Search (LHNS) paradigm to iteratively search in the heuristic neighborhood in a principled way for efficient heuristic design. Three distinct methods are designed under this neighborhood search paradigm and demonstrated on three widely studied problems. Results indicate that LHNS exhibits very competitive performance and surpasses existing EC-based methods in efficiency. It also demonstrates sufficient robustness in the absence of problem-specific knowledge regarding the target problem. The efficiency and robust adaptability make it a practical new solution for efficient heuristic design.