به حداقل رساندن هزینه های سوخت در شبکه های انتقال گاز توسط برنامه ریزی پویا و گسسته تطبیقی

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.

Natural gas has become one of the most important energy resources worldwide. Consequently, the volumes of gas flowing from the fields through transmission networks to the market have been increasing steeply during the past decades, and in parallel, a growing interest in reducing costs associated with pipeline gas transportation has been observed. A gas transmission network is a system consisting of sources, pipelines, compressors and distribution centers. At the sources, a supply of gas received from external fields is refined, and transported via pipelines and compressors to the distribution centers. The distribution centers are the end points of the transmission network, and the gas finally received here is input to local distribution networks supporting households and other clients. The flow capacity of any pipeline increases with the inlet pressure and decreases with the outlet pressure of the pipeline. If no compressors are installed along a flow path, the pressure will be continuously decreasing. Since the pressure at the distribution centers typically is fixed, the flow capacity may therefore eventually become prohibitively small. To increase the pressure, and thereby the flow capacity, compressors are hence installed at the entry points of selected pipelines. Operation of the compressors incurs a cost depending on the flow and their inlet and outlet pressures. In this paper, the fuel cost minimization problem (FCMP) to transport natural gas in a general class of transmission networks is addressed. The FCMP involves two types of continuous decision variables: mass flow rate through each arc, and gas pressure level at each node. The problem is to determine a transportation plan minimizing the total fuel cost, while meeting a specified demand at the distribution centers. An extensive literature on the FCMP has been published over the past 30 years. Most of the suggested solution methods are limited to pipelines networks with acyclic structures, and in such instances, the suggested methods have shown a strong potential. In some of the more recent works, methods for cyclic networks have been developed. However, since these optimization approaches require a certain sparse network structure, their applicability is somewhat restricted. The following sections give a more detailed overview of the most relevant methods. A common assumption is that the system is in steady-state, which means that rapid changes in parameter values do not occur. 1.1. Methods based on dynamic programming By discretizing the range of the pressure variables, FCMP has in several works been formulated as a combinatorial problem that can be approached by dynamic programming (DP). Wong and Larson (1968) published the first work on optimization of pipeline transportation of natural gas by DP. They applied it to a gun-barrel (linear) network, that is a problem instance where the underlying network is a path, using a recursive formulation. A disadvantage was that the length and diameter of the pipeline segment were assumed to be constant because of limitations of DP. Martch and McCall (1972) modified the problem by adding branches to the pipeline segments and letting the length and diameter of the pipeline segments vary. However, since their problem formulation did not allow unbranched network, more complicated network systems could not be handled. The first attempt to solve instances with tree-shaped networks by DP was done by Zimmer (1975). A similar approach was described by Lall and Percell (1990). They allowed a divergent branch in their systems and included an integer decision variable into the model that represented the number of operating compressors in the stations. Carter (1998) developed an algorithm referred to as non-sequential DP. The principal idea of the method is to reduce the network by three basic reductions techniques until it consists of a single node. The method can handle a wide range of instances with cyclic networks, but fails if the networks are not sufficiently sparse. Based on this approach, Borraz-Sánchez and Ríos-Mercado, 2004 and Borraz-Sánchez and Ríos-Mercado, 2009 developed a hybrid meta-heuristic combining tabu search and non-sequential DP. The restriction that the networks must be sparse is however a shortcoming that the hybrid method inherits from the original paper. 1.2. Methods based on gradient techniques Percell and Ryan (1987) applied a generalized reduced gradient (GRG) method for solving FCMP. In comparison with DP, an advantage of GRG is that the rapid growth in instance size caused by many discretization points is avoided. Also, GRG is applicable to cyclic networks. Nonetheless, only a local optimum can be provided, of which instances of FCMP can have many, and the solution to be output depends on the choice of starting point. Flores-Villarreal and Ríos-Mercado (2003) extended the previous study by means of an extensive computational evaluation of the GRG method. 1.3. Other techniques and related problems Wu, Ríos-Mercado, Boyd, and Scott (2000) address the non-convex nature of FCMP, and suggest mathematical models that provide strong relaxations, and hence tight lower bounds on the minimum cost. Based on this model and the PhD thesis of Wu (1998), they demonstrated the existence of a unique solution to a non-linear algebraic equations system over a set of flow variables. This theoretical result lead to a technique for reducing the size of the original network without altering its mathematical structure. Villalobos-Morales, Cobos-Zaleta, Flores-Villarreal, Borraz-Sánchez, and Ríos-Mercado (2003) formulated a non-linear optimization model that also contains integer variables representing the number of compressor units inside a compressor station. Cobos-Zaleta and Ríos-Mercado (2002) extended this model, and suggested a solution technique based on outer approximation. 1.4. Contributions from the current work Several works have demonstrated that, at least in acyclic and sparse cyclic instances of FCMP, it is a promising approach to discretize the pressure variables, and apply DP to the resulting combinatorial problem. The purpose of this research is twofold: First, we demonstrate how such approaches can be applied to networks of arbitrary structure. Second, in order to keep the running time down in dense and cyclic instances, we propose a new scheme for discretizing the pressure variables. This scheme is adaptive in the sense that it avoids fine discretization of variables in area unlikely to contain good solutions, and intensifies discretization in more promising regions. The remainder of the paper is organized as follows: In the next section, we define the problem in mathematical terms. In Section 3, we present a contemporary solution method, and point out a simple instance where it fails. In Section 4, we show how the weakness of the method discussed in Section 3 can be overcome by our alternative method. Our adaptive discretization method is given in Section 5. Results from computational experiments are reported in Section 6, and concluding remarks are given in Section 7.

In this paper, we have studied a model (FCMP) for minimizing compressor fuel cost in transmission networks for natural gas. An arc in the network model corresponds to either a pipe or a compressor, and the decision variables are arc flow and node pressure. In addition to flow conservation constraints, the model contains non-linear constraints relating pipeline flow to inlet and outlet pressure, as well as non-convex constraints defining the operation domain of the compressors. Following a general algorithmic idea, which has been suggested and supported experimentally in several recent works, we consider a procedure where each iteration consists of a flow improvement step and a pressure optimization step. Alternating between flow and pressure, one set of decision variables is kept fixed in each step. Still in agreement with previously suggested methods, the non-convex subproblem of optimizing pressure is approximated by a combinatorial one. This is accomplished by discretization of the pressure variables. The contribution of this paper is a method for solving the discrete version of the problem in instances where previously suggested methods fail. Unlike methods based on successive network reductions, our method does not make any assumptions concerning the sparsity of the network. By constructing a tree decomposition of the network, and apply dynamic programming to it, we are able to solve the discrete version of the pressure optimization problem without enumerating the whole solution space. By an adaptive discretization scheme, we obtain significant speed-up of the dynamic programming approach in comparison with fixed discretization. We have tested our solution methods on a set of imaginary instances, and compared the results to those obtained by applying both a global and a local optimizer to the continuous version of the problem. The experiments indicate that a method guaranteeing the global optimum in reasonable time seems unrealistic even for small instances. Further, discretizing the pressure variables and applying dynamic programming to a tree decomposition gives better results than applying a commercially available local optimization package. Non-convex continuous optimization problems can in general be approached by discretization of the variable space, and in many cases, the resulting discrete problem can be solved by dynamic programming. The challenge of finding the ideal balance between accuracy in the discrete model and speed of the DP-algorithm is however hardly avoidable by the approach. We therefore believe that the adaptive discretization scheme developed in this paper may have merit beyond the specific application in gas transmission networks studied here.