# Operation Optimization of Natural Gas Transmission Pipelines Based on Stochastic Optimization Algorithms: A Review

Authors: Xia Wu; Changjun Li; Yufa He; Wenlong Jia
Journal: Mathematical Problems in Engineering
 (2018)

---

## Abstract

Operation optimization of natural gas pipelines has received increasing attentions, due to such advantages as maximizing the operating economic benefit and the gas delivery amount. This paper provides a review on the most relevant research progress related to the steady-state operation optimization models of natural gas pipelines as well as corresponding solution methods based on stochastic optimization algorithms. The existing operation optimization model of the natural gas pipeline is a mixed-integer nonlinear programming (MINLP) model involving a nonconvex feasible region and mixing of continuous, discrete, and integer optimization variables, which represents an extremely difficult problem to be solved by use of optimization algorithms. A survey on the state of the art demonstrates that many stochastic algorithms show better performance of solving such optimization models due to their advantages of handling discrete variables and of high computation efficiency over classical deterministic optimization algorithms. The essential progress mainly with regard to the applications of the Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Simulated Annealing (SA) algorithms, and their extensions is summarized. The performances of these algorithms are compared in terms of the quality of optimization results and the computation efficiency. Furthermore, the research challenges of improving the optimization model, enhancing the stochastic algorithms, developing an online optimization technology, researching the transient optimization, and studying operation optimization of the integrated energy network are discussed.


---

## Body

## 1. Introduction

The natural gas is a low-carbon, clean, and high-quality energy source. The BP Statistical Review reports that the global natural gas consumption amount has continuously increased by an average rate of 2.3% per year over past ten years, as shown in Figure1. The total gas consumption reached 3.54 × 1012 m3 in 2016 [1], which accounted for 25% of the primary energy production in the world. The pipeline is one of the most important ways that transport large amounts of natural gas from sources to end consumers due to its convenience, economy, and reliability. By the end of 2017, the total natural gas pipeline length worldwide was more than 270 × 104 km [2]. In particular, the United States has more than 210 natural gas pipeline systems and 198 × 104 km of natural gas pipelines, which represents the largest natural gas pipeline network in the world.Figure 1
The natural gas consumption amount during the past ten years. The data were taken from BP Statistical Review of World Energy June 2017 [1].Normally, pipeline operators concern about three essential objectives, namely, the natural gas delivery amount, the economic benefit, and the line pack defined as the volume of natural gas stored in the pipeline at any moment, when operating a pipeline [3]. The gas delivery amount is usually constrained by production amounts of gas sources, consumption amounts required by consumers, the maximum allowable transmission amount of the pipeline, and gas stored in external facilities such as underground gas storage facilities. The economic benefit is determined by the gas purchasing expenditures, the gas sales income, and the pipeline operating cost. Lastly, the line pack relies on the pressures and temperatures along the pipeline. The aim of the pipeline operation optimization is to reach the maximum natural gas delivery amount, or to reach the maximum line pack, or to reach the maximum economic benefit, or to reach two or more objectives simultaneously. For example, the optimization objective can be stated as maximizing the gas delivery amount while minimizing the total fuel consumption of the compressor stations. However, these two objectives are not easy to be reached simultaneously because a higher pressure is necessary for transporting larger gas delivery amount, whereas more fuel consumption amounts of compressors are required when acquire higher pressures. The higher gas delivery amounts do not necessarily mean high economic benefits. In other words, these two objectives conflict with each other. Ríos-Mercado and Borraz-Sánchez [4] did an excellent review on various optimization objectives.The operation scheme of a natural gas pipeline usually consists of the pressures, temperatures, gas delivery amounts at all gas sources and gas terminals, the running statuses and powers of all compressors, and so on. The operation scheme is often developed based on the experience of the operator or by use of the pipeline simulation method [4]. There are two groups of methods broadly used to get the optimal operation schemes of natural gas pipelines: the operation scheme evaluating method and the mathematical optimization method. The previous method selects the best scheme from a set of existing and feasible schemes; thus the results are naturally limited by initial candidate schemes [3]. The latter method calculates the optimal scheme by building and solving a mathematical optimization model that typically consists of an objective function and many necessary constraints [5]. The objective function generally covers one or more optimization objectives as discussed earlier, and the constraints limit the optimization variables within specific physical bounds [6–8]. Obviously, the latter method is more likely to get a higher quality operation scheme in comparison with the previous one. Nevertheless, the operation optimization model has already been recognized as a nonconvex nonlinear problem (NLP) involving linear and nonlinear constraints and equality and inequality equations [9]. Furthermore, if the number of running compressors along the pipeline is considered, the model will become a more complicated mixed-integer NLP (MINLP) model. These features make the solution of the model extremely difficult. Pfetsch et al. [10] made a detailed review on the NLP for the operation optimization problem of natural gas pipelines.Over the past decades, a huge number of algorithms have been proposed to solve the optimization problems. The dynamic programming (DP), the generalized reduced gradient (GRG), and the linear programming (LP) methods are three typical deterministic methods that have been extensively involved in solving the operation optimization model of natural gas pipelines, especially to solve the minimization fuel cost problem (MFCP) of the compressors [4]. The DP is the most successful method among these methods because it guarantees the global optimum and easily handles nonlinearity problem [5, 11]. However, the computation cost of the DP algorithm increases exponentially with increasing the number of the problem’s dimension. Hence, the DP is difficult to be extended to large-scale and complicated pipeline networks involving hundreds of gas sources, consumers, and pipes. In comparison with DP, the GRG method handles the dimensionality issue relatively well and, thus, can be applied to large-scale and complicated pipeline networks [7]. However, the GRG method is easily entrapped into the local optimum due to the gradient search strategy. Many improved LP methods have a solid mathematical background [10] and the ability to find the global optimum, but they are not designed for solving the NLP problem. Moreover, none of the above three deterministic methods are designed for solving the resulting MINLP model related to some special optimization problems of natural gas pipelines [4].Unlike previous deterministic methods, some newly emerging stochastic optimization algorithms have shown many advantages over classical deterministic methods in terms of dealing with the large-scale pipeline network and the MINLP problem. Recently, a number of successful industry projects associated with applications of stochastic algorithms have been reported, including applications of the Genetic Algorithm (GA) [12, 13], Ant Colony Optimization (ACO) [13], Simulated Annealing (SA) optimization [14], Particle Swarm Optimization (PSO) [15], and their extensions. These achievements show prospective ways of efficient solving the operation optimization model of natural gas pipelines.The present review primary focuses on progress with regard to steady-state operation models of natural gas pipelines and related solution methods based on stochastic algorithms. In what follows, we briefly introduced the components consisting of gas pipelines and corresponding gas network topologies. Then, we summarized the most significant progress on operation optimization models, including the objective functions and constraints. After that, we reviewed the notable applications of GA, PSO, ACO, SA, and other algorithms on solving operation optimization problems. Also, the comparisons between stochastic and classical deterministic optimization algorithms are presented. Finally, the major challenges in this field are discussed in Section4.


## 2. The Optimal Operation Model of Natural Gas Pipelines

### 2.1. Natural Gas Pipelines

The schematic of a typical natural gas transmission system is shown in Figure2, which contains a set of gas gathering pipelines, transmission pipelines, distribution pipelines, compressor stations, and distribution stations [16]. The task of the gas gathering pipelines is gathering raw natural gas at production wells and transporting gas to processing plants. After removing impurities, transmission pipelines transport clean natural gas thousands of kilometers from processing plants to city gate stations. Finally, distribution pipelines distribute gas to end consumers.Figure 2
A schematic of a natural gas transmission system.The above three types of pipelines mainly vary with materials, diameters, operating pressure, and transmission distance. Among them, the transmission pipelines have the largest values regarding pressures, diameters, and lengths. Steel transmission pipelines are typically between 24 and 36 inches in diameter and operated at pressures ranging from 3 to 12 MPa. Due to the elevation change and friction loss along the pipeline, compressors installed in series or parallel are required in order to compensate for the lost pressure of the gas. The distance between two compressor stations typically varies from 90 to 180 km. It is estimated that 3–5% of the gas transported is consumed by the compressors, which takes 25–50% of the total operating budget of the pipeline [20, 21].In reality, the natural gas transmission system is more complicated than that depicted in Figure2. The trunk pipeline together with a lot of pipeline branches usually results in three kinds of pipeline network topologies: (a) linear or a gun barrel, (b) tree or branched, and (c) cyclic [4]. An optimization method, of course, should be applicable to pipeline networks with any kind of topologies.A node-element matrix method is a practical way that depicts the pipeline network’s topology. This method assumes that the pipeline system is composed a number of nodes and elements [22, 23]. The element contains all the pipes and devices, including compressors, regulators, valves, and other facilities, while gas sources, consumers, and connection points of elements are defined as the node. Using this method, the topology of a gas network involving Nn nodes and Ne elements can be described by a Nn×Ne matrix.Figure3 shows a combined tree and cyclic gas pipeline network consisting of six nodes, four pipes, and two devices (one compressor and one valve). The corresponding node-element matrix is expressed by (1), where each row refers to an element and each column represents a node. The values 1 and −1 in the matrix refer to the upstream and downstream nodes of the element, respectively. The value 0 indicates that there is no connection between the node and the element [15, 24]. Thus, all the inflow and outflow elements that connect with a specified node can be found by searching a fixed column of the resulting node-element matrix.(1)α=1-100000-11000010-1000001-1000001-100010-1.Figure 3
A gas pipeline network composed of a tree and a cyclic network.Normally, a pipeline has two operating statuses: steady state and transient state. The steady state indicates the status that all the operating parameters of the pipeline do not vary with time. On the contrary, the transient state considers the changes of operating parameters with time. Although the actual pipeline is in a rigorous transient state [25], using a series of steady state, namely, the quasisteady state method, is a practical way to approximate the real transient optimization problem [17], as shown in Figure 4. Therefore, in this paper, we focus on the steady-state operation optimization problem.Figure 4
Approximation of the transient process by use of a quasisteady method [17].


### 2.2. The Operation Optimization Model

#### 2.2.1. Objective Functions

The objective function represents the target that should be achieved by use of the optimization method. For the optimal operation of natural gas pipelines, the objective functions generally fall into three aspects: (a) maximize the total throughput or maximize the gas delivery amount for a specific consumer, (b) maximize the line pack defined as the volume of natural gas stored in the pipeline at any moment, and (c) maximize the economic benefit [18].(i) Gas Delivery Amount Maximization. The total gas delivery amount reflects whether the pipelines and related facilities have been sufficiently utilized or not [15, 18]. Constrained by gas supply plans, the gas delivery amount is usually fixed in a specific range. However, if a specified pipeline is a part of a pipeline network, maximizing the gas delivery amount will improve its contribution to the total transmission amount of the whole pipeline network. Thus, the gas delivery amount maximization is often considered as an objective function. Its general form is given by (2)maxfD=∑i=1NnβQni,where fD is the gas delivery amount; Nn is the total number of nodes; Qni is the gas flow rate at the ith node; β is a coefficient; if the node is a gas source, β=1; otherwise, β=0; the subscript i refers to the node index.(ii) Line Pack Maximization. The natural gas consumption amount varies with the time; thus the pipeline is also designed to be a short-term natural gas storage tool in order to meet the gas peak demands or to alleviate the fluctuation of gas supply. The line pack is defined as the volume of natural gas stored in the pipeline at any moment. Obviously, maximizing the line pack improves the pipeline peak ability [18, 28]. This objective function is formulated as follows:(3)maxfLP=∑j=1NPLPj,where fLP is the total line pack volume; NP is the total number of pipes; LPj is the line pack volume of the jth pipe; the subscript j refers to the pipe index.(iii) Operation Economic Benefit Maximization. The operation economic benefit is defined as the difference between the gas sales income and the costs associated with the gas purchasing, pipeline’s operating, management, and compressors running costs [15, 29]. This objective function is given by (4)maxfB=∑i=1NnSiQni-∑j=1NpRjfm-∑l=1NcHclCclWl,where fB is the economic benefit; Si is the gas sale or purchase unity price at the ith node; Qni is the inflow/outflow rate at the ith node; for the inflow rate, Qni is set to a positive value, otherwise Qni is set to a negative value; Rj is the management and operation cost coefficient of the jth pipe; fm is the pipeline management and operation unit cost; Nc is the total number of compressors; Hcl is the status of the lth compressor, which is a binary variable (1 or 0); Ccl is the lth compressor’s cost coefficient; Wl is the lth compressor’s power. The subscript l refers to the compressor index.Equation (4) covers a series of operating costs; however, previous research shows that the fuel consumption of all compressors takes 25–50% of the total operating budget of a pipeline [21]. Thus, minimizing the fuel cost would greatly contribute to the economic benefit. The minimum fuel cost problem (MFCP) represents the most popular topic in the field of the optimal operation of natural gas pipelines since 1968 [5, 30]. The MFCP objective function can be extracted from (4) and expressed by the following [6, 12, 31]:(5)minfC=∑l=1NcHclCclWl.More recently, another new objective function named the minimization of carbon dioxide emission has been proposed due to the increasing concerns on the environment and greenhouse control issues [32]. The CO2 emission amount is positively correlated with fuel consumption, so it can be simultaneously solved with the MFCP issue. For instance, Tabkhi [33] incorporated the fuel cost and CO2 emission cost into one minimum operating cost function.(iv) Multiobjective Functions. As previously mentioned, some of the objectives are conflicting. To avoid the nonsolution problem, the traditional optimization models typically involve only one objective. More recently, development of multiobjective optimization algorithms offers a new way to simultaneously optimize two or more objectives by use of a unified optimization model.Wu et al. [15] proposed a biobjective optimization model that considers the maximum gas delivery amount and the maximum operating benefit by use of a weighted hybrid objective function, which is essentially a single-objective optimization model. Unlike the weighted method, the Pareto optimality provides a method to determine the optimal solutions from a set of candidate multiobjective solutions [35]. According to the concept of the Pareto optimality, the multiobjective function can be formulated as follows [23]:(6)minfx=minf1x,…,fnx.The concept of Pareto optimality yields a set of nondominated solutions, named the Pareto-optimal set or Pareto-optimal front, as shown in Figure5. Sometimes, it is difficult to make a decision on which solution is the best one. Hence, an additional decision-making method is required to select the “best” one from a set of feasible solutions [36]. Related to this issue, Rodriguez et al. [23] proposed a biobjective model to simultaneously optimize the minimum fuel consumption and the maximum gas delivery amount. Alinia Kashani and Molaei [18] established a unified model to optimize the maximum gas delivery amount, the maximum line pack, and the minimum fuel cost. In spite of that, published achievements regarding the multiobjective optimization are much fewer than the single-objective optimization problem.Figure 5
Pareto front for the multiobjective optimization of the line pack, the gas delivery amount, and the operating cost [18]. The points A, B, and C on the surface indicate the Pareto optimum points.


