可压缩网络流的输送策略研究

刘 炜，吴瑞明

(上海交通大学 安泰经济与管理学院，上海 200030)

1 引言

流是一个被广泛使用的概念，在数学、工程学、力学、计算机科学等领域均有涉及。在网络输送问题中，无论实际上输送的是何种物质，都可以被视为是流的输送。例如，水管输送的是水，电路输送的是电，以天然气为代表的气体也可以通过管道运送，而在做数理研究时，这些都可以被抽象为流，而忽略其本身物理性质的不同。

在传统的流模型中，当一个流或多个流流入一个节点时，节点不会对流的总量有任何影响，即不论流入节点的流量为多少，流出节点时的流量均与流入节点时的流量相同，除非流进入该节点后不再流出。而在现实生活中，许多流并不会满足这样的性质。例如，河道中的水流流经水坝时，由于水坝能够拦截水流以及调节流量，因此水流流出水坝时，其流量将很有可能与流入水坝时不同；同样，天然气流进入输气站时，由于输气站及周边用户通常有用气需求，流出输气站的天然气量也会与流入输气站时不同。因此，传统的流模型在研究这种性质的流输送问题时变得不再适用，我们需要一个新的模型及算法来解决拥有这种性质的流的运输问题，而拥有这种性质的流通常就被称为可压缩流。

在之前的研究中，蒋洋(2014)研究了交通运输中的网络流问题，建立了若干个交通运输网络流模型，涵盖了不同情况下的交通状况分析，取得了一定的成果。孙华灿等(2008)从货运生产实践出发，研究了运输过程中的路径优化与成本节约问题，并提出了一个适用于特定条件的数学模型。而林振智&文福拴(2009)通过研究电力系统输电过程的运行特点，提出了若干适合输电系统的运行策略，并将其运用于实践，促进了一些地区输电网络的更新与发展。

同时，研究者们也在尝试运用启发式算法来解决网络输运的相关问题。郎茂祥&胡思继(2002)将爬山算法与遗传算法相结合，构造了解决物流路径优化问题的混合遗传算法，在一定程度上启发了现实生活中的物流管理。沐士光(2010)基于电信网络的运行情况，运用改进的遗传算法，在充分节省优化费用的基础上降低了网络拓扑路径的总长度，并在网络的时效性与应用的智能性方面取得了一定的成果。

在管道输运问题方面，Dandy G C等(1996)通过研究水管网络的运行，找到了适合的效用函数，有效提升了纽约水管网的运行效率，引起了一定的社会反响。

但是，关于可压缩流的网络输送尚无系统的研究成果，因此本文尝试通过研究可压缩流的相关性质，提出系统解决这一问题的模型及算法，具有一定的理论与实用价值。

2 问题描述

以天然气网络输送为例。天然气的输送通常有若干条线路，每条线路上有若干个输气站，每个输气站有一定的天然气需求，用于维护输气站自身的正常运转以及售卖天然气给输气站周边的用户以获取一定利益。在输气时，起点输气站将一定量的天然气流装进管道，经过管道的输送到达相邻的下游输气站。下游输气站根据需求取用后将剩余天然气装进管道继续输送至下一个输气站。气流最终经过每一个输气站并由于各站点的取用持续减少，最终到达终点输气站，一次天然气输运就此结束。

在实际情况中，不同线路上的某些站点也有若干条支线相连接，因此形成了天然气输送网络。在网络中，每一段线路都对应两个参数，即单位成本与输气容量。单位成本指在该段线路上每输送一个单位天然气所需要付出的成本，输气容量指该段线路所能通过的最大天然气量。这两个参数决定了一定数量的天然气通过一段线路所需要付出的成本，而一次天然气输运所需要的总成本即为每段线路的输送成本之和。

显然，一次天然气输送的最优情况满足以下两个条件，即：

(1) 每个站点及周边用户的需求得到满足；

(2) 本次输送的总成本降到最低。

如果每一次天然气输送都能满足上述条件，那么从长期的角度来看，运营者可以节省的费用将十分可观，同时输气线路的效率也将显著提升。

将以上问题抽象化可以得到如图1所示的模型：

图1 天然气网络输送问题抽象模型

在模型中，Vs1-Vt1与Vs2-Vt2分别为两条输送线路，Vs1，Vs2分别为两条线路的起点，Vt1，Vt2分别为两条线路的终点。V1，V2，V3，V4是Vs1-Vt1线路上的中间节点(线路上仍有其他节点，仅列举一部分，下同)，V5，V6，V7，V8是Vs2-Vt2线路上的中间节点，不同线路上的若干节点间可以连通，箭头揭示了流运动的方向。每段线路上的参数为该段线路所对应的单位成本(括号中左边数值)以及输送容量(括号中右边数值)，每个节点上的参数为该节点的需求量。问题的目标就是以最小的费用输送满足所有节点需求量的可压缩流。

