Heuristics for Minimum Cost Steady-State Gas Transmission Networks

In this paper we propose and present two heuristics for the problem of minimizing fuel cost on steady-state gas transmission problems on looped networks. One of the procedures is based on a two-stage iterative procedure, where, in a given iteration, gas flow variables are fixed and optimal pressure variables are found via dynamic programming in the first stage. In the second stage, the 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. The other proposed heuristic adapts some concepts from generalized reduced gradient methods to attempt to find the direction step. This work focuses on looped network topologies, that is, networks with at least one cycle containing two or more compressor stations. These topologies possess the highest degree of difficulty in real-world problems.