多商品网络流 (Multi Commodity Network Flow, MCNF)⚓︎
约 3369 个字 预计阅读时间 11 分钟 总阅读量 次
多商品网络流，一个很有趣也很重要的优化问题，在通信、交通、物流和经济领域都有应用。其基础的模型框架可以视为一个线性规划。一言以蔽之，我们考虑一个网络，其中有多种商品，每个商品都有一定数量，都需要从一个起点流通到一个终点，决策者需要规划商品流动路线使得满足需求、尽可能最大/小目标函数的同时不违背特定约束（譬如容量）。
比如说，在交通领域，一个场景是：给定了城市路网的连通结构（路段、交叉口），给定人群的出行需求（即某些OD对之间的流量），已知每个路段的容量。如果不考虑流量对道路通行时间的影响（即不考虑拥堵，出行成本固定），假设所有车辆都由决策者调度，此时如何安排每个OD对之间的路径选择和路径流量，使得所有人出行成本最小？
起初只是想简单记录一下模型，顺便回顾一下求解算法，没想到这个问题在最近 (2020好像也不是很近？) 还有个小综述。见 Salimifard, K., Bigharaz, S. The multicommodity network flow problem: state of the art classification, applications, and solution methods. Oper Res Int J 22, 1–47 (2022). https://doi.org/10.1007/s12351-020-00564-8.
Node-Arc Form (节点-弧形式)⚓︎
节点-弧（Node-arc）形式是 MCNF 问题最经典和最直观的表示方法。它关注的是每一种商品在网络中每一条弧上的具体流量。
标记⚓︎
- \(N\): 网络中所有节点的集合。
- \(A\): 网络中所有有向弧（arc）的集合，弧由节点对 \((i, j)\) 表示。
- \(K\): 网络中所有商品（commodity）的集合。
| 标记 | 含义 |
|---|---|
| \(s_k\) | 商品 \(k\) 的源点 (origin node)，\(s_k \in N\)。 |
| \(t_k\) | 商品 \(k\) 的汇点 (destination node)，\(t_k \in N\)。 |
| \(d^k\) | 商品 \(k\) 的总需求量（total demand）。 |
| \(c_{ij}^k\) | 在弧 \((i,j)\) 上运输一单位商品 \(k\) 的成本。 |
| \(u_{ij}\) | 弧 \((i,j)\) 的容量（capacity）。这是所有商品共享的容量。 |
| \(b_i^k\) | 表示节点 \(i\) 对于商品 \(k\) 的供给/需求量。这是一个为了方便表示流量守恒约束而引入的符号，具体定义见后 |
决策变量：\(x_{ij}^k\): 在弧 \((i,j)\) 上的商品 \(k\) 的流量（flow）。
数学规划模型⚓︎
节点-弧形式可以表示为以下线性规划问题：
目标函数:
\[
\min Z^*(x) = \sum_{k \in K} \sum_{(i,j) \in A} c_{ij}^k x_{ij}^k \quad (1)
\]
约束条件:
\[
\begin{align*}
& \sum_{(i,j) \in A} x_{ij}^k - \sum_{(j,i) \in A} x_{ji}^k = b_i^k && \forall i \in N, \forall k \in K \quad &(2) \\
& \sum_{k \in K} x_{ij}^k \le u_{ij} && \forall (i,j) \in A \quad &(3) \\
& x_{ij}^k \ge 0 && \forall (i,j) \in A, \forall k \in K \quad &(4)
\end{align*}
\]
其中，
\[b_i^k =
\begin{cases}
d^k & \text{if } i = s_k \\
-d^k & \text{if } i = t_k \\
0 & \text{if } i \in N \setminus \{s_k, t_k\}
\end{cases}\]
解释⚓︎
-
目标函数 (1): 最小化网络中需要运输的所有商品的总运输成本。成本是每条弧上每种商品流量与其单位运输成本乘积的总和。
-
约束 (2) - 流量守恒约束 (Flow Conservation Constraint): 该约束也被称为供需约束。对于网络中的 每一个节点 \(i\) 和 每一种商品 \(k\)，所有从节点 \(i\) 流出的该商品总量（\(\sum x_{ij}^k\)）减去所有流入节点 \(i\) 的该商品总量（\(\sum x_{ji}^k\)），必须等于该节点 \(i\) 对该商品的净供给量 \(b_i^k\)。
- 在源点 \(s_k\)，净流出量为 \(d^k\)。
- 在汇点 \(t_k\)，净流入量为 \(d^k\) (即净流出量为 \(-d^k\))。
- 在中间节点，流入量等于流出量。
-
约束 (3) - 共享容量约束 (Bundle/Capacity Constraint): 对于网络中的 每一条弧 \((i, j)\)，流经该弧的 所有商品 的总流量之和，不能超过该弧的预设容量 \(u_{ij}\)。这是体现“多商品”间资源竞争的核心约束。
-
约束 (4) - 非负约束 (Non-negativity Constraint): 确保所有弧上的商品流量都是非负的，这符合物理世界的实际情况。
Arc-Path Form (弧-路径形式)⚓︎
弧-路径形式（Arc-path form）从另一个角度来构建 MCNF 模型。它不再关注单个弧上的流量，而是将决策变量定义在从源点到汇点的完整“路径”上。这种形式的变量数量可能非常多（路径数量是指数级增长的），但其约束结构相对简单。正因为 MCNF 可以被构建成这种模型，它天然适合用基于分解的、列生成的相关精确式算法进行求解。
标记⚓︎
- \(A\): 网络中所有有向弧（arc）的集合。
- \(K\): 网络中所有商品（commodity）的集合。
- \(P^k\): 对于商品 \(k\)，从其源点 \(s_k\) 到汇点 \(t_k\) 的所有可能（简单）路径的集合。
| 标记 | 含义 |
|---|---|
| \(d^k\) | 商品 \(k\) 的总需求量（total demand）。 |
| \(u_a\) | 弧 \(a\) 的容量（capacity），其中 \(a \in A\)。 |
| \(PC_p^c\) | 路径 \(p\) 的成本。此成本通常由构成该路径的所有弧的成本之和计算得出 (\(PC_p^c = \sum_{a \in p} c_a^k\))。 |
| \(\delta_a^p\) | 一个二进制参数，用于指示路径 \(p\) 是否经过了弧 \(a\)。如果路径 \(p\) 包含了弧 \(a\)，则 \(\delta_a^p = 1\)；否则为 \(0\)。 |
决策变量：\(f_p\): 在路径 \(p\) 上的流量。注意，路径 \(p\) 本身是属于某个特定商品 \(k\) 的路径集合 \(P^k\) 的，因此 \(f_p\) 代表了该商品在特定路径上的流量。
弧-路径形式可以表示为以下线性规划问题：
数学规划模型⚓︎
目标函数:
\[
\min Z^*(f) = \sum_{k \in K} \sum_{p \in P^k} PC_p^c f_p \quad (5)
\]
约束条件:
\[
\begin{align*}
& \sum_{p \in P^k} f_p = d^k && \forall k \in K \quad &(6) \\
& \sum_{k \in K} \sum_{p \in P^k} \delta_a^p f_p \le u_a && \forall a \in A \quad &(7) \\
& f_p \ge 0 && \forall p \in P^k, \forall k \in K \quad &(8)
\end{align*}
\]
解释⚓︎
-
目标函数 (5): 最小化总运输成本。该成本是所有商品在各自所有可行路径上的流量与对应路径成本乘积的总和。
-
约束 (6) - 需求满足约束 (Demand Satisfaction Constraint): 对于 每一种商品 \(k\)，其所有可选路径 (\(p \in P^k\)) 上的流量之和，必须恰好等于该商品的总需求量 \(d^k\)。这个约束确保了每种商品的需求都得到满足。
-
约束 (7) - 共享容量约束 (Capacity Constraint): 对于网络中的 每一条弧 \(a\)，所有 使用到该弧的路径 的流量总和不能超过该弧的容量 \(u_a\)。这里的关键是通过 \(\delta_a^p\) 参数来识别出哪些路径的流量需要计入特定弧的容量消耗中。这个约束将路径流量与弧的物理限制关联起来。
-
约束 (8) - 非负约束 (Non-negativity Constraint): 确保所有路径上的流量都是非负的。
关于目标函数⚓︎
| 类别 (Category) | 核心目标 (Core Objective) | 需求处理方式 | 关键问题 |
|---|---|---|---|
| 最小成本多商品网络流 (Min-cost MCNF) |
在满足所有需求的前提下，最小化总运输成本。 | 需求 \(d^k\) 是一个必须满足的硬约束。模型必须找到一个能运送所有 \(d^k\) 的可行流。 | “如何用最低的成本将所有指定的货物从A点运到B点？” |
| 最大流量多商品网络流 (Max MCNF) |
最大化网络中所有商品的总流量之和。 | 通常不考虑或弱化“需求”概念。目标是尽可能地提高整个网络的总吞吐量。 | “这个网络最多能同时运输多少总量的货物？” |
| 最大并发流问题 (Max-concurrent MCNF) |
最大化一个公共比例因子 \(z\)，使得每种商品的需求 \(d^k\) 至少能被满足 \(z * d^k\) 的量。 | 需求 \(d^k\) 是一个基准。模型试图按相同比例（“并发地”）满足所有需求，并让这个比例最大化。 | “我们最多能同时满足每种商品需求的百分之多少？” |
-
Min-cost MCNF ：这是最常见的形式，也是上面建模里的表达。它的前提是 “需求必须全部满足”，然后在这个前提下寻找成本最低的方案。它回答的是 “how to do it cheaply”。
-
Max MCNF：这个问题的目标非常纯粹，就是让流经网络所有弧的总流量最大化。它不关心每种商品是否被公平对待。例如，如果运送商品A比运送商品B能更快地占满网络容量，模型可能会优先运送大量的A而忽略B，只要总流量最大即可。它回答的是 “what's the total capacity”。
-
Max-concurrent MCNF：这是 Max MCNF 的一个变体，但加入了“公平性”或“按比例满足”的思想。它不再追求总流量最大，而是追求一个最大的满足比例 \(z\)。例如，如果最大并发流的解是 \(z=0.8\)，这意味着网络有能力同时满足每种商品各自需求的80%。这在通讯网络中非常常见，用于评估网络能为所有用户提供多大比例的服务质量。它回答的是 “how much of everyone's demand can we satisfy fairly”。
一些魔改、一些应用⚓︎
凸多商品网络流问题 (The Convex Multicommodity Flow Problem)⚓︎
事实上，在通信网络中，一种建模是把问题凸化而不仅仅是线性化。这种方式常用于 Massage routing problems， 可以参考：Adam Ouorou, Philippe Mahey, Jean-Philippe Vial. A survey of algorithms for convex multicommodity flow problems. Management Science, 2000. hal-01729109.
作为一个非线性的 MCNF 变体，其核心特点是目标函数为一个凸函数，而非线性函数。这使得模型能够描述成本（如延时）随着流量增加而加速增长的现实情况，即所谓的拥塞效应。该模型采用节点-弧形式进行构建。为了方便表示，下面引入了矩阵和向量标记。
标记⚓︎
- \(G=(V, E)\): 一个有向图，包含 \(m\) 个节点 (nodes) 和 \(n\) 条弧 (arcs)。
- \(K\): 网络中需要运输的商品种类数量。
| 标记 | 含义 |
|---|---|
| \((s_k, t_k)\) | 商品 \(k\) 的源点-汇点对。 |
| \(r_k\) | 商品 \(k\) 的流量需求 (flow requirement)，即必须从 \(s_k\) 发送到 \(t_k\) 的总量。 |
| \(c_j\) | 弧 \(j\) 的容量。 |
| \(M\) | 图 \(G\) 的 \(m \times n\) 节点-弧关联矩阵 (node-arc incidence matrix)。矩阵的每一行对应一个节点，每一列对应一条弧。对于列 \(j\) (代表弧 \((u,v)\)) 和行 \(i\) (代表节点)，其元素 \(M_{ij}\) 的值为：\(1\) 如果 \(i=u\) (弧的起点)，\(-1\) 如果 \(i=v\) (弧的终点)，\(0\) 其他情况。 |
| \(b_k\) | 一个 \(m\) 维向量，用于表示商品 \(k\) 的源点和汇点。其所有元素都为0，除了在源点 \(s_k\) 对应的位置为 \(1\)，在汇点 \(t_k\) 对应的位置为 \(-1\)。 |
| \(f_j(\cdot), f_{kj}(\cdot)\) | 与弧 \(j\) 和商品 \(k\) 相关的凸成本函数。 |
决策变量:
- \(x_{kj}\): 在弧 \(j\) 上的商品 \(k\) 的流量。
- \(x_{0j}\): 在弧 \(j\) 上的总流量 (所有商品流量之和)。
数学规划模型⚓︎
目标函数:
\[
\min f(x) = \sum_{j=1}^{n} f_j(x_{0j}) + \sum_{k=1}^{K} \sum_{j=1}^{n} f_{kj}(x_{kj})
\]
约束条件:
\[
\begin{align*}
& x_{0j} = \sum_{k=1}^{K} x_{kj} && j=1, \dots, n \quad &(1) \\
& M x_k = r_k b_k && k=1, \dots, K \quad &(2) \\
& x_k \ge 0 && k=1, \dots, K \quad &(3) \\
& 0 \le x_{0j} \le c_j && j=1, \dots, n \quad &(4)
\end{align*}
\]
这里 \(x_k\) 是一个 \(n\) 维向量，其展开为 \((x_{k1}, x_{k2}, ..., x_{kn})\)。
解释⚓︎
-
目标函数: 最小化一个总的凸成本。这个成本函数通常由两部分构成：
- \(f_j(x_{0j})\): 与 总流量 相关的成本。这部分是模拟拥塞的关键，当总流量 \(x_{0j}\) 接近弧的容量 \(c_j\) 时，该成本会急剧增加。
一个在数据网络中常见的例子是 Kleinrock 延迟函数，它只考虑总流量成本，具体形式为：
\[ f_j(x_{0j}) = \frac{x_{0j}}{c_j - x_{0j}} \]这个函数直观地表示了当弧上的流量接近其容量时，平均延迟会趋向于无穷大。
- \(f_{kj}(x_{kj})\): 与 单个商品 流量相关的成本。
-
约束 (1) - 总流量定义: 这是一个定义性约束，它将辅助变量 \(x_{0j}\) (总流量) 定义为该弧上所有不同商品流量 \(x_{kj}\) 的总和。
-
约束 (2) - 流量守恒约束 (矩阵形式): 这是标准流量守恒约束的一种==紧凑的矩阵表达形式==。
- \(M x_k\) 这个乘积计算了对于商品 \(k\)，网络中每个节点的净流出量（流出量 - 流入量）。
- \(r_k b_k\) 这个乘积生成一个向量，其在源点 \(s_k\) 位置的值为 \(r_k\)，在汇点 \(t_k\) 位置的值为 \(-r_k\)，在其他所有节点位置的值为 0。
- 因此，整个等式确保了对于每种商品 \(k\)，其在源点的净流出量为 \(r_k\)，在汇点的净流入量为 \(r_k\)，在所有中间节点的流量是守恒的（流入等于流出）。
-
约束 (3) - 非负约束: 保证所有商品在所有弧上的流量都是非负的。
-
约束 (4) - 容量约束: 保证任何一条弧上的总流量都不能超过该弧的物理容量 \(c_j\)。