keywords: Generalized minimum cost flow; Successive shortest path; Natural gas distribution networks.
We consider an extension of the minimum cost flow problem (MCFP) in a network where each edge (i,j) (arc or link) has a multiplier α(i,j). Such problems occur in network based systems where flow is not conserved on every edge. We consider this problem for the natural gas distribution networks with edges representing pipelines and compressors (multipliers) and nodes connects pipelines together or reroutes pipelines. First, we give an analysis of the problem in gas distribution networks from a graph point of view then provide a solution using an extension of the successive shortest path algorithm which is illustrated with a numerical example of interest consisting of 7 nodes, 9 pipelines and 2 compression stations with data chosen arbitrarily. Results indicated that flow is not conserved as gas flow at the sink node is reduced compared to that at the start node