查看“基于网络流的业务规划器”的源代码

<languages/>

== 概述 / 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 支持几种规模 / 方案：

{| class="wikitable"
! 规模 / 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（[[Special:MyLanguage/DPS调度算法详解|DPS调度算法详解]]）
   - 流场（[[Special:MyLanguage/流场规划|流场规划]]）
      │  每辆车的具体路径
      ▼
  [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 次规划记 ''解时间 + 任务数 + 改变的边数''。

== 相关页面 / See also ==
* [[Special:MyLanguage/调度内核运行原理|调度内核运行原理]]
* [[Special:MyLanguage/DPS调度算法详解|DPS调度算法详解]]
* [[Special:MyLanguage/流场规划|流场规划]]
* [[Special:MyLanguage/Simple软件架构|Simple软件架构]]
* [[Special:MyLanguage/使用手册 - 车队管控|使用手册 - 车队管控]]

[[Category:技术报告]]