ARS: Automatic Routing Solver with Large Language Models
This addresses the problem of time-consuming manual solver design for practitioners in logistics and routing, offering an automated solution for complex constraints, though it is incremental as it builds on existing LLM-based methods.
The paper tackles the challenge of automating routing algorithm design for complex real-world Vehicle Routing Problems (VRPs) by introducing RoutBench, a benchmark of 1,000 VRP variants, and ARS, an LLM-based solver that automatically generates constraint-aware heuristic code. The result shows ARS outperforms state-of-the-art methods, solving 91.67% of common VRPs and achieving at least a 30% improvement across benchmarks.
Real-world Vehicle Routing Problems (VRPs) are characterized by a variety of practical constraints, making manual solver design both knowledge-intensive and time-consuming. Although there is increasing interest in automating the design of routing algorithms, existing research has explored only a limited array of VRP variants and fails to adequately address the complex and prevalent constraints encountered in real-world situations. To fill this gap, this paper introduces RoutBench, a benchmark of 1,000 VRP variants derived from 24 attributes, for evaluating the effectiveness of automatic routing solvers in addressing complex constraints. Along with RoutBench, we present the Automatic Routing Solver (ARS), which employs Large Language Model (LLM) agents to enhance a backbone algorithm framework by automatically generating constraint-aware heuristic code, based on problem descriptions and several representative constraints selected from a database. Our experiments show that ARS outperforms state-of-the-art LLM-based methods and commonly used solvers, automatically solving 91.67% of common VRPs and achieving at least a 30% improvement across all benchmarks.