# 超越目标等价性：基于LLM的车辆路径问题优化建模中的约束注入

# 超越目标等价：基于约束注入的LLM优化建模在车辆路径问题上的应用
来源：https://arxiv.org/html/2606.04816

Xizi Luo1,2†, Changhong He1,2†, Dongdong Geng2, Chenggong Shi2, Yu Mei2∗
1北京航空航天大学，北京，中国
2百度公司，北京，中国
[email protected], [email protected]
[email protected], [email protected], [email protected]

###### 摘要

大语言模型（LLMs）正日益被用于将自然语言描述的优化问题转化为可执行的求解器代码。然而，对于约束密集型运筹学（OR）问题，现有的数据过滤与训练流程主要依赖目标等价信号，如差分测试和答案一致性。当被测试实例上的相关约束不具约束力时，即便程序添加了虚假约束或悄然遗漏了必要约束，也能通过这些信号。我们提出**约束注入**方法，利用可行探针检测虚假过约束，利用单约束违反探针揭示约束遗漏。将其与差分测试结合，构成**双重验证器**。我们在车辆路径问题（VRPs）上对其进行实例化和评估——VRP 是一类具有代表性的约束密集型组合优化测试平台，其容量、时间窗、配送站和服务规则在自然语言场景中相互耦合。该验证器被复用为 SFT 数据合成中的拒绝采样过滤器，以及群体相对策略优化（GRPO）中的逐 rollout 奖励。我们开发了 VRPCoder，这是一个将自然语言 VRP 场景转化为 Gurobi 脚本的端到端 8B 模型，并附有覆盖 21 个变体的专家验证 VRP 基准测试集。在四个 VRP 基准测试上，VRPCoder-GRPO 达到了 93% 的平均 Pass@1，在三个基准上超越 Gemini-3.1-Pro Preview，比 Claude-Sonnet-4.5 高出平均 28 个百分点，比现有 OR-LLMs 高出平均 78 个百分点。

超越目标等价：基于约束注入的LLM优化建模在车辆路径问题上的应用
Xizi Luo1,2†, Changhong He1,2†, Dongdong Geng2, Chenggong Shi2, Yu Mei2∗
1北京航空航天大学，北京，中国 2百度公司，北京，中国
[email protected], [email protected]
[email protected], [email protected], [email protected]

11脚注：通讯作者。22脚注：该工作完成于作者在百度实习期间。

## 1 引言

