Optimization

1л optimization problems, the search for the optimal solution is done by iteratively transferring the current solution to a newer and hopefully better solution. Optimization methods can usually overcome numerical simulation approaches because of two main limitations. First, there is no guarantee from simulation ^aPproaches that the achieved result is optimal (or cost is minimal). Second, deter­mining pipe diameters depends only on the experience of users. Therefore, for the same problem, different users always take different decisions, which is not of ^lnterest [8].

Pf discharge pressure press

/: pipelines и: units Sa: set of arcs

^ typical pipeline network for delivering natural gas requires a vast number of facilities and limitations, which should be considered. Because of the complex ^nature of the natural gas pipeline network, problems defined in this scope seek
different aims and methods that certain requirements have to be considered in their optimization methodologies to achieve satisfactory and robust enough solutions to cover the most important aspects of the network. In such complex and huge net­works, proper planning for transmission and distribution networks has a special importance because even a small reduction in operation expenses and investment costs can include considerable amounts of money and improvements in the system utilization, which is more valuable in gas-rich countries. Growing natural gas net­works, make them more complex, and from the optimization perspective, develop­ing effective algorithms becomes more important.

Network Optimization

According to Osiadacz [19], network optimization means finding a certain objec­tive function in such a way that design parameters, development structures, and parameters of the network operation are optimum. In the last two decades, so many researchers in the natural gas area have paid attention to optimization methods to find the optimal solution in various fields of the natural gas industry. Depending on which decisions are going to be made and what are the variables that are sought to make optimum objective function, all optimization problems defined in this field can be decomposed into four groups: optimal design, optimal flow, optimal opera­tion, and optimal expansion.

Network Design

Network design decisions are key strategic decisions, and the consequences of mak­ing these decisions poorly are often severe [10]. The network design problem occurs in many diverse application areas, including facility location, material-handling sys­tems, natural gas or electric power transportation, and telecommunications.

In the optimal design of a natural gas network, the main design parameters of basic components of the network including pipelines and compressor stations are provided over a planning horizon in such a way that considering the network constraints the customers are satisfied with a minimum annualized cost [11,12]. Outputs of the system will be the design characteristics of pipelines, including diameters, pressures, and flow rates, and such design parameters of compressor sta­tions as location, suction pressure, pressure ratio, station throughput, fuel consump­tion, and station power consumption. Each parameter and characteristic influences the overall construction and operating cost to some degree [12].

Mohitpour et al. [13] defined and explained the major influencing factors on pipeline system design: properties of fluid, design conditions, magnitude or loca­tions of demand and supply nodes, codes and standards, route, topography, access, environmental impacts, financial matters, hydrological impacts, seismic and volca­nic impacts, material, construction, operation, protection, and long-term integrity.

Network Flow

The main objective of network flow optimization in the natural gas and other industries is minimizing costs and providing sufficient services to customers, which j_S close to operational decisions. In this type of problem, decision variables are defined to determine the volume of gas flowing through the network. Many of the network flow's problems such as minimum cost flow problems, shortest path pro­blems, maximum flow problems, and transmission network planning can be mod­eled as different forms of mathematical programming with linear or nonlinear functions and integer or mixed-integer variables.

To date, many models have been developed to describe the gas flow though the network as well, but there are several difficulties to find the suitable solution for the developed models because of their nonlinear and nonconvex nature [3].

By making use of the introduced notations, the general form of network flow model, taken from Ahuja et al. 114], can be presented as follows:

Minimize

]T CjjXy (19.1)

VJ)eN subject to

E ч E */<=«'• (^,9-²>

{/:(/, J)eN) \j:(jJ)eN\

0 < Xjj <Pjj ViJeN (19.3)

Set of the first constraints (Eqn (19.2)) is mass balance constraints, and set of the second constraints (Eqn (19.3)) presents the capacity boundaries for gas flowing between the /th and yth nodes.

Network Operation

