A Constructive Heuristic Algorithm for Distribution System Planning

A constructive heuristic algorithm (CHA) to solve distribution system planning (DSP) problem is presented. The DSP is a very complex mixed binary nonlinear programming problem. A CHA is aimed at obtaining an excellent quality solution for the DSP problem. However, a local improvement phase and a branching technique were implemented in the CHA to improve its solution. In each step of the CHA, a sensitivity index is used to add a circuit or a substation to the distribution system. This sensitivity index is obtained by solving the DSP problem considering the numbers of circuits and substations to be added as continuous variables (relaxed problem). The relaxed problem is a large and complex nonlinear programming and was solved through an efficient nonlinear optimization solver. Results of two tests systems and one real distribution system are presented in this paper in order to show the ability of the proposed algorithm.

Constructive heuristic algorithm for the DC model in network transmission expansion planning

A novel constructive heuristic algorithm to the network expansion planning problem is presented the basic idea comes from Garver's work applied to the transportation model, nevertheless the proposed algorithm is for the DC model. Tests results with most known systems in the literature are carried out to show the efficiency of the method.

Constructive heuristic algorithm in branch-and-bound structure applied to transmission network expansion planning

A constructive heuristic algorithm to solve the transmission system expansion planning problem is proposed with the aim of circumventing some critical problems of classical heuristic algorithms that employ relaxed mathematical models to calculate a sensitivity index that guides the circuit additions. The proposed heuristic algorithm is in a branch-and-bound algorithm structure, which can be used with any planning model, such as Transportation model, DC model, AC model or Hybrid models. Tests of the proposed algorithm are presented on real Brazilian systems.

A constructive heuristic algorithm to Short Term Transmission Network Expansion Planning

In this paper a method for solving the Short Term Transmission Network Expansion Planning (STTNEP) problem is presented. The STTNEP is a very complex mixed integer nonlinear programming problem that presents a combinatorial explosion in the search space. In this work we present a constructive heuristic algorithm to find a solution of the STTNEP of excellent quality. In each step of the algorithm a sensitivity index is used to add a circuit (transmission line or transformer) to the system. This sensitivity index is obtained solving the STTNEP problem considering as a continuous variable the number of circuits to be added (relaxed problem). The relaxed problem is a large and complex nonlinear programming and was solved through an interior points method that uses a combination of the multiple predictor corrector and multiple centrality corrections methods, both belonging to the family of higher order interior points method (HOIPM). Tests were carried out using a modified Carver system and the results presented show the good performance of both the constructive heuristic algorithm to solve the STTNEP problem and the HOIPM used in each step.

Distribution network planning using a constructive heuristic algorithm

An optimization technique to solve distribution network planning (DNP) problem is presented. This is a very complex mixed binary nonlinear programming problem. A constructive heuristic algorithm (CHA) aimed at obtaining an excellent quality solution for this problem is presented. In each step of the CHA, a sensitivity index is used to add a circuit or a substation to the distribution network. This sensitivity index is obtained solving the DNP problem considering the numbers of circuits and substations to be added as continuous variables (relaxed problem). The relaxed problem is a large and complex nonlinear programming and was solved through an efficient nonlinear optimization solver. A local improvement phase and a branching technique were implemented in the CHA. Results of two tests using a distribution network are presented in the paper in order to show the ability of the proposed algorithm. ©2009 IEEE.

An application of a modified constructive heuristic algorithm to transmission expansion planning

Transmission expansion planning (TEP) is a non-convex optimization problem that can be solved via different heuristic algorithms. A variety of classical as well as heuristic algorithms in literature are addressed to solve TEP problem. In this paper a modified constructive heuristic algorithm (CHA) is proposed for solving such a crucial problem. Most of research papers handle TEP problem by linearization of the non-linear mathematical model while in this research TEP problem is solved via CHA using non-linear model. The proposed methodology is based upon Garver's algorithm capable of applying to a DC model. Simulation studies and tests results on the well known transmission network such as: Garver and IEEE 24-bus systems are carried out to show the significant performance as well as the effectiveness of the proposed algorithm. © 2011 IEEE.

Transmission Expansion Planning Via a Constructive Heuristic Algorithm in Restructured Electricity Industry

The transmission expansion planning problem in modern power systems is a large-scale, mixed-integer, nonlinear and non-convex problem. this paper presents a new mathematical model and a constructive heuristic algorithm (CHA) for solving transmission expansion planning problem under new environment of electricity restructuring. CHA finds an acceptable solution in an iterative process, where in each step a circuit is chosen using a sensitivity index and added to the system. The proposed model consider multiple generation scenarios therefore the methodology finds high quality solution in which it allows the power system operate adequacy in an environment with multiple generators scenarios. Case studies and simulation results using test systems show possibility of using Constructive heuristic algorithm in an open access system.

Combined heuristic with fuzzy system to transmission system expansion planning

A heuristic algorithm that employs fuzzy logic is proposed to the power system transmission expansion planning problem. The algorithm is based on the divide to conquer strategy, which is controlled by the fuzzy system. The algorithm provides high quality solutions with the use of fuzzy decision making, which is based on nondeterministic criteria to guide the search. The fuzzy system provides a self-adjusting mechanism that eliminates the manual adjustment of parameters to each system being solved. (C) 2010 Elsevier B.V. All rights reserved.