#### 2.2.2. Constraints

(i) Inequality Constraints. Inequality constraints are used to limit pipeline flow rates, pressures, and temperatures in specified ranges. The inequality constraints are often given at each node as follows:(7)Qnimin≤Qni≤Qnimaxi=1,2,…,NnPnimin≤Pni≤Pnimaxi=1,2,…,NnTnimin≤Tni≤Tnimaxi=1,2,…,Nn,where Qni is the volume inflow/outflow rate at the ith node; Tni is the temperature at the ith node; Pni is the pressure at the ith node; subscripts min and max refer to the minimum and maximum allowable values, respectively. Tni can be calculated from the energy equation for the one-dimensional pipe flow [16].(ii) Equality Constraints. Equality constraints mainly represent the governing equations of gas flowing in pipelines, which include the mass balance, pressure, and temperature equations. The equality constraints are given by following equations [15, 30]: (8)∑k∈UiαikMik=0i=1,2,…,Nn;k=1,2,…,Ne(9)PQj2-PZj2=fPMj2j=1,2,…,Np(10)Tdowni=T0i+Tupi-T0ie-aL,where subscripts i, j, and k refer to the index of the node, pipeline, and element, respectively; Ui is the set of elements connected with the ith node; Mik is the absolute mass flow rate of the kth element connected with the ith node; αik is a constant, αik=1 if the kth element comes out from the ith node; αik=-1 if kth element goes into the ith node; Ne=Nc+Np. PQj is the jth pipe’s inlet pressure; PZj is the jth pipe’s outlet pressure; Mj is the absolute mass flow rate of the jth pipe; Tupi is the temperature at the pipe’s inlet node; T0 is the environment temperature; Tdown is the temperature at the pipe’s outlet node; fP is pressure function, fP=16λZRT/π2D5; λ is the friction facto; Z is the compressibility factor; R is gas constant; D is the internal diameter of the pipe; a is a coefficient defined as a=KπD/MCp; K is the overall heat transfer coefficient; CP is the specific heat capacity of natural gas.(iii) Compressor Constraints. There are two types of compressors installed along the gas transmission pipeline: centrifugal and reciprocating compressors. A reciprocating compressor is used to boost natural gas with high pressure and in small quantity, which uses the movement of the piston to create a vacuum inside the cylinder. The centrifugal compressor uses fans to create a vacuum and is used to boost natural gas with relatively lower pressure and in large quantity. Due to the centrifugal compressor can boost the significant higher amount of gas and requires less maintenance than the reciprocating compressor, almost all the trunk natural gas pipelines are equipped with the centrifugal compressor [37]. Hence, in this paper, we only review the significant progress regarding the constraints of centrifugal compressors.The compressor constraints were originally developed based on an ideal compressor assumption, which does not consider the nonlinear relationships between the compressor’s pressure head, power, efficiency, compressor ratio, and volume flow rate, as shown in Figure6. However, these constraints also have been extensively used, primarily due to their simplicity [12]. In an outstanding work done by Wu et al. [6], a set of polynomial correlations including the surge and stonewall curves were developed to describe the feasible domain of a centrifugal compressor, thus overcoming the defects of the previous idealized compressor model. These constraints given by (11) have already been widely adopted in gas pipeline optimization models [27, 30, 38] in the past fifteen years. In reality, these constraints are similar to the compressor models embedded in some well-known gas pipeline simulation tools, such as the Pipeline Studio and Synergi Pipeline Simulator [39]. Based on Wu’s compressor’s constraints, Sanaye and Mahmoudimehr [19] accounted for more correction parameters in compressor’s constraints related to the ambient temperature, the part load operation, and the operation out-of-design rotational speed of compressors, yielding constraints that are more likely to represent the real operating behavior of compressors. (11)W=MHηHns2=AH+BHQns+CHQns2+DHQns3,η=AE+BEQns+CEQns2+DEQns3nsmin≤ns≤nsmaxsurge≤Qns≤stonewall,where subscripts H, s, E refer to the pressure head, rotation speed, and efficiency, respectively; A, B, C, D are coefficients; H is the pressure head; n is the rotation speed; η is the efficiency.Figure 6
The operation envelop ofQ, H, ns for a single compressor unit [6].In addition to the compressor’s operating parameters, the compressor’s running status (ON or OFF) is an important parameter needed to be optimized, in particular for the systems with a series of compressors. Wu et al. [15] used the values of unity and zero to describe the compressor’s status, which introduces new discrete variables into the model. Alternatively, the status can be determined according to the ratio of the discharge pressure to the suction pressure of the compressor. The condition that the compressor ratio is equal to or less than the unity indicates the OFF status; otherwise, the status is ON. Hence, the status can be treated as a continuous variable instead of a discrete variable.


#### 2.2.3. The Optimization Model

In previous sections, we summarized various objective functions and constraints. For a specified optimization problem, the optimization model can always be formulated as a general form, given by (12), regardless of which objective function is selected and how many constraints are included [15, 18]. (12)minfmXm=1,2,…,cSubject to:hiX=0i=1,2,…,γgjX≥0j=1,2,…,ξ,where fm refers to the objective function; X is the vector of optimization variables; hi represents equality constraints; g represents inequality constraints; γ and ξ represent the total number of the equality constraints and inequality constraints, respectively.In (12), the optimization variables are parameters in the model to be optimized and often include the pressure, temperature, inflow rate, and outflow rate at each node, the flow rate in each element (the pipe and compressor), and status and power of each compressor, as given by(13)X=Pn1,Qn1,Tn1,Pn2,Qn2,Tn2,…,PnNn,QnNn,TnNn,M1,M2,…,MNe,W1,W2,…,WNC,Hc1,Hc2,…,HcNC,where the pressures, flow rates, and compressors’ powers are continuous parameters and the compressors’ statuses are discrete parameters. Due to the presence of a nonlinear objective function, the nonconvex feasible region and mixing of continuous, discrete, and integer optimization variables, the optimization problem is attributed as a mixed-integer nonlinear programming (MINLP) problem that is difficult to be solved by optimization algorithms [40, 41].


## 2.1. Natural Gas Pipelines

The schematic of a typical natural gas transmission system is shown in Figure2, which contains a set of gas gathering pipelines, transmission pipelines, distribution pipelines, compressor stations, and distribution stations [16]. The task of the gas gathering pipelines is gathering raw natural gas at production wells and transporting gas to processing plants. After removing impurities, transmission pipelines transport clean natural gas thousands of kilometers from processing plants to city gate stations. Finally, distribution pipelines distribute gas to end consumers.Figure 2
A schematic of a natural gas transmission system.The above three types of pipelines mainly vary with materials, diameters, operating pressure, and transmission distance. Among them, the transmission pipelines have the largest values regarding pressures, diameters, and lengths. Steel transmission pipelines are typically between 24 and 36 inches in diameter and operated at pressures ranging from 3 to 12 MPa. Due to the elevation change and friction loss along the pipeline, compressors installed in series or parallel are required in order to compensate for the lost pressure of the gas. The distance between two compressor stations typically varies from 90 to 180 km. It is estimated that 3–5% of the gas transported is consumed by the compressors, which takes 25–50% of the total operating budget of the pipeline [20, 21].In reality, the natural gas transmission system is more complicated than that depicted in Figure2. The trunk pipeline together with a lot of pipeline branches usually results in three kinds of pipeline network topologies: (a) linear or a gun barrel, (b) tree or branched, and (c) cyclic [4]. An optimization method, of course, should be applicable to pipeline networks with any kind of topologies.A node-element matrix method is a practical way that depicts the pipeline network’s topology. This method assumes that the pipeline system is composed a number of nodes and elements [22, 23]. The element contains all the pipes and devices, including compressors, regulators, valves, and other facilities, while gas sources, consumers, and connection points of elements are defined as the node. Using this method, the topology of a gas network involving Nn nodes and Ne elements can be described by a Nn×Ne matrix.Figure3 shows a combined tree and cyclic gas pipeline network consisting of six nodes, four pipes, and two devices (one compressor and one valve). The corresponding node-element matrix is expressed by (1), where each row refers to an element and each column represents a node. The values 1 and −1 in the matrix refer to the upstream and downstream nodes of the element, respectively. The value 0 indicates that there is no connection between the node and the element [15, 24]. Thus, all the inflow and outflow elements that connect with a specified node can be found by searching a fixed column of the resulting node-element matrix.(1)α=1-100000-11000010-1000001-1000001-100010-1.Figure 3
A gas pipeline network composed of a tree and a cyclic network.Normally, a pipeline has two operating statuses: steady state and transient state. The steady state indicates the status that all the operating parameters of the pipeline do not vary with time. On the contrary, the transient state considers the changes of operating parameters with time. Although the actual pipeline is in a rigorous transient state [25], using a series of steady state, namely, the quasisteady state method, is a practical way to approximate the real transient optimization problem [17], as shown in Figure 4. Therefore, in this paper, we focus on the steady-state operation optimization problem.Figure 4
Approximation of the transient process by use of a quasisteady method [17].


## 2.2. The Operation Optimization Model

### 2.2.1. Objective Functions

The objective function represents the target that should be achieved by use of the optimization method. For the optimal operation of natural gas pipelines, the objective functions generally fall into three aspects: (a) maximize the total throughput or maximize the gas delivery amount for a specific consumer, (b) maximize the line pack defined as the volume of natural gas stored in the pipeline at any moment, and (c) maximize the economic benefit [18].(i) Gas Delivery Amount Maximization. The total gas delivery amount reflects whether the pipelines and related facilities have been sufficiently utilized or not [15, 18]. Constrained by gas supply plans, the gas delivery amount is usually fixed in a specific range. However, if a specified pipeline is a part of a pipeline network, maximizing the gas delivery amount will improve its contribution to the total transmission amount of the whole pipeline network. Thus, the gas delivery amount maximization is often considered as an objective function. Its general form is given by (2)maxfD=∑i=1NnβQni,where fD is the gas delivery amount; Nn is the total number of nodes; Qni is the gas flow rate at the ith node; β is a coefficient; if the node is a gas source, β=1; otherwise, β=0; the subscript i refers to the node index.(ii) Line Pack Maximization. The natural gas consumption amount varies with the time; thus the pipeline is also designed to be a short-term natural gas storage tool in order to meet the gas peak demands or to alleviate the fluctuation of gas supply. The line pack is defined as the volume of natural gas stored in the pipeline at any moment. Obviously, maximizing the line pack improves the pipeline peak ability [18, 28]. This objective function is formulated as follows:(3)maxfLP=∑j=1NPLPj,where fLP is the total line pack volume; NP is the total number of pipes; LPj is the line pack volume of the jth pipe; the subscript j refers to the pipe index.(iii) Operation Economic Benefit Maximization. The operation economic benefit is defined as the difference between the gas sales income and the costs associated with the gas purchasing, pipeline’s operating, management, and compressors running costs [15, 29]. This objective function is given by (4)maxfB=∑i=1NnSiQni-∑j=1NpRjfm-∑l=1NcHclCclWl,where fB is the economic benefit; Si is the gas sale or purchase unity price at the ith node; Qni is the inflow/outflow rate at the ith node; for the inflow rate, Qni is set to a positive value, otherwise Qni is set to a negative value; Rj is the management and operation cost coefficient of the jth pipe; fm is the pipeline management and operation unit cost; Nc is the total number of compressors; Hcl is the status of the lth compressor, which is a binary variable (1 or 0); Ccl is the lth compressor’s cost coefficient; Wl is the lth compressor’s power. The subscript l refers to the compressor index.Equation (4) covers a series of operating costs; however, previous research shows that the fuel consumption of all compressors takes 25–50% of the total operating budget of a pipeline [21]. Thus, minimizing the fuel cost would greatly contribute to the economic benefit. The minimum fuel cost problem (MFCP) represents the most popular topic in the field of the optimal operation of natural gas pipelines since 1968 [5, 30]. The MFCP objective function can be extracted from (4) and expressed by the following [6, 12, 31]:(5)minfC=∑l=1NcHclCclWl.More recently, another new objective function named the minimization of carbon dioxide emission has been proposed due to the increasing concerns on the environment and greenhouse control issues [32]. The CO2 emission amount is positively correlated with fuel consumption, so it can be simultaneously solved with the MFCP issue. For instance, Tabkhi [33] incorporated the fuel cost and CO2 emission cost into one minimum operating cost function.(iv) Multiobjective Functions. As previously mentioned, some of the objectives are conflicting. To avoid the nonsolution problem, the traditional optimization models typically involve only one objective. More recently, development of multiobjective optimization algorithms offers a new way to simultaneously optimize two or more objectives by use of a unified optimization model.Wu et al. [15] proposed a biobjective optimization model that considers the maximum gas delivery amount and the maximum operating benefit by use of a weighted hybrid objective function, which is essentially a single-objective optimization model. Unlike the weighted method, the Pareto optimality provides a method to determine the optimal solutions from a set of candidate multiobjective solutions [35]. According to the concept of the Pareto optimality, the multiobjective function can be formulated as follows [23]:(6)minfx=minf1x,…,fnx.The concept of Pareto optimality yields a set of nondominated solutions, named the Pareto-optimal set or Pareto-optimal front, as shown in Figure5. Sometimes, it is difficult to make a decision on which solution is the best one. Hence, an additional decision-making method is required to select the “best” one from a set of feasible solutions [36]. Related to this issue, Rodriguez et al. [23] proposed a biobjective model to simultaneously optimize the minimum fuel consumption and the maximum gas delivery amount. Alinia Kashani and Molaei [18] established a unified model to optimize the maximum gas delivery amount, the maximum line pack, and the minimum fuel cost. In spite of that, published achievements regarding the multiobjective optimization are much fewer than the single-objective optimization problem.Figure 5
Pareto front for the multiobjective optimization of the line pack, the gas delivery amount, and the operating cost [18]. The points A, B, and C on the surface indicate the Pareto optimum points.


