当前位置： 首页 > news >正文

【文献笔记】ARS: Automatic Routing Solver with Large Language Models

news 2025/7/23 7:56:55

ARS: Automatic Routing Solver with Large Language Models
https://github.com/Ahalikai/ARS-Routbench/

ARS：基于大语言模型的自动路由求解器

1. 概述

1.1. 研究背景

车辆路径问题（VRP）是一类经典的组合优化问题，广泛应用于物流、运输和医疗等领域。VRP的复杂性源于其多样化的约束条件（如车辆容量、时间窗、优先级等）以及问题规模的增长。传统方法通常依赖专家设计特定算法或使用通用求解器（如CPLEX、Gurobi），但这些方法需要深入的问题建模和手动算法设计，难以适应多样化的VRP变体。

大型语言模型（LLMs）因其强大的推理和代码生成能力，为自动化算法设计提供了新的可能性。然而，现有研究主要集中于标准VRP的少量变体，难以应对复杂VRP场景。

ARS框架旨在利用LLMs的自然语言处理和代码生成能力，自动生成针对不同VRP变体的约束感知启发式算法，从而提高求解的通用性和效率。

1.2. 贡献

  1. 提出ARS框架：是一种基于问题描述自动创建约束感知的启发式算法框架，增强了用于路径优化的主干启发式算法，提供了一个适应性框架，以解决用自然语言表达的多种路由问题。
  2. 构建RoutBench数据集：包含1000个VRP变体，涵盖24种约束类型，用于标准化的VRP求解器评估。
  3. 实验验证：ARS在RoutBench和其他基准数据集（如CVRPLib）上表现出色，优于其他基于LLM的方法和传统求解器。

2. 研究方法 ARS

在这里插入图片描述

2.1. ARS框架概述

ARS框架的目标是根据用户提供的自然语言问题描述和实例数据，自动生成针对VRP变体的约束检查和评分程序，并结合启发式搜索求解问题。框架结构如图1所示，包含以下组件：

  • 输入：用户提供自然语言格式的问题描述（如“每条路径的总负载不得超过车辆容量，节点[7,8]不得在同一路径上”）和实例数据（如节点需求、距离矩阵、时间窗等）。
  • 输出：一个启发式求解器，包含约束检查程序（验证解的合法性）和约束评分程序（量化约束违反程度），用于优化VRP解。
  • 核心组件：
    • 数据库：存储六种代表性约束类型（车辆容量、距离限制、时间窗、取送货、相同车辆、优先级）及其代码模板。
    • 生成模块：根据输入利用LLM选择相关约束并生成代码。
    • VRP求解器：基于生成的约束检查和评分程序，采用启发式搜索框架（包括破坏与修复和局部搜索）求解VRP。

工作流程分为三个主要步骤：约束选择、约束检查程序生成、约束评分程序生成，以及一个骨干启发式求解。

2.1.1. 约束选择（Constraint Selection）
  • 目标：从用户输入的自然语言描述中识别与VRP变体相关的约束类型。
  • 实现：
    • 用户输入的自然语言问题描述 III（如：“每条路径的总负载不得超过车辆容量，节点[7,8]不得在同一路径上”）被送入LLM。
    • LLM根据数据库 DDD 中存储的约束类型进行匹配，输出与输入最相关的约束类型 SSS。（这一过程类似于RAG，虽然作者没有明说）
    • 如果没有匹配的约束，LLM返回“No Relevant Constraint”。
  • 提示工程：分析用户输入，输出匹配的约束类型（明确要求LLM仅基于用户输入和数据库中的约束示例进行选择，不添加额外解释）。
    • 提示词
      For the description in the VRP problem, 
identify and provide the relevant constraint types from the following list: 
{constraint_description}  
According to the user input: 
{user_input} 
If no constraint types match the user input, respond with: "No Relevant Constraint".  
Do not give additional explanations.
    • 结果示例：
      According to the user input:
The total load of each route must not exceed the vehicle capacity. 
Nodes [7, 8] must not be on the same route.
First Call Output:
1. Constraint type: Vehicle Capacity Constraint
2. Constraint type: Same Vehicle Constraint
2.1.2. 约束检查程序(Checker)生成（Constraint Checking Program Generation）
  • 目标：生成一个Python函数，用于检查VRP解是否满足用户描述III指定的约束。
  • 实现：
    • 输入包括用户的问题描述 III、选定的约束类型SSS及其代码模板（上一步从数据库中获取的）。
    • 让LLM修改原有模板生成新约束 C_new，构成自定义检查函数。
  • 提示工程：要求LLM严格遵循提供的函数模板和约束描述，生成简洁的代码。
    • 提示词：
      As a Python algorithm expert, please implement a function to check the constraints 
