车辆路径（VRP）上下文模型

1. 概述

VRP 上下文定义客户、仓库、车型、路线及其资源语义，供路线生成和路线编译共同使用。它负责数据与路线的有效性，不直接建立受限主问题。

1. 依赖上下文

输入适配层提供经过单位转换的实例；距离、行驶时间和成本由计算策略提供。

2. 概念 / 实体

1. 客户与仓库

$q_{i}$ ：客户 $i$ 的需求量，使用统一的载荷单位。

$[e_{i}, l_{i}]$ ：客户 $i$ 允许开始服务的时间窗； $s_{i}$ 为服务时长。

仓库提供路线起终点及其适用时间范围，不作为需要覆盖的客户。

2. 车型与路线

$Q_{v}$ ：车型 $v$ 的容量； $m_{v}$ 为可用车辆数； $f_{v}$ 为启用一辆车的固定成本。

路线 $r$ 是一个指定车型的仓库到仓库访问序列。 $a_{i r}$ 表示路线是否访问客户 $i$ 。

3. 变量

1. 决策变量

本上下文不声明求解器决策变量。路线使用量 $x_{r}$ 由路线编译上下文拥有。

2. 辅助变量

本上下文不声明辅助求解变量。路线载荷、服务时刻和成本是领域计算结果，不是额外的主问题变量。

4. 谓词

$customer (n)$ ：节点 $n$ 是客户。

$depot (n)$ ：节点 $n$ 是仓库。

$visits (r, i)$ ：路线 $r$ 访问客户 $i$ 。

$elementary (r)$ ：路线 $r$ 不重复访问客户。

5. 集合

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

$A_{v}$ ：车型 $v$ 允许使用的有向弧集合。

$R_{v}$ ：车型 $v$ 的可行路线集合； $R$ 为这些路线的并集。

$C_{r}$ ：路线 $r$ 访问的客户集合； $A_{r}$ ：路线按顺序经过的弧。

6. 中间值

1. 载荷与覆盖系数

一条路线的载荷是其访问客户需求的总和。覆盖系数是路线数据，而不是主问题中的二元变量。

L_{r} = \sum_{i \in C_{r}} q_{i}, a_{i r} = {\begin{cases} 1, & i \in C_{r}, \\ 0, & i \notin C_{r} . \end{cases}

2. 到达、等待与服务

给定车型 $v$ 的行驶时间 $τ_{i j}^{v}$ ，从节点 $i$ 到节点 $j$ 的到达时刻、服务开始时刻及离开时刻分别为：

t_{j}^{a r r} = t_{i}^{d e p} + τ_{i j}^{v}, t_{j}^{s t a r t} = max {t_{j}^{a r r}, e_{j}}, t_{j}^{d e p} = t_{j}^{s t a r t} + s_{j} .

提前到达允许等待，因此不能把服务开始时间窗误写成禁止提前到达。

3. 路线成本

固定成本与弧成本相加得到路线成本；距离不必直接等于行驶时间或成本。

c_{r} = f_{v} + \sum_{(i, j) \in A_{r}} c_{i j}^{v}, r \in R_{v} .

7. 断言

输入与策略应保持单位一致、需求非负以及时间窗有序：

\forall i \in C : q_{i} \geq 0 \land e_{i} \leq l_{i} \land s_{i} \geq 0.

令 $n_{k} (r)$ 表示路线 $r$ 的第 $k$ 个节点。初等路线中的每个客户最多出现一次：

\forall r \in R, \forall i \in C : # {k : n_{k} (r) = i} \leq 1.

8. 约束

1. 路线资源可行性（Route Resource Feasibility）

描述：路线必须满足容量与服务开始时间窗，并从允许的仓库出发、返回允许的仓库。

L_{r} \leq Q_{v}, e_{i} \leq t_{i}^{s t a r t} \leq l_{i}, \forall r \in R_{v}, \forall i \in C_{r} .

这些是路线构造与验证规则，不是本上下文向受限主问题额外注册的约束行。跨路线的客户覆盖和车队数量约束属于路线编译上下文。

9. 目标函数（如适用）

本上下文没有独立优化目标。它提供路线成本 $c_{r}$ ，由路线编译上下文在第二阶段使用；路线生成上下文则根据阶段目标和对偶价格计算约化成本。

10. 算法引用

算法	引用位置	说明
路线校验	输入与结果分析	检查仓库、访问次数、容量、服务时刻及单位
路线资源递推	第 6 节	按访问顺序累计载荷并计算等待与服务
计算策略	第 6 节	提供距离、行驶时间与成本

Kotlin VRP 上下文源码；Kotlin/Rust 示例入口。

11. 通用语言

术语	符号	定义
客户	$i \in C$	需要被服务的需求节点
车型	$v \in V$	容量、固定成本和车辆数量的组合
路线	$r \in R_{v}$	指定车型的可行访问序列
服务开始	$t_{i}^{s t a r t}$	到达并完成等待后开始服务的时刻
覆盖系数	$a_{i r}$	路线是否访问客户

12. 设计决策

决策	备选方案	原因
将路线作为领域对象	在所有上下文中重复定义弧变量	统一生成、编译与校验使用的语义
区分到达与服务开始	直接限制到达时刻不得早于时间窗	正确表达等待
分离资源校验与主问题约束	将路线资源再次展开为主问题行	保持路线列分解的边界

13. 变更记录

版本	变更	原因
1.1	统一双语结构、时间语义与变量归属	避免将领域属性误当作求解器变量

车辆路径（VRP）上下文模型 ​

1. 概述 ​

1. 依赖上下文 ​

2. 概念 / 实体 ​

1. 客户与仓库 ​

2. 车型与路线 ​

3. 变量 ​

1. 决策变量 ​

2. 辅助变量 ​

4. 谓词 ​

5. 集合 ​

6. 中间值 ​

1. 载荷与覆盖系数 ​

2. 到达、等待与服务 ​

3. 路线成本 ​

7. 断言 ​

8. 约束 ​

1. 路线资源可行性（Route Resource Feasibility） ​

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

10. 算法引用 ​

11. 通用语言 ​

12. 设计决策 ​

13. 变更记录 ​