3 模型求解与策略分析

3.1 模型转化

运筹学已经解决了传统流的最小费用最大流问题，其具体模型如图2所示：

图2 传统流的最小费用最大流模型

在传统流的最小费用最大流模型中，Vs为线路的起点，Vt为线路的终点。V1，V2，V3，V4，V5是Vs-Vt线路上的中间节点，箭头揭示了流运动的方向。每段线路上的参数为该段线路所对应的单位成本(括号中左边数值)以及输送容量(括号中右边数值)。

显然，传统流的最小费用最大流模型与可压缩流的最小费用最大流模型有诸多不同，主要表现在：

(1) 传统模型只有一个起点和一个终点，而可压缩流模型有多个起点和多个终点；

(2) 传统模型的中间节点及终点均没有需求量，而可压缩流模型的中间节点及终点均有需求量。

以数学符号来表示，假设流量为F，对任一点Vi，其输出流量为SCvi，输入流量为SRvi，则

在传统网络流模型中，

在改进的网络流模型中，

因此，可压缩流的最小费用最大流模型并不能用传统流的最小费用最大流模型的解法直接求解。然而，由于可压缩流模型与传统模型仍有许多相似之处，如果能将可压缩流的最小费用最大流模型转化为传统流的最小费用最大流模型，则可以使用已有的解法求解。具体的转化过程如下：

(1) 新增一虚拟点Vs，并将该点用虚拟线路连接至所有的起点。同时，新增一虚拟点Vt，将所有的终点用虚拟线路连接至该点。在成本方面，所有新增虚拟线路的单位成本均视为0。在容量方面，Vs至各起点的容量视为无穷大，各终点到Vt的容量视为各终点的需求量。

(2) 将所有的中间节点用虚拟线路连接至Vt。在成本方面，所有新增虚拟线路的单位成本均视为0。在容量方面，各中间节点到Vt的容量视为各中间节点的需求量。

这样做的原因如下：

首先，可压缩流模型有多个起点和多个终点，经过以上处理后可以回归到一个起点和一个终点。在容量方面，Vs至各起点的容量视为无穷大，是因为不论最后从各起点输入多少流量，都必须得到满足，而Vs至各起点的线路实际上是不存在的，因此不可能限制容量。同样，各终点到Vt的容量也可以视为无穷大，但在实际情况中，由于流量流至终点时一般来说只剩下满足终点周边需求的量(终点不再传输流)，各终点到Vt的容量通常不会超过各终点的需求量(若超过需求量则所求的流并不是最小费用流)。因此，也可将各终点到Vt的容量视为各终点的需求量。

其次，对于中间节点，SCvi-SRvi=-需求量，稍加变形即可得到SCvi-SRvi+需求量=0，而右边为0满足传统模型。因此，只需将左边变为输出流量减去输入流量即可。实际上，观察式子左边可以得到SCvi-SRvi+需求量=SCvi+需求量-SRvi。也就是说，当输入流量为SRvi时，若输出流量为SCvi+需求量，则将满足传统模型。SCvi为原有的输出流量，因此考虑增加一条输出虚拟线路至某一点，其输出流量即为需求量，单位成本为0，这样就可以满足传统模型。此时我们可以观察到，所有终点连接至虚拟点Vt的线路的容量即为各终点的需求量，而将要新增的中间点到某一点的输出流量也为需求量，因此不妨将中间点接出的虚拟线路也连接到虚拟终点Vt，这样可以避免点的数量再增加。

在经过以上处理后，模型中所有节点的性质都与传统流的最小费用最大流模型无异，即可压缩流的最小费用最大流模型转化为了传统模型。

3.2 模型求解与策略分析

传统流的最小费用最大流模型可用多种方法求解，其中，贪心算法是效率较高的一种。贪心算法是一种求局部最优解的方法。在这一问题中，所有局部最优解的累积就成为全局最优解，因为这一问题属于特殊的最短路径问题，而最短路径问题的全局最优解即为所有局部最优解的累积。

贪心算法最重要的步骤是贪心策略的选择，只有选择正确而高效的贪心策略，才能够根据这一策略求局部最优解以及全局最优解。本问题的贪心策略是总选择起点到终点单位成本最低的路径，这是因为系统的总成本只与每一段路径的单位成本和流过这一段路径的流量有关，而一个流从起点流向终点时，无论流量大小，都需要流过路径上的每一段，因此贪心策略的主体就是每一段路径单位成本的总和，而其他因素不在考虑范围之内。

贪心算法的具体步骤如下：

(1)找到一条从起点到达终点的距离最短的路径，距离使用该路径上的边的单位费用之和来衡量，最短距离记为m(Vs,Vt)；

(2)然后找出这条路径上的边的容量的最小值b，则当前最大流增加b，同时当前最小费用增加b*m(Vs,Vt)；