### 2.2.2. Constraints

(i) Inequality Constraints. Inequality constraints are used to limit pipeline flow rates, pressures, and temperatures in specified ranges. The inequality constraints are often given at each node as follows:(7)Qnimin≤Qni≤Qnimaxi=1,2,…,NnPnimin≤Pni≤Pnimaxi=1,2,…,NnTnimin≤Tni≤Tnimaxi=1,2,…,Nn,where Qni is the volume inflow/outflow rate at the ith node; Tni is the temperature at the ith node; Pni is the pressure at the ith node; subscripts min and max refer to the minimum and maximum allowable values, respectively. Tni can be calculated from the energy equation for the one-dimensional pipe flow [16].(ii) Equality Constraints. Equality constraints mainly represent the governing equations of gas flowing in pipelines, which include the mass balance, pressure, and temperature equations. The equality constraints are given by following equations [15, 30]: (8)∑k∈UiαikMik=0i=1,2,…,Nn;k=1,2,…,Ne(9)PQj2-PZj2=fPMj2j=1,2,…,Np(10)Tdowni=T0i+Tupi-T0ie-aL,where subscripts i, j, and k refer to the index of the node, pipeline, and element, respectively; Ui is the set of elements connected with the ith node; Mik is the absolute mass flow rate of the kth element connected with the ith node; αik is a constant, αik=1 if the kth element comes out from the ith node; αik=-1 if kth element goes into the ith node; Ne=Nc+Np. PQj is the jth pipe’s inlet pressure; PZj is the jth pipe’s outlet pressure; Mj is the absolute mass flow rate of the jth pipe; Tupi is the temperature at the pipe’s inlet node; T0 is the environment temperature; Tdown is the temperature at the pipe’s outlet node; fP is pressure function, fP=16λZRT/π2D5; λ is the friction facto; Z is the compressibility factor; R is gas constant; D is the internal diameter of the pipe; a is a coefficient defined as a=KπD/MCp; K is the overall heat transfer coefficient; CP is the specific heat capacity of natural gas.(iii) Compressor Constraints. There are two types of compressors installed along the gas transmission pipeline: centrifugal and reciprocating compressors. A reciprocating compressor is used to boost natural gas with high pressure and in small quantity, which uses the movement of the piston to create a vacuum inside the cylinder. The centrifugal compressor uses fans to create a vacuum and is used to boost natural gas with relatively lower pressure and in large quantity. Due to the centrifugal compressor can boost the significant higher amount of gas and requires less maintenance than the reciprocating compressor, almost all the trunk natural gas pipelines are equipped with the centrifugal compressor [37]. Hence, in this paper, we only review the significant progress regarding the constraints of centrifugal compressors.The compressor constraints were originally developed based on an ideal compressor assumption, which does not consider the nonlinear relationships between the compressor’s pressure head, power, efficiency, compressor ratio, and volume flow rate, as shown in Figure6. However, these constraints also have been extensively used, primarily due to their simplicity [12]. In an outstanding work done by Wu et al. [6], a set of polynomial correlations including the surge and stonewall curves were developed to describe the feasible domain of a centrifugal compressor, thus overcoming the defects of the previous idealized compressor model. These constraints given by (11) have already been widely adopted in gas pipeline optimization models [27, 30, 38] in the past fifteen years. In reality, these constraints are similar to the compressor models embedded in some well-known gas pipeline simulation tools, such as the Pipeline Studio and Synergi Pipeline Simulator [39]. Based on Wu’s compressor’s constraints, Sanaye and Mahmoudimehr [19] accounted for more correction parameters in compressor’s constraints related to the ambient temperature, the part load operation, and the operation out-of-design rotational speed of compressors, yielding constraints that are more likely to represent the real operating behavior of compressors. (11)W=MHηHns2=AH+BHQns+CHQns2+DHQns3,η=AE+BEQns+CEQns2+DEQns3nsmin≤ns≤nsmaxsurge≤Qns≤stonewall,where subscripts H, s, E refer to the pressure head, rotation speed, and efficiency, respectively; A, B, C, D are coefficients; H is the pressure head; n is the rotation speed; η is the efficiency.Figure 6
The operation envelop ofQ, H, ns for a single compressor unit [6].In addition to the compressor’s operating parameters, the compressor’s running status (ON or OFF) is an important parameter needed to be optimized, in particular for the systems with a series of compressors. Wu et al. [15] used the values of unity and zero to describe the compressor’s status, which introduces new discrete variables into the model. Alternatively, the status can be determined according to the ratio of the discharge pressure to the suction pressure of the compressor. The condition that the compressor ratio is equal to or less than the unity indicates the OFF status; otherwise, the status is ON. Hence, the status can be treated as a continuous variable instead of a discrete variable.


### 2.2.3. The Optimization Model

In previous sections, we summarized various objective functions and constraints. For a specified optimization problem, the optimization model can always be formulated as a general form, given by (12), regardless of which objective function is selected and how many constraints are included [15, 18]. (12)minfmXm=1,2,…,cSubject to:hiX=0i=1,2,…,γgjX≥0j=1,2,…,ξ,where fm refers to the objective function; X is the vector of optimization variables; hi represents equality constraints; g represents inequality constraints; γ and ξ represent the total number of the equality constraints and inequality constraints, respectively.In (12), the optimization variables are parameters in the model to be optimized and often include the pressure, temperature, inflow rate, and outflow rate at each node, the flow rate in each element (the pipe and compressor), and status and power of each compressor, as given by(13)X=Pn1,Qn1,Tn1,Pn2,Qn2,Tn2,…,PnNn,QnNn,TnNn,M1,M2,…,MNe,W1,W2,…,WNC,Hc1,Hc2,…,HcNC,where the pressures, flow rates, and compressors’ powers are continuous parameters and the compressors’ statuses are discrete parameters. Due to the presence of a nonlinear objective function, the nonconvex feasible region and mixing of continuous, discrete, and integer optimization variables, the optimization problem is attributed as a mixed-integer nonlinear programming (MINLP) problem that is difficult to be solved by optimization algorithms [40, 41].


## 2.2.1. Objective Functions

The objective function represents the target that should be achieved by use of the optimization method. For the optimal operation of natural gas pipelines, the objective functions generally fall into three aspects: (a) maximize the total throughput or maximize the gas delivery amount for a specific consumer, (b) maximize the line pack defined as the volume of natural gas stored in the pipeline at any moment, and (c) maximize the economic benefit [18].(i) Gas Delivery Amount Maximization. The total gas delivery amount reflects whether the pipelines and related facilities have been sufficiently utilized or not [15, 18]. Constrained by gas supply plans, the gas delivery amount is usually fixed in a specific range. However, if a specified pipeline is a part of a pipeline network, maximizing the gas delivery amount will improve its contribution to the total transmission amount of the whole pipeline network. Thus, the gas delivery amount maximization is often considered as an objective function. Its general form is given by (2)maxfD=∑i=1NnβQni,where fD is the gas delivery amount; Nn is the total number of nodes; Qni is the gas flow rate at the ith node; β is a coefficient; if the node is a gas source, β=1; otherwise, β=0; the subscript i refers to the node index.(ii) Line Pack Maximization. The natural gas consumption amount varies with the time; thus the pipeline is also designed to be a short-term natural gas storage tool in order to meet the gas peak demands or to alleviate the fluctuation of gas supply. The line pack is defined as the volume of natural gas stored in the pipeline at any moment. Obviously, maximizing the line pack improves the pipeline peak ability [18, 28]. This objective function is formulated as follows:(3)maxfLP=∑j=1NPLPj,where fLP is the total line pack volume; NP is the total number of pipes; LPj is the line pack volume of the jth pipe; the subscript j refers to the pipe index.(iii) Operation Economic Benefit Maximization. The operation economic benefit is defined as the difference between the gas sales income and the costs associated with the gas purchasing, pipeline’s operating, management, and compressors running costs [15, 29]. This objective function is given by (4)maxfB=∑i=1NnSiQni-∑j=1NpRjfm-∑l=1NcHclCclWl,where fB is the economic benefit; Si is the gas sale or purchase unity price at the ith node; Qni is the inflow/outflow rate at the ith node; for the inflow rate, Qni is set to a positive value, otherwise Qni is set to a negative value; Rj is the management and operation cost coefficient of the jth pipe; fm is the pipeline management and operation unit cost; Nc is the total number of compressors; Hcl is the status of the lth compressor, which is a binary variable (1 or 0); Ccl is the lth compressor’s cost coefficient; Wl is the lth compressor’s power. The subscript l refers to the compressor index.Equation (4) covers a series of operating costs; however, previous research shows that the fuel consumption of all compressors takes 25–50% of the total operating budget of a pipeline [21]. Thus, minimizing the fuel cost would greatly contribute to the economic benefit. The minimum fuel cost problem (MFCP) represents the most popular topic in the field of the optimal operation of natural gas pipelines since 1968 [5, 30]. The MFCP objective function can be extracted from (4) and expressed by the following [6, 12, 31]:(5)minfC=∑l=1NcHclCclWl.More recently, another new objective function named the minimization of carbon dioxide emission has been proposed due to the increasing concerns on the environment and greenhouse control issues [32]. The CO2 emission amount is positively correlated with fuel consumption, so it can be simultaneously solved with the MFCP issue. For instance, Tabkhi [33] incorporated the fuel cost and CO2 emission cost into one minimum operating cost function.(iv) Multiobjective Functions. As previously mentioned, some of the objectives are conflicting. To avoid the nonsolution problem, the traditional optimization models typically involve only one objective. More recently, development of multiobjective optimization algorithms offers a new way to simultaneously optimize two or more objectives by use of a unified optimization model.Wu et al. [15] proposed a biobjective optimization model that considers the maximum gas delivery amount and the maximum operating benefit by use of a weighted hybrid objective function, which is essentially a single-objective optimization model. Unlike the weighted method, the Pareto optimality provides a method to determine the optimal solutions from a set of candidate multiobjective solutions [35]. According to the concept of the Pareto optimality, the multiobjective function can be formulated as follows [23]:(6)minfx=minf1x,…,fnx.The concept of Pareto optimality yields a set of nondominated solutions, named the Pareto-optimal set or Pareto-optimal front, as shown in Figure5. Sometimes, it is difficult to make a decision on which solution is the best one. Hence, an additional decision-making method is required to select the “best” one from a set of feasible solutions [36]. Related to this issue, Rodriguez et al. [23] proposed a biobjective model to simultaneously optimize the minimum fuel consumption and the maximum gas delivery amount. Alinia Kashani and Molaei [18] established a unified model to optimize the maximum gas delivery amount, the maximum line pack, and the minimum fuel cost. In spite of that, published achievements regarding the multiobjective optimization are much fewer than the single-objective optimization problem.Figure 5
Pareto front for the multiobjective optimization of the line pack, the gas delivery amount, and the operating cost [18]. The points A, B, and C on the surface indicate the Pareto optimum points.


## 2.2.2. Constraints

