چند گام به طور همزمان در تغییر الگوریتم هیوریستیک سازنده برای برنامه ریزی توسعه شبکه انتقال

In this paper, a Constructive Heuristic Algorithm (CHA) is presented to solve the Transmission Network Expansion Planning Problem (TNEP), a complex non-convex Mixed Integer Non-Linear Programming (MINLP) problem with multiple local minima. In the proposed algorithm, the non-linearities are resolved through the following feature: when discrete decision variables are given, the model becomes linear in the continuous variables. A CHA is developed which improves the current solution by implementing multiple step simultaneous changes over a number of saturated transmission lines, in contrast to the approach traditionally followed, which implements one change at a time. Solutions to test problems are computed.

As a result of deregulation, and with advances in transmission technologies, generating companies have been selling power to more distant demand nodes. This has led to an increase in the role of the transmission grid. Expanding grid capacities on a timely basis in order to meet the growing demand cost effectively is an important task. This should be done to assure that no bottlenecks exist in the transmission sector, which is the vehicle for all generating companies to reach their customers [1]. In the U.S., an insufficient transmission capacity has been quoted as one of the causes for many problems such as price spikes, market power exploitation and even black-outs [2]. The Transmission Network Expansion Planning (TNEP) problem is a complex non-convex Mixed Integer Non-Linear Programming (MINLP) problem with multiple local minima. Finding good primal algorithms to solve this problem has received ample attention in the literature [3], [4], [5], [6], [7] and [8]. However, there is still no consensus as to the superiority of any of these solutions mechanisms in terms of achieving global optimality and the quality of the solution. Most primal solution approaches seek to identify satisfactory solutions with minimum effort. In this paper, a Constructive Heuristic Algorithm (CHA) is presented to solve the TNEP problem. The proposed CHA is based on a principle generated from empirical evidence that suggests that, in order to solve transmission bottlenecks, it is generally necessary to expand the capacities of multiple congested transmission lines simultaneously. This facilitates and accelerates the search process and, in addition, makes the logic of the algorithm very easy to communicate in non-technical terms to policy makers and regulators. It is generally assumed when performing TNEP that the generating sector has sufficient spare capacity and as such the planning for the transmission sector can be done independently [3], [4], [5], [6], [7] and [8]. Transmission congestion is then solely due to lack of transmission capacities and not due to lack of generating capacities. This is the assumption that is being made in this paper. TNEP can be performed in a static or in a dynamic environment. In a static environment, power demands are considered constants [3], [4], [5], [6], [7] and [8]. In a dynamic environment TNEP is performed considering constant demands for several contiguous years to achieve benefits from coordinating the recommended expansion projects [9], [10] and [11]. Power flow along transmission lines is generally modeled using either AC or DC equations. In the AC model the real and the reactive power are both considered and voltage and current are represented as sinusoidal. This model allows inclusion of more details so that issues such as reactive power and transmission losses can be properly considered [12], [13], [14], [15] and [16]. The DC model is a simplification of the AC model under the assumptions that voltage is maintained at a reasonably constant level and the difference in the phase angles (θ) between the sending and receiving end is small so that approximations of cos(θi − θj) → 1 and sin(θi − θj) → (θi − θj) can be made to simplify the flow model, ignoring reactive power and transmission losses [17] and [18]. This simplification is commonly used to study real power planning [3], [4], [5], [6], [9], [13], [19], [20], [21] and [22]. Notwithstanding this simplification the TNEP problem is still a complex non-convex MINLP problem. Due to the complexity of the TNEP problem for real life systems involving a considerable number of supply and demand nodes, some modeling assumptions are made to identify preliminary optimal solutions for macro level planning. The model generally used for this purpose is the DC model. This is the model being followed in the present paper. These preliminary macro level solutions are evaluated further, during a second stage of the planning process, using AC power flow equations to determine the impact of the proposed expansion plans in transmission losses, reactive power and network reliability, among other aspects [14], [19] and [20]. The objective function of the formulation presented in this paper differs from many of the other papers in the literature in the respect that it includes the generating costs as well, besides including the investments costs and the load curtailment cost. The generation costs reflect prices in the solution of the optimal dispatch problem solved by the entity managing the transmission network, such as an Independent System Operator (ISO). Including generation costs in the objective function is equivalent to imbedding the optimal dispatch function while determining the adequacy of the grid capacities. This approach has been followed by several authors [13] and [23]. Once loads at the demand nodes become random variables, the optimal grid capacities will have buffer large enough to meet time varying demands. The impact of including generating costs at time varying prices will be equivalent to providing transmission pick up capacities proportional to the network outlet capacity at the generation nodes considering their degree of participation in the optimal dispatches. The capacities in the transmission grid have to be bounded from above and these decisions are made by trade-offs between the transmission capacity expansion costs and load curtailment costs. In this paper power flow equations are assumed to follow DC model [17] and [18] as mentioned before, consequently the TNEP model is a non-convex MINLP problem, involving two sets of variables one discrete and the other continuous. When values of discrete variables are given TNEP becomes a linear programming problem in continuous variables. A conditional optimal solution for the given set of discrete variables is thus easily found using any linear programming (LP) package, but obtaining an unconditional optimal solution is a very challenging task. The non-linearities in the proposed model are due to products of two decision vectors E (discrete) and θ (continuous). Once vector E has been chosen, the objective function and the constraints become linear in θ, reducing the conditional problem to a linear programming problem in θ, which can be solved easily. The problem thus boils down to efficiently iterating over the possible values of E. The above scheme has elements of Bender's Decomposition technique [3], [24] and [25]. The non-linearities in the model have been treated differently in the present paper. The CHA presented in Ref. [26] requires solving a non-linear problem at each iteration. The CHA presented in Ref. [27] is based on Garver's CHA for the transportation model and it is applied to multistage planning. These algorithms require computing a sensitivity index to identify the best line for incrementing its capacity. The algorithm proposed in this paper does not require computation of any sensitivity index. It uses information about the slacks in the transmission capacities of the preceding linear programming iteration. While iterating over the discrete vector E, the search strategy for the algorithm presented in this paper is based on identifying saturated lines in the current solution. These lines are considered as potential candidates for expansion. Instead of changing capacity of one transmission line at a time, which most of the available algorithms in the literature follow [26] and [27], the proposed algorithm increments simultaneously capacities of multiple lines. This gives the advantage of opening up several bottlenecked paths, which might not have been opened by the strategy of incrementing capacity of one line at a time. The algorithm gets out of local minima more easily, jumping from one neighborhood to another by virtue of the fact that transmission capacities for several lines are changed simultaneously. A list of potentially good solutions is maintained during search. While pursuing a solution from this list, if improvement does not occur for a predetermined number of consecutive trials, a switch is made to another solution from the list closest to the incumbent in terms of the objective value. The method traditionally followed to get out of the local minima is through having multiple starts. Some other well-known heuristic methods such as simulated annealing [6], [13] and [22], genetic algorithm [5] and [22], and Tabu Search [4] have characteristics which essentially are based on multiple start concept and achieve success in searching for the global minimum for a problem of the same type as the TNEP to a varying degree. This paper is organized as follows: in Section 2 the TNEP model is presented. In Section 3 the rationale for the proposed algorithm is described. In Section 4 a CHA to solve the model is developed. Solutions to two classical test problems are presented in Section 5. Conclusions are given in Section 6.

