基于网络流的业务规划器

概述 / Overview

"业务规划器"是调度链路最上层的决策器：把 业务任务列表（订单、生产工单）映射成 AGV 任务集合。基于网络流的实现把这一映射建模为 最大流 / 最小费用流问题，让规划在大规模、多约束、多目标的场景下仍然高效收敛。

The business planner is the topmost decision layer in the scheduling chain: it maps business jobs (orders, production work-orders) onto AGV tasks. The network-flow implementation casts this as a max-flow / min-cost flow problem so planning stays tractable at large scale with many constraints and objectives.

适用 / When applicable

货 ↔ AGV ↔ 工位三方匹配（混型货物多）/ Goods ↔ AGV ↔ work-station three-way matching with mixed cargo types.
业务有明确成本指标（节拍、能耗、磨损分布）/ Business has clear cost metrics (cycle time, energy, wear distribution).
任务量 ≥ 100 / 小时 / Task volume ≥ 100 / hour.

简单单线场景不需要网络流 —— 用 FIFO + 简单贪心即可。

For small linear deployments, FIFO + greedy is fine.

网络流模型 / Network-flow model

最经典模型（最小费用最大流）：

 S (源 / source)
  │
  ▼ cap=1 cost=0 (每个 AGV 一条供给边)
 ┌───────────────────────────────────┐
 │  Layer 1: AGV agent nodes          │
 └───────────────────────────────────┘
          │ cap=∞ cost=c_ij
          ▼ (c_ij = AGV_i 执行 task_j 的成本)
 ┌───────────────────────────────────┐
 │  Layer 2: Task nodes (each task = 1 node) │
 └───────────────────────────────────┘
          │ cap=1 cost=0
          ▼
 T (汇 / sink)

求解 min-cost flow → 哪 AGV 做哪个任务的指派。

Solve min-cost flow → which AGV does which task.

成本 c_ij 通常包含： The cost c_ij typically includes:

当前位置到取货点的距离（行驶时间）/ distance from current position to pickup
AGV 当前剩余电量与任务能耗的匹配度 / battery vs energy required
当前车型与货物匹配度（如：托盘叉车不能搬料筐）/ vehicle-cargo compatibility
公平性惩罚（让 每辆车工作量 均衡）/ workload-fairness penalty
时间窗（任务必须 N 秒内取走）/ time-window pressure

求解器 / Solvers

SimpleCore 支持几种规模 / 方案：

规模 / Scale	算法 / Algorithm	复杂度 / Complexity
< 200 任务	SSP (Successive Shortest Paths)	O(F · (n + m) log n)
200 – 2000 任务	Cost-scaling / Network Simplex	O(n³)
> 2000 任务	LP 松弛 + 圆整 / LP relaxation + rounding	近似 / Approximate
任意	增量重规划 / Incremental replanning	上次解 + δ

增量重规划 / Incremental replanning

业务规划不能 每秒重头跑 —— 上一次的解大部分可用。MDCS 采用 增量更新：

新任务进入 → 加节点 + 增广路径。
AGV 完成任务 → 移除节点 + 重路由其它任务。
AGV 故障 → 标该供给边 cap=0，对其原任务重新分配。

The business planner doesn't replan from scratch each second — most of the previous solution stays valid. MDCS uses incremental updates: add tasks via augmenting paths; remove completed tasks; on AGV failure, zero its supply edge and reassign its tasks.

与调度内核的关系 / Relation to the scheduler kernel

业务规划器上接业务系统（WMS / ERP），下接调度内核（DPS / 流场）：

 WMS / ERP
     │  订单 / 工单
     ▼
 [业务规划器 / Business planner]   ← 本页 / this page
     │  任务对 AGV 的指派
     ▼
 [调度内核 / Scheduler kernel]
  - DPS（DPS调度算法详解）
  - 流场（流场规划）
     │  每辆车的具体路径
     ▼
 [Car.actualSendScript] → 单车执行

业务规划只关心 谁做什么，不关心具体路径与交管。

The business planner only decides who does what. Paths and traffic control are the scheduler kernel's job.

调试与可视化 / Debug & visualisation

在 SimpleComposer 中开 Planner Trace：每次规划的所有边 + cost + 求得流值都可视化。
增量重规划失败时，规划器会 回退到全量重跑并打印 diff。
性能采样：每 N 次规划记 解时间 + 任务数 + 改变的边数。