(i) Inequality Constraints. Inequality constraints are used to limit pipeline flow rates, pressures, and temperatures in specified ranges. The inequality constraints are often given at each node as follows:(7)Qnimin≤Qni≤Qnimaxi=1,2,…,NnPnimin≤Pni≤Pnimaxi=1,2,…,NnTnimin≤Tni≤Tnimaxi=1,2,…,Nn,where Qni is the volume inflow/outflow rate at the ith node; Tni is the temperature at the ith node; Pni is the pressure at the ith node; subscripts min and max refer to the minimum and maximum allowable values, respectively. Tni can be calculated from the energy equation for the one-dimensional pipe flow [16].(ii) Equality Constraints. Equality constraints mainly represent the governing equations of gas flowing in pipelines, which include the mass balance, pressure, and temperature equations. The equality constraints are given by following equations [15, 30]: (8)∑k∈UiαikMik=0i=1,2,…,Nn;k=1,2,…,Ne(9)PQj2-PZj2=fPMj2j=1,2,…,Np(10)Tdowni=T0i+Tupi-T0ie-aL,where subscripts i, j, and k refer to the index of the node, pipeline, and element, respectively; Ui is the set of elements connected with the ith node; Mik is the absolute mass flow rate of the kth element connected with the ith node; αik is a constant, αik=1 if the kth element comes out from the ith node; αik=-1 if kth element goes into the ith node; Ne=Nc+Np. PQj is the jth pipe’s inlet pressure; PZj is the jth pipe’s outlet pressure; Mj is the absolute mass flow rate of the jth pipe; Tupi is the temperature at the pipe’s inlet node; T0 is the environment temperature; Tdown is the temperature at the pipe’s outlet node; fP is pressure function, fP=16λZRT/π2D5; λ is the friction facto; Z is the compressibility factor; R is gas constant; D is the internal diameter of the pipe; a is a coefficient defined as a=KπD/MCp; K is the overall heat transfer coefficient; CP is the specific heat capacity of natural gas.(iii) Compressor Constraints. There are two types of compressors installed along the gas transmission pipeline: centrifugal and reciprocating compressors. A reciprocating compressor is used to boost natural gas with high pressure and in small quantity, which uses the movement of the piston to create a vacuum inside the cylinder. The centrifugal compressor uses fans to create a vacuum and is used to boost natural gas with relatively lower pressure and in large quantity. Due to the centrifugal compressor can boost the significant higher amount of gas and requires less maintenance than the reciprocating compressor, almost all the trunk natural gas pipelines are equipped with the centrifugal compressor [37]. Hence, in this paper, we only review the significant progress regarding the constraints of centrifugal compressors.The compressor constraints were originally developed based on an ideal compressor assumption, which does not consider the nonlinear relationships between the compressor’s pressure head, power, efficiency, compressor ratio, and volume flow rate, as shown in Figure6. However, these constraints also have been extensively used, primarily due to their simplicity [12]. In an outstanding work done by Wu et al. [6], a set of polynomial correlations including the surge and stonewall curves were developed to describe the feasible domain of a centrifugal compressor, thus overcoming the defects of the previous idealized compressor model. These constraints given by (11) have already been widely adopted in gas pipeline optimization models [27, 30, 38] in the past fifteen years. In reality, these constraints are similar to the compressor models embedded in some well-known gas pipeline simulation tools, such as the Pipeline Studio and Synergi Pipeline Simulator [39]. Based on Wu’s compressor’s constraints, Sanaye and Mahmoudimehr [19] accounted for more correction parameters in compressor’s constraints related to the ambient temperature, the part load operation, and the operation out-of-design rotational speed of compressors, yielding constraints that are more likely to represent the real operating behavior of compressors. (11)W=MHηHns2=AH+BHQns+CHQns2+DHQns3,η=AE+BEQns+CEQns2+DEQns3nsmin≤ns≤nsmaxsurge≤Qns≤stonewall,where subscripts H, s, E refer to the pressure head, rotation speed, and efficiency, respectively; A, B, C, D are coefficients; H is the pressure head; n is the rotation speed; η is the efficiency.Figure 6
The operation envelop ofQ, H, ns for a single compressor unit [6].In addition to the compressor’s operating parameters, the compressor’s running status (ON or OFF) is an important parameter needed to be optimized, in particular for the systems with a series of compressors. Wu et al. [15] used the values of unity and zero to describe the compressor’s status, which introduces new discrete variables into the model. Alternatively, the status can be determined according to the ratio of the discharge pressure to the suction pressure of the compressor. The condition that the compressor ratio is equal to or less than the unity indicates the OFF status; otherwise, the status is ON. Hence, the status can be treated as a continuous variable instead of a discrete variable.


## 2.2.3. The Optimization Model

In previous sections, we summarized various objective functions and constraints. For a specified optimization problem, the optimization model can always be formulated as a general form, given by (12), regardless of which objective function is selected and how many constraints are included [15, 18]. (12)minfmXm=1,2,…,cSubject to:hiX=0i=1,2,…,γgjX≥0j=1,2,…,ξ,where fm refers to the objective function; X is the vector of optimization variables; hi represents equality constraints; g represents inequality constraints; γ and ξ represent the total number of the equality constraints and inequality constraints, respectively.In (12), the optimization variables are parameters in the model to be optimized and often include the pressure, temperature, inflow rate, and outflow rate at each node, the flow rate in each element (the pipe and compressor), and status and power of each compressor, as given by(13)X=Pn1,Qn1,Tn1,Pn2,Qn2,Tn2,…,PnNn,QnNn,TnNn,M1,M2,…,MNe,W1,W2,…,WNC,Hc1,Hc2,…,HcNC,where the pressures, flow rates, and compressors’ powers are continuous parameters and the compressors’ statuses are discrete parameters. Due to the presence of a nonlinear objective function, the nonconvex feasible region and mixing of continuous, discrete, and integer optimization variables, the optimization problem is attributed as a mixed-integer nonlinear programming (MINLP) problem that is difficult to be solved by optimization algorithms [40, 41].


## 3. Model Solution Based on Stochastic Optimization Algorithms

Unlike the conventional deterministic algorithms, the stochastic methods are inspired by either the social behavior of biological species or natural biological evolution, resulting in the evolutionary and heuristic algorithms. The biological species used in these stochastic algorithms originally are gathered by individual samples, so the solution strategy does not rely on the gradient information and is able to adapt to discrete variables. Also, stochastic algorithms are shown to be more efficient than some classical deterministic algorithms for solving the MINLP problems [12, 15, 42]. In this paper, we reviewed the essential progress on solving the operation optimization problems of natural gas pipelines by use of the Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Optimization (ACO), Simulated Annealing (SA), and other algorithms including the Differential Evolution (DE) and Tabu Search (TS). Figure 7 shows that using the stochastic algorithms to solve the gas pipeline operation optimization problems represents a growing concern in recent ten years.Figure 7
The timeline of applying stochastic algorithms to solve operation optimization problems of natural gas pipelines.


### 3.1. Genetic Algorithm (GA)

The Genetic Algorithm (GA) is a kind of metaheuristic search algorithm based on the Darwinian’s evolutionary ideas of natural selection and genetics [36], which was first applied to solve the operation optimization problems of natural gas pipeline in 1987 by Goldberg [43]. GA starts from a population of individuals that represent feasible solutions of the optimization problem, where each individual is represented by a chromosome composed of all the optimization variables, as shown in Figure 8. The optimal solution is then obtained by implementing procedures of the selection, crossover, and mutation on the original individuals (chromosomes) through consecutive generations. In each generation, a fitness function related to the objective function and constraints is firstly used to evaluate the fitness value of each individual. The individuals having higher fitness values are more likely to be selected as parents to generate new individuals in the next generation, and some of the individuals having lower fitness values are dropped. Then, the crossover operator is applied to recombine different portions of selected individuals. As a result, some better candidate individuals might be created in the next generation. Finally, the mutation operator is randomly applied to some individuals, yielding the enhancement of the global search ability of the algorithm. These procedures are repeated until all individuals reach a satisfactory fitness value, or alternatively, say that until the algorithm converges [44].Figure 8
Schematic diagram of the chromosome of GA [19]. Each chromosome is composed of all variables in the optimization model.Goldberg [43] firstly applied GA to solve the natural gas pipeline optimization problem. He built an operation optimization model for a natural gas pipeline system with forty compressors for the purpose of minimizing the total power of all compressors. He assumed that the compressors’ efficiencies and head rises are constants; thus the variables to be optimized are the compressors’ running statuses. After that, the initial population consisting of 100 individuals that represent all compressors’ statuses was generated. The crossover probability and mutation probability were set to 0.7 and 0.01, respectively. Computations show that near-optimal results are obtained after 50 generations of evolution. In particular, even three different initial populations are applied, they finally yield similar optimal results, which shows a good convergence and reproducibility. Goldberg [45] later extended the GA to the transient optimization of a single line pipeline. He suggested that GAs are ready for application to other more difficult optimization cases.Based on Goldberg’s achievements, the most important progress focuses on using newly improved GAs to solve the optimization problems. Li et al. [24] used an adaptive genetic algorithm (AGA) proposed by Srinivas and Patnaik [46] to solve the pipeline operation optimization problem. The AGA method dynamically adjusts the crossover and mutation probabilities according to the average fitness of the population, the maximum fitness of all individuals so far, and the fitness of a specified individual, which yields lower crossover and mutation probabilities when the specified individual is closer to the best individual so far. Therefore, the historical information belonging to “better individuals” is retained, and the convergence performance can be significantly enhanced in comparison to the original GA. Li et al. [24] reported a successful application of the AGA to a pipeline network consisting of 22 pipes and 21 nodes. However, there are no compressors in the example studied and, also, they did not compare the performance of the AGA with other existing GAs. Sanaye and Mahmoudimehr [19] applied the GA to solve the MFCP problem of three types of natural gas transmission network including the linear, branched, and cyclic pipeline structures. A detail compressor model associated with the pressure, efficiency, stonewall and surge curves, and related correction parameters is presented. Sanaye and Mahmoudimehr [19] presented that the GA has higher computation speed in comparison to the nonsequential dynamic programming (NDP) because the NDP’s computing time exponentially depends on pressure and flow rate step sizes, as shown in Figure 9. MohamadiBaghmolaei et al. [47] used the GA to solve the MFCP of a real 56-inch pipeline involving four boosting units located in the south of Iran. They developed an Artificial Neural Network (ANN) model to describe the relationship between compressor’s flow rate, head rise, and rotation speed instead of using the conventional compressor’s equations as previously mentioned.Figure 9
Comparison of required computing time for NDP and GA methods [19]. (a) Required computing time for the NDP method; (b) required computing time for the GA method.
(a) (b)In addition to the single-objective optimization, significant achievements have been reached with regard to the multiobjective optimization by use of GAs. Botros et al. [48] reported several successful multiobjective optimization cases of applying GAs to large-scale pipeline networks operated by TransCanada Pipeline Ltd. They considered four different objectives: (a) minimizing fuel consumption, (b) minimizing fuel consumption while maximizing gas delivery amount, (c) minimizing line pack while maximizing gas delivery amount, and (d) maximizing line pack while maximizing gas delivery amount. In comparison to Goldberg’s model [43], this model accounts for the constraints associated with the compressors’ surge and stonewall curves related to the compressors’ flow rates and rotation speeds. They built the fitness function by incorporating the objective function and constraints in the penalty function manner, which is shown to be sufficient enough for these optimization problems studied. This method was successfully applied to two pipeline networks. One of them has 10 compressor stations and 20 optimization variables, while another one has 25 compressor stations, resulting in 54 decision variables. The optimization results are given by Pareto fronts. However, when evaluating 50000 design cases, the total computing time is approximately one day, which indicates a relative expensive computation cost. Later, they researched more improved methods to enhance the computation efficiency, such as the hybrid GA and gradient-based algorithm and the parallel processing technical [49]. These improved methods were incorporated into an automated optimization system belonging to TransCanada Pipeline Ltd.More recently, a novel Nondominated Sorting Genetic Algorithm II (NSGA-II) has attracted growing attentions for solving the multiobjective operation optimization problem [50]. NSGA-II uses a fast nondominated sorting approach, which reduces the amount of computation from O (mn3) (m refers to the number of objectives and n refers to population size) in the NSGA to O (mn2). Also, an elitism strategy is adopted in NSGA-II, ensuring some good individuals not to be discarded in the evolutionary process. Finally, NSGA-II applies the fast crowded distance estimation procedure and simple crowded comparison operator, overcoming the problem of the NSGA that requires the specification of a sharing parameter. As a result, it is able to find a much better spread of solutions and better convergence near the true Pareto-optimal front in comparison to the Pareto-archived evolution strategy and strength-Pareto evolutionary algorithms [51].Rodriguez et al. [23] used the NSGA-II to simultaneously optimize the maximum gas delivery amount, the minimum fuel consumption, and related CO2 emissions amount of compressors. The Pareto front obtained from the multiobjective optimization algorithm can be served to determine the minimum and maximum line pack while considering the gas delivery and CO2 emission amount. Also, the results offer a practical way to determine the minimal CO2 emission amount for a given gas delivery amount by operating compressor stations in appropriate manners. Alinia Kashani and Molaei [18] employed the NSGA-II algorithm to balance the maximum gas delivery amount, the maximum line pack, and the minimum operating cost for a pipeline consisting of two gas sources, ten pipe segments, and five compressors. In this model, the gas flow rates and pressures of gas sources, the statuses, and rotational speeds of compressors are taken as optimization variables. Hu et al. [31] used the NSGA-II algorithm to solve a multiobjective optimization model for planning the combined gas and electricity network. Both of the investment cost and the production cost of the combined system are minimized. In particular, a fuzzy decision approach is employed to select the final optimal solution from the resulting Pareto front.In summary, GAs have been extensively involved in solving the optimal operation problems of natural gas pipelines over past 30 years. The feasibility and effectiveness of GAs also have been proven by a number of worldwide successful industry projects. More recently, the NSGA-II is shown to be a promising algorithm for solving multiobjective optimization models for natural gas pipelines [18, 31].


