A Hybrid Unit Commitment Approach Incorporating Modified Priority List with Charged System Search Methods ()
1. Introduction
The immense competition in power industry is forcing the operators to run the system by maximizing the benefits to both supplier and consumer. The unit commitment (UC) problem is a non-linear, non-convex, large-scale, mixed integer problem. It involves the determination of an optimum start-up and shut-down schedule of generating units that minimizes operating cost, while satisfying a set of system constraints over a time period [1] [2] . Numerous efficient and robust UC methods have been developed and can be classified into two main categories [3] : The first category represents numerical optimization techniques such as priority list methods (PL) [4] [5] [6] , dynamic programming method (DP) [7] [8] , Lagrangian relaxation (LR) [9] [10] [11] , and the popular branch-and-bound method (BB) [12] [13] [14] [15] . The PL method is fast but highly heuristic and gives schedules with relatively high operation costs. The DP method was widely used for the UC problem but suffered from the curse of dimensionality [16] when applied to a modern large-scale system with heavy constraints. LR has shown some potential in solving large-scale unit commitment problems by decomposing the primal problem into a set of single unit optimization sub-problems that are easier to solve with dynamic programming. The primary difficulty of this method is that it requires adopting certain measures to convert optimal dual solutions into feasible solutions for the primal problem because of the duality gap. The BB method uses a linear function to represent fuel consumption and time-dependent start-up cost, and obtains the required lower and upper bounds. However, its computational time increases exponentially with a number of dimensions of the UC problem. The second category represents meta-heuristic algorithm such as genetic algorithms (GA) [17] [18] [19] , evolutionary programming (EP) [20] [21] , simulated annealing (SA) [22] [23] , particle swarm optimization (PSO) [24] [25] [26] [27] and others [28] - [37] . In recent years, meta-heuristic algorithms have been widely used to solve some complex optimization problems in power systems. However, the biggest problem that the meta-heuristic algorithm faced is that the optimization space can be extended by penalty function method through the processing of constraints. As a result, the computational efficiency is rather low. Meta-heuristic algorithms require excessive computation time, especially for a large system size due to their random and iterative nature. Additionally, pure meta-heuristic methods commonly get stuck at a local optimum rather than at the global optimum. Even small percentage reduction in fuel costs typically leads to considerable savings for electric utilities. Consequently, a complete and efficient approach for solving the UC problem is urgently required.
In this paper, a hybrid algorithm that combines the Modified Priority List (MPL) and Charged System Search (CSS) methods is proposed for solving the UC problem. The MPL method is utilized to obtain an initial UC solution for a system over a 24-hr and 168-hr period. Next, this paper seeks better UC solutions to reduce total production cost using the CSS method. Charged System Search (CSS) is a population based meta-heuristic algorithm that was proposed recently by Kaveh and Talatahari [38] . In the CSS, each solution candidate is considered as a charged sphere called a Charged Particle (CP). The effectiveness of the proposed methodology was evaluated on several case studies and the results have been presented in this paper.
Therefore, the main contributions of this paper can be summarized as follows:
i) The Modified Priority List (MPL) method is proposed to solve the UC problem. MPL has multifold computational advantages over other UC algorithms. This is validated through large-scale unit commitment problem studies.
ii) In order to further improve the performance of the proposed MPL method, it is combined with Charged System Search algorithm and the obtained algorithm is known as hybrid MPL-CSS method. MPL-CSS manages to produce lower production cost solutions in most test cases.
This remainder of this paper is organized as follows: Section 2 formulates the UC problem. Section 3 introduces the proposed method that combines the MPL with CSS algorithms. Section 4 conducts numerical simulations and compares various UC solving methods. Finally, concluding remarks are discussed in Section 5.
2. Problem Formulation
2.1. Objective
The total fuel cost of unit k in time period t is usually given as a second order function of 
as follows:
(1)
where coefficients
, 
, and 
are the cost coefficients of unit k. In order to preserve the MILP formulation, the quadratic production cost of thermal generating units (1) is approximated by a piecewise linear function as in [14] .The objective function 
that is the sum of the fuel and start-up costs for all units is defined as:
(2)
The total start-up cost 
can be computed by the equation as below:
(3)
In general, as the OFF time is increased, then the start-up cost is increased [39] . If unit’s OFF time is larger than
, then the start-up cost will be the cold start cost.
2.2. Constraints
2.2.1. System Power Balance Constraints
(4)
Dt means the load demand at time t.
2.2.2. System Spinning Reserve Constraints
Spinning reserve requirements are necessary in the power generation scheduling to prevent a power supply interruption. Spinning reserve requirements can be specified in terms of excess generation output:
(5)
2.2.3. Generation Limits Constraints
Every online unit has generation limits:
(6)
2.2.4. Operation Ramp-Rate Limit Constraints
The operation range of every online unit is also constrained by its up and down ramp rate limits:
(7)
2.2.5. Minimum Up-Time and Down-Time Constraints
A unit must be online for a certain number of time intervals before it can be shut-down:
(8)
A unit must be offline for a certain number of time intervals before it can be started-up:
(9)
3. Proposed Hybrid Method
3.1. Modified Priority List (MPL)
In order to improve the efficiency of Meta-heuristic in a large search space, this paper proposed the MPL method to reduce the search space and this will ensure the accuracy of Meta-heuristic algorithm.
3.1.1. Production of All Possible Candidate Units for Each Time Period Based on the Cost
In the beginning, the candidate units are built for each hour to satisfy (4-6), and the minimum online unit at time t is determined by using (10). Next, the cheaper unit will be turn on with high priority. The heat rate ($/MW) of each unit is represented as (11). As shown in Figure 1, most of load is supplied by base units and the remaining load is supplied by other units
. Base units and other units form the unit combination, which is represented as (12). In this way, the search space is limited and the computation time is reduced, which is suitable for large-scale unit application. Then, the candidate unit combinations are collected and the final candidate unit combination 
is obtained by (13).
![]()
(10)
![]()
(11)
![]()
Figure 1. Rearrange units according to the heat rate.
![]()
(12)
![]()
(13)
3.1.2. Simulation
According to our UC experience, there is a significant rule to determine the unit commitment: the unit will not be off once it turns on before the peak load; the unit will not be on once it turns off after the peak load. Therefore, the unit commitment ![]()
at time t can be used to choose the next unit commitment and obtain suitable solutions ![]()
by using (14). Then the minimum cost of unit commitment can be chosen from these solutions ![]()
for next hour by using (15). In Figure 2, the reason why Simulation chooses ![]()
is that ![]()
does not violate UC constraints and its benefit is superior to the benefits from the candidate UC combinations after![]()
.
![]()
(14)
where L is the number of suitable unit candidates in the next hour.
![]()
(15)
The simulation algorithm is shown in Algorithm 1―Simulation.
The Algorithm 1―Simulation is suitable for the UC problem in a renewable energy environment. In order to obtain a more accurate solution, the Modified Priority List (MPL) is proposed in this paper. The difference between the MPL method and the Simulation algorithm is that the MPL implemented the simulation for each![]()
. By using the MPL algorithm, the solution is more accurate but the computation time is increased. The MPL algorithm is shown in Algorithm 2―MPL.
![]()
Figure 3. Rearrangement of unit scheduling to satisfy the constraint of minimum down-time.
3.1.3. Procedure
After the UC solution is solved by the MPL algorithm, some units ![]()
may violate the constraint―Equation (9) during the large load change. For example, as shown in Figure 3(a), the minimum down time of ![]()
and ![]()
is 3 hours; therefore, the UC solution in the squared-bold-italic part violates Equation (9). If the UC solution is changed to the squared-bold-italic part in Figure 3(b), the new UC solution can satisfy Equations (4)-(9) but the reserve and total cost increases. However, the reduction on reserve and total cost is significant for the UC problem. Therefore, this paper proposed hybrid MPL-CSS algorithm to solve the UC solution. After the MPL completes the initial unit commitment solutions, the CSS is then used to modify the solution in the repeated search space, which can reduce the total cost.
In the MPL-CSS algorithm, on the basis of ![]()
for![]()
, the turn-off time of units is extended to satisfy (9) and put them sequentially into the set ![]()
as shown in (16), which would reduce the reserve. The priority is determined by evaluating the contribution on the cost by using Equation (17) for each![]()
. Then a suitable solution is proposed for each ![]()
by considering (18) and (19). The feasible solutions, as shown in (20), are combined to form the search space of CSS for each hour.
![]()
(16)
![]()
(17)
![]()
(18)
![]()
(19)
![]()
(20)
In the solution space![]()
, it may exist a better solution compared to the last solution of ![]()
Therefore, we use the CSS to search for a more accurate solution in ![]()
and update![]()
; then we deal with the next ![]()
. Following the above step, the ![]()
is updated continuity to optimize the unit commitment ![]()
until the convergence of ![]()
ends. The MPL-CSS algorithm can summarize the characteristic of the UC solution and narrow down the search space. It is very efficient, especially for long-term UC schedule with a large system. The pseudo code of the MPL-CSS algorithm is shown in Algorithm 3. It also indicates the clear process about the proposed method.
3.2. Charge System Search Algorithm (CSS)
The Charged System Search (CSS) algorithm is based on the Coulomb and Gauss laws from electrical physics and the governing laws of motion from the Newtonian mechanics [40] . The algorithm can be considered as a multi-agent approach, where each agent is a Charged Particle (CP). Each CP is assigned a random position. The fitness of each CP is calculated first. The magnitude of the charge of each CP is calculated as
![]()
(21)
where ![]()
and ![]()
are the so far best and the worst fitness of particles, respectively. ![]()
represents the fitness of the ith CP. n is the total number of CPs.
The CSS utilizes a Charged Memory (CM) that saves the best so far CP vectors [40] and their related objective function values. The CM size is equal to a quarter of the number of CPs. At the end of every iteration, the worst particle is replaced by CM.
The separation distance ![]()
between two CPs is defined as follows:
![]()
(22)
where ![]()
and ![]()
are the position of the ith and jth CPs respectively, ![]()
is the position of the best CP, and ɛ is a small positive number that is taken to prevent singularity. Moving probability of each CP towards the others is determined by using
![]()
(23)
where rand is uniformly distributed in the range (0,1).
Each CP is considered as a sphere with radius a that is limited to the size of the search space.
![]()
(24)
The resultant force acting on the ith CPs is calculated by using (14):
![]()
(25)
where ![]()
is the resultant force acting on the jth.
Each CP moves to the new position and the new velocity is calculated as:
![]()
(26)
![]()
(27)
where ![]()
and ![]()
are two random numbers that are uniformly distributed in the range of (0,1). ![]()
is the size of each step. ![]()
is the mass of the ith CP and is equal to![]()
. ![]()
and ![]()
represent the acceleration coefficient and velocity coefficient respectively. The parameters ![]()
and ![]()
are defined as:
![]()
(28)
![]()
(29)
![]()
is regarded as the weight of exploitation; ![]()
is regarded as the weight of exploration. As the value of iteration increases, then ![]()
will be increased but ![]()
will be reduced.
4. Numerical Results
4.1. One-Day Unit Scheduling
The proposed MPL-CSS method is tested on the systems with 10 to 100 units, considering a 24-h scheduling horizon. The detailed data for 10-, 20-, 40-, 60-, 80-, and 100-units, and the corresponding load demands can be found in [17] . The spinning reserve is assumed to be 10% of the demand in our cases. The proposed program that combines MPL with CSS is coded in MATLAB and implemented on a personal computer with an Intel i7-2600 CPU 2.6 GHz and a 4.0 GB RAM. To prevent misleading results obtained from our simulation owing to the stochastic nature of the CSS, in each case, the results of 20 trial runs were averaged.
The result of the generation scheduling of the best solution of MPL and MPL-CSS for 10-unit until 100-unit systems is given in Table 1. The UC schedule for 100-unit system is shown in Table 2. It is noted that the maximum iteration number is set based on the convergence characteristic of the proposed MPL-CSS method. The MPL-CSS manages to generate a better result as compared to the MPL method. In term of computation time, MPL capable in achieving solutions in short amount of time, while MPL-CSS further improves the solution quality within reasonable time. Additionally, the improved results from CSS are very precise, since all of them have zero standard deviation values.
In Table 3, the UC results which obtained using the proposed MPL-CSS are compared with those in previous works. In this paper, the CSS particle number is set at 5 because the optimal solution with a short computation time can be achieved. Table 3 shows the effectiveness and robustness of the proposed method to solve the UC problem, as the result is comparable to previous works. The best results from Table 3 is represented by bold numbers, it is obvious that the MPL-CSS method performs superior and can achieves lowest UC cost. The results of MPL-CSS are more accurate and with zero standard deviation, compared with other algorithms. This is significant in power system operation, as this will provide the most reliable info for the system operator in any decision making.
![]()
Table 1. UC costs and computation time using the proposed method.
![]()
Table 2. Best UC schedule of MPL-CSS in large-scale 100-unit case.
![]()
![]()
Table 3. Comparison of UC costs by using various methods.
The execution time is an important factor, too. It is to be mentioned here that computational time is not a good measure for comparing performances of two algorithms, as the computing machines as well as their technical specifications are usually different. Moreover, the computational time will generally vary, even in the same machine, mainly due to the levels of code optimization and programming skills. Therefore, computational times of the different algorithms have been linearly normalized by frequency proportions of the employed CPUs (scaled for a 2.6 GHz processor) for fairer comparison, and are implicitly reported in Table 3. The bold cells in Table 3 indicate the minimum cost and computation time among various UC methods for 10-units to 100-units scheduling, which indicate that the computation time of the proposed MPL-CSS is the fastest, except the MPL method. Additionally, the computation time of the proposed MPL-CSS is higher than that of the EPSO in the 100-unit scheduling condition; however, the operating cost of the proposed MPL-CSS is lower than that of the EPSO. Therefore, the proposed methods can achieve high-quality UC solutions within a reasonable time.
4.2. Seven-Day Unit Scheduling
In the section, the MPL-CSS is implemented to a seven-day unit scheduling. The load curve in [27] is used, and shown in Table 4. For each hour, UC is carried out considering the corresponding load factor. The seven-day unit scheduling result for MPL-CSS, and BF algorithms, which includes operating cost and computation time of 10- to 100-unit systems, is shown in Table 5. It is shown that MPL-CSS results in lower cost as compared to other algorithms. Seldom publications showed the result of a seven-day UC problem. Therefore, Table 5 only give a comparison between the proposed algorithm and BF method.
5. Conclusion
This paper proposes a hybrid algorithm for solving the UC problem. The algo-
![]()
Table 5. Comparison of a seven-days UC problem.
rithm combines the MPL algorithm with the CSS method; the MPL method is utilized to obtain an initial UC solution over a 24-hr period, and the CSS method is then applied to a limited period to achieve a better UC solution. The algorithm allows users to choose between two alternatives―a fast engine using the MPL only and an accurate engine with the scarification of computational time using the MPL-CSS method. The efficiency of the proposed method is proved by a typical system with 10 to 100 units. The UC results by using the proposed algorithm are compared with those obtained by using previously developed methods. The numerical results reveal that the cost of generation using the MPL-CSS is consistently less than those by using other algorithms in most cases. Additionally, the computation time is also superior as compared to other heuristic algorithms.
Acknowledgements
This work was financially supported by the Ministry of Science and Technology in Taiwan under the project of This work was financially supported by the Ministry of Science and Technology in Taiwan under the project of Enhancement of Power Quality for Transmission/Distribution Network and Development of Wheeling Technologies and Operations Planning (Project number: 106-3113- E-194-001-).
Nomenclature
![]()
Load demand for time period t.
![]()
Spinning reserve requirement.
![]()
Hot start cost of unit k.
![]()
Cold start cost of unit k.
![]()
Maximum generation of unit k.
![]()
Minimum generation of unit k.
![]()
Maximum ramp-rate of unit k.
![]()
Set of units.
![]()
Set of wind units.