Natural gas is considered by many to be the most important energy source for the future. The objectives of energy commodities strategic problems can be mainly related to natural gas and deal with the definition of the *"optimal*" gas pipelines design which includes a number of related sub problems such as: Gas stations (compression) location and Gas storage locations. Needless to say these problems involve amount of money of the order of magnitude of the tens of billions € and often these problems can be a multi-countries problem. From the economic side, the natural gas consumption is expected to continue to grow linearly to approximately 153 trillion cubic feet in 2030, which is an average growth rate of about 1.6 percent per year. Because of the properties of natural gas, pipelines were the only way to transport it from the production sites to the demanding places, before the concept of Liquefied Natural Gas (LNG). The transportation of natural gas via pipelines remains still very economical.

From an optimization standpoint, the gas pipeline design problems can be divided in the following main sub problems:

- how to setup the pipeline network, i.e. its topology;
- how to determine the optimal diameter of the pipelines;
- how to allocate compressor stations in the pipeline network;

Typically, the mathematical programming formulations of these optimization problems contain a lot of nonlinear/nonconvex and even nonsmooth constraints and objective functions because of the underlying physic of the gas flows that needs to be considered. The classic constraints are the so-called Weymouth panhandle equations, which are a potential-type set of constraints and relate the pressure and flow rate through an arc (m,n) of the pipeline.

As in many other situations problems 1-3 are a single problem but a *divide et impera* principium is applied. Therefore the problems 1 and 2 are somehow determined via simulations and normally there are - in the first but also in the 2 - a lot of economic drivers, and also political drivers when many countries are involved. From a technical point of view, instead probably the most challenging problem is the number 3, the compression stations allocation. Because of the high setup cost and high maintenance cost, it is desirable to have the best network design with the lowest cost. This problem concerns a lot of variables: the number of compressor stations which is an integer variable, the pipeline length between two compressor stations, and the suction and discharge gas pressures at compressor stations. This problem is computationally very challenging since it includes not only nonlinear functions in both objective and constraints but, in addition, also integer variables.

In the current Energy market context, district heating has an important role as it often leverages on existing significant sources of heat generated by industrial processes, a mix of renewable sources and Combined Heat and Power (hereafter CH&P) units, all of them environmentally beneficial because of their high energy efficiency when compared to conventional condensing power plants (not to mention that single, large scale plants are significantly more efficient and safe than numerous low scale heat-generation units).

From a management standpoint, heat distribution becomes a strategic business issue, related to the design of the district heating network that require large investments, due to the cost of materials and civil works for the realization of the network.

Proper strategic design of network (i.e. definition of the most convenient backbone pipelines to lay down) and tactical targeting of most promising potential customers are both aimed at maximizing the Net Present Value (NPV) of the investment.

The problem calls for finding the extension plan for an existing (or eventually empty) district heating network that maximizes the NPV at a given time horizon. It is therefore necessary to decide: (i) the set of potential new customers that should be reached, (ii) which new pipelines should be installed, and (iii) their diameter.

Research on representation and simulation in details of the behavior of the thermo-hydraulic network through sets of non-linear equations can be found in literature, for example (Bohm, 1999) and (Y.S. Park, 2000). In (Aringhieri, 2003), an integer programming model is proposed for the optimal selection of the type of heat exchangers to be installed at the users’ premises in order to optimize the return temperature at the plant. The authors achieve good system efficiency at a reasonable cost. Boldrin et al. (Bordin, 2016) developed a mathematical model to support district heating system planning by identifying the most advantageous subset of new users that should be connected to an existing network. In (Bettinelli, 2016), an economic and a thermo-hydraulic Mixed Integer Linear Programming (MILP) models have to be considered. The economic model takes into account:

- Production cost and selling revenues;
- Cost for network link activation, that depends on the diameter of the selected pipes;
- Cost for customer connections;
- Amortization;
- Taxes;
- Budget constraints.

Moreover, while the investment on the backbone pipelines is done on the first year, new customers are not connected immediately, but following an estimated acquisition curve (e.g., 25% the first year, 15%, the second year,…). Hence, the corresponding costs and revenues have to be scaled accordingly

The thermos-hydraulic model must ensure the proper operation of the extended network. The following constraints are to be imposed:

- Flow conservation at the nodes of the network;
- Minimum and maximum pressures at the nodes;
- Plants operation limit: maximum pressure on the feed line, minimum pressure on the return line, minimum and maximum flow rate;
- Pressure drop along the links;
- Maximum water speed and pressure drop per meter.

