有m个供应站si，每个供应站能够生产sup(si)个单位的商品。有n个需求站tj，每个需求站需要dem(tj)个单位的商品。而且还有w个仓库wk，每个仓库能够接收和转运最大为maxk个单位的商品，转运的费用为每个单位wpk。每一个供应站si到需求站tj的单位开销d(i,j)是固定的，从供应站si运送到仓库wk的开销为每单位ts(i,k)，然后从仓库wk转运到需求站tj的开销为ts(k,j)。我们的目标是决定了从供应站si到需求站tj的流f(i,j)之后，最小化总开销，可以定义为：
总开销（TC）=总运输开销（TSC）+总转运开销（TTC）
TSC=∑i∑jd(i,j)*f(i,j)
TTC=∑i∑kts(i,k)*f(i,k)+∑j∑kts(j,k)*f(j,k)
目标是寻找到所有的f(i,j)≥0，确保TC在满足供应和需求限制之后最小。最后，通过一个仓库的网络流的单位为0，确保没有添加或者损失任何的单位。sup(si)和dem(ti)必须大于0。运输的开销d(i,j)、ts(i,k)和ts(k,j)必须大于等于0。
解决方案
我们将转运问题转换成最小开销流问题（如图8-8所示），构造了这样一个图G=(V,E)：
V共有n+m+2*w+2个顶点
每个供应站si被映射成一个顶点i，每个仓库wk映射成两个顶点，m+2*k-1和m+2*k。每个需求站tj映射成顶点1+m+2*w+j。然后创建一个新的源点src（标记为0）和新的汇点tgt（标记为n+m+2*w+1）。
E共有(w+1)*(m+n)+m*n+w条边
在转运问题中构建边的过程可以在代码库中的Transshipment类找到。
如果对应的最小开销流问题能够得到解，那么转运问题也能够得到解，所有的f(u,v)＞0的边（u,v）∈E构成了结果集合。这些边的f(u,v)*d(u,v)之和是结果集合的总开销。
图 8-8 转运问题转换成最小开销流问题