Minimizing fuel cost in gas transmission networks by dynamic programming and adaptive discretization

In this paper, the problem of computing optimal transportation plans for natural gas by means of compressor stations in pipeline networks is addressed. The non-linear (non-convex) mathematical model considers two types of continuous decision variables: mass flow rate along each arc, and gas pressure level at each node. The problem arises due to the presence of costs incurred when running compressors in order to keep the gas flowing through the system. Hence, the assignment of optimal values to flow and pressure variables such that the total fuel cost is minimized turns out to be essential to the gas industry. The first contribution from the paper is a solution method based on dynamic programming applied to a discretized version of the problem. By utilizing the concept of a tree decomposition, our approach can handle transmission networks of arbitrary structure, which makes it distinguished from previously suggested methods. The second contribution is a discretization scheme that keeps the computational effort low, even in instances where the running time is sensitive to the size of the mesh. Several computational experiments demonstrate that our methods are superior to a commercially available local optimizer.