(3)将这条路径上的每条正向边的容量都减少b，每条反向边的容量都增加b；

(4)重复以上步骤直到无法找到从源点到达汇点的路径。

由于在转化过程中，所有的中间节点和终点都被连接到一个虚拟终点Vt，所以算法开始时，从起点到终点的路径有许多条。通过以上的步骤，贪心算法每次找出一条路径，也就为一个节点找到了最小费用流。当所有节点的最小费用流都被找到时，根据贪心算法的性质，将所有的结果累加即为全局最优解，即整个系统的最小费用最大流。

4 案例分析

以某公司的天然气输送网络为例，该公司拥有两条输送线路，分别为线路A与线路B。线路A有18个输气站，从上游到下游分别编号为A1，A2，…，A18，线路B有24个输气站,从上游到下游分别编号为B1，B2，…，B24。同时，两条线路中都有若干站点与另一条线路的站点相连，天然气可在这些站点间双向流动，具体如下：

支线1：B1-A8

支线2：B20-A14

支线3：B22-A16

天然气输送网络的参数包含单位成本表(表1)、容量表(表2)以及需求量表(表3)(A18与B24为终点，不考虑输气单位成本；A1与B1为起点，不考虑需求量)。

根据以上数据，运用算法，可以得出从起点到每一点的满足需求的最小费用路径，如表4所示。

表1 某公司天然气输送网络线路单位成本(以每段线路起点为标志，单位：元/立方米)

表2 某公司天然气输送网络线路容量(以每段线路起点为标志，单位：万立方米)

表3 某公司天然气输送网络站点需求量(单位：万立方米)

表4 某公司天然气输送网络输送路径(以邻接方式表示)

表4中，某一点的上一站表示从起点到该点的最小费用路径中该点的上一站，而起点到上一站的最小费用路径与上一站到该站的直接路径结合即为起点到该站的最小费用路径。因此，结合起点到每一站点的最小费用流即可得到整个系统运行的最小费用最大流。

5 结论与展望

可压缩流是流的一种特殊形式。但是，在现实生活中，可压缩流却有十分广泛的应用。无论是河流、石油、天然气或其他物质，在以流的形式运动时都会具有一些可压缩流的性质与特征，因而可压缩流网络输送的模型与算法无疑具有极强的现实意义。本文通过对特定模型性质的研究，揭示了可压缩流网络输送的一般规律，并提出了较为高效的算法来解决这一问题，较好地达到了预期的目标。在某公司的案例中，运用该算法所得的成本比该公司目前运营的实际成本减少了15%左右，获得了明显的效果，而这一算法对现实生活中其他可压缩流的输送问题将提供较为可行的解决方案。

当然，这一模型也有许多改进的空间。例如，当线路的容量不能满足所有节点的需求量时，其结果将会产生一定的变化。同样，如果各站点之间具有优先级的不同，这一情况也将改变模型的设置，使得解决方案更为复杂。因此，算法本身仍可以持续改进，以适应不同的需求，相信未来的研究将使模型本身与算法都越来越完善。

[ 1 ] 孙华灿, 李旭宏, 陈大伟,等. 综合运输网络中合理路径优化模型[J]. 东南大学学报(自然科学版), 2008, 38(5):873-877.

[ 2 ] 林振智, 文福拴. 基于加权复杂网络模型的恢复路径优化方法[J]. 电力系统自动化, 2009, 33(6):11-15.

[ 3 ] 郎茂祥, 胡思继. 用混合遗传算法求解物流配送路径优化问题的研究[J]. 中国管理科学, 2002, 10(5):51-56.

[ 4 ] 沐士光. 遗传算法在网络优化问题中的研究与应用[J]. 计算机仿真, 2010, 27(5):128-131.

[ 5 ] 蒋洋. 多式联运服务网络优化建模方法研究[D]. 北京：北京交通大学, 2014.

[ 6 ] 张鹏程. 基于改进遗传算法的冷链物流路径优化研究[D]. 淮南：安徽理工大学, 2016.

[ 7 ] 许星. 物流配送路径优化问题的研究[D]. 杭州：浙江大学, 2006.

[ 8 ] BAIR E S. Applied Ggroundwater modeling—simulation of flow and advective transport[J]. Groundwater, 2016(54).

[ 9 ] DANDY G C, SIMPSON A R, MURPHY L J. An improved genetic algorithm for pipe network optimization[J]. Water Resources Research, 1996, 32(2):449-458.

[10] WANG N, HO K, PAVLOU G, et al. An overview of routing optimization for internet traffic engineering[J]. IEEE Communications Surveys & Tutorials, 2008, 10(1):36-56.

[11] YAN B, WANG Y, KILLOUGH J E. Beyond dual-porosity modeling for the simulation of complex flow mechanisms in shale reservoirs[J]. Computational Geosciences, 2016, 20(1):69-91.