### 3.2. Particle Swarm Optimization (PSO) Algorithm

The Particle Swarm Optimization (PSO) algorithm is an evolutionary optimization algorithm inspired by the movement of organisms in a flock of birds or a school of fish [52]. Similar to GA, the candidate solutions in PSO are composed of a population of particles spread in the solution space. Each particle is featured by a position and a velocity, where the position represents a feasible solution for the optimization problem in the multidimensional solution space, and the velocity moves the particle itself from one position to another position over consecutive iterations. At each iteration step, every candidate particle is quantitatively evaluated by use of a fitness function. During this process, every particle records its personal best position searched so far, and the particle having the best fitness value around the neighborhood is marked as the global/local best particle. The move speed of each particle is determined by the current motion, the personal best position, and the global best position, as shown in Figure 10. Thus, all the particles are prone to move to the region with the highest fitness value. By repeating the moving process, all the particles will eventually aggregate in the highest fitness value region, which indicates the convergence of the PSO algorithm. Since the PSO makes few assumptions regarding the problems to be optimized, it is able to search very large solution spaces.Figure 10
A schematic for the position updating of a particle [26]. xik represents the position of the ith particle at the kth step, namely, the old position; xik+1 is the new position; vik is the current speed; pi, pk refer to the personal and global best positions, respectively. The move speed vik+1 is calculated from the current speed and swarm influence.The PSO algorithms cannot guarantee the global optimum solution because of the premature problem that indicates the particles converge to a local optimum region rather than a global one. Thus, some improvement strategies have already been applied to either the PSO algorithm itself or the optimization model in order to alleviate its premature problem. In fact, the prematurity is naturally a feature of many other algorithms, such as GA and ACO as will be discussed later.Adjusting the inert weight represents a growing concern in reducing the optimization problem by use of the PSO algorithm. The inert weight represents the effect of the current motion of the particle on the movement of the next step. A higher inert weight indicates that the current motion has a greater effect on the movement of the particle. Li et al. [53] used the PSO algorithm to solve the MFCP of natural gas pipeline networks in which the relaxed gas flow equations are used as constraints. The relaxed flow equations accept approximate solutions of the flow equations as candidate particles, which enlarges the solution searching domain of this PSO algorithm in comparison with the method of using the rigorous flow equations. They presented that, under the same initial conditions and required accuracy, the proposed method and the simplex algorithm give the optimal gas consumption amounts of 1.52 m3/s and 1.5528 m3/s, respectively. The results demonstrate that the PSO algorithm is able to find higher quality solutions in comparison with the LP method. Zheng and Wu [27] presented an improved PSO to solve the MFCP of gas pipelines. A method based on an exponential function is employed to change the inert weight of PSO with the evolution generation, which essentially enhances the global search ability and the convergence speed in comparison to the original PSO algorithm. That is, at the beginning, the inertia weight is a large value that enables the PSO algorithm to search large solution spaces, thus avoiding the premature convergence problem. After a certain number of evolution generations, all the particles tend to converge to the near-optimal domain; thus a small inertia weight is used to speed up the convergence. They tested this new method by applying it to a pipeline system with up to 17 compressor stations. The results show that the relative errors of the optimization results given by the improved PSO, ACO, and DP algorithms are less than 1%, whereas the computation cost of the PSO is 4 to 8 times less than that of the ACO and 170 times less than that of the DP. These comparisons show that the proposed PSO algorithm has a high computation efficiency while keeping the similar optimization results.Wu et al. [15] used an inertia-adaptive PSO (IAPSO) to solve a biobjective optimization model that considers the maximum operating benefit and the maximum gas delivery amount. The IAPSO automatically increases the inertia weight of PSO when the particle is apart from the global best value and conversely and decreases the inertia weight when the particle is approaching the global best value. This adaptive adjustment method gives the IAPSO stronger global search ability when candidate particles are apart from the global best position so far. This method was applied to a pipeline with four compressor stations and compared to five other PSO algorithms including the PSO-TVIW, HPSO-TVAC, MPSO-TVAC, and CLPSO algorithms [54]. They presented that the IAPSO not only shows faster convergence speed but also gives better optimization results in terms of the biobjective functions, as shown in Figure 11. These results show that the PSO algorithm should be well designed to get the better optimization solution. In other words, the final optimization results are dependent on how the original PSO is improved.Figure 11
The converge curves of different PSO algorithms for an operation optimization problem of a natural gas pipeline [15].In addition to apply the PSO to solve the operation optimization problems of natural gas pipelines, there are also a number of successful applications in the fields of the operation optimization of oil pipeline [55], the layout optimization of the oil and gas pipelines [56], and the optimal control of compressors [57]. Although these optimization problems are different from the operation optimization of gas pipelines, they also mentioned that some specific techniques should be adopted to overcome the premature shortcoming when using the original PSO.In summary, the PSO is featured by its high computation speed. Nevertheless, how to alleviate the premature defect of the original PSO algorithm is quite challenging since the main idea in PSO resembles the overall idea in gradient search methods, but adapted to a population. Actually, the parameters setting (e.g., the number of particles and the maximum number of function evaluations) affects the final performance of the PSO algorithm when solving the MINLP problem [15].


### 3.3. Ant Colony Optimization (ACO) Algorithm

The Ant Colony Optimization (ACO) algorithm is a nature-inspired optimization method proposed by Dorigo in 1992 [58]. This method mimics the process of ants searching for the shortest path between the nest and the food source. At the beginning, a school of ants starts from their nest to randomly search for food in the region around the nest. If one ant succeeds in finding food, it goes back to the nest and leaves a chemical pheromone trail along the searching path. The other ants will follow the path identified by the pheromone trail, so all the ants will be able to find the same food source in the shortest way [59]. The two critical procedures of the ACO algorithm are the edge selection and pheromone updating. Each edge represents a feasible solution consisting of the optimization variables. The initial edges are developed by the random search of ants. All edges construct the multidimensional solution space for the optimization problem. The ants move along the edges and left pheromone in edges during the iteration process. The edge with a higher level of pheromone is more likely to be selected by ants, and, in turn, more pheromone is left if more ants pass through one edge [60].Chebouba et al. [13, 60] are the first people who solve operation optimization problems of natural gas pipelines by use of the ACO algorithm. They used a two-stage technique (local updating and global updating) to update the pheromone trail, yielding an improved two-stage ACO algorithm. This method was applied to solve the MFCP of the Hassi R’mel-Arzew gas pipeline involving one gas source, one gas user, six pipes, and five compressor stations. Computations show that the relative errors between ACO results and DP results are typically less than 1%, but the computation speed of ACO is more than 14 times faster than that of the DP. These achievements prove the feasibility of applying the ACO to solve the gas pipeline optimization problem. In 2012, Chebouba and Meglouli [42] used a combined ANN and ACO algorithm to optimize the number of operating compressor and related discharge pressures of a gas pipeline system under the steady-state assumption. In comparison to the previous work, they used the ANN method to describe the compressor’s performance rather than the nonlinear equations mentioned in Section 2.2. MohamadiBaghmolaei et al. [47] also employed the ANN to calculate the compressor’s performance, but they used the GA as the optimization algorithm instead of the ACO.Arya and Honwad [20] applied the original ACO to solve the MFCP of a pipeline network involving 18 nodes, 2 compressor stations, and 3 identical compressors in each station. Under the fixed gas flow rate, the fuel costs calculated by the ACO and GRG methods were compared. They presented that the ACO is able to lead a further fuel savings of 0.015 kg/s and a total economic saving of nearly US $ 350,000 per year in comparison to the results calculated by the GRG method. These results demonstrate that ACO yields higher quality solutions in comparison with the GRG method. However, to the best of our knowledge, ACO has not been implemented in systems with more complicated pipelines so far.


### 3.4. Simulated Annealing (SA) Algorithm

Annealing in metallurgy technical is a process involving heating and controlled cooling of a material in order to change the properties of crystals and to reduce defects of a material [61]. According to the thermodynamic theory, the heating process increases the thermodynamic free energy of the metal material, and the cooling process decreases the thermodynamic free energy. Eventually, the thermodynamic free energy will drop to a global minimum value when the material reaches the equilibrium state. Inspired by such processes, Khachaturyan et al. [62] proposed the Simulated Annealing (SA) algorithm in 1979 that approximates the global optimum of a specified function in a probabilistic searching manner. That is, an energy function is analogous to the thermodynamic free energy of the system and acts as an objective function of the optimization problem. During the cooling process, a current solution can be replaced with a “neighbor” solution with a certain probability even if the current solution is better than the “neighbor” one. This feature enhances the stochastic search and global optimization abilities of the SA. Although Kirkpatrik et al. [63] provided a useful framework for the combinational optimization of large and complex systems based on the SA in 1983, SA has only been applied to operation optimization of natural gas pipelines since 2007.Zhang et al. [64] employed a hybrid GA and SA (GASA) algorithm to calculate the maximum operating benefit a large-scale gas pipeline network. The investigated pipeline network contains 98 nodes but no compressors. They found that the hybrid GASA has better performance than the improved complex algorithm. Rodríguez et al. [14] presented a research of using a metaheuristic algorithm called Simulated Annealing with GAMS (SAG) to optimize the layout of long-distance hydrocarbon pipelines. They show that SAG is robust because a high percentage of the near-optimal solutions can be found. For more topics with regard to the application of SA to other pipeline optimization problems, the readers are referred to Chen et al. [65], Samora et al. [66], and Zhou et al. [55].


### 3.5. Other Algorithms and Hybrid Ones

Some other algorithms also have been applied to solve the operation optimization problem of natural gas pipelines, including the Differential Evolution (DE) algorithm [67], Artificial Neural Networks (ANN) [47], Support Vector Machine (SVM) [68], and the Tabu Search (TS) algorithm [69]. Also, a lot of efforts have been made to alleviate inherent shortcomings of original stochastic algorithms by use of hybrid strategies which combine advantages of two or more stochastic algorithms yielding new hybrid optimization algorithms.DE, similar to GA, is an evolutionary algorithm composed of three operations, the mutation, crossover, and selection. However, DE is featured by its mutation process that creates a new solution by adding the weighted difference between two solutions to a third solution. Based on the literature survey, DE is often applied in some hybrid algorithms. Malamura and Murata [67] proposed a hybrid method by combing the Differential Evolution (DE), Genetic Algorithm (GA), and Hybrid Petri net (HPN) methods in order to solve the MFCP of gas networks. This hybrid algorithm is implemented based on the framework of DE, where firstly the HPN gets results in the reduction of complexity in the optimization problem formulation, then DE is used to optimize the continuous variables (flow rates for compressors in each station), and finally GA is applied to optimize the discrete variables (status of compressors) when DE reaches the optimal solution in each iteration. The proposed method reduces the complexity of the optimization problem. Also, it provides an effective way to deal with the optimization model containing discrete and continuous variables. Wu et al. [70] replaced the reproduction operator of the original GA with that of the Differential Evolution (DE) algorithm. The resulting hybrid DE-GA algorithm was applied to get the minimal annual operating cost of compressor stations of a pipeline network system associated with 11 pipes and 2 compressor stations. They demonstrated that the hybrid DE-GA method improves the global optimization ability and effectively overcomes the premature convergence of the original GA.SVM and ANN are mainly applied to fit or to forecast the pipeline’s operation parameters, such as the prediction of the gas load and the compressor’s performance [47, 68]. So, SVM and ANN are usually combined with other optimization algorithms when applied to solve the operation optimization problem of gas pipelines.Borraz-Sánchez and Ríos-Mercado [69] proposed a hybrid nonsequential DP (NDP) and Tabu Search method, namely, the NDPTS method to get the optimal flow rates and pressures in a natural gas pipeline. They used TS to find the best non-tabu list from an initial feasible set of flows, and then the NDP method determines the optimal pressures. The results demonstrated that the performance of the NDPTS has been improved by 1%–17% in terms of the solution speed and optimized values when compared with GRG and NDP methods.Besides, variations of many stochastic optimization algorithms have been developed in recent years and applied to other industry fields [71], but applications of them in the operation optimization of natural gas pipelines are rarely reported. On the other hand, hybrid algorithms take advantage of different stochastic algorithms; thus they have better theoretical foundations than some randomly improved algorithms [67, 70]. Hence, applying hybrid stochastic algorithms probably represents a development tendency of solving the operation optimization problems of natural gas pipelines.


### 3.6. Comparison of Stochastic Algorithms

