【文獻筆記】ARS: Automatic Routing Solver with Large Language Models

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. 貢獻

提出ARS框架：是一種基于問題描述自動創建約束感知的啟發式算法框架，增強了用于路徑優化的主干啟發式算法，提供了一個適應性框架，以解決用自然語言表達的多種路由問題。
構建RoutBench數據集：包含1000個VRP變體，涵蓋24種約束類型，用于標準化的VRP求解器評估。
實驗驗證：ARS在RoutBench和其他基準數據集（如CVRPLib）上表現出色，優于其他基于LLM的方法和傳統求解器。

2. 研究方法 ARS

在這里插入圖片描述

2.1. ARS框架概述

ARS框架的目標是根據用戶提供的自然語言問題描述和實例數據，自動生成針對VRP變體的約束檢查和評分程序，并結合啟發式搜索求解問題。框架結構如圖1所示，包含以下組件：

輸入：用戶提供自然語言格式的問題描述（如“每條路徑的總負載不得超過車輛容量，節點[7,8]不得在同一路徑上”）和實例數據（如節點需求、距離矩陣、時間窗等）。
輸出：一個啟發式求解器，包含約束檢查程序（驗證解的合法性）和約束評分程序（量化約束違反程度），用于優化VRP解。
核心組件：
- 數據庫：存儲六種代表性約束類型（車輛容量、距離限制、時間窗、取送貨、相同車輛、優先級）及其代碼模板。
- 生成模塊：根據輸入利用LLM選擇相關約束并生成代碼。
- VRP求解器：基于生成的約束檢查和評分程序，采用啟發式搜索框架（包括破壞與修復和局部搜索）求解VRP。

工作流程分為三個主要步驟：約束選擇、約束檢查程序生成、約束評分程序生成，以及一個骨干啟發式求解。

2.1.1. 約束選擇（Constraint Selection）

目標：從用戶輸入的自然語言描述中識別與VRP變體相關的約束類型。
實現：
- 用戶輸入的自然語言問題描述 $I$ （如：“每條路徑的總負載不得超過車輛容量，節點[7,8]不得在同一路徑上”）被送入LLM。
- LLM根據數據庫 $D$ 中存儲的約束類型進行匹配，輸出與輸入最相關的約束類型 $S$ 。（這一過程類似于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解是否滿足用戶描述 $I$ 指定的約束。
實現：
- 輸入包括用戶的問題描述 $I$ 、選定的約束類型 $S$ 及其代碼模板（上一步從數據庫中獲取的）。
- 讓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解違反約束的程度，便于啟發式算法在搜索中做“軟約束懲罰”，逐步朝向可行解收斂。
實現：
- 輸入包括用戶的問題描述 $I$ 、約束檢查程序（從上一步生成）和約束描述。
- 用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變體。