组合优化三剑客：TSP、CVRP 和 FFSP

在强化学习、图神经网络甚至大模型应用的各类论文中，TSP、CVRP 和 FFSP 这三组缩写几乎屡见不鲜。它们是组合优化问题中的经典基准测试集，广泛用于验证优化算法、神经策略甚至 AI 规划系统的性能。

但很多人对它们的理解仅停留在“这是三个数据集”。实际上，它们代表了三类截然不同的优化难题，各自有不同的结构约束、建模方式与工业落地场景。

这篇文章就来带你一次性梳理清楚：TSP、CVRP、FFSP 是什么、为什么难、数据集怎么来的，以及它们在今天的 AI 优化领域中的地位。

TSP：旅行商问题，组合优化的 Hello World

定义： TSP（Traveling Salesman Problem）要求给定若干城市，找到一条最短路径，使得旅行者从一个城市出发，恰好访问每个城市一次，最终回到起点。

形式化建模：

• 输入：城市集合 C=c1,...,cnC = {c_1, ..., c_n}C=c1​,...,cn​ 和距离矩阵 DDD
• 输出：一个排列 τ\tauτ，使得 ∑kDτk,τk+1\sum_k D_{\tau_k, \tau_{k+1}}∑k​Dτk​,τk+1​​ 最小，且 τ\tauτ 是 CCC 的一个全排列

难点：

• 解空间为 n!n!n!，即使是 50 个城市，枚举所有路径也不现实
• 是著名的 NP-hard 问题，最优解无法在多项式时间内求出

数据集：

• TSPLib：包含了几十个真实城市距离图（如 berlin52、pr2392 等）
• 常用于测试算法是否“能解”，是否有泛化能力

应用场景：

• 线路规划、无人机路径、芯片布线、仓库拣货

CVRP：有容量限制的车辆路径规划问题

定义： CVRP（Capacitated Vehicle Routing Problem）是 TSP 的一个扩展版本，考虑不止一个旅行者，而是多辆车从一个仓库出发，为客户送货，且每辆车的负载有限。

关键约束：

• 每辆车从同一个 depot 出发
• 每个客户有不同的 demand（需求）
• 每辆车的总配送量不得超过容量限制 QQQ
• 所有客户都必须被覆盖，不能重复访问

数据集：

• CVRPLib：提供标准 benchmark 实例，包括节点坐标、需求量、车辆容量
• 现代强化学习方法如 POMO、Pointerformer 等都在此类数据集上做评测

挑战性：

• 不仅要考虑路径长度，还需设计合理的“客户分配方案”
• 调度 + 路径优化的二重优化问题

应用场景：

• 城市物流、快递路线、集配中心优化、电商仓储配送

FFSP：柔性车间调度问题，工业界的真实模拟

定义： FFSP（Flexible Flow Shop Problem）是制造业调度问题的核心模型。它模拟多个工件经过多个机器的生产过程，每道工序必须遵循一定顺序，但可以在不同机器上灵活调度。

模型特点：

• 每个任务由多个阶段组成（Flow Shop）
• 每阶段可能对应多台机器（Flexible）
• 目标通常是最小化 Makespan（完成所有任务的最晚结束时间）

数据集来源：

• 通常是合成数据或真实制造流程简化
• 包含任务数量、每阶段可选机器数、每台机器的处理时间矩阵等

难点在于：

• 多阶段多资源分配问题
• 机器资源冲突、工序顺序等复杂约束
• 含有强烈的时序性和并发性，Gantt 图几乎是标配可视化手段

典型应用：

• 智能工厂排产
• 半导体多道工序调度
• 医疗检查排队（带有流程阶段）

为什么这三个问题总被用来做 benchmark？

简单来说，它们分别代表了三个典型的优化维度：

无论是启发式算法、图神经网络，还是强化学习和大模型规划框架，只要能在这三类问题上打出漂亮成绩，就意味着算法具备通用优化能力的潜质。

尤其在 RL4CO（Reinforcement Learning for Combinatorial Optimization）兴起之后，TSP 和 CVRP 更是成为强化学习策略网络的默认验证场景。

思考

TSP、CVRP 和 FFSP 之所以能成为组合优化领域的“三大金刚”，不仅因为它们涵盖了路径规划、资源调度和并行任务分配这三种本质问题，更因为它们构成了现实工程系统中最常见的结构性瓶颈。

在调度一个快递网络、运营一条智能产线，或控制一个具身智能体行动路径时，背后隐藏的优化任务，最终几乎都可以映射成这三类问题之一。

也正因如此，它们在学术上是 benchmark，在工程上则是“内功修炼”的门槛。

如果一个 AI 系统无法在这些问题上找到可解释、可泛化、可部署的策略，那它的智能只能停留在“演示级别”。

在大模型成为操作系统、强化学习重新被定义为策略精炼手段的今天，TSP 不再是最短路径的数学练习，而是规划智能体“动作意图”的抽象建模；CVRP 不再是一个冷冰冰的节点网络，而是一个复杂的资源调度过程，可以与 LLM 的语义理解能力融合；FFSP 更像是一场任务协作的对话，每台机器都是 token，每个工序就是上下文。我们看到的是一种结构智能的回归——在 token 与 graph 之间，在优化目标与偏好之间，大模型开始学会“系统化地决策”。而这些组合优化问题，正是最好的试金石。