Comparing different optimization algorithms provides insightful information to understand the advantages and disadvantages of each algorithm. Table1 gives the published literature related to the comparison of optimization algorithms used to solve operation optimization models of natural gas pipelines. Since the global optimization ability and the computation speed represent two main concerns of an optimization algorithm, almost all comparison focus on these two points.Table 1
Comparison of optimization algorithms for solving the operation optimization problems of natural gas pipelines.
Objective function Optimization algorithm Reference MFCP GA, SIMPLEX [49] MFCP GA, ES, MILP [72, 73] MFCP of integrated energy system NDPTS, DP, GRG [69] MFCP ACO, DP [13] MFCP and the maximum gas delivery GA,ε-constraint [23] MFCP GA, NDP [19] MFCP PSO, ACO, DP [27] The maximum operating benefit and the maximum gas delivery IAPSO, PSO-TVIW, HPSO-TVAC, MPSO-TVAC, CLPSO [15] MFCP ACO, GRG [20] MFCP PSO, GA [71]Table1 shows that comparisons between stochastic algorithms and gradient-based/dynamical programming methods are common. Comparisons between stochastic algorithms and gradient-based (e.g., GRG) methods will demonstrate the global optimization ability of stochastic algorithms due to the fact that gradient-based methods are prone to be entrapped into the local optimum. Arya and Honwad [20] used ACO and GRG to solve the MFCP of a gas pipeline with six compressors. The length of the pipeline is 300 km, the diameter is from 0.787 m to 0.889 m, and the mass flow rate is 150 kg/s. The results demonstrated that the ACO yields lower suction pressures and higher efficiencies of compressors in comparison with the results of GRG, resulting in the gas fuel saving of 0.015 kg/s and of approximately US$350,000 per year. Borraz-Sánchez and Ríos-Mercado [69] solved the MFCP of seven gas pipelines by use of NDPTS and GRG. It is observed that NDPTS yields significant better solutions than the GRG. The relative improvement of NDPTS over GRG is from 0.004% to 112.37% for seven cases.On the other hand, comparisons between stochastic algorithms and the dynamical programming methods (e.g., DP and NDP) are used to validate the final optimization results and to check the computation efficiency because the DP has the global optimization ability but extremely expensive computation cost. Almost all related comparisons show that stochastic optimization algorithms not only are able to find similar solutions in comparison to the gradient-based methods but also have higher computation efficiency than traditional deterministic algorithms [20, 23, 27, 49]. For example, Nguyen et al. [72, 73] simultaneously optimized the fuel cost, maintenance cost, startup cost, shut cost, and oversupply cost of all compressors by use of the mixed-integer linear programming (MILP), the expert system (ES), and the original GA provided in the MATLAB toolbox. Based on their research findings, MILP and GA give exactly the same results for the costs except for the startup cost, for which GA gives a slightly higher result. On the other hand, the ES generates worse results with higher costs for all these objectives. Sanaye and Mahmoudimehr [19] applied GA and NDP to solve the MFCP of one branched pipeline and two cyclic pipelines. They presented that the difference between objective values obtained from GA and NDP is in the range of 0–0.55%, which shows a very similar optimization result. However, the computing time of NDP exponentially increases with increasing of the pressure and flow rate step sizes, while the computing time of GA did not show such a dependency on these parameters. Under some specific conditions, the computing time of NDP is 20 times longer than that of GA. Chebouba et al. [13] found that, for the MFCP of gas pipelines, the difference between objective values obtained by the ACO and DP is less than 0.22% while the ACO is 14–27 times faster than the DP.Besides, comparisons of stochastic algorithms also have been reported in many published papers, which would provide guidance to select a proper optimization method. Published literature reveals that GA gives the similar optimization results as the ACO. Khademi and Khosravi [71] compared the performance of GA and PSO when applying to optimize a weighted summation of the total number of running compressor stations and their total fuel consumption. They showed that GA leads to more accurate results to match the real operating conditions of the pipeline. Zheng and Wu [27] presented the quantitative comparisons of ACO, PSO, and DP in terms of computing time and gas consumption amount when these methods are applied to solve the MFCP of a gas pipeline with five compressor stations, as shown in Figure 12. They found that the differences between the optimization results obtained by these three methods are in the range of 0–0.37%. However, the computing speed of the PSO is 8.52 times faster than that of the ACO. Moreover, the average computing time of DP method is about 8 times longer than that of the ACO.Figure 12
Comparison of computing time and gas consumption for a gas pipeline with five compressor stations optimized from PSO, ACO, and DP [27].Besides different kinds of stochastic optimization algorithms, variations of the same kind of stochastic algorithms show different optimization results as well as the convergence speed. Wu et al. [15] found that when IAPSO, PSO-TVIW, HPSO-TVAC, MPSO-TVAC, and CLPSO are applied to solve the maximum flow rate and maximum operation benefit of a gas pipeline, the difference between the optimal maximum flowrates goes from 2.94% to 6.98%, and the difference between the optimal operation benefit goes from 4.52% to 12.76%. Also, IAPASO presents the fastest convergence speed whereas the PSO-TVIW shows the slowest convergence speed, as depicted in Figure 11.In summary, the operation optimization model of natural gas pipelines is recognized as a MINLP model which is not easy to be solved even by previous mentioned stochastic algorithms. However, among GA, PSO, ACO, and SA algorithms, GA represents the most successful one over past thirty years in terms of the quality of the optimization results, the computation speed, and the ability of handling the discrete variables, whereas other three algorithms have been used only in recent ten years and their applications are relatively few. The GA and its extensions have been applied to a huge number of pipeline networks that are featured by different scales and topology structures including the gun barrel, the tree, and the cyclic networks. In particular, the NSGA-II has been taken as a standard algorithm for solving multiobjective optimization models in recent years [31, 50]. Nevertheless, it should be noted that stochastic algorithms cannot guarantee the global optimum and the premature convergence problem is naturally a feature of these algorithms.


## 3.1. Genetic Algorithm (GA)

The Genetic Algorithm (GA) is a kind of metaheuristic search algorithm based on the Darwinian’s evolutionary ideas of natural selection and genetics [36], which was first applied to solve the operation optimization problems of natural gas pipeline in 1987 by Goldberg [43]. GA starts from a population of individuals that represent feasible solutions of the optimization problem, where each individual is represented by a chromosome composed of all the optimization variables, as shown in Figure 8. The optimal solution is then obtained by implementing procedures of the selection, crossover, and mutation on the original individuals (chromosomes) through consecutive generations. In each generation, a fitness function related to the objective function and constraints is firstly used to evaluate the fitness value of each individual. The individuals having higher fitness values are more likely to be selected as parents to generate new individuals in the next generation, and some of the individuals having lower fitness values are dropped. Then, the crossover operator is applied to recombine different portions of selected individuals. As a result, some better candidate individuals might be created in the next generation. Finally, the mutation operator is randomly applied to some individuals, yielding the enhancement of the global search ability of the algorithm. These procedures are repeated until all individuals reach a satisfactory fitness value, or alternatively, say that until the algorithm converges [44].Figure 8
Schematic diagram of the chromosome of GA [19]. Each chromosome is composed of all variables in the optimization model.Goldberg [43] firstly applied GA to solve the natural gas pipeline optimization problem. He built an operation optimization model for a natural gas pipeline system with forty compressors for the purpose of minimizing the total power of all compressors. He assumed that the compressors’ efficiencies and head rises are constants; thus the variables to be optimized are the compressors’ running statuses. After that, the initial population consisting of 100 individuals that represent all compressors’ statuses was generated. The crossover probability and mutation probability were set to 0.7 and 0.01, respectively. Computations show that near-optimal results are obtained after 50 generations of evolution. In particular, even three different initial populations are applied, they finally yield similar optimal results, which shows a good convergence and reproducibility. Goldberg [45] later extended the GA to the transient optimization of a single line pipeline. He suggested that GAs are ready for application to other more difficult optimization cases.Based on Goldberg’s achievements, the most important progress focuses on using newly improved GAs to solve the optimization problems. Li et al. [24] used an adaptive genetic algorithm (AGA) proposed by Srinivas and Patnaik [46] to solve the pipeline operation optimization problem. The AGA method dynamically adjusts the crossover and mutation probabilities according to the average fitness of the population, the maximum fitness of all individuals so far, and the fitness of a specified individual, which yields lower crossover and mutation probabilities when the specified individual is closer to the best individual so far. Therefore, the historical information belonging to “better individuals” is retained, and the convergence performance can be significantly enhanced in comparison to the original GA. Li et al. [24] reported a successful application of the AGA to a pipeline network consisting of 22 pipes and 21 nodes. However, there are no compressors in the example studied and, also, they did not compare the performance of the AGA with other existing GAs. Sanaye and Mahmoudimehr [19] applied the GA to solve the MFCP problem of three types of natural gas transmission network including the linear, branched, and cyclic pipeline structures. A detail compressor model associated with the pressure, efficiency, stonewall and surge curves, and related correction parameters is presented. Sanaye and Mahmoudimehr [19] presented that the GA has higher computation speed in comparison to the nonsequential dynamic programming (NDP) because the NDP’s computing time exponentially depends on pressure and flow rate step sizes, as shown in Figure 9. MohamadiBaghmolaei et al. [47] used the GA to solve the MFCP of a real 56-inch pipeline involving four boosting units located in the south of Iran. They developed an Artificial Neural Network (ANN) model to describe the relationship between compressor’s flow rate, head rise, and rotation speed instead of using the conventional compressor’s equations as previously mentioned.Figure 9
Comparison of required computing time for NDP and GA methods [19]. (a) Required computing time for the NDP method; (b) required computing time for the GA method.
(a) (b)In addition to the single-objective optimization, significant achievements have been reached with regard to the multiobjective optimization by use of GAs. Botros et al. [48] reported several successful multiobjective optimization cases of applying GAs to large-scale pipeline networks operated by TransCanada Pipeline Ltd. They considered four different objectives: (a) minimizing fuel consumption, (b) minimizing fuel consumption while maximizing gas delivery amount, (c) minimizing line pack while maximizing gas delivery amount, and (d) maximizing line pack while maximizing gas delivery amount. In comparison to Goldberg’s model [43], this model accounts for the constraints associated with the compressors’ surge and stonewall curves related to the compressors’ flow rates and rotation speeds. They built the fitness function by incorporating the objective function and constraints in the penalty function manner, which is shown to be sufficient enough for these optimization problems studied. This method was successfully applied to two pipeline networks. One of them has 10 compressor stations and 20 optimization variables, while another one has 25 compressor stations, resulting in 54 decision variables. The optimization results are given by Pareto fronts. However, when evaluating 50000 design cases, the total computing time is approximately one day, which indicates a relative expensive computation cost. Later, they researched more improved methods to enhance the computation efficiency, such as the hybrid GA and gradient-based algorithm and the parallel processing technical [49]. These improved methods were incorporated into an automated optimization system belonging to TransCanada Pipeline Ltd.More recently, a novel Nondominated Sorting Genetic Algorithm II (NSGA-II) has attracted growing attentions for solving the multiobjective operation optimization problem [50]. NSGA-II uses a fast nondominated sorting approach, which reduces the amount of computation from O (mn3) (m refers to the number of objectives and n refers to population size) in the NSGA to O (mn2). Also, an elitism strategy is adopted in NSGA-II, ensuring some good individuals not to be discarded in the evolutionary process. Finally, NSGA-II applies the fast crowded distance estimation procedure and simple crowded comparison operator, overcoming the problem of the NSGA that requires the specification of a sharing parameter. As a result, it is able to find a much better spread of solutions and better convergence near the true Pareto-optimal front in comparison to the Pareto-archived evolution strategy and strength-Pareto evolutionary algorithms [51].Rodriguez et al. [23] used the NSGA-II to simultaneously optimize the maximum gas delivery amount, the minimum fuel consumption, and related CO2 emissions amount of compressors. The Pareto front obtained from the multiobjective optimization algorithm can be served to determine the minimum and maximum line pack while considering the gas delivery and CO2 emission amount. Also, the results offer a practical way to determine the minimal CO2 emission amount for a given gas delivery amount by operating compressor stations in appropriate manners. Alinia Kashani and Molaei [18] employed the NSGA-II algorithm to balance the maximum gas delivery amount, the maximum line pack, and the minimum operating cost for a pipeline consisting of two gas sources, ten pipe segments, and five compressors. In this model, the gas flow rates and pressures of gas sources, the statuses, and rotational speeds of compressors are taken as optimization variables. Hu et al. [31] used the NSGA-II algorithm to solve a multiobjective optimization model for planning the combined gas and electricity network. Both of the investment cost and the production cost of the combined system are minimized. In particular, a fuzzy decision approach is employed to select the final optimal solution from the resulting Pareto front.In summary, GAs have been extensively involved in solving the optimal operation problems of natural gas pipelines over past 30 years. The feasibility and effectiveness of GAs also have been proven by a number of worldwide successful industry projects. More recently, the NSGA-II is shown to be a promising algorithm for solving multiobjective optimization models for natural gas pipelines [18, 31].


## 3.2. Particle Swarm Optimization (PSO) Algorithm

