Seongbae Kim
Institute of Information Technology, Inc.
The Woodlands, USA
E. Andrew Boyd
PROS Revenue Management
Houston, USA
Abstract: Gas 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 non-linearity and non-convexity in both the set of feasible solutions and the objective function.
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 effectiviness of the proposed procedure.