1、启发式方法的混合天然气管道网络优化摘要：在本文中，有循环网络拓扑结构的天然气输送系统也就是说，至少有一个周期包含两个或更多的网络压缩机站弧线，我们为其的成本最小化提出一个混合燃料启发式求解过程。我们的启发式求解方法是基于两阶段的迭代过程。在一个特定的迭代，在第一阶段，气体流量的变量在每个网络弧中是固定的并且最优压力变量在每个网络节点通过非连续的动态规划被发现。在第二阶段，压力变量是固定的，短期记忆tabu搜索程序是用来指导搜索流量变量空间。实证证据表明程序建议的结果优于现有的我们知道的最好的方法。关键词：稳态，天然气，传输网络，非凸问题，动态规划，tabu搜索。1 介绍在本文中，我们处理发生在
2、天然气长输管道系统压缩机站的燃料消耗最小化问题。在天然气输送过程中，由于天然气和管道内壁直接的摩擦以及天然气和周围环境直接的热传递，天然气的能量和压力都降低了。为了使气体能在持续流过系统，有必要定期增加它的压力，所以在整个网络中安装压缩机站。据估计，压缩机站通常消耗输送天然气的3%至5%,这个运输成本是重要的，因为天然气的数量在大型运输系统中是巨大的。另一方面，即使在天然气业务方面有轻微的改善从经济角度看也能够产生重大的积极影响，所以这实际上提供了我们进行本工作的主要动机。这个问题表示为一个弧对应于管道压缩机站和节点对应的物理互连点的网络。我们考虑两种类型的连续决策变量：通过每个弧的质量流率，
3、和在每个节点的天然气压力等级。因此,从优化的角度来看,这个问题被建模为一个非线性程序(NLP), 其目标函数是典型的非线性和非凸, 是典型的非凸约束集。众所周知非凸NLP是NP-hard6，这激励我们选择提出了启发性算法。该研究的额最新动态揭示了几个重要事实，首先，有 2 各基本类型的网络拓扑结构，非循环和循环。我们想强调下，前者是一个类型的拓扑结构，在过去的 30 年已取得了大部分的关注。几种解决方法已被发现，其中大多数是基于动态规划（DP ），其中重点是非循环网络。特别是，对于处理循环拓扑结构而言，梯度搜索和DP的方法在应用上成功的很少或很有限。前者的主要限制是其局部最优状态，后者的主要缺
4、点是，它在流量变化是固定的问题应用受限制，所以最终也是最佳的解决方法是预先制定一个流量变化集合，这是因为循环拖布很多难以解决。在本论文中，我们提出了一种新的求解方法来解决如何优化操作天然气管网系统中的压缩机站这个问题，重点在循环拓扑。此技术结合了一个在 tabu 框架中的非连续的 DP 技术（最初是由卡特提出2）。在过去的十二年中，建立了自己的立场的 TS 作为一种有效的元启发式指导在若干不同领域优化问题的设计和算法实现的解决方案的组合(Glover and Laguna5)。这一成功的关键原因是，该算法具有充分的灵活性，允许设计者在选择参数和子算法时利用原来的领域知识。在这种情况下，即使我们
5、面对的是不断优化问题，目标函数的高非凸性和解决局部最优的 TS 的高通用性，使 TS 有一个非常有吸引力的提出一个合适的离散的解决方案的空间。广泛的采取自行业内的数据经验证据表明了该方法的有效性。一个与以前方法的基于GRG和最先进的卡特DP技术的比较表明了我们的程序的显著的优越性。此外，为了评估我们提供的解决方案的质量，一个下限过程被推导，结果表明我们的技术差距与最优发现小于16%，其中大部分小于10%，这是一个重要的进展，是当前领域的先进水平，这项工作的科学贡献是提供了最好的科学技术，到现在为止，我们所知道的最好的，解决循环拓扑中的这类问题的。本文的其余部分组织如下：本文的其余部分组织如下。
6、在第二节中，我们正式介绍燃料消耗最小化问题（FCMP） ，描述其主要特点，模型假设，以及重要的属性。然后，在第3节中，我们提出一个对于这个问题较早的方法的检讨，强调其与我们工作的联系，以及我们如何试图利用其中的一些。在第4节对建议的方法提供了详细的介绍。一个启发式泛运算的评价，包括与早期方法的比较，则在第5节。最后我们在第6节用一个结论和未来的研究方向结束这一工作。2 问题描述管道系统模型主要可分为稳态和瞬态系统，这两者之间的区别如下。通过管道的流体力学受一个偏微分方程约束，这个偏微分方程则与时间衍生物有关。根据稳定状态的假定，有可能制定出这个方程，并简化为一个非线性和无导数的方程。从优化的方
7、面看这使得问题更加容易处理。像所有一切的工作（在第3节回顾） ，这里我们假设了一个稳定的状态模型。也就是说，我们的模型给已经运作了较长一段时间的系统提供了一个解决方案，这是一种在工业上常见的做法。瞬态分析基本上是由描述性模型做完的。因此对于瞬态系统优化仍然成为这个伟大研究在这一领域的挑战之一。我们还假设我们的工作用确定性模型，即每个参数已知的确定性，这是一个非常合理的假设。在压缩站而言，我们假设我们用离心压缩机组，这最常见于工业。至于网络模型而言，我们假设网络是平衡的，即无气损失，每个网络中的弧采用了预先指定的方向。2.1 模型这个模型最初是由吴等人制作的19。集V:网络中所有节点的集合Vs：
8、供应节点的集合(V s V )Vd：需求节点的集合(V d V )Ap：管道弧的集合Ac：压缩站弧的集合A：网络中所有弧的集合；A=ApAc参数Uij：管道(i, j)容量弧；(i, j) ApRij：管道(i, j)阻力；(i, j) ApPiL,PiU：每个节点限制的最低压和最高压；iVBi：节点i的净流量；i V，Bi0，if iVs，Bi0，if iVd，Bi=0 ， 否则变量xij：弧(i, j) 的质量流量；(i, j) Api：节点i的压力；iV公式（1）cAj)(i, ),jijipxg最简化 （2）Bijjji ),(,约束 （3）UPA,（4）22ijjixRpji V （
9、5）iLi,（6）ijjijDx),( cj,（7）0,ijpiAji,目标函数（1）代表了在系统中的燃料消耗总量。约束（2）-（3）是较典型的代表了节点质量平衡和弧的能力的网络节点约束，分别为，约束（4）代表了每个稳态假设下的管道的气体流动动力学，约束（5）代表了限制在每个节点的压力。这些限制由压缩机的物理特性确定。约束（六）代表非凸可行的计算压缩机站（i，j）域D ij。最后，数学模型的有界以非负的变量（7）决定。该Dij的代数表示是基于从压缩机采取的经验数据的曲线拟合方法的结果。用于测量燃料消耗，我们使用给定的格式如下的函数：， 1),(mijijjij pxpxgijjijDpx),(
10、其中 和 M 是假设常数（和已知的）依赖天然气物理性质的参数。一个更详细和自然的关于压缩机站域和燃料消耗函数的研究已经给出了19。3.先前的工作在本节中，我们回顾过去30年中对解决FCMP最终要的帮助。3.1 基于动态规划的方法DP的主要好处是全局最优一定会发现且非线性很容易处理，与此相反，其应用只限于飞循环网络，而线性（也称gun-barrel）或树拓扑结构该计算增加了问题的维数指数，通常被称为维数灾难。DP管道优化最初在1960年代晚期应用于gun-barrel系统。由于其运算行为和处理非线性顺序系统的多功能性，它一直是最好的方法之一。DP在1968年首次由黄和拉森应用于线性系统是16，并
11、应用于他们的树状拓扑结构。一个类似的方法被Lall和Percell描述与1990年17,他们允许了们的系统中的一个分支。循环网络上最重要的工作归功于卡特2，他开发了一种非连续的DP算法，但仅限于一组固定的流量。在我们的工作中，我们运用卡特的想法，并将其整合进为反复调整流量的Tabu搜索方案内大获成功。这将在第4节做进一步阐述。3.2 基于梯度搜索方法1987年，Percell和瑞安11基于广义简约梯度（GRG）为非循环结构的非线性优化技术应用了不同的方法。对比DP,GRG的优点之一是他们可以相对较好的处理维数问题，因此，可用于循环结构。然而，作为一个以梯度搜索为基础的方法，它不一定有全局最优方
12、案，尤其是当决策变量是离散时。Villalobos-Morales和Ros-Mercado15评估GRG预处理技术，如缩放可变范围，并选择能为循环和非循环结构得到一个更好的结果的开始方案。更近些时候，Flores-Villarreal和Ros-Mercado4进行的一个广泛的GRG计算评估套用了大量的实例循环结构并取得相对成功。这项工作没有和DP比较，所以这是我们贡献的一部分，提供了一个比较框架在卡特的NDP，GRG，并且我们的方法测试了同样的实例。3.3 其他方法吴，博伊德，斯科特18提出了一个只有一个压缩机站单位燃料成本最小化的数学模型。这是第一部作品，充分定义了离心压缩机的数学描述。后来
13、，吴等人19完成了同样的问题的分析，但考虑了压缩站几个单元。在一个相关的工作，一些关于管网的最重要的理论特性被Ros- Mercado等开发13。在这个问题的变化上，Cobos-Zaleta和Ros- Mercado3最近提出一个技术解决方案。即基于外部的一个近似的平等放松和充实的理想的OA/RA/EP求解混合整数非线性编程模型成立，其中一个整数决策变量，代表每个站运行的压缩机组数量。他们展示了令人满意的结果，因为他们在许多情况下测试均能找到局部最优。优化技术也被用于瞬态（依时间变化）模型应用（例如Osiadacz8，Osiadacz和Swierczewski10）和网络设计（例如Osiada
14、cz和Gorecki9），并取得有限成功。看Ros-Mercado12为应用于天然气管道优化技术问题提供更多参考。重要的是要提到优化方法迄今发展的工作所需要的一般假设，然而，由于问题变得更加复杂，从优化角度谈及进一步研究和算法的有效发展更有必要。4.解法基本上，建议的方法包括四个部分：(一)预处理：这一阶段是通过收缩决策变量范围给定完善可行的计算域来进行的，并减少网络的大小通过缩减技术（出于R os-Mercado等的工作13）；（二）找到一个初始可行的流量：在这个阶段，一个可行流量的发现有两种不同的方法，经典赋值方法和降低任务图算法；（三）找到一个最优的组压力值：在这一阶段，应用非连续DP（
15、NDP）算法发现最佳压力集（预定义流前一个阶段）；（四）流量修改：在这里，试用Tabu搜索框架找出一组不同的流量。所以程序的核心思想是执行元件（三）和（四）迭代直到满足一个停止准则。正如我们所知，从管网的理论特性来说13,步骤（四）用于非循环拓扑是不必要的，因为存在一组独特的最佳流量，可以在事前确定预处理值。所以，我们这里专注于循环拓扑。为了在第（三）阶段发现最佳压力，我们实行激发自卡特的NDP技术，整体过程被称为NTDPS。在以前的工作里，步骤（一）、（二）、（三）是相当有据可查的，所以在本节的提醒，我们假设我们有一个初始可行流量，并提供组件的说明（四），这是建议工作的核心。4.1 整体过程
16、简单的说，我们开始程序，通过NDP算法找到一个初始流量可行集，然后生成x的邻居列表，Vx。我们在一个属于循环的选择弧内取了一个质量流量并且通过增加或减少其值x组来修改它。请注意，一旦这个值设立，弧中其他的流量变量就很容易确定，所以，从这个意义上说，正是这个质量流量成为属性。那么选择最好的x属于非Tabu的Vx而相应的子集更新。重复这种局部搜索和选择最好的非Tabu邻居的过程直到满足终止准则为止。4.2 Tabu搜索建议我们定义一个可行性解决方案的本质是基于直接与网络拓扑相关的循环的三个基本组成部分：（一）静态组件：质量流量率值不属于任何周期；（二）变量元件：质量流量率值属于一个周期；（三）搜索
17、组件：在网络中的所以压力变量。TS的搜索空间被流量变量定义因为一旦变化率固定，通过NDP能发现最佳的压力变量。此外，我们不需要处理整组流量变量，但每组一个。这是因为你在一个周期内修复流量，其余的流量都可以唯一确定。因此，一个向量x=(x1 , . . . , xm)代表一个给定的状态，其中 xm是一个属于循环w的弧。现在，简单讨论下NDPTS的组件。1. 初始解生成：要生成一个初步的解决方案，我们使用一个两阶段的程序。首先，找到一个可行流量组，然后用NDP算法发现一个最优压力集（对应流量组）1。图 2 循环拓扑的一个可行解决方案的基本组成部分2. 邻域V x：让我们确定一个给定方案x的邻域V
18、x，通过稍微修改 x即可达到。（8）2/,321,NsizejxRv这里Nsize的大小是预定义的邻域大小。注意，对于一个给定的解决方案，我们不储存整个解决方案，但只有在选定的弧流进行修改。3. Tabu列表：Tabu列表用来保持在过去的迭代中创建了最优方案的属性，使他们不能用于创建新的解决方案。对着迭代反复进行，一个新的属性值进入TL,而最老的那个属性值，如果超出了TL的大小，将被释放。特别是，TL的大小是TS的控制参数，提供好的解决方案的TL的大小通常随着V x大小增长。4. 终止条件：搜索在iter的最大迭代后终止，这是一个用户指定参数。5.实证评价拟议的TS的开发是在C +上，运行在S
19、olaris7的Sun Ultra10工作站上。所有压缩机有关的数据被Villalobos-Morales等描述，并由一个管道行业资讯公司提供，为了Tabu列表和其邻域的大小，我们分别使用值5 8 10 和20 30 40做了几个preliminar实验。由于篇幅所限微调实验和测试实例的完整描述请找作者。在微调实验的preliminar计算中，我们发现以下算法参数给力最好的结果。- 迭代极限（ITER的最大值=100） 。- V（X） 的离散大小（x= 5）-压力变量的离散大小（压差p= 20）-Tabu列表大小（Ttenure=8） ，-邻域大小（n大小= 20）为了简要评价程序的有效性，我
20、们应用算法解决不同的循环下的网络拓扑结构在同一平台上的多个实例。为此，我们进行了两项实验。在实验中，我们提出一个我们程序和实际中迄今已知的最好的GRG之间的比较。实验B中我们与卡特NDP的方法进行了比较，该方法代表了迄今已知的最好DP。5.1 对比分析1：NDPTS vs GRG表1显示了GRG与NDPTS之间的循环网络的比较。对于GRG，我们用了在4中的执行情况。第一列显示的实际测试。这里ncm后缀表示该实例有n个节点和m各压缩机站。第二第三列显示GRG和NDPTS解决方案，最后一栏显示了NSPTS对于GRG的改善。首先，NDPTS 能够提供解决方案的所有实例测试，而GRG这五个失败。结果表
21、明，NDPTS 过程中优于 GRG上解的质量。在计算工作量方面，GRG运行，在不到2秒。而NDPTS 运行在一个 270-400秒之间。5.2 对比分析1：NDPTS vs NDP现在，我们提出一个比较分析显示了对比简单的NDP算法应用NDPTS 后取得的进步。与GRG相比，卡特算法是当前领域内最先进的。在表2中，第一列显示了实际测试，第二列给出了NDP的解决方案，第三列给出了发现最佳值的NDPTS,最后一列是 NDPTS相对NDP改善的百分比。可以看出，NDPTS相对NDP的改善，11个测试实例中有6个大于了10%，2个大鱼8%，只有1个的改善低于1%。NDP的运行实际不到20秒。5.3 下
22、限比较为了用该算法评估交付的解决方案的质量必须得到一个下限。现在，为了一个非凸问题产生下限可能非常艰巨，而去的一个凸封套可能像原来问题一样困难。然而，为了这个问题，我们注意到带领我们进入一个近似下限的两个事实。首先，通过在模型FCMP中解放约束问题使每个压缩站分开。现在，这仍是一个非凸问题，但是，我们利用的是，在一个压缩机中，目标是一个仅有三个变量的函数，所以我们建立了这个函数的一个三维网格，并轻松找到了被分开的问题的全局最佳(对于一个指定的离散)。表3显示了这些结果，第一列是实例测试，第二和第三分别显示了下限和启发式算法提出的最佳值。最后一列显示了相对NDPTS的优化差距。从表中可见，所以被
23、测实例的相对优化差距的相对最优都小于17%，11个中表 3：NDP 和 NDPTS 之间的比较有 7 的相对差距小于 10%并且他们中的 3 个优化相对差距小于 1%，这显示了该方法的成效。最后，虽然我们的 NDPTS 算法找到了比 GRG 和简单 NDP 更优的解决方案，但它更昂贵。一般而言，很容易证明能导致哪怕小的改进都需要很多额外的时间，这是因为天然气运输成本先对巨大。6.结论在这项工作中，我们针对天然气管道工业中出现的难题提出了一个基于NDP 和 TS 的混合元启发式解决方法。NDPTS 的实施主要基于小项目记忆策略。在实验工作中非常成功，因为它能够比以前那些方法提供更好的解决方案。这
24、代表，我们的知识是这个领域内的一个先进重大的贡献。即将进行的研究仍然有许多领域适用。建议的过程是一个基于短期记忆的Tabu 搜索。这将是一个集合了先进和多样化的 TS 策略。此外，从优化角度看一个在伟大的同行业内的挑战是解决时间依赖系统。致谢：这项研究得到了墨西哥科学与技术全国理事会（CONACYT grant J33187-A）和Autonoma de Nuevo Le大学的科学技术研究项目支持（UANLPAICYT grant CA820-04）。我们还有感谢两位帮助改善摘要的不知名的编辑。References1. C. Borraz-S anchez and R. Z. R os-Mer
25、cado. A non-sequential dynamic programming approach for natural gas network optimization. WSEAS Transactions on Systems, 3(4):13841389, 2004.2. R. G. Carter. Pipeline optimization: Dynamic programming after 30 years. In Proceedingsof the 30th PSIG Annual Meeting, Denver, October 1998.3. D. Cobos-Zal
26、eta and R. Z. R os-Mercado. AMINLP model for minimizing fuel consumption on natural gas pipeline networks. In Proceedings of the XI Latin-Ibero-American Conference on Operations Research, Concepci on, Chile, October 2002.4. H. J. Flores-Villarreal and R. Z. R os-Mercado. Computational experience wit
27、h a GRG method for minimizing fuel consumption on cyclic natural gas networks. In N. E. Mastorakis, I. A. Stathopulos, C. Manikopoulos, G. E. Antoniou, V. M. Mladenov, and I. F.Gonos, editors, Computational Methods in Circuits and Systems Applications, pages 9094.WSEAS Press, Athens, Greece, 2003.5.
28、 F. Glover and M. Laguna. Tabu Search. Kluwer, Boston, 1997.6. R. Horst, P. M. Pardalos, and N. V. Thoai. Introduction to Global Optimization.Kluwer Academic Publishers, Dordrecht, The Netherlands, 1995.7. H. S. Lall and P. B. Percell. A dynamic programming based gas pipeline optimizer. In A. Bensou
29、ssan and J. L. Lions, editors, Analysis and Optimization of Systems, volume 144 of Lecture Notes in Control and Information Sciences, pages 123132, Berlin, 1990. Springer-Ver lag.8. A. J. Osiadacz. Dynamic optimization of high pressure gas networks using hierarchical systems theory. In Proceedings o
30、f the 26th PSIG Annual Meeting, San Diego, October 1994.9. A. J. Osiadacz and M. G orecki. Optimization of pipe sizes for distribution gas network design. In Proceedings of the 27th PSIG Annual Meeting, Albuquerque, October 1995.10. A. J. Osiadacz and S. Swierczewski. Optimal control of gas transportation systems. In Proceedings of the 3rd IEEE Conference on Control Applications, pages 795796, August 1994.
