Automatic Algorithm Design Assisted by LLMs for Solving Vehicle Routing Problems

Currently, automatic algorithm design for solving combinatorial optimization problems (COPs) is a popular research area, since manual algorithm design typically demands substantial domain-specific knowledge and considerable time cost. In this paper, we propose an automatic algorithm design paradigm, AutoDH, based on deep reinforcement learning (DRL) that takes advantages of both large language models (LLMs) and traditional heuristics for solving the Capacitied Vehicle Routing Problems (CVRPs). In AutoDH, the agent can intelligently select the most cost-effective heuristics from the LLM pool, improvement pool, and perturbation pool, according to the current state, to refine the current solution. The LLM pool consists of three LLMs that can automatically design algorithms to enhance the current solution based on the given prompts. The improvement pool consists of local search heuristics to fine-tune and improve the current solutions. Meanwhile, heuristics in the perturbation pool can significantly perturb the current solutions to escape local optima. Moreover, to ensure the learning efficacy of AutoDH, a reward that integrates the improvement in solution quality, the time cost of heuristic, and the cost of invoking LLMs API is designed. The effectiveness of AutoDH is validated on CVRPs with various scales.