路线编译上下文模型

1. 概述

路线编译上下文将可行路线编译为受限主问题（RMP），拥有路线使用变量、人工覆盖变量、客户覆盖行、车队数量行和分阶段目标。

1. 依赖上下文

VRP 上下文提供客户、车型和成本语义；路线生成上下文提供可行路线列。应用层控制分支节点、列生成迭代及阶段切换。

2. 概念 / 实体

1. 客户与车型

$m_{v}$ ：车型 $v$ 可用车辆数；每条路线使用一辆相应车型的车。

2. 路线列

$a_{i r} \in {0, 1}$ ：路线 $r$ 是否覆盖客户 $i$ 。

$c_{r}$ ：路线成本，在进入主问题前转换为一致的成本单位。

3. 分支节点与阶段

分支节点 $b$ 限定允许的路线，迭代 $t$ 限定已生成的列。第一阶段消除人工覆盖，第二阶段优化路线成本。

3. 变量

1. 决策变量

$x_{r}$ ：路线使用量，无量纲。节点线性松弛使用 $x_{r} \in R_{\geq 0}$ ， $\forall r \in R_{b, t}$ ；最终整数方案要求 $x_{r} \in Z_{\geq 0}$ 。不能将每次 RMP 求解都写成整数规划。

2. 辅助变量

$u_{i}$ ：人工覆盖量，无量纲， $u_{i} \in R_{\geq 0}$ ， $\forall i \in C$ 。它用于第一阶段建立可求解的覆盖行，不是最终方案允许丢弃客户的业务变量；第二阶段固定 $u_{i} = 0$ 。

3. Kotlin/Rust 注册形式

Kotlin 用 UIntVariable1 注册路线变量，列生成求解器通过 linearRelax() 显式转成连续松弛；人工覆盖使用 URealVariable1。Rust 的路线与人工覆盖变量直接以 $[0, 1]$ 连续域注册。因此上面的非负数学域不表示两种语言拥有相同的注册类型或默认数值上界。

覆盖等式与非负性会推出 $u_{i} \leq 1$ ；对至少覆盖一个客户的路线，同样推出 $x_{r} \leq 1$ 。这些是模型约束的推论，不应与 Kotlin 变量声明时的默认上界混淆。最终整数路线由分支定价检验。

4. 谓词

$covers (r, i)$ ：路线 $r$ 覆盖客户 $i$ 。

$type (r, v)$ ：路线 $r$ 使用车型 $v$ 。

$compatible (r, b)$ ：路线满足分支节点 $b$ 的要求与禁止规则。

$active (r, t)$ ：路线在第 $t$ 次主问题求解前已加入列池。

5. 集合

$C$ ：客户集合； $V$ ：车型集合。

$R_{b, t}$ ：节点 $b$ 在迭代 $t$ 已插入且分支兼容的可行路线列。

$R_{b, t}^{v}$ ： $R_{b, t}$ 中使用车型 $v$ 的路线。

以下公式均针对固定的 $b, t$ ；加入新列后需要更新这些求和范围。

6. 中间值

1. 客户覆盖量

描述：客户覆盖是路线使用量按覆盖系数加权的和。

Y_{i} = \sum_{r \in R_{b, t}} a_{i r} x_{r}, \forall i \in C .

2. 车队使用量

描述：每条路线消耗一辆相应车型的车。

F_{v} = \sum_{r \in R_{b, t}^{v}} x_{r}, \forall v \in V .

3. 路线总成本

Z = \sum_{r \in R_{b, t}} c_{r} x_{r} .

$Y_{i}, F_{v}, Z$ 是线性表达式，不是独立决策变量。

7. 断言

每条列必须先通过路线可行性检查并满足当前分支规则：

\forall r \in R_{b, t} : feasible (r) \land compatible (r, b) .

每条可用路线指定一个车型且不重复访问客户：

\forall r \in R_{b, t} : \exists! v \in V : type (r, v), \forall i \in C : a_{i r} \in {0, 1} .

8. 约束

1. 客户覆盖（Customer Coverage）

描述：每个客户必须被路线或第一阶段人工量恰好覆盖一次。

s . t . Y_{i} + u_{i} = 1, \forall i \in C .

2. 车队数量（Fleet Limit）

描述：选中路线消耗的车辆数不能超过可用数量。

s . t . F_{v} \leq m_{v}, \forall v \in V .

3. 第二阶段人工量固定（Phase-II Artificial Fixing）

描述：进入成本优化阶段后，不再允许用人工量替代真实服务。

s . t . u_{i} = 0, \forall i \in C .

推论：此时覆盖行化为 $Y_{i} = 1$ 。路线的容量、时间窗和初等性已经由列的可行性保证，不应再次虚构为本上下文的弧级约束。

9. 目标函数（如适用）

1. 第一阶段

描述：最小化未由真实路线覆盖的人工量。

min Z^{I} = \sum_{i \in C} u_{i} .

2. 第二阶段

描述：固定全部人工量为零后，最小化真实路线成本。

min Z^{I I} = \sum_{r \in R_{b, t}} c_{r} x_{r} .

这是两个阶段，不是用未定义的大常数 $M$ 拼成 $M \sum_{i} u_{i} + Z$ 的单一目标。

10. 算法引用

算法	引用位置	说明
受限主问题求解	第 3、8、9 节	求解节点 LP 并提取客户和车队行对偶价格
列插入	第 5、6 节	更新变量池及覆盖、车队和目标系数
两阶段切换	第 8、9 节	在人工覆盖消除后固定人工量并切换目标
分支定价	应用层	处理分数解、节点界与整数可行方案

Kotlin 路线编译源码；Kotlin/Rust 示例入口。

11. 通用语言

术语	符号	定义
路线使用量	$x_{r}$	路线列在主问题中的取值
人工覆盖	$u_{i}$	第一阶段临时补足的客户覆盖
覆盖量	$Y_{i}$	真实路线对客户的覆盖
车队使用量	$F_{v}$	指定车型被使用的车辆数
受限主问题	$R_{b, t}$	只包含当前节点已有路线列的主问题

12. 设计决策

决策	备选方案	原因
明确 LP 与整数方案的变量域	在所有阶段声明整数变量	对偶定价需要节点 LP
分阶段处理人工覆盖与成本	使用未定义的大常数混合目标	明确可行性恢复和成本优化的不同职责
按分支节点过滤路线池	所有节点共享未经筛选的列	保证分支规则贯穿主问题与定价

13. 变更记录

版本	变更	原因
1.1	对齐双语变量域、覆盖行及两阶段目标	消除旧子页与整体模型之间的矛盾

路线编译上下文模型 ​

1. 概述 ​

1. 依赖上下文 ​

2. 概念 / 实体 ​

1. 客户与车型 ​

2. 路线列 ​

3. 分支节点与阶段 ​

3. 变量 ​

1. 决策变量 ​

2. 辅助变量 ​

3. Kotlin/Rust 注册形式 ​

4. 谓词 ​

5. 集合 ​

6. 中间值 ​

1. 客户覆盖量 ​

2. 车队使用量 ​

3. 路线总成本 ​

7. 断言 ​

8. 约束 ​

1. 客户覆盖（Customer Coverage） ​

2. 车队数量（Fleet Limit） ​

3. 第二阶段人工量固定（Phase-II Artificial Fixing） ​

9. 目标函数（如适用） ​

1. 第一阶段 ​

2. 第二阶段 ​

10. 算法引用 ​

11. 通用语言 ​

12. 设计决策 ​

13. 变更记录 ​