The Particle Swarm Optimization (PSO) algorithm is an evolutionary optimization algorithm inspired by the movement of organisms in a flock of birds or a school of fish [52]. Similar to GA, the candidate solutions in PSO are composed of a population of particles spread in the solution space. Each particle is featured by a position and a velocity, where the position represents a feasible solution for the optimization problem in the multidimensional solution space, and the velocity moves the particle itself from one position to another position over consecutive iterations. At each iteration step, every candidate particle is quantitatively evaluated by use of a fitness function. During this process, every particle records its personal best position searched so far, and the particle having the best fitness value around the neighborhood is marked as the global/local best particle. The move speed of each particle is determined by the current motion, the personal best position, and the global best position, as shown in Figure 10. Thus, all the particles are prone to move to the region with the highest fitness value. By repeating the moving process, all the particles will eventually aggregate in the highest fitness value region, which indicates the convergence of the PSO algorithm. Since the PSO makes few assumptions regarding the problems to be optimized, it is able to search very large solution spaces.Figure 10
A schematic for the position updating of a particle [26]. xik represents the position of the ith particle at the kth step, namely, the old position; xik+1 is the new position; vik is the current speed; pi, pk refer to the personal and global best positions, respectively. The move speed vik+1 is calculated from the current speed and swarm influence.The PSO algorithms cannot guarantee the global optimum solution because of the premature problem that indicates the particles converge to a local optimum region rather than a global one. Thus, some improvement strategies have already been applied to either the PSO algorithm itself or the optimization model in order to alleviate its premature problem. In fact, the prematurity is naturally a feature of many other algorithms, such as GA and ACO as will be discussed later.Adjusting the inert weight represents a growing concern in reducing the optimization problem by use of the PSO algorithm. The inert weight represents the effect of the current motion of the particle on the movement of the next step. A higher inert weight indicates that the current motion has a greater effect on the movement of the particle. Li et al. [53] used the PSO algorithm to solve the MFCP of natural gas pipeline networks in which the relaxed gas flow equations are used as constraints. The relaxed flow equations accept approximate solutions of the flow equations as candidate particles, which enlarges the solution searching domain of this PSO algorithm in comparison with the method of using the rigorous flow equations. They presented that, under the same initial conditions and required accuracy, the proposed method and the simplex algorithm give the optimal gas consumption amounts of 1.52 m3/s and 1.5528 m3/s, respectively. The results demonstrate that the PSO algorithm is able to find higher quality solutions in comparison with the LP method. Zheng and Wu [27] presented an improved PSO to solve the MFCP of gas pipelines. A method based on an exponential function is employed to change the inert weight of PSO with the evolution generation, which essentially enhances the global search ability and the convergence speed in comparison to the original PSO algorithm. That is, at the beginning, the inertia weight is a large value that enables the PSO algorithm to search large solution spaces, thus avoiding the premature convergence problem. After a certain number of evolution generations, all the particles tend to converge to the near-optimal domain; thus a small inertia weight is used to speed up the convergence. They tested this new method by applying it to a pipeline system with up to 17 compressor stations. The results show that the relative errors of the optimization results given by the improved PSO, ACO, and DP algorithms are less than 1%, whereas the computation cost of the PSO is 4 to 8 times less than that of the ACO and 170 times less than that of the DP. These comparisons show that the proposed PSO algorithm has a high computation efficiency while keeping the similar optimization results.Wu et al. [15] used an inertia-adaptive PSO (IAPSO) to solve a biobjective optimization model that considers the maximum operating benefit and the maximum gas delivery amount. The IAPSO automatically increases the inertia weight of PSO when the particle is apart from the global best value and conversely and decreases the inertia weight when the particle is approaching the global best value. This adaptive adjustment method gives the IAPSO stronger global search ability when candidate particles are apart from the global best position so far. This method was applied to a pipeline with four compressor stations and compared to five other PSO algorithms including the PSO-TVIW, HPSO-TVAC, MPSO-TVAC, and CLPSO algorithms [54]. They presented that the IAPSO not only shows faster convergence speed but also gives better optimization results in terms of the biobjective functions, as shown in Figure 11. These results show that the PSO algorithm should be well designed to get the better optimization solution. In other words, the final optimization results are dependent on how the original PSO is improved.Figure 11
The converge curves of different PSO algorithms for an operation optimization problem of a natural gas pipeline [15].In addition to apply the PSO to solve the operation optimization problems of natural gas pipelines, there are also a number of successful applications in the fields of the operation optimization of oil pipeline [55], the layout optimization of the oil and gas pipelines [56], and the optimal control of compressors [57]. Although these optimization problems are different from the operation optimization of gas pipelines, they also mentioned that some specific techniques should be adopted to overcome the premature shortcoming when using the original PSO.In summary, the PSO is featured by its high computation speed. Nevertheless, how to alleviate the premature defect of the original PSO algorithm is quite challenging since the main idea in PSO resembles the overall idea in gradient search methods, but adapted to a population. Actually, the parameters setting (e.g., the number of particles and the maximum number of function evaluations) affects the final performance of the PSO algorithm when solving the MINLP problem [15].


## 3.3. Ant Colony Optimization (ACO) Algorithm

The Ant Colony Optimization (ACO) algorithm is a nature-inspired optimization method proposed by Dorigo in 1992 [58]. This method mimics the process of ants searching for the shortest path between the nest and the food source. At the beginning, a school of ants starts from their nest to randomly search for food in the region around the nest. If one ant succeeds in finding food, it goes back to the nest and leaves a chemical pheromone trail along the searching path. The other ants will follow the path identified by the pheromone trail, so all the ants will be able to find the same food source in the shortest way [59]. The two critical procedures of the ACO algorithm are the edge selection and pheromone updating. Each edge represents a feasible solution consisting of the optimization variables. The initial edges are developed by the random search of ants. All edges construct the multidimensional solution space for the optimization problem. The ants move along the edges and left pheromone in edges during the iteration process. The edge with a higher level of pheromone is more likely to be selected by ants, and, in turn, more pheromone is left if more ants pass through one edge [60].Chebouba et al. [13, 60] are the first people who solve operation optimization problems of natural gas pipelines by use of the ACO algorithm. They used a two-stage technique (local updating and global updating) to update the pheromone trail, yielding an improved two-stage ACO algorithm. This method was applied to solve the MFCP of the Hassi R’mel-Arzew gas pipeline involving one gas source, one gas user, six pipes, and five compressor stations. Computations show that the relative errors between ACO results and DP results are typically less than 1%, but the computation speed of ACO is more than 14 times faster than that of the DP. These achievements prove the feasibility of applying the ACO to solve the gas pipeline optimization problem. In 2012, Chebouba and Meglouli [42] used a combined ANN and ACO algorithm to optimize the number of operating compressor and related discharge pressures of a gas pipeline system under the steady-state assumption. In comparison to the previous work, they used the ANN method to describe the compressor’s performance rather than the nonlinear equations mentioned in Section 2.2. MohamadiBaghmolaei et al. [47] also employed the ANN to calculate the compressor’s performance, but they used the GA as the optimization algorithm instead of the ACO.Arya and Honwad [20] applied the original ACO to solve the MFCP of a pipeline network involving 18 nodes, 2 compressor stations, and 3 identical compressors in each station. Under the fixed gas flow rate, the fuel costs calculated by the ACO and GRG methods were compared. They presented that the ACO is able to lead a further fuel savings of 0.015 kg/s and a total economic saving of nearly US $ 350,000 per year in comparison to the results calculated by the GRG method. These results demonstrate that ACO yields higher quality solutions in comparison with the GRG method. However, to the best of our knowledge, ACO has not been implemented in systems with more complicated pipelines so far.


## 3.4. Simulated Annealing (SA) Algorithm

Annealing in metallurgy technical is a process involving heating and controlled cooling of a material in order to change the properties of crystals and to reduce defects of a material [61]. According to the thermodynamic theory, the heating process increases the thermodynamic free energy of the metal material, and the cooling process decreases the thermodynamic free energy. Eventually, the thermodynamic free energy will drop to a global minimum value when the material reaches the equilibrium state. Inspired by such processes, Khachaturyan et al. [62] proposed the Simulated Annealing (SA) algorithm in 1979 that approximates the global optimum of a specified function in a probabilistic searching manner. That is, an energy function is analogous to the thermodynamic free energy of the system and acts as an objective function of the optimization problem. During the cooling process, a current solution can be replaced with a “neighbor” solution with a certain probability even if the current solution is better than the “neighbor” one. This feature enhances the stochastic search and global optimization abilities of the SA. Although Kirkpatrik et al. [63] provided a useful framework for the combinational optimization of large and complex systems based on the SA in 1983, SA has only been applied to operation optimization of natural gas pipelines since 2007.Zhang et al. [64] employed a hybrid GA and SA (GASA) algorithm to calculate the maximum operating benefit a large-scale gas pipeline network. The investigated pipeline network contains 98 nodes but no compressors. They found that the hybrid GASA has better performance than the improved complex algorithm. Rodríguez et al. [14] presented a research of using a metaheuristic algorithm called Simulated Annealing with GAMS (SAG) to optimize the layout of long-distance hydrocarbon pipelines. They show that SAG is robust because a high percentage of the near-optimal solutions can be found. For more topics with regard to the application of SA to other pipeline optimization problems, the readers are referred to Chen et al. [65], Samora et al. [66], and Zhou et al. [55].


## 3.5. Other Algorithms and Hybrid Ones

Some other algorithms also have been applied to solve the operation optimization problem of natural gas pipelines, including the Differential Evolution (DE) algorithm [67], Artificial Neural Networks (ANN) [47], Support Vector Machine (SVM) [68], and the Tabu Search (TS) algorithm [69]. Also, a lot of efforts have been made to alleviate inherent shortcomings of original stochastic algorithms by use of hybrid strategies which combine advantages of two or more stochastic algorithms yielding new hybrid optimization algorithms.DE, similar to GA, is an evolutionary algorithm composed of three operations, the mutation, crossover, and selection. However, DE is featured by its mutation process that creates a new solution by adding the weighted difference between two solutions to a third solution. Based on the literature survey, DE is often applied in some hybrid algorithms. Malamura and Murata [67] proposed a hybrid method by combing the Differential Evolution (DE), Genetic Algorithm (GA), and Hybrid Petri net (HPN) methods in order to solve the MFCP of gas networks. This hybrid algorithm is implemented based on the framework of DE, where firstly the HPN gets results in the reduction of complexity in the optimization problem formulation, then DE is used to optimize the continuous variables (flow rates for compressors in each station), and finally GA is applied to optimize the discrete variables (status of compressors) when DE reaches the optimal solution in each iteration. The proposed method reduces the complexity of the optimization problem. Also, it provides an effective way to deal with the optimization model containing discrete and continuous variables. Wu et al. [70] replaced the reproduction operator of the original GA with that of the Differential Evolution (DE) algorithm. The resulting hybrid DE-GA algorithm was applied to get the minimal annual operating cost of compressor stations of a pipeline network system associated with 11 pipes and 2 compressor stations. They demonstrated that the hybrid DE-GA method improves the global optimization ability and effectively overcomes the premature convergence of the original GA.SVM and ANN are mainly applied to fit or to forecast the pipeline’s operation parameters, such as the prediction of the gas load and the compressor’s performance [47, 68]. So, SVM and ANN are usually combined with other optimization algorithms when applied to solve the operation optimization problem of gas pipelines.Borraz-Sánchez and Ríos-Mercado [69] proposed a hybrid nonsequential DP (NDP) and Tabu Search method, namely, the NDPTS method to get the optimal flow rates and pressures in a natural gas pipeline. They used TS to find the best non-tabu list from an initial feasible set of flows, and then the NDP method determines the optimal pressures. The results demonstrated that the performance of the NDPTS has been improved by 1%–17% in terms of the solution speed and optimized values when compared with GRG and NDP methods.Besides, variations of many stochastic optimization algorithms have been developed in recent years and applied to other industry fields [71], but applications of them in the operation optimization of natural gas pipelines are rarely reported. On the other hand, hybrid algorithms take advantage of different stochastic algorithms; thus they have better theoretical foundations than some randomly improved algorithms [67, 70]. Hence, applying hybrid stochastic algorithms probably represents a development tendency of solving the operation optimization problems of natural gas pipelines.


## 3.6. Comparison of Stochastic Algorithms