An efficient heuristic for total flowtime minimisation in no-wait flowshops

In this paper, we address the problem of scheduling jobs in a no-wait flowshop with the objective of minimising the total completion time. This problem is well-known for being nondeterministic polynomial-time hard, and therefore, most contributions to the topic focus on developing algorithms able to obtain good approximate solutions for the problem in a short CPU time. More specifically, there are various constructive heuristics available for the problem [such as the ones by Rajendran and Chaudhuri (Nav Res Logist 37: 695-705, 1990); Bertolissi (J Mater Process Technol 107: 459-465, 2000), Aldowaisan and Allahverdi (Omega 32: 345-352, 2004) and the Chins heuristic by Fink and Voa (Eur J Operat Res 151: 400-414, 2003)], as well as a successful local search procedure (Pilot-1-Chins). We propose a new constructive heuristic based on an analogy with the two-machine problem in order to select the candidate to be appended in the partial schedule. The myopic behaviour of the heuristic is tempered by exploring the neighbourhood of the so-obtained partial schedules. The computational results indicate that the proposed heuristic outperforms existing ones in terms of quality of the solution obtained and equals the performance of the time-consuming Pilot-1-Chins.

Some heuristic algorithms for total tardiness minimization in a flowshop with blocking

The flowshop scheduling problem with blocking in-process is addressed in this paper. In this environment, there are no buffers between successive machines: therefore intermediate queues of jobs waiting in the system for their next operations are not allowed. Heuristic approaches are proposed to minimize the total tardiness criterion. A constructive heuristic that explores specific characteristics of the problem is presented. Moreover, a GRASP-based heuristic is proposed and Coupled with a path relinking strategy to search for better outcomes. Computational tests are presented and the comparisons made with an adaptation of the NEH algorithm and with a branch-and-bound algorithm indicate that the new approaches are promising. (c) 2007 Elsevier Ltd. All rights reserved.

Analysis of heuristic algorithms for the transportation model in static and multistage planning in network expansion systems

The usefulness of the application of heuristic algorithms in the transportation model, first proposed by Garver, is analysed in relation to planning for the expansion of transmission systems. The formulation of the mathematical model and the solution techniques proposed in the specialised literature are analysed in detail. Starting with the constructive heuristic algorithm proposed by Garver, an extension is made to the problem of multistage planning for transmission systems. The quality of the solutions found by heuristic algorithms for the transportation model is analysed, as are applications in problems of planning transmission systems.

Using traditional heuristic algorithms on an initial genetic algorithm population applied to the transmission expansion planning problem

This paper analyses the impact of choosing good initial populations for genetic algorithms regarding convergence speed and final solution quality. Test problems were taken from complex electricity distribution network expansion planning. Constructive heuristic algorithms were used to generate good initial populations, particularly those used in resolving transmission network expansion planning. The results were compared to those found by a genetic algorithm with random initial populations. The results showed that an efficiently generated initial population led to better solutions being found in less time when applied to low complexity electricity distribution networks and better quality solutions for highly complex networks when compared to a genetic algorithm using random initial populations.

Heuristic algorithm to solve the short term transmission network expansion planning

In this paper, a method for solving the short term transmission network expansion planning problem is presented. This is a very complex mixed integer nonlinear programming problem that presents a combinatorial explosion in the search space. In order to And a solution of excellent quality for this problem, a constructive heuristic algorithm is presented in this paper. In each step of the algorithm, a sensitivity index is used to add a circuit (transmission line or transformer) or a capacitor bank (fixed or variable) to the system. This sensitivity index is obtained solving the problem considering the numbers of circuits and capacitors banks to be added (relaxed problem), as continuous variables. The relaxed problem is a large and complex nonlinear programming and was solved through a higher order interior point method. The paper shows results of several tests that were performed using three well-known electric energy systems in order to show the possibility and the advantages of using the AC model. ©2007 IEEE.

A review and evaluation on constructive heuristics to optimise product mix based on the Theory of Constraints

In this paper, we address the problem of defining the product mix in order to maximise a system's throughput. This problem is well known for being NP-Complete and therefore, most contributions to the topic focus on developing heuristics that are able to obtain good solutions for the problem in a short CPU time. In particular, constructive heuristics are available for the problem such as that by Fredendall and Lea, and by Aryanezhad and Komijan. We propose a new constructive heuristic based on the Theory of Constraints and the Knapsack Problem. The computational results indicate that the proposed heuristic yields better results than the existing heuristic.

Interior point algorithm for linear programming used in transmission network synthesis

This article presents a well-known interior point method (IPM) used to solve problems of linear programming that appear as sub-problems in the solution of the long-term transmission network expansion planning problem. The linear programming problem appears when the transportation model is used, and when there is the intention to solve the planning problem using a constructive heuristic algorithm (CHA), ora branch-and-bound algorithm. This paper shows the application of the IPM in a CHA. A good performance of the IPM was obtained, and then it can be used as tool inside algorithm, used to solve the planning problem. Illustrative tests are shown, using electrical systems known in the specialized literature. (C) 2005 Elsevier B.V. All rights reserved.