Designing straight gunbarrel pipelines
To facilitate the calculation of the design of a pipeline, gas engineers proposed to reduce the high number of alternatives by applying criteria based on previ-ous experiences and/or usual engineering practices. A first class of procedures is a trial and error process among several candidate designs proposed beforehand (Mohitpour, Golshan and Murray ). For that purpose, Lang  highlights the usefulness of simulation softwares to assess what is the best trade-oﬀ between com-pressor costs and pipeline costs. A second approach is to establish some optimal properties to reduce the number of variables. Hence, Cheeseman  states that the compression ratios giving the minimum energy consumption should be equal for each station. Kabirian and Hemmati  assume that the new compressor stations are located in the middle of pipes. In the French handbook of Chapon on design and construction of gas trans-portation networks”, the following assumptions are made:
• the layout is horizontal,
• the flowrate Q is constant along the pipeline,
• the number of compressor stations is known.
Besides, the power is approximated by a specific logarithmic formulation. In this case, Chapon asserts, without any proof, that the resolution of the pipeline design problem with diﬀerential calculation leads to the following optimal char-acteristics of the network:
• diameters are equal on each pipeline segments (including the terminal seg-ments)
• discharge pressures for all compressor stations are equal to the maximum admissible operational pressure of the pipelines.
• compressor stations are equidistant, and hence, compressor ratios are equal.
Thanks to these properties, the computation is strongly simplified with only two remaining variables to determine: one optimal diameter and one op-timal compression ratio for the whole pipeline. Then, it is only necessary to select the right number of compressor stations which minimizes the associated costs. Bouckly  presents a partial proof of the above properties but the argu-ments were not very clear and always limited to the Chapon’s framework. In his PhD thesis, Hafner  does not discuss the validity of these assertions and only details the calculation’steps of the two last remaining variables. More recently, Ainouche  based his cost analysis on the same properties.
First attempts to apply OR techniques
Edgar et al.  were the first to apply mathematical programming techniques to such an open-ended problem. They considered the minimization of the total cost of operation per year including the capital cost in their objective function against which the above parameters are to be optimized. The capital cost of the compressor stations was either a linear function of the horsepower or a linear function of the horsepower with a fixed capital outlay for zero horsepower to account for installation, foundation, and other costs. The first cost relationship allowed direct application of non linear programming techniques, but it did require the initial postulation of compressor location. The technique, when converged, indicated which compressor stations should be deleted. They solved the second scenario using the branch and bound technique to handle the integer variables which are the number of compressors. They applied their techniques not only to gunbarrel pipelines but also to branched systems (with fixed branch lengths). Soliman and Murtagh  showed that a commercial nonlinear solver (MINOS, ) could be used to solve large instance of the continuous pipeline design problem (without fixed installation outlay) within moderate computing times. More recently, Babu, et al.  applied Diﬀerential Evolution, an evolutionary computation technique, to the same problem and example as Edgar et al. . Both scenarios above mentioned have been solved by these population based-search algorithms. They found optimal costs closed to the cost of Edgar et al. but the optimal variables were less close to their bounds than with Edgar et al.
OR methods overview applied to pipeline network design
On the pipe networks (water, gas, hydrogen), the capacities are given by the non linear relations linking the flow and the pressures at the two ends of the pipe. The first works of design of networks of pipelines were done during the design of collecting networks of gas wells production. So, Rothfarb and al.  studied the optimal design of an oﬀshore natural gas network. In , Baskaharan et al. are confronted to a similar problem of optimal design of a network of collection of several wells in a desert environment (Australia). They show that, under certain conditions, the optimal collecting network is a treelike network. Let us note that both works  and  consider only networks of collection of gas from several wells (multi-sources) but with a unique point of collection. That’s defined the value of the flow on each arc. In , Walters uses the techniques of the dynamic programming to investigate all the possible trees on a water distribution network with several sources (springs) and the multiple wells (with potential fixed to sources and minimal potential in the points of exits). We shall note finally the recent works (2006) of Nie  on the topology of pipes networks with cycles and multi-sources by means of the use of neuronal networks.
Methods for optimal sizing of pipe networks
Because of the laying constraints of pipelines in industrial nations, the optimal topology of networks of pipelines problems gradually left the place with problems of the sizing of the diameters of the distribution networks with fixed topology. The main diﬃculty to handle in such sizing problem is the combina-torial choice of commercial available sizes. These problems of sizing a piping system have been widely studied in the literature. To tackle this problem in reasonable computation times, a first class of papers dealing with pipe network sizing (of either water or gas) uses meta-heuristics such as genetic algorithms, see [1, 28, 93, 103].
A second class of papers uses methods based on continuous relaxation. Hansen et al.  use a trust region successive linear programming method. Their algorithm directly handles the discrete choice of diameter but each step (in which the variation of diameter is continuous) needs a linearization of the objective func-tion and constraints, as well as a procedure for adjusting the diameter in order to satisfy the lower bound on pressures. De Wolf and Smeers  (1996) deal only with the continuous variables of diameter. Their objective function combines the cost of purchasing gas at supply nodes and the investment cost on the network. They solve the resulting nonsmooth optimization problem using a bundle algo-rithm. Zhang and Zhu  propose to model the combinatorial aspect with one binary variable per diameter on each arc associated with a choice constraint on these variables (with a sum of binary variables equal to one). As they consider the continuous relaxation of their binary variables, they assume that they can split an arc into several parts, each one associated with only one discrete value of diameter. They proved that it is not optimal to split an arc into more than two parts. In order to compute a solution, they reformulate the problem as a bilevel program and use trust-region methods.
Let us remind the paper by Osiadacz and Gorecki  (1995) where a sequen-tial quadratic algorithm is applied to a continuous relaxation. Flowrate variables are eliminated by assuming the gas speed on each pipeline to be constant. The continuous solution is then rounded to the nearest discrete diameter. More recently, we shall note the works of Babonneau and Vial  on the design of the networks of water flowing due to the gravity. Bakhouya  investigated an extension of the pipeline sizing problem by in-cluding the sizing of the compressor station. In that case, the optimization is to find the optimal trade-oﬀ between compression capacity and pipeline capacity. As a result of this study, the optimal solution prefers to increase the pipe sizes instead of compressor stations.
Gas trunkline from one source to one consumption node
In that first case, our goal is to determine the least-cost configuration of a trun-kline (with compressors) linking one single supply node to one single delivery point without any withdrawals and assumptions on the compressor station location. Let us define a ”section” k, as the association of a pipe followed by a compressor station to oﬀset the pressure drop. The compression occurs at the outlet of the section. There is no loss of generality in assuming such a structure, since either the compression ratio can be taken equal to 1, or the length of a section can be zero.
Edgar et al. , Boucly  or Soliman et al.  have established the cost model introduced hereafter. The objective function comprises the sum of terms for each section consisting of:
• the annualized capital expenditure of the pipe and compressor,
• the operating cost of the compressor.
The annualized capital costs for each pipeline section depend linearly on the pipe diameter and length with a factor αp, the amortization factor reducing the capital cost to an annual cost.
Operating and maintenance charges Oc (OPEX) for a compressor station are directly related to the horsepower W ().
The capital expenditure (CAPEX) of a compressor station is divided into two parts:
• an initial fixed installation outlay B,
• a cost increasing with the power: CcW , where Cc is the compressor capital cost per unit horsepower.
Table of contents :
1.1 The Natural gas Supply Chain
1.2 Main drivers for investment in natural gas supply chain
1.2.1 Demand drives investments
1.2.2 Additionnal incentives to invest
1.2.3 Other project examples
1.3 Main Features of existing pipeline systems
1.3.1 Gas Trunklines
1.3.2 Gas Networks
1.4 Problem Definition
1.5 Designing pipeline networks for the future: Hydrogen networks
2 Operations Research and Gas Networks: State of the art
2.1 Origin of gas simulation
2.2 Optimization of the operations
2.3 Designing straight gunbarrel pipelines
2.3.1 Usual rules of thumbs
2.3.2 First attempts to apply OR techniques
2.4 OR methods overview applied to pipeline network design
2.4.1 Topology optimization of pipe networks
2.4.2 Methods for optimal sizing of pipe networks
2.5 Position of the thesis
3 Physical Background
3.2 Compression Power
4 Increasing the network capacity : always the best choice?
4.1 Network simulation
4.1.1 Potential Formulation
4.1.2 Network equilibrium problem
4.1.3 Network performance criteria
4.2 Paradox formulation
4.4 When will the paradox not occur?
4.5 How to detect the paradox?
5 Investment Optimization Models
5.1 Model 1 : Gas trunkline from one source to one consumption node .
5.1.1 Objective function
5.2 Model 2 : Topology/sizing of single source pipeline distribution systems
5.3 Model 3 : Pipe reinforcement of multi source transportation networks
6 Design : Optimal features
6.1 Optimal features of gas trunklines
6.1.1 General optimality conditions
6.1.2 Optimal properties
6.1.3 Optimal Values
6.2 Characteristics of the optimal topology of single source pipeline distribution networks
6.3 Numerical verifications
7 Sizing Methods
7.1 Local search for joint topology/sizing optimization
7.1.1 Topology initialisation
7.1.2 Sizing of the continuous diameters on a tree
7.1.3 Tree Improvement Heuristic
7.2 Selection of pipe selections to reinforce on existing networks
7.2.1 Pipe selection continuous program
7.2.2 Solving the continuous program
7.3 Branch & Bound algorithms for reinforcement problems
7.3.1 General principles
7.3.2 Reduced Branch & Bound
7.3.3 Numerical Results
8 An extension : investment scheduling
8.1 Modeling of the multi-period problem
8.2 Dynamic programming
8.2.1 Feasible State generation
8.2.2 Principle of Optimality
8.2.3 DP Algorithm
8.3.2 Forward Algorithm
8.3.3 Fast Forward Algorithm
8.3.4 Backward algorithm
8.4 Case Study
8.4.1 Features of the tested network
8.4.2 Pipe Selection
8.4.3 Diameter Optimization
8.4.4 Scheduling Optimization
8.5 Tests on larger networks
9 Conclusions & Future Works
9.1.2 Optimal features
9.1.3 Combinatorial Pipe sizing
9.1.4 Invesment Scheduling
9.2 Overall capacity reinforcement problem
9.2.1 With new compression stations
9.2.2 With additional compression power on existing stations
9.3 Strategic/Operational integration
9.4 Robust degign and sizing of gas networks
9.4.2 A robust optimization model
A Compression power: Numerical approximations
B Extended Models: Mathematical formulation
B.1 Installation of new compressor stations
B.2 Installation of additional compression power
B.3 Strategic/Operational bilevel model
B.4 Robust Optimization model .