Comparing different optimization algorithms provides insightful information to understand the advantages and disadvantages of each algorithm. Table1 gives the published literature related to the comparison of optimization algorithms used to solve operation optimization models of natural gas pipelines. Since the global optimization ability and the computation speed represent two main concerns of an optimization algorithm, almost all comparison focus on these two points.Table 1
Comparison of optimization algorithms for solving the operation optimization problems of natural gas pipelines.
Objective function Optimization algorithm Reference MFCP GA, SIMPLEX [49] MFCP GA, ES, MILP [72, 73] MFCP of integrated energy system NDPTS, DP, GRG [69] MFCP ACO, DP [13] MFCP and the maximum gas delivery GA,ε-constraint [23] MFCP GA, NDP [19] MFCP PSO, ACO, DP [27] The maximum operating benefit and the maximum gas delivery IAPSO, PSO-TVIW, HPSO-TVAC, MPSO-TVAC, CLPSO [15] MFCP ACO, GRG [20] MFCP PSO, GA [71]Table1 shows that comparisons between stochastic algorithms and gradient-based/dynamical programming methods are common. Comparisons between stochastic algorithms and gradient-based (e.g., GRG) methods will demonstrate the global optimization ability of stochastic algorithms due to the fact that gradient-based methods are prone to be entrapped into the local optimum. Arya and Honwad [20] used ACO and GRG to solve the MFCP of a gas pipeline with six compressors. The length of the pipeline is 300 km, the diameter is from 0.787 m to 0.889 m, and the mass flow rate is 150 kg/s. The results demonstrated that the ACO yields lower suction pressures and higher efficiencies of compressors in comparison with the results of GRG, resulting in the gas fuel saving of 0.015 kg/s and of approximately US$350,000 per year. Borraz-Sánchez and Ríos-Mercado [69] solved the MFCP of seven gas pipelines by use of NDPTS and GRG. It is observed that NDPTS yields significant better solutions than the GRG. The relative improvement of NDPTS over GRG is from 0.004% to 112.37% for seven cases.On the other hand, comparisons between stochastic algorithms and the dynamical programming methods (e.g., DP and NDP) are used to validate the final optimization results and to check the computation efficiency because the DP has the global optimization ability but extremely expensive computation cost. Almost all related comparisons show that stochastic optimization algorithms not only are able to find similar solutions in comparison to the gradient-based methods but also have higher computation efficiency than traditional deterministic algorithms [20, 23, 27, 49]. For example, Nguyen et al. [72, 73] simultaneously optimized the fuel cost, maintenance cost, startup cost, shut cost, and oversupply cost of all compressors by use of the mixed-integer linear programming (MILP), the expert system (ES), and the original GA provided in the MATLAB toolbox. Based on their research findings, MILP and GA give exactly the same results for the costs except for the startup cost, for which GA gives a slightly higher result. On the other hand, the ES generates worse results with higher costs for all these objectives. Sanaye and Mahmoudimehr [19] applied GA and NDP to solve the MFCP of one branched pipeline and two cyclic pipelines. They presented that the difference between objective values obtained from GA and NDP is in the range of 0–0.55%, which shows a very similar optimization result. However, the computing time of NDP exponentially increases with increasing of the pressure and flow rate step sizes, while the computing time of GA did not show such a dependency on these parameters. Under some specific conditions, the computing time of NDP is 20 times longer than that of GA. Chebouba et al. [13] found that, for the MFCP of gas pipelines, the difference between objective values obtained by the ACO and DP is less than 0.22% while the ACO is 14–27 times faster than the DP.Besides, comparisons of stochastic algorithms also have been reported in many published papers, which would provide guidance to select a proper optimization method. Published literature reveals that GA gives the similar optimization results as the ACO. Khademi and Khosravi [71] compared the performance of GA and PSO when applying to optimize a weighted summation of the total number of running compressor stations and their total fuel consumption. They showed that GA leads to more accurate results to match the real operating conditions of the pipeline. Zheng and Wu [27] presented the quantitative comparisons of ACO, PSO, and DP in terms of computing time and gas consumption amount when these methods are applied to solve the MFCP of a gas pipeline with five compressor stations, as shown in Figure 12. They found that the differences between the optimization results obtained by these three methods are in the range of 0–0.37%. However, the computing speed of the PSO is 8.52 times faster than that of the ACO. Moreover, the average computing time of DP method is about 8 times longer than that of the ACO.Figure 12
Comparison of computing time and gas consumption for a gas pipeline with five compressor stations optimized from PSO, ACO, and DP [27].Besides different kinds of stochastic optimization algorithms, variations of the same kind of stochastic algorithms show different optimization results as well as the convergence speed. Wu et al. [15] found that when IAPSO, PSO-TVIW, HPSO-TVAC, MPSO-TVAC, and CLPSO are applied to solve the maximum flow rate and maximum operation benefit of a gas pipeline, the difference between the optimal maximum flowrates goes from 2.94% to 6.98%, and the difference between the optimal operation benefit goes from 4.52% to 12.76%. Also, IAPASO presents the fastest convergence speed whereas the PSO-TVIW shows the slowest convergence speed, as depicted in Figure 11.In summary, the operation optimization model of natural gas pipelines is recognized as a MINLP model which is not easy to be solved even by previous mentioned stochastic algorithms. However, among GA, PSO, ACO, and SA algorithms, GA represents the most successful one over past thirty years in terms of the quality of the optimization results, the computation speed, and the ability of handling the discrete variables, whereas other three algorithms have been used only in recent ten years and their applications are relatively few. The GA and its extensions have been applied to a huge number of pipeline networks that are featured by different scales and topology structures including the gun barrel, the tree, and the cyclic networks. In particular, the NSGA-II has been taken as a standard algorithm for solving multiobjective optimization models in recent years [31, 50]. Nevertheless, it should be noted that stochastic algorithms cannot guarantee the global optimum and the premature convergence problem is naturally a feature of these algorithms.


## 4. Research Challenges

Application of stochastic algorithms contributes to the technical breakthrough of solving the resulting MINLP problem. However, there are still quite a few areas that pose a wide range of challenges.The first research challenge focuses on the improvement of the optimization model. The objective functions in existing models mainly cover the economic benefit and environment aspects, such as the gas delivery amount, the line package, the fuel consumption, the CO2 emission amount, and the pipeline operating and management costs. Besides these objectives, recently, the pipeline safety has attracted increasing concerns because the pipeline failure would cause severe disasters and economic loss [74]. Adding the pipeline reliability objective (e.g., the gas hydrate formation risk and the pipe rupture risk) to existing models is a promising way to simultaneously optimize the pipeline operating economic, environmental, and safety aspects [3], as shown in Figure 13. This work will require further research on the quantitative risk assessment and related failure probability predictions and failure consequence computations [75]. Since the safety objective has a different dimension with existing objective functions, a proper decision method should be developed to select the best solution from the Pareto front if a multiobjective objective function is used.Figure 13
The development of optimization objectives.In addition to the objective functions, constraints still need to be improved to match the pipeline’s real operating cases. Since some constraints use the simplified forms of the gas flow governing equations, they cannot precisely describe the pipe flow. As a result, the optimization results cannot completely satisfy the real pipeline’s hydraulic and thermal constraints. Although using the original governing equations in the optimization model is more likely to get optimization results that satisfy the pipeline’s real operating conditions, it makes the model itself extremely complicated. A practical method to solve this problem is combining the pipeline simulation model and the optimization model. That is, once the optimization results are obtained from the optimization model, the simulation model is then applied to adjust the optimized parameters that deviate from the simulation models. Considering that the simulation is time-consuming, the simulation method is recommended to be performed every certain number of optimization iterations rather than applying it to each candidate solution at each optimization iteration. The flow chart of combing the pipeline simulation and optimization models is depicted in Figure14. Except for validating the optimization results, the simulation methods also can offer the initial candidate solutions for stochastic algorithms, as presented by Wu et al. [15].Figure 14
The flow chart of combining simulation and optimization models.The second challenge is developing robust and efficient optimization algorithms. The strong global optimization ability and high computation efficiency are two most important concerns of stochastic optimization algorithms. Among GA, PSO, ACO, and SA algorithms, only the GA has been extensively applied in industries. The other three algorithms have not been thoroughly studied. Since many parameters in these algorithms influence the global search ability and the convergence speed, the sensitivity analysis of related parameters should be firstly researched subject to different cases. The expected achievements will yield general rules to set optimal parameters for these algorithms. Then, the performances of these algorithms need to be investigated in order to figure out the applicable ranges of each algorithm, which will eventually provide a guidance to select a proper optimization algorithm for a specified case. Based on the sensitivity analyses and comparison of different algorithms, the improvement methods should be researched to overcome some shortcomings of existing optimization algorithms. Hybrid stochastic algorithms could contribute to the significant improvements of the original methods because they combine the advantages of different methods, such as the hybrid SA-GA [70] and DE-GA [64] algorithms. However, published literature regarding this topic is limited. Many hybrid strategies have not yet been applied to the pipeline optimization, such as the hybrid GA-PSO [76] and GA-ACO [77] algorithms. Moreover, most of the published literature focuses on solving the optimization model for a gun barrel or a branched pipeline system. The optimization method for the more complicated cyclic pipeline systems also should be researched.The third challenge is researching the online optimization technology. The supervisory control and data acquisition (SCADA) system has already been widely installed on pipelines. Combining the online simulation technology and the pipeline operation optimization technology yields an online optimization technology, which is a promising way to make full use of optimization results [78]. The framework of this technology is shown in Figure 15. With the online optimization technology, the actual pipeline operating data collected from the SCADA system can be set as the initial candidate solutions of stochastic algorithms, and, in turn, the optimization results give useful information to optimally adjust the pipeline. Moreover, a decision-making system makes a decision on whether the suggested optimal operating scheme is adopted or not. Obviously, how to connect the simulation model, optimization model, and the SCADA system is a core problem that needs to be solved when developing an online optimization technology.Figure 15
The framework of the online optimization technology.The fourth challenge is the research of the transient optimization for natural gas pipelines. Although the previously introduced quasisteady optimization methods can obtain the approximate results of transient optimization, it cannot precisely depict the real transient process. Published literature introduced that the biggest difference between the steady-state and transient optimization problems is the increasing of the constraint equations and decision variables. A transient optimization requires the use of partial differential equations involving the continuity, energy, and momentum equations to describe the change of related decision variables, such as gas flow, velocity, density, pressure, and temperature, with time. As a result, the inherent complexity of the optimization problem has been increased. However, stochastic optimization algorithms have already shown potential advantages over classical optimization algorithms when solving the transient problems. Chebouba [38] used the NSGA-II solver embedded in the modeFRONTIER optimization software to firstly maximize the line pack and secondly to minimize the total power of a pipeline in a period of 24 hours. They presented that this method is able to minimize the CO2 emission since the CO2 emission amount has a positive relationship with the compressor’s power. Mahlke et al. [79] used the SA to solve the MFCP of a transient natural gas pipeline. They built the energy function by incorporating the objective function and all constraints by use of a penalty function. Many necessary details with regard to performing the SA procedures were presented, including the design of the neighborhood structure, step size selection, generation of the initial feasible solution, and cooling scheme. Besides, in order to enlarge the solution space to be searched, gas flow governing equations are relaxed by adding appropriate penalty factors. In particular, they used piecewise linear functions to approximate the nonlinear equations in the optimization model. Based on these special strategies, they proposed a combinational SA and a branch-and-cut algorithm which is tested by three real-world cases involving 11 to 31 pipes and 3 to 15 compressor stations provided by the German gas company E.ON Ruhrgas AG. It can be concluded that applying the stochastic optimization algorithms will contribute to the development of transient optimization of natural gas pipelines. In summary, works on this area are still in a developing phase [4].Nowadays, energy network, which is a new concept and includes several infrastructures such as electrical and gas networks, has been proposed [80]. The electrical generation and gas production are named as sources, and all the consumers take energy from the energy hubs. The introduction of the conversion between different energies (electrical and natural gas) makes the energy network highly flexibility to fully utilize all the energies. With this regard, the term “energy flow” is adopted to refer to terms “power flow” and “gas flow.” The aim of the operation focuses on how to simultaneously optimize the different types of energy networks such as the electrical network and the gas network, as depicted in Figure 16.Figure 16
The schematic of solving the operation optimization problem of the energy network [34].In general, the optimization model of the energy network is a nonconvex, nonsmooth, nondifferential, high-dimensional, and highly nonlinear optimal energy flow model. It is extremely difficult to solve. Most recently, Derafshi Beigvand et al. [34] presented that the Gravitational Search Algorithm, PSO, GA, and DE are able to solve the operation optimization model of the energy network involving the electrical and gas networks. Since many hybrid optimization algorithms and variations of the basic PSO, GA, and DE algorithms have already shown advantages over the basic optimization algorithms when solving the operation optimization problem of natural gas pipelines, these hybrid and extended stochastic optimization algorithms are expected to solve the operation optimization of energy networks in the future.


## 5. Conclusions

We reviewed important progress on steady-state operation optimization models of natural gas pipelines and solutions methods based on stochastic algorithms including the GA, PSO, ACO, SA, and other algorithms. The operation optimization model is confirmed to be a mixed-integer nonlinear programming (MINLP) model consisting of a nonconvex feasible region and mixing of continuous, discrete, and integer optimization variables. Current optimization models cover objectives involving the gas delivery amount, the line pack, the compressor’s fuel cost, the management cost, and the CO2 emission amount. However, the pipeline safety is receiving less attention. Adding the pipeline safety objective function is a promising way to simultaneously optimize the pipeline operating economic, environmental, and safety concerns.Since 1985, stochastic optimization algorithms have contributed to the technical breakthrough of solving the MINLP problem due to their advantages of handling discrete variable and of higher computation speed over classical optimization algorithms. In particular, GA and its extensions have been successfully applied to a large number of industry cases that are featured by different scales and topology structures including the gun barrel, the tree, and the cyclic networks, and the new NSGA-II algorithm is promising to solve the multiobjective operation optimization problems of natural gas pipelines. Although applications of PSO, ACO, and SA algorithms are relatively few, PSO has already shown much higher computation speed than the GA and ACO. However, the premature problem of all these stochastic optimization algorithms remains unsolved. Moreover, the hybrid algorithms would provide useful methods to alleviate the shortcomings of existing algorithms because the hybrid strategies combine advantages of two or more stochastic algorithms, but related applications with regard to the operation optimization problems of the gas pipeline are rarely reported.The online optimization technology that integrates the optimization model, the simulation model, the decision-making system, and the SCADA system is a promising way of making use of the optimization results. The pipeline operation data provides initial candidate solutions for the optimization model, and, in turn, the optimization results provide useful information for the pipeline control. Moreover, research challenges involving the transient optimization and operation optimization of the integrated energy network are discussed.



---

*Source: 1267045-2018-04-12.xml*