In this paper, a CHA was developed to solve the TNEP problem. Because the TNEP problem is a non-convex MINLP with multiple local minima, achieving a global optimal solution is extremely difficult. Due to the complexity of this problem most of the approaches which seek to solve it are primal based; they do not guarantee convergence to a global solution, nor do they allow an assessment as to the quality of the solution as compared to the unknown optimal value. Currently, there are no primal-dual approaches successfully applied to the TNEP to overcome these limitations. As a primal approach, the CHA presented here shares the limitations enumerated above. However, the proposed algorithm attempts to improve the search process by exploiting the feature whereby the non-linearities in the model are resolved when the values of the discrete variables are given, making it a linear programming problem in the continuous variables. The search process is also improved by making multiple simultaneous increases in transmission capacities over a number of congested transmission lines, in contrast to the traditional approach of making one increase at a time in the capacity of a transmission line. As contrasted to several other heuristic algorithms that have been applied to the TNEP problem this algorithm reduces the probability of becoming trapped in local minima, as an iterative step is more likely to take the search to a different neighborhood on account of the several simultaneous multi-step changes which are made. Another important feature of the algorithm is that its search principle, which is based on increasing the transmission capacities of multiple congested transmission lines, is easy to communicate and explain to practitioners and policy makers. This is the case because it can be supported with empirical evidence.