Efficient operation of natural gas transmission systems: A network-based heuristic for cyclic structures

In this paper we propose a heuristic solution procedure for fuel cost minimization on gas transmission systems with a cyclic network topology, that is, networks with at least one cycle containing two or more compressor station arcs. Our heuristic solution methodology is based on a two-stage iterative procedure. In a particular iteration, at a first stage, gas flow variables are fixed and optimal pressure variables are found via dynamic programming. At a second stage, pressure variables are fixed and an attempt is made to find a set of flow variables that improve the objective function by exploiting the underlying network structure. Empirical evidence supports the effectiveness of the proposed procedure outperforming the best existing approach to the best of our knowledge.Scope and purposeGas transmission network problems differ from traditional network flow problems in some fundamental aspects. First, in addition to the flow variables for each arc, which in this case represent mass flow rates, a pressure variable is defined at every node. Second, besides the mass balance constraints, there exist two other types of constraints: (i) a nonlinear equality constraint on each pipe, which represents the relationship between the pressure drop and the flow; and (ii) a nonlinear non-convex set which represents the feasible operating limits for pressure and flow within each compressor station. The objective function is given by a nonlinear function of flow rates and pressures. In the real world, these type of instances are very large both in terms of the number of decision variables and the number of constraints, and very complex due to the presence of nonlinearity and non-convexity in both the set of feasible solutions and the objective function.