ARS: Automatic Routing Solver with Large Language Models

📄 arXiv: 2502.15359v3 📥 PDF

作者: Kai Li, Fei Liu, Zhenkun Wang, Xialiang Tong, Xiongwei Han, Mingxuan Yuan, Qingfu Zhang

分类: cs.AI, cs.CL

发布日期: 2025-02-21 (更新: 2025-05-19)

备注: Authorship is under discussion; arXiv release will follow finalization

💡 一句话要点

提出ARS：利用大语言模型自动解决具有复杂约束的车辆路径问题

🎯 匹配领域: 支柱九：具身大模型 (Embodied Foundation Models)

关键词: 车辆路径问题 大语言模型 自动求解器 约束感知 启发式算法

📋 核心要点

  1. 现有VRP求解器设计依赖人工，难以应对现实世界中复杂多变的约束条件，且缺乏通用性。
  2. ARS利用大语言模型自动生成约束感知的启发式代码，增强现有算法框架，从而实现自动求解。
  3. 实验表明，ARS在RoutBench基准测试中显著优于现有方法，能够有效解决多种VRP变体。

📝 摘要（中文）

现实世界的车辆路径问题(VRPs)具有各种实际约束，使得手动设计求解器既需要大量知识又耗时。虽然自动设计路径算法越来越受到关注，但现有的研究仅探索了有限的VRP变体，并且未能充分解决现实场景中遇到的复杂和普遍的约束。为了填补这一空白，本文引入了RoutBench，这是一个包含1000个VRP变体的基准，这些变体源自24个属性，用于评估自动路径求解器在解决复杂约束方面的有效性。与RoutBench一起，我们提出了自动路径求解器(ARS)，它使用大型语言模型(LLM)代理来增强骨干算法框架，通过基于问题描述和从数据库中选择的几个代表性约束自动生成约束感知的启发式代码。实验表明，ARS优于最先进的基于LLM的方法和常用的求解器，自动解决了91.67%的常见VRP，并在所有基准测试中实现了至少30%的改进。

🔬 方法详解

问题定义：现实世界的车辆路径问题（VRPs）通常包含各种复杂的约束条件，例如时间窗、容量限制、车辆类型限制等。传统的手动设计求解器方法需要领域专家花费大量时间和精力，针对不同的约束条件设计不同的启发式算法，缺乏通用性和可扩展性。现有的自动求解器方法通常只关注有限的VRP变体，无法有效解决实际场景中遇到的复杂约束。

核心思路：ARS的核心思路是利用大型语言模型（LLM）的强大代码生成能力，根据VRP的问题描述和约束条件，自动生成约束感知的启发式代码，从而增强现有的骨干算法框架。通过这种方式，ARS可以自动适应不同的VRP变体，并有效地解决复杂约束。

技术框架：ARS的整体框架包括以下几个主要模块：1) 问题描述模块：将VRP的问题描述和约束条件转化为LLM可以理解的文本格式。2) LLM代理模块：利用LLM生成约束感知的启发式代码。该模块的关键在于如何设计合适的prompt，引导LLM生成高质量的代码。3) 骨干算法框架：选择一个现有的VRP求解算法作为骨干框架，例如LKH、OR-Tools等。4) 代码集成模块：将LLM生成的启发式代码集成到骨干算法框架中，从而增强算法的性能。

关键创新：ARS的关键创新在于利用LLM自动生成约束感知的启发式代码。与传统的手动设计方法相比，ARS可以大大降低人工成本，并提高求解器的通用性和可扩展性。与现有的基于LLM的方法相比，ARS更加注重对约束条件的建模，并能够生成更加有效的启发式代码。

关键设计：ARS的关键设计包括：1) Prompt设计：设计合适的prompt，引导LLM生成高质量的启发式代码。Prompt需要包含VRP的问题描述、约束条件、以及一些示例代码。2) 约束选择：从约束数据库中选择代表性的约束条件，用于指导LLM生成代码。3) 代码集成：设计合适的接口，将LLM生成的代码集成到骨干算法框架中。4) 评价指标：设计合适的评价指标，用于评估LLM生成的代码的质量。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

ARS在RoutBench基准测试中表现出色，自动解决了91.67%的常见VRP，并在所有基准测试中实现了至少30%的改进。与最先进的基于LLM的方法和常用的求解器相比，ARS具有显著的优势，证明了其在解决复杂约束VRP方面的有效性。

🎯 应用场景

ARS具有广泛的应用前景，可以应用于物流配送、交通运输、生产调度等领域。通过自动生成针对特定约束条件的求解器，可以大大提高问题求解的效率和质量，降低人工成本。未来，ARS可以进一步扩展到其他组合优化问题，例如旅行商问题、车辆调度问题等。

📄 摘要（原文）

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.