Some operational decisions should be taken into account for the network to ensure that the demand for natural gas is met. At high pressures of natural gas, the opera­tion cost of the network is determined based on the operation of compressors because of the significant percentage of running costs of compressor stations in the total budget of companies. In low and medium pressures, an optimal operational cost is achieved through leakage reduction by optimizing the nodal pressures [9]. hi general, the operating cost belonging to the natural gas network normally takes ^UP more than 60% of the total cost of the pipeline [5]. Therefore, operational deci­sions have a significant effect on the network performances. Given the fact that the amount of natural gas in the pipeline system is set by compressor stations and that the cost associated with the operation of compressor stations, including turning them on and off, the most critical operational decision in a natural gas network is electing compressors. This important decision, which is influenced by the com­pressors' capacity and the energy required to turn the compressor units on and off, ^S|gnificantly affects total natural gas operation cost. Another critical factor on the Performance of the natural gas network is starting or stopping compressors because ^of their different outputs [5]. Therefore, efficient operation of the complex networks of natural gas can substantially reduce airborne emissions, increase safety, and decrease the daily operating cost [3].

Network Expansion

In today's competitive markets, natural gas companies are interested in expanding the network and consequently serving potential customers because their market shares will be larger and the achieved profits will increase. In network expansion, generally the objective is scheduling the investments to supply an economic and reliable energy with minimal cost, which is not easy to achieve [15]. To make an optimal capacity expansion of natural gas network, several decisions regarding the time, size, and location of expansion should be made [11]. The projects dealing with networks expansion have various steps that are different from country to country and from company to company based on rules and governmental eco­nomic policies [16].

Referring to the literature, researchers mentioned different aspects to current difficulties of network development and expansion. Davidson et al. [10] have indi­cated these difficulties from some angles: the many existing options for expanding and generating a prespecified layout, existing uncertainties in absorbing the custo­mers and profits, difficulty in estimating construction costs because of difficulties in calculating the length and unit cost per length for new pipes to expand, and finally the dynamic nature of the problem. In this matter, Kabirian and Hemmati [16] have paid attention to the presentation of an integrated strategic plan, which considers different aspects of the network development on a long-time horizon. They introduced the difficulties of this subject in various points, including cover­ing development and strategic planning in both short and long run, identifying the locations and schedules of new compressor stations and pipelines in the network, determining the best type and routing of the pipelines, selecting the best combina­tion of natural gas procurement from available sources, and providing the best operating conditions for compressor stations in long-run horizons [16]. By accu­racy of data input for new substation availability, substation reinforcements, local generation, and future load location, which should be sent under dynamic or non- determined status, a robust decision making is possible. These uncertainties can be presented in mathematical models as well, but the nature of the problem, which is nonconvex and multiobjective, makes it difficult to solve. However, it can be sim­plified through linearization of the objective functions and simplify the problem description [15].

Chung et al. [17] focused on transmission networks planning through a mathe­matical model with three objectives, including investment cost, reliability, and environmental impacts. The model was formulated using the approach of goal pro­gramming and solved by a genetic algorithm (GA). For analyzing the decisions, a fuzzy decision method was used to select the best scheme. In distribution networks, Carvalho and Ferreira [15] proposed an evolutionary algorithm for the stochastic planning of the large-scale networks under uncertain conditions and introduced the difficulties of optimizing networks expansion, including multistage investment decisions, the large-scale distribution network, and a huge variety of operation policies, variable demands, investment costs, equipment variabilities, and locations that make the decision very insightful.

The reviewed papers in the scope of optimization in the natural gas industry based on the decisions tried to make have been classified in Table 19.1.

\ 9.2.3 Model Characteristics

Each defined problem on natural gas networks follows several assumption. The assumptions are presented in the form of constraints and affect the problem com­plexity and formulation. In addition, sometimes researchers focus on part of a network that has special characteristics. Usually, in this area some properties are determined as the problem statement first. Some of the most usual attributes of nat­ural gas network problems have been illustrated in this section.

Steady State or Nonsteady State

The state of natural gas pipeline networks in different models is presented with two main categories: steady state and transient state. These states are determined through considering or not considering a partial differential equation involving deri­vation with respect to time [4]. In other words, this classification is dependent on how the gas flow changes in relation to time.