for the vehicle routing problem (VRP) 
based on the provided description and relevant code.  
User input: {user_input}  
Relevant Examples: {related_constraints_and_codes}  
Do not give additional explanations.
    • 代码示例：
      def check_constraints(solution: VrpState) -> bool:# Check vehicle capacity constraintfor route in solution.routes:total_demand = sum(solution.problem_data["demand"][node] for node in route)if total_demand > solution.problem_data["capacity"]:return False# Check nodes [7, 8] not on same route constraintfor route in solution.routes:if 7 in route and 8 in route:return Falsereturn True
2.1.3. 约束评分程序(Scorer)生成（Constraint Scoring Program Generation）
  • 目标：生成一个Python函数，用于量化VRP解违反约束的程度，便于启发式算法在搜索中做“软约束惩罚”，逐步朝向可行解收敛。
  • 实现：
    • 输入包括用户的问题描述III、约束检查程序（从上一步生成）和约束描述。
    • 用LLM生成一个约束评分函数(违约评分函数，分数越小越好)
    • 评分程序通过基于约束检查结果分配定量分数，来评估约束条件被满足的程度。（支持软约束建模，使启发式搜索在早期探索阶段可以容忍部分违约解，并通过惩罚机制逐步逼近可行解）
  • 提示工程：要求LLM基于约束检查代码生成评分逻辑，确保评分函数与检查函数一致。
    • 提示词：
      As a Python algorithm expert, 
please implement a function to calculate the constraint violation score 
for the Vehicle Routing Problem (VRP) based on the given constraints.  
Function Template: {function_template}  
Constraints Description: {constraints_description}  
Check Constraints Code: {related_constraints_and_codes}  
Do not give additional explanations.
    • 代码示例：
      def calculate_violation_score(solution: VrpState) -> float:violation_score = 0.0  # Check vehicle capacity constraint for route in solution.routes: total_demand = sum(solution.problem_data["demand"][node] for node in route) if total_demand > solution.problem_data["capacity "]: violation_score += (total_demand - solution.problem_data[" capacity"])# Check nodes [7, 8] not on same route constraint for route in solution.routes: if 7 in route and 8 in route:violation_score += 1.0  return violation_score...
2.1.4. 约束感知启发式（CAH）生成（Constraint-Aware Heuristic Generation）

由前面的约束检查（Checker）和评分程序（Scorer）生成最终判断逻辑：约束感知启发式（CAH）

在这里插入图片描述

这个启发式逻辑允许从不可行区域逐步爬升到可行区域，并不断提升目标值（如路径总长度），该启发式评价逻辑也使得搜索过程具有‘目标函数-约束可行性’双重导向。

2.2. 启发式求解器（Augmented Heuristic Solver）

  • 目标：利用生成的约束检查和评分程序，结合启发式搜索框架求解VRP。
  • 实现：
    • 搜索框架：采用基于单点搜索的骨干启发式框架，包含两个主要阶段：
      1. 破坏与修复（Destroy & Repair）：
        • 使用多种破坏算子（如随机移除、字符串移除）从当前解中移除部分客户或路径。
        • 破坏算子的选择通过轮盘赌机制（Roulette Wheel Selection）实现，优先选择历史表现较好的算子。
        • 修复阶段使用贪心策略将删除的客户重新插入解决方案，目标是路径更短且逐渐满足约束。
      2. 局部搜索（Local Search）：
        • 在破坏与修复后，进一步使用局部搜索（如2-opt）对解进行优化，调整节点顺序以减少路径成本。
        • 2-opt算子通过移除两条非邻近边并重新连接，改变节点顺序以寻找更优解。
    • 约束感知：生成的约束检查和评分程序嵌入到搜索框架中，确保解满足约束或最小化违反程度。

3. RoutBench数据集构建

在这里插入图片描述

  • RoutBench 的构建基于 6 类现实中常见且结构性强的约束类型（车辆容量C、距离限制L、时间窗TW、取送货PD、相同车辆S、优先级P），每类选取 4 个子变体，总共构成 24 个具体约束种类。
  • 从中均匀采样 1000 组变体，组成 RoutBench 数据集。
数据子集名条件数量用途
RoutBench-S≤ 3 个约束500中等复杂度任务
RoutBench-H≥ 4 个约束500高复杂度测试集
  • 所有实例由 Solomon C103 数据集生成基础坐标，并加入不同约束
  • 每个实例包含三部分内容：
    • 自然语言问题描述（problem description）：如“每条路径的长度不能超过100，节点 [5,8] 需由同一车辆服务”等；
    • 实例数据（instance data）：包括节点位置、需求、时间窗、车队设置等；
    • 验证代码（validation code）：Python 函数格式，用于判定 LLM生成的代码是否满足所有约束。

4. 实验

4.1. 实验设置

