مدل تسهیلات برای به حداقل رساندن هزینه سوخت شبکه های حالت پایدار خط لوله گاز

Natural gas, driven by pressure, is transported through pipeline network systems. As the gas flows through the network, energy and pressure are lost due to both friction between the gas and the pipes' inner wall, and heat transfer between the gas and its environment. The lost energy of the gas is periodically restored at the compressor stations which are installed in the network. These compressor stations typically consume about 3–5% of the transported gas. This transportation cost is significant because the amount of gas being transported worldwide is huge. These facts make the problem of how to optimally operate the compressors driving the gas in a pipeline network important. In this paper, we address the problem of minimizing the fuel cost incurred by the compressor stations driving the gas in a transmission network under steady-state assumptions. In particular, the decision variables include pressure drops at each node of the network, mass flow rate at each pipeline leg, and the number of units operating within each compressor station. We present a mathematical model of this problem and an in-depth study of the underlying mathematical structure of the compressor stations. Then, based on this study, we propose two model relaxations (one in the compressor domain and another in the fuel cost function) and derive a lower bounding scheme. We also present empirical evidence that shows the effectiveness of the lower bounding scheme. For the small problems, where we were able to find optimal solutions, the proposed lower bound yields a relative optimality gap of around 15–20%. For a larger, more complex instance, it was not possible to find optimal solutions, but we were able to compute lower and upper bounds, finding a large relative gap between the two. We show this wide gap is mainly due to the presence of nonconvexity in the set of feasible solutions, since the proposed relaxations do a very good job of approximating the problem within each individual compressor station. We emphasize that this is, to the best of our knowledge, the first time such a procedure (lower bound) has been proposed in over 30 years of research in the natural gas pipeline area

