Learning Heuristics to Solve Dynamic Vehicle Routing Problems Using Large Language Models

Modern logistics companies face significant challenges in efficiently managing dynamic transportation systems, particularly in addressing Dynamic Vehicle Routing Problems (DVRP). These complex problems require specialized expertise for effective algorithm design. Traditional approaches often rely on manual algorithm design for specific routing problems. Reinforcement learning (RL)-based methods, though capable of learning heuristics for diverse routing problems, suffer from poor training efficiency and weak generalization to out-of-distribution (OOD) scenarios. To address these limitations, we leverage the strong generalization capabilities of large language models (LLMs) and adopt an LLM-based heuristic learning approach for DVRP. Our method learns heuristics and autonomously generates executable code within an evolutionary framework, requiring fewer than 10 samples for training. This enables fast training while maintaining robust performance on large-scale OOD instances. Comprehensive experiments across multiple routing problems—including Vehicle Routing Problems (VRP), VRP with Time Windows (VRPTW), DVRP, and DVRP with Time Windows (DVRPTW)—demonstrate that our approach learns effective heuristics and consistently surpasses Greedy baselines. Moreover, in constrained optimization tasks (VRPTW and DVRPTW), our method attains higher feasibility rates than Greedy baselines and approaches the performance of expert-designed heuristics. The proposed method presents a promising and scalable solution with significant potential for real-world industrial deployment.1