模块内容说明
数据集RoutBench（1000个复杂VRP实例），Common Problems（48个经典变体）
评测指标- SR (Success Rate)：程序是否能正确完成建模与求解并通过验证
- RER (Runtime Error Rate)：程序运行时报错的比例
对比方法与 7种LLM-based baseline 方法 对比，包括：
① Standard Prompting
② CoT（Chain-of-Thought）
③ Reflexion
④ PHP（Progressive Hint Prompting）
⑤ CoE（Chain-of-Experts）
⑥ Self-debug
⑦ Self-verification
主模型GPT-4o 为主要生成模型，其他实验也涉及 DeepSeek-V3、LLaMA-3.1-70B 等
环境Intel Xeon Gold 6248R处理器（3.0 GHz，128 GB内存，Windows 10）

4.2. 结果分析

4.2.1. 主要结果

在这里插入图片描述

  • 在常规VRP任务上（Common Problems），ARS 的成功率高达 91.67%，远超其他方法的 40%左右；
  • 在复杂多约束场景（RoutBench-H）上，ARS 仍能保持近 50% 成功率，其他方法普遍不到 15%；
  • 运行错误率RER也极低，表明 ARS 程序质量稳定。
4.2.2. 与求解器比较

在这里插入图片描述
在这里插入图片描述

  • ARS 生成程序不仅可行，还能产生性能优异的解；
  • 在运行效率上，时间显著优于CPLEX和Gurobi；
  • 在复杂问题上甚至优于 OR-Tools
  • ARS在常见问题上取得了最高的成功率（SR），并且与其他求解器相比，需要的代码行数（LOC）最少。因为ARS框架中，LLM只需要使用简单的Python语法编写约束代码，而其他求解器则受到其特定实现的限制，需要高度标准化的建模
4.2.3. 不同LLM模型的比较

在这里插入图片描述

  • 解决VRP变体的成功率在不同的LLM之间有所不同
  • DeepSeek-V3是这些LLM中处理VRP变体最有效的LLM
4.2.4. 消融实验

在这里插入图片描述

  • 移除约束选择步骤会导致ARS的SR下降。没有这个步骤，ARS会获取所有六个代表约束，这些约束可能与当前的VRP无关，并可能误导LLM
  • 移除数据库对ARS生成正确程序的性能影响更大。如果没有数据库来参考相关约束，LLM必须独立生成所有约束，对LLM提出了更高的要求

5. 总结

  • 提出了一种利用 LLM 自动设计约束感知启发式算法的框架ARS，以增强启发式路由优化框架，用于具有复杂和实际约束的VRP变体。此外，我们
  • 构造了RoutBench，这是一个由24个VRP约束衍生的1,000个VRP变体组成的综合基准。每个变体包括问题描述、实例数据和验证代码
  • ARS的实验评估特别有前途，证明了其相对于现有基于LLM的方法和常用求解器的优越性能。

5.1. 局限性与未来工作

  • 局限性：
    • ARS依赖通用启发式框架，可能在某些特定VRP变体上不如专用算法高效。
    • LLM生成的代码可能因模型能力或提示设计而存在误差。
  • 未来工作：
    • 优化提示设计以提高代码生成质量。
    • 集成更先进的搜索算法（如分支定价）以提升求解效率。
    • 扩展RoutBench以覆盖更多VRP变体。
http://www.lryc.cn/news/596070.html

相关文章：

  • PHP获取淘宝拍立淘（以图搜图）API接口操作详解
  • 如何迁移jenkins至另一台服务器
  • 一个基于现代C++智能指针的优雅内存管理解决方案
  • 探索飞算JavaAI：AI赋能Java开发的新范式
  • docker 设置镜像仓库代理
  • 碰一碰发视频源码搭建：支持OEM
  • 初识opencv01——基本api操作
  • 分布式高可用ELK平台搭建及使用保姆级教程指南
  • 大数据之Hive:Hive中week相关的几个函数
  • 分布式数据库中间件ShardingSphere
  • Protobuf学习
  • SysMind：Go 语言驱动的AI系统运维助手
  • 用Python实现神经网络(六)
  • 【计算机网络 篇】TCP基本认识和TCP三次握手相关问题
  • WebSocket心跳机制实现要点
  • 深入浅出理解 TCP 与 UDP：网络传输协议的核心差异与应用
  • 基于SpringBoot+Vue的高校特长互助系统（WebSocket实时聊天、协同过滤算法、ECharts图形化分析）
  • JavaScript，发生异常，try...catch...finally处理，继续向上层调用者传递异常信息
  • zabbix“专家坐诊”第295期问答
  • 服务器无法访问公网的原因及解决方案
  • 在 WebSocket 中使用 @Autowired 时遇到空指针异常
  • XML高效处理类 - 专为Office文档XML处理优化
  • 智能制造——解读52页汽车设计制造一体化整车产品生命周期PLM解决方案【附全文阅读】
  • 智慧制造合同解决方案
  • React 项目性能优化概要
  • 客户案例 | Jabil 整合 IT 与运营，大规模转型制造流程
  • 厚铜板载流革命与精密压合工艺——高可靠性PCB批量制造的新锚点
  • 中小制造企业如何对技术图纸进行管理？
  • OneCode 3.0 @FormAnnotation 注解速查手册
  • 漫画版：细说金仓数据库