Natural gas, driven by pressure, is transported through a pipeline network system. As the gas flows through the network, pressure (and energy) is lost due to both friction between the gas and the pipe inner wall, and heat transfer between the gas and its environment. To overcome this loss of energy and keep the gas moving, compressor stations are installed in the network, which consume part of the transported gas resulting in a fuel consumption cost. Principal concerns with both designing and operating a gas pipeline network are maximizing throughput and minimizing fuel cost. Numerical simulations based on either steady-state or transient models of the networks have been used to attempt to provide solutions to these problems. The problem we address in this paper is minimizing fuel cost for steady-state gas pipeline networks. As the gas industry has developed, gas pipeline networks have evolved over decades into very large and complex systems. A typical network today might consist of thousands of pipes, dozens of stations, and many other devices, such as valves and regulators. Inside each station, there can be several groups of compressor units of various vintages that were installed as the capacity of the system expanded. Such a network may transport thousands of MMCFD (1 MMCFD = 10’ cubic feet per day) of gas, of which 335% is used by the compressor stations to move the gas. It is estimated [ 11 that the global optimization of operations can save at least 20% of the fuel consumed by the stations. Hence, the problem of minimizing fuel cost is of tremendous importance. With the aid of today’s powerful digital computers, numerical simulation of gas pipeline networks can be very accurate. This opens the door to the development of optimization algorithms. Over the years, many researchers have attempted this with varying degrees of success. The difficulties of such optimization problems come from several aspects. First, compressor stations are very sophisticated entities themselves. They might consist of a few dozen compressor units with different configurations and characteristics. Each unit could be turned on or off, and its behavior is nonlinear. Second, the set of constraints that define feasible operating conditions in the compressors along with the constraints in the pipes constitute a very complex system of nonlinear constraints. Surfing on such a manifold to attempt to find global optimal solutions demands an in-depth understanding of its structure. Finally, operations of the valves and regulators may introduce certain discontinuities to the problems as well. The purpose of this paper is first to provide an in-depth study of the underlying mathematical structure of the compressor stations. Then, based on this study, we present a mathematical model of the fuel cost minimization problem, and derive a lower bounding scheme based on the following two model relaxations: (i) relaxation of the fuel cost objective function; and (ii) relaxation of the nonconvex nonlinear compressor domain. Finally, we present empirical evidence that shows the quality of the proposed relaxations. The results are promising. For the small instances, where we were able to find both optimal solutions for the original problem (upper bound), and for the relaxed problem (lower bound) by all exhaustive approach, we found that the proposed relaxations yielded a relative optimality gap of around 15-20%. We also tested the procedure in a larger, more complex instance. For this instance, it was not possible to find optimal solutions, but it was still possible to calculate lower and upper bounds. We found that the proposed relaxations were in fact doing a good job of approximating the cost function within each individual compressor station. However. when optimizing over the complete domain (including all compressors at once, and other system constraints), the overall bound was not good due mainly to the nonconvexity of t,he set of feasible solut,ions and to the presence of multiple local optima in the fuel cost function ~1. We would like to emphasize that, to the best of our knowledge, this is the first time such a proc,edure (lower bound) has been proposed in over thirty years of research in the field of natural gas pipelines. The rest of the paper is organized as follows. In Section 2, we highlight the most relevant work related t,o optimal operation on steady-state gas transmission networks. The compressor unit and stat.ion models we have developed are presented in Section 3. In Section 4, we formally introduce the fuel cost minimization problem and present several relaxations that allows us to devise a lowt~r bounding scheme. These procedures have been tested with a few numerical examples in Section 5. We end the paper in Section 6 with our conclusions and directions for future work. 2. RELATED WORK Numerical simulations of gas pipeline networks have been carried out through this century and results can now be very accurate, especially with the aid of powerful digital computers. Osiadacz’s book [2] stands as the best reference on this subject. The earlier work on developing optimizat,ion algorithms for fuel cost minimizat,ion in steadyst, at,a gas transmission networks can be traced back to Wang and Larson’s work [3] in 1968, which made use of d.vnamic programming (DP) techniques to solve problems with simple “gunbarrel” network structures. More recently, La11 and Percell [4] p. resented a DP algorithm that handles topologies with diverging branches, and incorporates into the model decision variables for representing the number of units to be operated within each compressor station. More recently, Carter [5] developed a nonsequential DP algorithm to handle looped networks when the mass flow rate variables are fixed. The rnain advantages of DP are that a global optimum is guaranteed to be found and that nonlinearity can be easily handled. Disadvantages of DP are that its application is practically limited to the networks with simple structures, such as “gun-barrel” 01 t,rec topologies, and that computation increases exponentially in the dimension of the problem. c~ommonly referred as t/be curse of dimension&y. Kim et al. [C;] extended Carter’s approach by proposing an approximation algorithm that iteratively acljusts the flow variables in a heuristic way. Percell and Ryan [7] addressed the problem by using the generalized reduced gradient (GRG) for nonlinear optimization. Advantages of the GRG method are that it avoids the dimensionality problem and that it may be applied to networks with loops. However, since the GRG method was based on a gradient search method, it is not theoretically guaranteed to find a global optimum, especially in the presence of discrete decision variables, and it may stall at local minima. In [a]: Wu et al. presented a mathematical model for the fuel cost minimization over a single unit, compressor station. Some of the properties studied in that paper have been extended heir to handle stations with mult,iple compressor units. Optimization techniques have also been applied for transient (time dependent) models (e.g.: [!),lO]) and network design (e.g., [II]) with modest success. (See [la] for more references on optimization techniques applied to gas pipeline problems.) It is important to mention that optimization approaches developed to da.te work well under some general assumptions; however, as the problems become more compiex, the need arises for further research and effective development of algorithms from the optimization perspective.

We have presented a study of the mathematical structure of compressor stations iu natural gas tra.nsmission networks. We have analyzed several important properties of both the set of feasible operating conditions and the associated cost function. The fuel cost minimization model has been presented. U’e have highlighted why this problem is difficult to solve (namely the nonlinearity, nonconvexity, and discontinuity in the objective function, and the nonconvexity of the feasible set). We have proposed and derived two model relaxations that allowed us to develop a lower bounding scheme. One relaxation consisted of developing linear supersets D of the feasible domains D. The other is the derivation of piecewise linear underestimator functions s of the minimum fuel cost functions CJ for the c-ornpressor stations. The proposed procedures have been tested on three test examples made from real-world data. For the first two examples, we have found lower bounds with relative gaps of 23% and 1570, respectively. These gaps were with respect to optimal solutions of the problems. The results fox the small problems show that the proposed relaxations are in fact, good. For the third example, the relative gap was very wide. We observed that the convex underestimator function was indeed a very good approximation to the function within each of the compressor stations. However, when optimizing over the complete domain, the overall bound was not good due mainly to the nonconvexity of the set of feasible solutions and to the presence of multiple local opt.ima in the fuel cost function g. As is well known, techniques for finding global optimal solutions to nonconvex problems, such as branch and bound, rely heavily on the capacity of generatin, u bu ood lower bounds. Furthel research in this area is needed for handling larger instances more effectively. A transient, or time dependent, model is another important problem that to date has not been aclequat,ely addressed from the optimization perspective. We should also mention the need for having a library of data sets that would allow more uniform algorit,hm testing and benchmarking among researchers and practitioners working in t.his area.