Parallel Simulated Annealing Applied To Long Term Transmission Network Expansion Planning

The simulated annealing optimization technique has been successfully applied to a number of electrical engineering problems, including transmission system expansion planning. The method is general in the sense that it does not assume any particular property of the problem being solved, such as linearity or convexity. Moreover, it has the ability to provide solutions arbitrarily close to an optimum (i. e. it is asymptotically convergent) as the cooling process slows down. The drawback of the approach is the computational burden: finding optimal solutions may be extremely expensive in some cases. This paper presents a Parallel Simulated Annealing, PSA, algorithm for solving the long term transmission network expansion planning problem. A strategy that does not affect the basic convergence properties of the Sequential Simulated Annealing algorithm have been implementeded and tested. The paper investigates the conditions under which the parallel algorithm is most efficient. The parallel implementations have been tested on three example networks: a small 6-bus network, and two complex real-life networks. Excellent results are reported in the test section of the paper: in addition to reductions in computing times, the Parallel Simulated Annealing algorithm proposed in the paper has shown significant improvements in solution quality for the largest of the test networks. © 1996 IEEE.121181188Aarts, E.H.L., , de Bont F. M. J. , Habers E. H. A. and Van Laarhoven P. J. M. : "Parallel Implementations of the Statistical Cooling Algorithm", Integration, the VLSI Journal 4, , pp. 209-238, 1986Romero, R., , Gallego R.A. , Monticelli A. : "Transmission System Expansion Planning by Simulated Annealing", Power Industry Computer Applications - PICA 95, Salt Lake City, , May 1995Mori, H., , Takeda K. : "Parallel Simulated Annealing for Power System Decomposition", IEEE Transaction on Power Systems, Vol. 9, No. 2, , May 1994Johnson, D.S., , Aragon C.R. , McGeoch L. A. , Schevon C. : "Optimization by Simulated Annealing: An Experimental EvaluationPart I, Graph Partitioning", Operations Research, Vol. 37, No. 6, , Nov. -Dec. 1989Aarts, E., , Korst J. : "Simulated Annealing and Boltzmann Machines", John Wiley &, , Sons, 1989Van Laarhoven, P.J.M., Aarts E. H. "Simulated Annealing: Theory and Applications", D. Reidel Publishing Company, , Holand, 1987Fischl, R., : "Optimal System Expansion Planning: A Critical Overview", ERDA & EPRI Conf., , Henniker, 1975Ilic-Spong, M., Et Al. "Secondary Voltage Control Systems Pilot Point Information", IEEE Trans. on Power Systems, Vol. 3, No. 2, Pp. 660-668, , May 1988Garver, L.L., : "Transmission Network Estimation Using Linear Programming", IEEE Trans. Power App. Syst. , Vol. PAS-89, Pp. 1688-1697, , Sept/Oct 1970Monticelli, A., , Santos Jr.A. , Pereira M.V. F. , Cunha S. , Praça J. G. , Park B. , "Interactive Transmission Network Planning Using A Least-Effort Criterion", IEEE Transactions PAS, Vol. 101, No. 10, Pp 3919-3925, , Oct. 1982Pereira, M.V.F., , Pinto L. M. V. G. , Cunha S. H. F. , Oliveira G. C. : "A Decomposition Approach to Automated Generation/Transmission Expansion Planning"IEEE Trans. Power App. Systems, Vol. PAS-104, No. 11, , November 1985Romero, R., , Monticelli A. :"A Zero-One Implicit Enumeration Method for Optimizing Investments in Transmission Expansion Planning", IEEE Transactions on Power Systems, Vol. 9, No. 3, , August 1994Hsiao, Y.T., , Chiang H.D. , Liu C. C. , Chen Y. L. "A Computer Package for Optimal Multi-Objective VAR Planning in Large Scale Power Systems", IEEE Transactions on Power Systems, Vol. 9, No. 2, , May 1994Drexl, A., "A Simulated Annealing Approach to the Multiconstraint Zero-One Knapsack Problem", Computing 40, , pp. 1-8, 1988Kirkpatrick, S., , Gelatt Jr.C.D. , Vecchi M. P. "Optimization by Simulated Annealing", Science 220, , pp. 671-680, 1983Romero, R., And A. Monticelli, "A Hierarchical Decomposition Approach for Transmission Network Expansion Planning", IEEE Trans. on Power Systems, Vol. 9, No. 1, Pp. 373-380, , Feb. 199