1. 课程导入与问题界定
车辆路径问题（Vehicle Routing Problem，简称 VRP）是运筹学与组合优化领域中最具代表性的问题之一。它的基本描述是：给定一个仓库（或配送中心）、一组地理位置分散的客户，以及一支容量有限的车辆队伍，如何为每辆车规划一条从仓库出发、依次访问若干客户、最终返回仓库的行驶路线，使得所有客户的需求都被满足，同时总行驶成本（通常是距离或时间）最小。这个看似简单的描述背后，隐藏着极其庞大的组合搜索空间——当客户数量增加到几十个时，可能的路线组合就已经远超天文数字。
要准确理解 VRP，需要先厘清它的四个核心要素。第一是客户，每个客户有确定的位置、需求量和服务时间窗（在基础模型中时间窗可以省略）。第二是车辆，每辆车有载重上限、可能的行驶里程上限，以及是否必须返回仓库的约束。第三是仓库，它是所有路线的起点和终点，也是货物装载的场所。第四是道路网络，它决定了任意两点之间的实际行驶距离或时间，通常用距离矩阵来表示。这四个要素共同构成了 VRP 的输入数据，任何一项发生变化，都会改变问题的求解难度和最优解的结构。
一个直观的示例：假设某配送中心有 1 个仓库、8 个客户，客户需求分别为 2、3、1、4、2、3、1、2（单位：吨），车辆载重上限为 8 吨。如果只用 1 辆车依次访问全部客户，总需求为 18 吨，显然超载，必须拆分为至少 3 条路线。如何拆分、每条路线访问哪些客户、以什么顺序访问，就是 VRP 要回答的问题。不同的拆分方式会产生不同的总行驶距离，而我们的目标就是找到总距离最短的那一种。
从上面的示例可以看出，VRP 的求解包含两个相互耦合的决策层次：一是分组决策，即把哪些客户分配给同一辆车；二是排序决策，即同一辆车访问客户的先后顺序。这两个层次并非独立——分组方式会影响每条路线内部的排序优化空间，而排序结果又反过来影响分组是否合理。正是这种耦合性，使得 VRP 不能简单地拆成两个独立问题分别求解，而需要专门的建模与算法设计。
上图展示了一个 8 客户、3 条路线的可行解结构。可以看到，每条路线都从仓库出发并返回仓库，路线内部的客户访问顺序决定了该路线的行驶距离，而客户如何分配到三条路线则决定了整体的分组格局。这个示例中三条路线载重均为 6 吨，均未超过 8 吨上限，是一个可行解；但它未必是最优解——换一种分组或排序方式，总距离可能更短。这正是 VRP 优化要解决的核心问题。
典型应用场景
VRP 并非抽象的数学游戏，它在现实中有极其广泛的应用。物流配送是最经典的场景：快递公司每天需要为成百上千个收件点安排配送路线，车辆容量、司机工作时间、客户收货时间窗都是硬约束。共享出行中的车辆调度问题可以看作 VRP 的变体：共享单车或共享汽车需要被调度到需求热点区域，调度车辆的路径规划直接影响运营效率。应急物资调度则对时间极为敏感：地震或洪水发生后，救援物资需要从储备仓库尽快送达多个受灾点，此时目标函数往往从“最小化距离”转变为“最小化最大送达时间”或“最大化覆盖需求”。这三个场景的共同点是：资源有限、需求分散、路径决策直接影响成本或服务质量。
课程学习路径与目标
本课程共 30 章，整体遵循“界定问题—建立模型—设计算法—实验验证”的主线。前几章将系统梳理 VRP 的问题定义、核心要素与常见变体（如带容量约束的 CVRP、带时间窗的 VRPTW、多仓库 VRP 等），帮助学习者建立清晰的问题边界。随后进入建模阶段，介绍如何用混合整数线性规划（MILP）描述 VRP，包括决策变量、目标函数与约束条件的写法。算法部分将覆盖精确算法（如分支定界、列生成）与启发式算法（如节约算法、禁忌搜索、遗传算法、蚁群算法），并重点讲解如何针对具体场景选择合适的求解策略。最后通过实验与案例分析，训练学习者独立完成“问题抽象—模型构建—算法实现—结果评估”的完整闭环。
学习建议：VRP 的难点不在于记住某个公式，而在于理解“约束如何塑造解空间”。建议在学习每个变体时，先手动画出一个小规模示例（如 5 个客户、2 辆车），尝试手动构造可行解并比较优劣，再进入代码实现。这种“先手算、后编程”的顺序能显著加深对模型结构的理解。
需要特别强调的是，VRP 的“最优解”往往难以在合理时间内求得，实际工程中更常见的是“在可接受时间内获得足够好的解”。因此，本课程在讲解精确算法时会明确其适用规模，在讲解启发式算法时会关注解的质量与计算时间的权衡。学习者应建立这样的意识：算法选择取决于问题规模、约束复杂度和业务对时效的要求，没有一种方法能通吃所有场景。