如何求解包含储罐节点的网络流问题

传统网络流的基础逻辑 #

传统网络流模型只包含三类节点：

• 源点：产生并向网络注入资源
• 交汇/路由节点：严格遵守流量守恒规则，完成资源的分流、合流转接
• 汇点：消耗、排出网络中的资源

这类模型的常规求解目标是计算最大流，也就是通过最优分配各边流量，最大化利用源点的供给能力，满足汇点的资源需求。

储罐节点的特性与适配难点 #

当网络中新增第四类节点——可存储资源并在后续释放的储罐时，传统网络流算法无法直接套用。储罐不会固定扮演某一类节点角色，会根据自身剩余容量、当前储有量、连接边的方向约束，动态切换为源点、汇点、交汇节点三类角色：

• 空罐没有存量资源时，不能作为源点向外输出流量
• 满罐没有剩余容量时，不能作为汇点接收外部流入的流量
• 储罐可以同时接入入流、出流边，也可以只接入单方向边，没有固定的连接要求。

储罐参与调度的典型运行场景 #

两个最基础的调度场景计算逻辑如下：

1. 源点供给为50单位/秒、汇点需求为5单位/秒，储罐接入交汇节点时：左侧入边流量为50单位/秒、右侧出边流量为5单位/秒，剩余45单位/秒的过剩流量全部由储罐吸纳
2. 源点供给为5单位/秒、汇点需求为50单位/秒，储罐接入交汇节点时：源点出流5单位/秒、储罐出流45单位/秒，两部分流量共同满足汇点总需求。

储罐的流量交互约束 #

储罐参与流量调度必须严格遵守连通性和边方向规则：

• 若储罐和网络的连接边为单向：
  • 只有当过流路径可以沿边方向到达储罐，且储罐有剩余容量时，储罐才能吸纳网络里的过剩流量
  • 只有当需求缺口可以沿边反向追溯到储罐，且储罐有存量资源时，储罐才能释放流量补给缺口

典型反例：源点供给50单位/秒、汇点需求5单位/秒，且储罐仅通过单向出边接入交汇节点时，要按传统最大流逻辑只传输5单位/秒流量到汇点，储罐完全不参与流量交互。

• 若储罐和网络的连接边为双向：储罐可以在满足储量、容量约束的前提下，灵活吸纳过剩流量或者补给需求缺口。

可落地的求解算法 #

这套算法只需要输入基础参数：网络图结构、各节点类型（储罐/交汇节点/源点/汇点）、源点供给量、汇点需求量，就能输出符合所有规则的各边流量，核心是通过节点拆分把储罐逻辑转化为传统上下界网络流可求解的结构，步骤如下：

1. 节点拆分处理所有储罐：把每个储罐拆成「入罐节点」「出罐节点」两个虚拟节点，模拟储罐的存、取隔离逻辑
   • 在入罐节点和出罐节点之间连一条边，边的总容量等于储罐的最大存储容量，边的初始已占用流量等于储罐的初始储有量，这条边的流量变化就对应储罐的储水量变动
   • 所有原本指向储罐的入边，全部调整为指向入罐节点；所有原本从储罐出发的出边，全部调整为从出罐节点出发
   • 如果储罐和相邻节点是双向边，就同时添加「相邻节点→入罐节点」「出罐节点→相邻节点」两条方向相反的边，单方向容量和原双向边的单方向容量一致
2. 构建全局超级源、超级汇：
   • 超级源点向每个真实源点连边，边容量等于对应源点的供给量
   • 每个真实汇点向超级汇点连边，边容量等于对应汇点的需求量
3. 按优先级求解上下界最大流：
   • 第一阶段优先找真实源点到真实汇点的可行路径分配流量，这部分流量不经过储罐，对应直供场景
   • 第二阶段在满足边方向、储罐剩余容量/存量约束的前提下，依次分配「过剩流量→储罐」的储水路径、「储罐→需求缺口」的补水路径，直到没有可行调度路径为止
4. 提取所有真实边的流量值作为最终结果，所有虚拟节点、虚拟边的流量不纳入输出。

内容的提问来源于stack exchange，提问作者The_Sympathizer