Continuous variables model pressures at nodes and flow rate on the links, and binary variables model decisions on the connection of new customers, on the installation of new links, on the diameter choice and on flow direction on the links. The last ones are necessary since district-heating networks contains cycles: the potential network usually corresponds to the street network. Thus, it is not possible to know a priori the flow direction on the links (at least not for all of them) and such decision must be included into the model.

The pressure drop along a pipe is a non-linear function that depends on flow rate, and on the diameter of the pipe. This can be approximated using a piecewise linear function, that translates into a set of linear constraints. Solving systems of non-linear equations is difficult and computationally expensive. For this reason, aggregation techniques of the network elements are often used to model large district heating networks, at the expense of some accuracy (Zhao, 1995), (H. Zhao, 1998), (Larsen H. V., 2002), (Loewen A. a., 2001), (Loewen A. a., 2001), (Larsen H. V., 2004). The higher the number of segments in the linear function, the smaller will be the approximation error. At the same time, the number of constraints grows (there is one piecewise-linear function for each combination of pipe and diameter) and the solving time increases. To keep the number of segments small, while obtaining a good accuracy, breakpoints of the piecewise-linear function can be concentrated in the most probable range of flow rate.

District heating networks can be quite large (hundreds of existing and potential users, thousands of links) making it difficult to solve the problem directly with the full MILP. Solution methods developed in (Bettinelli, 2016) approach the problem in three steps.

- solve the linear relaxation of the MILP model and use it to select water direction in all the pipes. Then, solve to integrality the MILP model, with the directions fixed, obtaining a first heuristic solution.
- In the solution found at step 1, detect the conflict points, which are the nodes of the network where different water direction meet. The flow direction is released for the nodes close to conflict points, and the MILP model is solved again, obtaining a second heuristic solution
- The full MILP, initialized with the best solution found in the previous steps, is solved, until either optimality or the time limit are reached.

Optit srl has developed a decision support system, in collaboration with the University of Bologna, based on the modelling mentioned above, that has been successfully used in two of largest multi-utility companies operating in the Italian District Heating market. The application leverages on open source Geographical Information System (GIS) to allow a simple user interface and a number of plug-in tools to manage the specific optimization issue.

1. Aringhieri, R., Malucelli, F.: Optimal operations management and network planning of a district heating system with a combined heat and power plant. Annals of Operations Research120(1-4), 173–199 (2003)

2. Bettinelli, A. a. (2016): Decision support systems for energy production optimization and network design in district heating applications. Technical Report OR-16-5, DEI –University of Bologna, under review by Integrated Series in Information Management.

2. Bøhm, B., Palsson, H., Larsen, H.V., Ravn, H.F.: Equivalent models for district heating systems. In: Proceeings of the 7th International Symposium on District Heating and Cooling. Nordic Energy Research Programme (1999)

3. Bordin, C., Gordini A., Vigo D., An optimization approach for district heating strategic network design, European Journal of Operational Research, Volume 252, Issue 1, 1 July 2016, Pages 296-307, ISSN 0377-2217,

4. Larsen, H.V., Bøhm, B., Wigbels, M.: A comparison of aggregated models for simulation and operational optimisation of district heating networks. Energy conversion and management45(7), 1119–1139 (2004)

5. Larsen, H.V., Palsson, H., Bøhm, B., Ravn, H.F.: Aggregated dynamic simulation model ofdistrict heating networks. Energy conversion and management43(8), 995–1019 (2002)

6. Loewen, A., Wigbels, M., Althaus, W., Augusiak, A., Renski, A.: Structural simplification of complex dh-networks-part 1. EUROHEAT AND POWER FERNWARME INTERNA-TIONAL30(5), 42–44 (2001)

7. Loewen, A., Wigbels, M., Althaus, W., Augusiak, A., Renski, A.: Structural simplification of complex dh-networks-part 2. Euroheat and Power-Fernwarme International30(6), 46–51(2001)

8. Park, Y.: State of the art report of Denmark, Germany and Finland. Simple models for operational optimization. Department of Mechanical Engineering, Technical University of Denmark(2000)

9. Zhao, H.: Analysis, Modelling and Operational Optimazation of District Heating Systems. Centre for District Heating Technology, Technical University of Denmark (1995)

10. Zhao, H., Holst, J.: Study on a network aggregation model in dh systems. Euro heat & power27(4-5), 38–44 (1998)

**Contributor**:

Robert Schwarz, ZIB