Steady state: In a large number of previous researches with optimization pro­blems in the field of natural gas network, the operation of systems is assumed in steady states because in the previous decades there was no need to quick responses to variability of demands and conditions and problems were simplified by convert­ing to subproblems in steady states [ 18].

In a steady-state system, the flow of gas is determined with some values which are independent from the time and constraints of the system, especially the ones describing the pipelines gas flow are described by algebraic nonlinear equations [6]. In the steady-state assumptions, it is possible to work out the partial differential equation and reduce to a nonlinear equation with no derivatives, which from the optimization view makes the problem more tractable [4].

Because loads and supplies are not a function of time in steady-state problems, the structure of the network—including the number of sources, compressor stations, valves and regulators, and the optimal parameters of operations including pressures ^and flows—are determined once [9]. General equations for steady-state flows in natural gas networks have been collected in Coelho and Pinho [19].

Nonsteady (transient) state: When load variations in a system are high, steady- state operations of that system are not desirable or even possible to consider such as when factors like deregulation and peak shaving are being considered. Therefore, efficient and responsive operations in dynamic statuses are essentially ^required to respond rapid variations in demands and conditions [18]. In a transient state system, the system variables such as mass flow rates through the pipelines ^and gas pressure levels at each node are defined as the functions of the time

	С
и	■м
jt аЗ	с я а
Z	X

ос 4».£ N — £ а. О ел с с а) и.£ N и £ £ £.S С ^ 3 -.2

>1 I 1>1 I I I I I I I I

я

I I I -> I I I I I I I I I I I

я

.S U сл

о.5 U £ «£ з s и. 2

о. С тз

I > > I I "> > I > I > I I >

&t5|a С 4< С ~ о -з г в U сл S (J

i) и w ■3 S. 1 I с и с я с к N И «- Н § 45 '3 С/5 я 3 X S О сл

I I I > I I I I I I I I I I I

IIIIII м м м м ->

МММ М М М М I

9JD

£ >.2 с- г z

Ml 1>1IIIII I

с ® 5 и

I I

•> I -> II I

> > >

>

>

ог -о

Г- N _ 5

— ^ ~

—: ° ~ 3

3.g | ^

в 3 1

с с ^ 2

о тз I = Г S I я" о _ w ^ "О "О о «3 я с U Я з £ и с с £ Я С.

с £ С. -

"О N тэ ^ с <4 Й Я! Я ------ D _ ? -5 5 U £ 2s Я 5 «А * b з о Я» ГЗ ^ и £

00 Я у

-

-£ >я "и СЛ

ОХ) <и —

Я £ « t S

Х> -С я О та < > сл со Ж

и CQ

dynamically. Usually, descriptive models are used to analyze transient states because of their intractable from the optimization point of view [7].

Cyclic Topology or Noncyclic Topology

Two fundamental types of network topologies are cyclic topology and noncyclic topology.

Cyclic: A cyclic topology is concerned with a network in which at least one cycle is present, including two or more compressor station arcs such as in Figure 19.5. In practice, effective algorithms for cyclic topologies do not exist [7].

Noncyclic: Most of the pipeline systems have noncyclic structures. A serial (or gun-barrel) structure is a special type of a noncyclic network where the associated reduced network is a simple path [3]. Tree structures are another type of the noncy­clic topology. A tree structure involves multiple converging and diverging branches in such a way that all nodes have in-degree equal to one, except one node, which has in-degree equal to zero [3]. Figure 19.6 is a sample for a serial topology, and Figure 19.7 presents a tree topology in natural gas networks.

To recognize the natural gas network topologies, Borraz-Sanchez and Ri'os- Mercado [7] explained a usual methodology. First, remove the compressor arcs from a given network temporarily. Second, merge the remaining connected components and eventually put the compressor arcs back in place. The obtained network is a reduced network. Three cases will occur from the reduced network. If it has a single path, the given network has a serial (gun-barrel) topology. If in the reduced network the compressors are arranged in branches, then the topology is a tree. If in the reduced network compressor stations are arranged to form cycle, the topology is cyclic.

19.2.4 Types of Methods

