车辆路径问题
背景与问题类
车辆路径问题（Vehicle Routing Problem, VRP）是物流与组合优化中的核心模型之一。经典说法可追溯至 Dantzig 与 Ramser（1959）：用若干辆容量有限的车，从仓库出发为分散的客户送货，在满足载重与业务规则的前提下，使总行驶费用或时间等目标最优。
在问题类层面，常令有向图 ，其中节点集 含仓库与客户； 为可行有向弧（完全图时可用大费用屏蔽不可行弧）。记：
- 仓库为节点 ；客户集合为 （），常记 或把仓库终点做成「副本」见下文。
- 车的集合为 ；每车最大载重（或等效容量上界）为 。
- 客户 的需求量为 ；通常设 、 若使用仓库终点副本。
- 弧 上单位费用或长度记为 （可不对称）。
典型可行要求包括（依具体 VRP 变体取舍）：
- 每车从仓库出发、服务若干客户后回到仓库。
- 每客户恰被一辆车访问并服务一次（除非定义成分批多次送）。
- 每车所装载的总需求不超过 。
- 在 VRPTW 中还要满足在节点 开始服务的时间落在时间窗 内，并在弧上满足时间传递关系。
在「全体客户、单车若可行则退化」的层次上，无容量、单车、仅最小化路长的 VRP 与 旅行商问题 同型；容量、多车、时间窗、多车场、取送货、周期等一加上，问题类迅速扩展，见下一节。VRP/VRPTW 一般为 NP-hard，精确算法（如分支定价）与 启发式 / 元启发式（节约值、插入 等）在工程上都很常见。表述与算例结构可参考 Desaulniers et al.（2006）等专著。
最简单模型：带容量、无时间窗（CVRP 骨架）
在尚未引入时间前，最简单的常用写法是 CVRP（Capacitated VRP，带容量 VRP）的三指标 0–1 弧变量。图结构仍用仓库起点 与终点副本 （同址车场、需求 0，与后节 VRPTW 一致），
为可行弧集。决策 含义同上。另引入连续变量 （），将 解释成：沿车 的路径，在节点 服务完成之后、车上已装的总需求；， 与 (8) 的弧上传递一起实现各点容量一致。与 旅行商问题 的 MTZ 辅助变量（常记为 ）同属实辅助变量加大 的线性衔接式，但此处的 是载重，与 TSP 中用于破子环的 含义不同。约定 、； 时 (8) 不增加 、只把终点的 与上一段衔接。在「 辆车全部出车、每车一条自 至 的有向路」的约定下，CVRP 闭式可写为 (1)–(9)（求和可只限于 中弧、与实现一致）：
式 (8) 在 时沿路径把 累进载重；在 时 ，上式即：若选弧 ，则回库时载重等于在 服务完成后的值。在 等自然紧下，常取 ，使 时 (8) 不割松弛中可行 ；亦可用弧上 等进一步收紧，依实现而定。
注：(2) 用从客户 出发的弧表示「恰一辆车从 前往下一节点」。若允许部分车闲置，常把 (3)(5) 改为 并加已用车上界或固定车成本等（不展开）。(1)–(5) 与 (6)–(8) 在整数 上给出沿路径的累计载重 MTZ 式，替代「一条和式 型」的标量上界。松弛层对对称、子环等仍有割、分支，本页不展开。(1)–(9) 已构成带 MTZ 型累计载重的 CVRP 三指标闭式。
常见变体（概念列举）
在「配送+路由」的实务里，还常见下列问题类名称（可互相叠加）：
- 带取/送货、时间窗的 CVRP；
- 多车场 VRP；
- 带时间窗的多车场 VRP；
- 周期 VRP；
- 带时间窗的周期 VRP；
- 强调装货与卸货时序或库存的 VRP 等（PDP/库存路径等更细子类在文献中另立名目）。
本页在 (1)–(9) 之上，下一节仅增加时间窗 、行驶时间 与服务开始时刻 ，得到 VRPTW。
带时间窗的 VRP（VRPTW）在 (1)–(9) 上的叠加
在与上节完全相同的 、、 与 含义，以及累计载重 与 (6)–(8) 的约定下，VRPTW 再引入连续（或按刻度整数化的）服务开始时间 （），及数据 （行驶与服务时间，约定与弧一致）、、大 或下节 （上标 表示时间用的紧常数，与 (8) 的 区分）。
与 CVRP 共同部分：目标、路由、MTZ 载重与二值仍取上节 (1)–(9)（不再重复抄录，联立时与下列 (10)–(12) 同时成立）。
新增时间衔接（Big–M，对 、；时间用大 记为 或弧上 ）：
时间窗：
不访问的 在实现中可不建 或让 (10) 仅在 有定义的弧上生效；(11) 与紧的 或 (12) 的 搭配利于数值稳定；若需严格地只对「实访」节点建 ，可另加 0–1 指示与 McCormick/大 等（与「完整骨架」的取舍有关，本页不展开）。
时间大 的紧化
不取无依据的 ，常对 (10) 用弧上常数。若时间窗为 ，一条常用取法为
并在 (10) 中把单一 换为 。与 记法不同文献若换字母，与最早/最晚可服务时刻一一对应即可。
注：全页在「无时间」时为 (1)–(9)；再叠 (10)–(12) 与 即为 VRPTW 的常用闭式。式号仅本页自洽；与站内其它 .md 的式号独立。小规模可试通用 MILP/MIQCP 解算器，大规模常配合 分支定价 与启发式。