A simulated annealing algorithm for transient optimization in gas networks. (English) Zbl 1126.90053

Summary: In this paper we present a simulated annealing approach for the gas network optimization problem. A gas network consists of a set of pipes to transport the gas from the sources to the sinks whereby gas pressure gets lost due to friction. Further on there are compressors, which increase gas pressure, and valves. The aim is to minimize fuel gas consumption of the compressors whereas demands of consumers have to be satisfied. The problem of transient (time-dependent) optimization of gas networks results in a highly complex mixed integer nonlinear program. We relax the equations describing the gas dynamic in pipes by adding these constraints combined with appropriate penalty factors to the objective function. A suitable neighborhood structure is developed for the relaxed problem where time steps as well as pressure and flow of the gas are decoupled. Our approach convinces with flexibility and very good computational results.


90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming


SINTEF; SIMONE; simannf90
Full Text: DOI


[1] Aarts E, Korst J (1989) Simulated annealing and Boltzmann machines. A stochastic approach to combinatorial optimization and neural computing. Wiley, New York · Zbl 0674.90059
[2] Aarts EHL, de Bont FMJ, Habers EHA, van Laarhoven PJ (1986) Parallel implementations of the statistical cooling algorithm. Integr VLSI J 4:209–238
[3] Bohachevsky IO, Johnson ME, Stein ML (1986) Generalized simulated annealing for function optimization. Technometrics 28(3):209–217 · Zbl 0609.65045
[4] Borraz-Sánchez C, Ríos-Mercado RZ (2005) A hybrid meta-heuristic approach for natural gas pipeline network optimization. In: Blesa MJ, Blum C, Roli A, Sampels M (eds) Hybrid Metaheuristics: Second International Workshop, HM 2005, Barcelona, Spain, August 29–30. Springer, Heidelberg, pp 54–65
[5] Carter R (1998) Pipeline optimization: dynamic programming after 30 years. In: Pipeline Simultaion Interest Group, URL: http://www.psig.org
[6] Černý V (1985) Thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm. J Optim Theory Appl 45:41–51 · Zbl 0534.90091
[7] Corana A, Marchesi M, Martini C, Ridella S (1987) Minimizing multimodal functions of continuous variables with the ”simulated annealing” algorithm. ACM Trans Math Softw 13:262–280 · Zbl 0632.65075
[8] Dekkers A, Aarts E (1991) Global optimization and simulated annealing. Math Program 50: 367–393 · Zbl 0753.90060
[9] Ehrhardt K, Steinbach M (2005) Nonlinear optimization in gas networks. In: Bock HG, Kostina E, Phu HX, Ranacher R (eds) Modeling, simulation and optimization of complex processes. Springer, Berlin, pp 139–148 · Zbl 1069.90014
[10] Gopal VN (1979) Techniques to optimize fuel and compressor combination selection. In: American Gas Association Transmission Conference
[11] Jenicek T (1993) Steady-state optimization of gas transport. In: Proceedings of the 2nd International Workshop SIMONE on Innovative Approaches to Modelling and Optimal Control of Large Scale Pipeline Networks, September 1993
[12] Kirkpatrick S, Gelatt CD Jr, Vecchi MP (1983) Optimization by simulated annealing. Science 220:671–680 · Zbl 1225.90162
[13] Králik J (1993) Compressor stations in SIMONE. In: Proceedings of the 2nd International Workshop SIMONE on Innovative Approaches to Modelling and Optimal Control of Large Scale Pipeline Networks, September 1993
[14] van Laarhoven PJM, Aarts EHL (1987) Simulated annealing: theory and applications. D. Reidel, Dordrecht
[15] Mahlke D (2005) Der Simulated Annealing Algorithmus zur transienten Optimierung von Gasnetzen. Master’s thesis, Technische Universität Darmstadt
[16] Martin A, Möller M, Moritz S (2006) Mixed integer models for the stationary case of gas network optimization. Math Program 105:563–582 · Zbl 1085.90035
[17] Metropolis N, Rosenbluth AW, Rosenbluth MN, Teller AH, Teller E (1953) Equation of state calculations by fast computing machines. J Chem Phys 21(6):1087–1092
[18] Michalewicz Z, Fogel DB (2000) How to solve it: modern heuristics. Springer, Heidelberg · Zbl 0943.90002
[19] Miki M, Hiroyasu T, Fushimi T (2003) Parallel simulated annealing with adaptive neighborhood determined by GA. IEEE Int Conf Syst Man Cybern 1:26–31
[20] Möller M (2004) Mixed integer models for the optimisation of gas networks in the stationary case. PhD thesis, Darmstadt University of Technology · Zbl 1069.90120
[21] Moritz S (2007) A mixed integer approach for the transient case of gas network optimization PhD thesis, Darmstadt University of Technology (to appear) · Zbl 1149.90380
[22] Nemhauser GL, Wolsey LA (1988) Integer and combinatorial optimization. Wiley, New York · Zbl 0652.90067
[23] Nolte A, Schrader R (2000) A note on the finite time behavior of simulated annealing. Math Oper Res 25(3):476–484 · Zbl 1073.90579
[24] Nowak MP, Westphalen M (2003) A linear model for transient gas flow. Technical Report STF38 S03601, SINTEF Industrial Management, Norway
[25] Osman IH, Kelly JP (eds) (1996) Meta-heuristics: theory and applications. Kluwer, Dordrecht
[26] Pratt KF, Wilson JG (1984) Optimization of operation of gas transmission systems. Trans Inst Meas Control 6(4):261–269
[27] Reeves CR (ed) (1993) Modern heuristic techniques for combinatorial problems. Halstead Press (Wiley), New York · Zbl 0942.90500
[28] Sekirnjak E (1998) Mixed integer optimization for gas transmission and distribution systems. INFORMS Meeting, Seattle, October 1998. Lecture notes
[29] Sekirnjak E (1999) Transiente Technische Optimierung (TTO-Prototyp). PSI Berlin, 1999. Technical Report
[30] Smeers Y, De Wolf D (2000) The gas transmission problem solved by an extension of the simplex algorithm. Manage Sci 46:1454–1465 · Zbl 1232.90355
[31] Vostrý Z (1993) Transient optimization of gas transport and distribution. In: Proceedings of the 2nd International Workshop SIMONE on Innovative Approaches to Modelling and Optimal Control of Large Scale Pipeline Networks, September 1993
[32] Wah BW, Chen YX (2000) Optimal anytime constrained simulated annealing for constrained global optimization. In: Proceedings Sixth International Conference on Principles and Practice of Constraint Programming, pp 425–440 · Zbl 1044.68807
[33] Wah BW, Wang T (1999) Constrained simulated annealing with applications in nonlinear continuous constrained global optimization. In: Proceedings of the 11th IEEE International Conference on Tools with Artificial Intelligence, pp 381–388
[34] Westphalen M (2004) Anwendungen der stochastischen Optimierung im Stromhandel und Gastransport. PhD thesis, Universität Duisburg-Essen
[35] Wright S, Somani M, Ditzel C (1998) Compressor station optimization. In: Pipeline Simulation Interest Group, Denver, Colorado, October 1998
[36] Záworka J (1993) Project SIMONE–Achievements and Running Development. Institute of Information Theory and Automation, Czech Republik
[37] Zimmer HI (1975) Calculating optimum pipeline operations. In: American Gas Association Transmission Conference
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.