3. 拣选路径问题建模：TSP与VRP在拣选中的应用

拣选路径优化本质上是一个组合优化问题。在WMS工程实践中，最核心的两个数学模型是旅行商问题（TSP）和车辆路径问题（VRP）。理解这两个模型及其在拣选场景下的变体，是设计高效波次与分区策略的理论基础。

3.1 旅行商问题（TSP）在拣选中的应用

TSP描述的是：给定一系列货位点，拣选员从起点（如出货暂存区）出发，每个货位点恰好访问一次，最后返回起点，求最短路径。在单区单人拣选场景中，TSP是基础模型。

3.1.1 TSP数学模型

设货位点集合为 \( V = \{0, 1, 2, ..., n\} \)，其中0为起点/终点，\( d_{ij} \) 为点i到点j的距离。决策变量 \( x_{ij} \) 表示是否从i直接走到j。模型如下：

目标函数：min Σᵢⱼ dᵢⱼ · xᵢⱼ

约束条件：
1. 每个点恰好进入一次：Σᵢ xᵢⱼ = 1, ∀j
2. 每个点恰好离开一次：Σⱼ xᵢⱼ = 1, ∀i
3. 消除子回路（MTZ约束）：
   uᵢ - uⱼ + n · xᵢⱼ ≤ n-1, ∀i≠j, i,j≠0
4. xᵢⱼ ∈ {0, 1}, uᵢ ≥ 0

3.1.2 TSP路径长度与时间成本模型

路径总时间成本由三部分组成：

总时间成本模型：

Total_Cost = α · T_walk + β · T_pick + γ · T_wait

其中 α, β, γ 为权重系数，由WMS策略配置。
典型值：α=1.0, β=1.2（拣取动作更耗时）, γ=1.5（拥堵惩罚）

3.2 车辆路径问题（VRP）在拣选中的应用

当多拣选员、多批次、多分区同时作业时，TSP扩展为VRP。VRP的核心是：为多台“车辆”（拣选员/AGV）规划路径，每台车从仓库起点出发，服务一组货位后返回，所有货位被覆盖且总成本最小。

3.2.1 VRP在波次拣选中的变体

3.2.2 VRP数学模型（CVRP示例）

在TSP模型基础上，增加车辆集合 \( K \) 和容量约束：

目标函数：min Σₖ∈K Σᵢⱼ dᵢⱼ · xᵢⱼₖ

约束条件：
1. 每个货位点恰好被一辆车服务：Σₖ Σⱼ xᵢⱼₖ = 1, ∀i≠0
2. 车辆容量约束：Σᵢ qᵢ · yᵢₖ ≤ Qₖ, ∀k
3. 路径连续性：Σᵢ xᵢⱼₖ = Σᵢ xⱼᵢₖ, ∀j,k
4. 起点终点约束：每辆车从0出发，回到0

其中：
  qᵢ = 货位i的拣选数量
  Qₖ = 车辆k的容量
  yᵢₖ = 1 表示货位i由车辆k服务

3.3 路径长度与时间成本模型对比

3.4 工程实践中的成本模型选择

在WMS系统中，路径优化引擎需要根据实时数据动态选择模型：

1. 单波次单区：使用TSP模型，以曼哈顿距离为度量，结合巷道通行规则修正距离矩阵。
2. 多波次多区：使用VRP模型，将每个波次视为一个“车辆”，容量为波次订单总件数。
3. 混合模式：先通过分区策略将大问题分解为多个TSP子问题，再通过VRP协调跨区路径。