优化问题通常以自然语言表达，而求解器需要形式化的建模代码（Ramamonjison 等，2022 (https://arxiv.org/html/2606.04816#bib.bib28)）。大语言模型（LLMs）提供了一种将此类问题转化为可执行求解器代码的有前景的方法。然而，可执行性与目标等价这两种主流接受信号，并不能保证所有预期约束都被忠实编码，从而损害了基于 LLM 的优化建模的可信度。

参见图注图 1：遗漏子回路消除约束的候选方案仍能与参考最优值匹配，因此差分测试接受了它。约束注入输入一个违反该约束的不连通子回路探针：正确程序将其判定为不可行，而存在缺陷的候选方案接受了它，从而暴露出约束遗漏。

现有基于 LLM 的优化建模方法主要分为三类。**推理时增强方法**通过提示、检索、自调试或智能体工作流改进冻结的 LLMs（Jiang 等，2025c (https://arxiv.org/html/2606.04816#bib.bib18); Li 等，2025 (https://arxiv.org/html/2606.04816#bib.bib23); Zhang 等，2026 (https://arxiv.org/html/2606.04816#bib.bib39)）。**监督微调（SFT）**在合成的问题–代码对上训练运筹学 LLMs（OR-LLMs），通常通过可执行性、差分测试或自一致性进行过滤（Huang 等，2025a (https://arxiv.org/html/2606.04816#bib.bib12); Lu 等，2025 (https://arxiv.org/html/2606.04816#bib.bib24); Zhang 等，2025 (https://arxiv.org/html/2606.04816#bib.bib40)）。**强化学习（RL）方法**使用求解器反馈，如目标匹配或答案一致性（Chen 等，2025 (https://arxiv.org/html/2606.04816#bib.bib6); Zhou 等，2026 (https://arxiv.org/html/2606.04816#bib.bib41); Ding 等，2026 (https://arxiv.org/html/2606.04816#bib.bib9)）。

尽管方法各异，SFT 数据过滤器和 RL 奖励在本质上都归结为目标等价，通常通过比较最优目标值来实现。然而，目标等价在结构上对约束集是盲目的：当受影响的约束在被测实例上不具约束力时，候选方案可能引入虚假约束或遗漏必要约束，同时仍与参考最优值匹配。我们将这两种失败模式称为**虚假过约束**和**约束隐式遗漏**。两者都能通过可执行性和差分测试过滤器，进入 SFT 数据，并获得正向 RL 奖励。图 1 (https://arxiv.org/html/2606.04816#S1.F1) 展示了一个路径实例上的这种失败情形，其中最优值不受缺失子回路消除约束的影响。

我们通过**约束注入**来弥补这一不足——这是一种验证算子，要求候选程序接受可行探针，并拒绝单约束违反探针。结合差分测试，构成双重验证器，其信号与任意单一实例上的最优值解耦。我们在车辆路径问题（VRPs）上实例化该双重验证器，VRP 是一类约束密集型测试平台，其容量、时间窗、配送站和服务规则在自然语言场景中相互耦合（Toth 和 Vigo，2014 (https://arxiv.org/html/2606.04816#bib.bib35); Laporte，2009 (https://arxiv.org/html/2606.04816#bib.bib21); Lahyani 等，2015 (https://arxiv.org/html/2606.04816#bib.bib20)）。该验证器先被复用为 SFT 数据合成的拒绝采样过滤器，再用作 GRPO 中的逐 rollout 奖励。所得模型 VRPCoder 是一个端到端 8B 模型，将自然语言 VRP 场景转化为 Gurobi 脚本，并配备涵盖 21 个变体的专家验证 VRP 基准测试集。

我们的贡献如下：
**(1)** 我们将目标等价识别为 SFT 过滤和 RL 奖励共同的盲点，并指出两种失败模式：虚假过约束和约束隐式遗漏。
**(2)** 我们提出约束注入，这是一种约束级验证器，利用可行探针检测虚假过约束，利用单约束违反探针检测约束遗漏，并将其与差分测试结合为双重验证器，复用于数据合成和 GRPO。
**(3)** 我们推出 VRPCoder 及涵盖 21 个变体的专家验证 VRP 基准测试集。在四个 VRP 基准上，VRPCoder-GRPO 达到 93% 的平均 Pass@1，在三个基准上超越 Gemini-3.1-Pro Preview，比 Claude-Sonnet-4.5 高出平均 28 个百分点，比现有 OR-LLMs 高出平均 78 个百分点。

## 2 相关工作

### 2.1 OR-LLMs 的监督微调

数据合成已被广泛应用于训练 OR-LLMs（Xiao 等，2025 (https://arxiv.org/html/2606.04816#bib.bib37)）。ORLM（Huang 等，2025a (https://arxiv.org/html/2606.04816#bib.bib12)）使用 GPT-4 扩展行业案例种子；OptMATH（Lu 等，2025 (https://arxiv.org/html/2606.04816#bib.bib24)）生成复杂度可控的问题，并通过双向重建建模进行过滤；LLMOPT（Jiang 等，2025a (https://arxiv.org/html/2606.04816#bib.bib15)）定义了一种五要素统一表示用于多指令调优；ReSocratic（Yang 等，2025 (https://arxiv.org/html/2606.04816#bib.bib38)）从结构化演示中推导问题–代码对。在这些流程中，接受信号主要依赖可执行性或目标等价。这些信号虽有助于过滤无效或明显错误的程序，但无法验证生成代码是否忠实实现了预期约束，因此可能遗漏不影响最优值的约束缺失情形。

### 2.2 OR-LLMs 的强化学习

在 SFT 之外，基于求解器可验证奖励的 RL 已成为 OR-LLMs 的自然发展方向，因为生成的程序可以被执行、求解，并通过可行性、目标值或答案一致性进行评估（Le 等，2022 (https://arxiv.org/html/2606.04816#bib.bib22)）。SIRL（Chen 等，2025 (https://arxiv.org/html/2606.04816#bib.bib6)）使用求解器执行作为结果反馈；FOARL（Jiang 等，2025b (https://arxiv.org/html/2606.04816#bib.bib17)）为组合优化引入了可行性与最优性感知的 RL；StepORLM（Zhou 等，2026 (https://arxiv.org/html/2606.04816#bib.bib41)）使用生成式过程奖励模型进行逐步监督；OR-R1（Ding 等，2026 (https://arxiv.org/html/2606.04816#bib.bib9)）以多数投票伪标签作为奖励执行测试时 GRPO。尽管这些奖励在 SFT 基础上改进了 OR 推理，但它们主要在解或答案层面运作，并不直接验证每个必要约束是否在生成代码中得到实现。对于约束密集型 VRP 求解器代码生成，超越求解器结果或答案一致性、在约束层面进行奖励仍是一个待探索的方向。

### 2.3 面向车辆路径问题的 LLMs

VRP 是基于 LLM 的优化建模在耦合约束下的代表性测试平台。NLCO（Jiang 等，2026 (https://arxiv.org/html/2606.04816#bib.bib16)）对自然语言组合优化（含路径任务）上的 LLM 推理进行基准测试；Huang 等（2024 (https://arxiv.org/html/2606.04816#bib.bib14)）表明通用 LLMs 具备初步的 VRP 代码生成能力，但在复杂约束下仍存在局限。另一方向通过推理时机制改进 VRP 求解：DRoC（Jiang 等，2025c (https://arxiv.org/html/2606.04816#bib.bib18)）将约束分解与检索和自调试相结合；ARS（Li 等，2025 (https://arxiv.org/html/2606.04816#bib.bib23)）和 AFL（Zhang 等，2026 (https://arxiv.org/html/2606.04816#bib.bib39)）在冻结 LLMs 上采用智能体工作流。这些研究均未涉及生成的求解器代码是否忠实编码了预期约束，而这正是本文的关注点。

## 3 预备知识

### 3.1 车辆路径问题

本文以有容量约束的车辆路径问题（CVRP）（Braekers 等，2016 (https://arxiv.org/html/2606.04816#bib.bib5)）作为 VRP 变体族的基础。设配送站索引为 $0$，车辆集合为 $M=\{1,\ldots,m\}$，节点集合为 $N=\{0,1,\ldots,n\}$（包含配送站和 $n$ 个客户）。可行弧集定义为 $A=\{(i,j)\mid i\in N,\ j\in N,\ i\neq j\}$。客户 $i$ 的需求记为 $d_i$，每辆车的容量为 $Q$，节点 $i$ 到 $j$ 的行驶费用为 $c_{ij}$。引入二元决策变量 $x_{ij}^k\in\{0,1\}$ 表示车辆 $k$ 是否直接从节点 $i$ 行驶至节点 $j$，辅助变量 $v_i\in[1,n]$ 表示客户 $i$ 在某条车辆路径中的访问顺序。CVRP 可形式化如下：

$$\min\quad\sum_{k\in M}\sum_{(i,j)\in A}c_{ij}x_{ij}^k,\tag{1}$$

$$\sum_{k\in M}\sum_{j:(i,j)\in A}x_{ij}^k=1,\quad\forall i\in N,\ i\neq 0,\tag{2}$$

$$\sum_{j:(0,j)\in A}x_{0j}^k\leq 1,\quad\forall k\in M,\tag{3}$$

$$\sum_{j:(i,j)\in A}x_{ij}^k=\sum_{j:(j,i)\in A}x_{ji}^k,\tag{4}$$

$$\quad\forall i\in N,\ k\in M,$$

$$\sum_{i\in N\setminus\{0\}}d_i\sum_{j:(i,j)\in A}x_{ij}^k\leq Q,\quad\forall k\in M,\tag{5}$$

$$v_i - v_j + n\sum_{k\in M}x_{ij}^k\leq n-1,\tag{6}$$

$$\quad\forall i,j\in N\setminus\{0\},\ i\neq j.$$

公式 (1 (https://arxiv.org/html/2606.04816#S3.E1)) 最小化总行驶费用。公式 (2 (https://arxiv.org/html/2606.04816#S3.E2)) 结合公式 (4 (https://arxiv.org/html/2606.04816#S3.E4)) 的流量守恒，确保每个客户恰好被服务一次。公式 (3 (https://arxiv.org/html/2606.04816#S3.E3)) 允许每辆车最多从配送站出发一次。公式 (5 (https://arxiv.org/html/2606.04816#S3.E5)) 强制执行车辆容量约束，公式 (6 (https://arxiv.org/html/2606.04816#S3.E6)) 通过 Miller-Tucker-Zemlin（MTZ）排序约束消除不连通子回路。

**本文考虑的 VRP 变体。** 我们通过在 CVRP 基础上添加约束模块和结构特征，涵盖 21 个 VRP 变体，包括时间窗、取送货、回程、多配送站路径、异构车队和开放路径。其中 18 个变体用于训练，其余 3 个作为留出集，用于评估组合泛化能力。完整映射见附录 A (https://arxiv.org/html/2606.04816#A1)。

### 3.2 任务形式化

给定自然语言 VRP 场景 $q$，模型 $f_\theta$ 生成端到端 Gurobi 脚本 $y=f_\theta(q)$，无需中间脚手架（如 `.lp` 文件、公式模板或符号表）。理想的脚本不仅应将实例求解至正确目标值，还应忠实编码 $q$ 中的显式约束以及对应 VRP 变体所需的隐式约束。

### 3.3 验证算子

我们使用两种算子验证生成的代码。

**差分测试。** 设 $\mathrm{solve}(C,I)$ 为在实例 $I$ 上执行脚本 $C$ 返回的最优目标值。对于两个脚本 $C_1$ 和 $C_2$，定义其差异为 $\mathrm{DIFF}(C_1,C_2,I)\triangleq|\mathrm{solve}(C_1,I)-\mathrm{solve}(C_2,I)|$。执行失败或不可行视为失败；否则，当两脚本返回的目标值差不超过 $\varepsilon_{\mathrm{obj}}$ 时，认为二者在 $I$ 上一致。

**约束注入。** 给定三元组 $(C,I,s)$，其中 $s$ 为一个路径方案，$\mathrm{INJ}$ 在实例 $I$ 上执行脚本 $C$ 以获取模型对象，将目标函数替换为常数（从而将问题转化为纯可行性查询），追加 Gurobi `addConstr` 调用将路径方案 $s$ 编码至候选脚本 $C$ 的变量空间，并返回求解器的可行性判定 $\mathrm{INJ}(C,I,s)\in\{\mathrm{Feasible},\mathrm{Infeasible}\}$。给定真实标签 $\ell(s)\in\{\mathrm{Feasible},\mathrm{Infeasible}\}$，正确性信号为 $\mathbf{1}[\mathrm{INJ}(C,I,s)=\ell(s)]$。具体编码方式取决于车队结构和探针角色；三种方案详见第 4.1 节 (https://arxiv.org/html/2606.04816#S4.SS1)。当实例由上下文固定时，将 $\mathrm{DIFF}(C_1,C_2,I)$ 简记为 $\mathrm{DIFF}(C_1,C_2)$，将 $\mathrm{INJ}(C,I,s)$ 简记为 $\mathrm{INJ}(C,s)$。

### 3.4 约束级探针

为针对目标等价的两种失败模式——虚假过约束和约束隐式遗漏——我们附加