路线生成上下文模型

1. 概述

路线生成上下文搜索满足资源与分支规则的初等路线，并向路线编译上下文返回改进列。定价问题是带资源约束的初等最短路问题（ESPPRC）。

1. 依赖上下文

VRP 上下文提供客户、车型、资源和计算策略；路线编译提供当前阶段及客户、车队行的对偶价格；应用层提供分支规则。

2. 概念 / 实体

1. 标签

一个标签记录当前节点、已访问客户集合、累计载荷、服务时刻和累计定价成本。标签是搜索状态，不是求解器变量。

2. 路线与价格

$c_r$：路线 $r$ 的真实成本。

${\pi }_i$：客户 $i$ 的覆盖等式对偶价格。

${\mu }_v$：车型 $v$ 的车队上限行对偶价格。本文使用主问题最小化模型中对应行的有符号对偶值，不预先取绝对值。

${\epsilon }_{rc}$：判断负约化成本的非负数值容差。

3. 变量

1. 决策变量

本上下文不复制主问题的路线使用量 $x_r$。定价搜索的结果是候选路线 $r$。

2. 辅助变量

标签状态 $(n,S,L,t,\gamma )$ 分别表示当前节点、已访问客户、载荷、服务开始时刻和累计定价成本。它们是算法状态，不是声明给主问题的辅助变量。

4. 谓词

$\mathrm{extendable}(\ell ,j)$：标签 $\ell$ 可以扩展到节点 $j$。

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

$\mathrm{improving}(r)$：路线约化成本小于 $-{\epsilon }_{rc}$。

$\mathrm{complete}$：定价已经充分搜索，能够确认不存在改进列；仅达到返回列数上限不满足该条件。

5. 集合

$C$：客户集合；$V$：车型集合；$N$：客户与仓库节点。

$A_v$：车型 $v$ 的可行弧；${\mathcal{L}}_v$：该车型的搜索标签集合。

${\mathcal{R}}_b^v$：满足资源与节点 $b$ 分支规则的全部车型 $v$ 路线，区别于主问题中已经插入的有限列池。

${\mathcal{R}}_b^{-}$：定价发现的负约化成本路线集合。

6. 中间值

1. 资源递推

从标签 $\ell =(i,S,L,t,\gamma )$ 扩展到未访问客户 $j$ 时，需求、服务时长和行驶时间分别为 $q_j,s_i,{\tau }_{ij}^v$：

$$L^{\prime }=L+q_j,t^{\prime }=max\{e_j,t+s_i+{\tau }_{ij}^v\},S^{\prime }=S\cup \{j\}.$$

$t^{\prime }$ 是服务开始时刻，不是未经等待的到达时刻。

2. 约化成本

令路线的阶段目标系数为：

$$c_r^{phase}=\{\begin{array}{ll}0,& \text{第一阶段},\\ c_r,& \text{第二阶段}.\end{array}$$

对车型 $v$ 的路线，客户与车队两类对偶价格均需计入：

$${\overline{c}}_r=c_r^{phase}-\sum _{i\in C_r}{\pi }_i-{\mu }_v,r\in {\mathcal{R}}_b^v.$$

成本和对偶值必须采用相同的数值归一化约定；分支要求通过路线兼容性限定搜索空间。

7. 断言

成功扩展必须保持不重复访问和资源可行性：

$$\mathrm{extendable}(\ell ,j)\Rightarrow j\notin S\wedge (i,j)\in A_v\wedge L^{\prime }\le Q_v\wedge t^{\prime }\le l_j.$$

该蕴含式描述“允许的扩展必须满足什么”，并不要求任意标签都能扩展到所有客户。

8. 约束

1. 路线可行性（Route Feasibility）

描述：定价只在仓库到仓库、客户不重复、满足容量、时间窗及分支规则的路线中搜索。

$$r\in {\mathcal{R}}_b^v\Rightarrow \mathrm{elementary}(r)\wedge L_r\le Q_v\wedge \mathrm{timeFeasible}(r)\wedge \mathrm{compatible}(r,b).$$

这些是标签扩展、筛选与完整路线验证条件，不是向主问题注册另一套弧变量和约束。

2. 改进列筛选（Improving Column Filter）

$${\mathcal{R}}_b^{-}=\{r\text{ 已被找到}:{\overline{c}}_r<-{\epsilon }_{rc}\}.$$

9. 目标函数（如适用）

描述：对允许的车型搜索阶段约化成本最小的路线。

$$\underset{v\in V,r\in {\mathcal{R}}_b^v}{min}{\overline{c}}_r.$$

只有完整定价确认没有负约化成本路线，才能支持列生成收敛判断。时间、列数或搜索限制导致的提前返回，不等价于此最优性结论。

10. 算法引用

算法	引用位置	说明
初始路线生成	主问题初始化	提供种子路线；人工覆盖负责可行性初始化
ESPPRC 标签扩展与支配	第 6—8 节	维护资源、访问集合和约化成本，淘汰被支配状态
分支兼容性筛选	第 4、8 节	将要求与禁止规则作用于搜索图和候选路线
定价完成状态	第 9 节	区分完整搜索与因限制而提前返回

Kotlin 路线生成源码；Kotlin/Rust 示例入口。

11. 通用语言

术语	符号	定义
标签	$\ell$	一条部分路线的搜索状态
已访问集合	$S$	标签已经服务的客户
约化成本	${\overline{c}}_r$	阶段目标系数减去对应约束行的对偶贡献
车队对偶	${\mu }_v$	车型可用数量约束的对偶值
定价完成	$\mathrm{complete}$	可以可靠判断是否仍有改进列的搜索状态

12. 设计决策

决策	备选方案	原因
使用 ESPPRC 标签搜索	枚举所有路线	在资源和初等性限制下增量搜索
计入客户与车队对偶	只减去客户对偶	与受限主问题全部基础行保持一致
明确完成状态	把每次返回视为搜索结束	防止受限搜索被误报为收敛

13. 变更记录

版本	变更	原因
1.1	对齐双语资源递推、阶段价格与定价边界	补全车队对偶并区分算法状态和模型变量