F'gure 19.5 A cyclic topology.

After introducing the natural gas problems and their main characteristics to distin­guish them from each other, a basic classification is done regarding methods of solving the natural gas pipeline networks. To find the best solution for the network problems, estimating the problem complexity is very important. It is quite clear to scholars in this area that the problems with cyclic structure are more difficult to

о—o^-o—O-^-O—o-^-o—о

Logistics Operations and Management

Optimization in Natural Gas Network Planning

Table 19.2 Priority of Methods to Solve Natural Gas Network Problems

Topology

Method

Cyclic

Noncyclic

Figure 19.6 A serial (gun-barrel) topology with three compressor stations.

(ИЖ)

Figure 19.7 A tree topology.

solve than problems with noncyclic topology. In other words, the dimension of pro­blems with cyclic topology is usually large and cannot be reduced by removing or fixing variables as happens in some noncyclic topology problems. The majority of the noncyclic gas network topologies have been developed based on dynamic pro­gramming and there are a large number of optimization algorithms for this type of topologies. Before we explain the suitability of methods for solving the planning problems of the natural gas network, we present Table 19.2.

Dynamic Programming

For the last few decades, dynamic programming (DP) has been utilized to opti­mally solve very large noncyclic networks such as gun-barrel and diverging branch tree systems, and some subclasses of cyclic networks. In general, to solve network problems with noncyclic systems by DP. flow variables are determined in advance and pressure variables are kept. Therefore, by converting a multi­dimensional problem into one dimension, the problem is simplified and solved easily. In a diverging branch, the problem is decomposed into a sequence of several one-dimensional DP problems in such a way that each deals with a sin­gle branch [6].

Since a DP simply satisfies constraints of any natural gas network and over­comes to nonconvexity and nonlinearity difficulties of feasible solutions, it can be used for noncyclic topologies but its computation difficulties increase with pro­blems dimensions exponentially [7]. Unlike noncyclic topology, the applicability oi DP for cyclic topologies is limited because the cycles break the linear structure or the network and the flow variables must be explicitly managed. In other words, the

DP

Gradient search Hierarchical programming Mathematical programming

DP for cyclic networks will be multidimensional. The main limitation of DP regarding the cyclic topology is that to solve this type of the problem the flow vari­ables must be fixed. Therefore, the achieved solution is optimal only with respect to a prespecified set of flow variables |4j. As it would appear from the literature, by increasing the consideration of cyclic topologies in the defined problems belonging to the natural gas system, the success of DP has been reduced.

Gradient Search

In 1987, the generalized reduced gradient (GRG) was introduced for the first time. GRG is based on a nonlinear optimization technique for noncyclic structures. In comparison to DP approaches, in the dimensionality issue for cyclic topologies GRG acts well, but it does not guarantee a global optimal solution, especially in cases where decision variables are discrete [4.7].

Hierarchical Control Mechanisms

In some transmission and distribution network problems, which are difficult to solve in an integrated way, other techniques such as hierarchical structures can be used in the process of solution to decompose the solution space to several levels. In the case of natural gas network hierarchical approaches, Rios-Mercado et al. [6] illustrated that the overall network is decomposed into two levels: the network state level as the highest level, and the compressor station level as the lowest level.

Mathematical Programming

^mce DP can not avoid trapping into the local optimum solutions, DP-based ^aPproaches and gradient searches have not had a valuable success rate to overcome difficulties of cyclic topologies in natural gas network problems. Therefore, these methods are more useful for the problems, which have fixed the flow variables, ^and consequently the optimality of the solution is only with respect to a prespeci- ^ed set of flow variables. For more than half a century, mathematical programming ^aPProaches have been used in various sections of the natural gas industry. Because

of nonconvexity of feasible solutions and nonlinearity and nonconvexity of objec tive functions of natural gas optimization problems formulated by mathematical models, a large number of local optimum solutions exist where metaheuristic meth ods help to escape from the local optimality. Overall, a rapid improving in optimi­zation algorithms is seen for solving complex mathematical models of natural gas networks, which has had a significant growth especially for cyclic topologies because of difficulties in solving the problems.