臺灣博碩士論文加值系統

由於配電系統復電問題屬於0與1的複雜開關組合問題，很難以數學規劃方法解決。以往一般經由搜尋過程來求解復電的問題，都以搜尋樹來表示其問題空間。在配電系統開關操作的問題中，系統上每個開關都有開啟、閉合兩種狀態。因此，一個包含有n個開關的系統而言，完整的問題空間最壞情況下將有2n種狀態，對於一個實際的配電系統復電開關操作組合而言，將使得問題太過龐大而難以在有限時間內處理。
本論文提出應用限制條件滿足(Constraint Satisfaction)法求解配電系統復電問題。利用配電系統運轉下的各種限制條件，使得決策變數（開關啟／閉狀態）間彼此的值域能夠有效地刪除不一致值，而避免重覆無謂的搜尋；因此在處理配電系統中最佳復電策略的問題，可以大幅縮小問題空間，提昇搜尋的速率。本文所提限制條件滿足法包含有反向搜尋(Back-Tracking Operation)、順向測試(Forward Checking Operation)、及前瞻推論(Look Ahead Inference Operation)，主要係依據變數間彼此的限制，在變數本身所允許的值域中找到符合所有條件的解。當問題之任一變數給定一值後，限制條件滿足法將利用與此給定值之變數相關的限制條件，主動的將一些不可行解於搜尋空間中剔除。其在搜尋過程中，對於每一個未給定變數之值域值，利用限制條件間之限制式去刪除不合適的值域值。並利用深度優先支界(Depth-First Branch and Bound)法在可行解中尋求最佳解。
本文中將於單故障點與雙故障點的兩個配電系統復電問題上，分別以限制條件滿足法與傳統模擬退火法(Simulated Annealing)進行問題求解之結果比較，以分析不同之求解方法對所得結果的影響。由測試結果得知，限制條件滿足法能求得與模擬退火法相近之近似最佳解，而在執行時間比較上，由於限制條件滿足法隨著限制條件愈趨嚴格而使搜尋空間能更有效減少，因而求解之速度相對於模擬退火法更為快速。

Due to the complicated combinatorial problem of distribution-system restoration with on/off switching operations, it is difficult to use conventional mathematical planning methods to solve this problem. Traditionally, through a decision-tree formulation, the problem is solved by means of a searching algorithm. In the switching operation problem of a distribution system, a switch in the system will be in on or off state. Therefore, in the worst case, an n-switch system would have a complete problem space of 2n states. For a combination of restoration switching operations in a practical distribution system, the dimension of problem is often too huge to solve in a limited time.
In this thesis, an application of constraint-satisfaction method is proposed to cope with the distribution-system restoration problem. By using different constraint conditions, domains of decision variables (on/off states of switches) that are not consistent with each other are deleted. Such an approach can thus greatly reduce the search space. The constraint-satisfaction method proposed in this thesis contains back-tracking operation, forward checking operation, and look-ahead inference operation. Among the feasible domains of individual decision variables, these operations find the feasible solutions according to the constraints between the decision variables. When any variable is assigned a value, the constraint-satisfaction method would employ constraints to delete the infeasible solutions from the searching space. In the searching process, the constraints are thus relied on to trim the solution space as much as possible. After that, a depth-first branch-and-bound optimization approach serves to find the optimal solution from the reduced feasible solution space.
Cases of single-fault point and double-fault point in two distribution-system restoration problems are used to test the proposed constraint-satisfaction method in comparison with the traditional simulated-annealing (SA) method. The impacts of different solution methods on the results are analyzed. The testing results reveal that the constraint-satisfaction approach can find the near-optimal solution obtained from the SA method within a far shorter solution time, owing to the searching space greatly reduced by the rigorous constraints.

第一章 緒論1
1-1 研究動機1
1-2 研究範圍2
1-3 研究方法回顧4
1-4 研究概要與目的5
1-5 論文架構6
第二章 配電系統之復電問題7
2-1 前言7
2-2 配電系統網路架構8
2-3 配電系統的操作狀態9
2-3-1 操作狀態之定義9
2-3-2 操作狀態的轉換13
2-4 配電系統負載潮流計算15
2-4-1 定功率負載18
2-4-2 定電流負載19
2-5 復電問題之目標函數與限制條件20
2-5-1 目標函數20
2-5-2 限制條件22
第三章 現有隨機搜尋方法25
3-1 前言25
3-2 模擬退火法介紹25
3-2-1 演算法則26
3-2-2 演算法則步驟30
3-2-3 演算法則結構31
3-3 模擬退火法應用於復電問題35
第四章 限制條件滿足法38
4-1 前言38
4-2 限制條件滿足問題38
4-3 限制條件滿足解配電系統復電問題43
4-3-1 反向搜尋43
4-3-2 順向測試49
4-3-3 前瞻推論53
4-4 復電問題之最佳化58
第五章 數值測試與結果分析62
5-1 前言62
5-2 例一：32個負載中心配電系統 62
5-2-1 系統簡介62
5-2-2 單故障點之數值測試62
5-2-3 雙故障點之數值測試67
5-3 例二：69個負載中心配電系統 71
5-3-1 系統簡介71
5-3-2 單故障點之數值測試71
5-3-3 雙故障點之數值測試77
5-4 綜合討論 79
第六章 結論與未來研究方向82
6-1 結論82
6-2 未來研究方向82

[1] K.P.Brand, J. Kopainsky, and W. Wimmer, "Topology-based Interlocking of Electrical Substation," IEEE Transactions on Power Delivery, Vol. PWRD-1, No. 3, pp. 118-126, July 1986.
[2] A.M. Stankovic and M.S. Calovic, "Graph Oriented Algorithm for Steady-State Security Enhancement in Distribution Networks," IEEE Transactions on Power Delivery, Vol. 4, No. 1, pp. 539-544, 1989.
[3] K. Aoki, K. Nara, and T. Satoh, "New Configuration Algorithm for Distribution System Priority Constrained Emergency Service Restoration," Proceedings of IFAC Conference on Power System and Plant Control, Seoul, Korea, pp. 443-448, 1989.
[4] A.L. Morelato and A. Monticelli, "Heuristic Search Approach to Distribution System Restoration," IEEE Transactions on Power Delivery, Vol. 4, No. 4, pp. 2235-2241, 1989.
[5] Y.Y. Hsu, H.M. Huang, H.C. Kuo, S.K. Peng, C.W. Chang, K.J. Chang, H.S. Yu, C.E. Chow, and R.T. Kuo, "Distribution System Service Restoration Using A Heuristic Search Approach," IEEE Transactions on Power Delivery, Vol. 7, pp. 734-740, 1992.
[6] Q. Zhou, D. Shirmohammadi, and W.H. Edwin Liu, "Distribution Feeder Reconfiguration for Service Restoration and Load Balancing," IEEE Transactions on Power System, Vol. 12, No 2, pp. 724-735, 1997.
[7] Y.Y. Hsu and H.C. Kuo, "A Heuristic Based Fuzzy Reasoning Approach for Distribution System Service Restoration," IEEE Transactions on Power Delivery, Vol. 9, No 2, pp. 948-953, April 1992.
[8] D.S. Kirschen and T.L. Volkmann, "Guiding a Power System Restoration with an Expert System," Paper 96 WM 008-3 PWRD, presented at the 1996 IEEE/PES Winter Meeting, January 21-25, 1996, Baltimore, Maryland, USA.
[9] H.J. Lee and Y.M. Park, "A Restoration Aid Expert System for Distribution Substations," IEEE Transactions on Power System, Vol. 8, No. 2, pp. 508-514, May 1993.
[10] C.C. Liu, S.J. Lee, and S.S. Venkata, "An Expert System Operation Aid for Restoration and Loss Reduction of Distribution System," IEEE Transactions on Power System, Vol. 3, No. 2, pp. 619-626, 1988.
[11] S. Civanlar, J.J. Grainger, H. Yin, and S.S.H. Lee, "Distribution Feeder Reconfiguration for Loss Reduction," IEEE Transactions on Power Delivery, Vol. PWRD-3, pp. 1217-1223, 1988.
[12] C.C. Kuo and H.C. Chang, "Applying a Refined Genetic Algorithm to Network Reconfiguration for Loss Reduction," IEE Japan Power & Energy Society Annual Proceeding, 1994.
[13] C.H. Castro, J.B. Bunch, and T.M. Topka, "Generalized Algorithm for Distribution Feeder Deployment and Sectionalizing," IEEE Transactions on Power Apparatus and Systems, Vol. 99, No. 2, pp. 549-557, 1980.
[14] L.J. Fogel, A.J. Owens, and M.J. Walsh, "Artificial Intelligence Through Simulated Evolution," New York, John Wiley & Sons, Inc. 1966.
[15] D. Shirmohammadi, "Service Restoration in Distribution Networks via Network Reconfiguration," IEEE Transactions on Power Delivery, Vol. 7, No. 2, pp. 952-958, 1992.
[16] N.D.R. Sarma, V.C. Prasad, K.S.P. Rao, and V. Sankar, "A New Network Reconfiguration Technique for Service Restoration in Distribution System," IEEE Transactions on Power Delivery, Vol. 9, No. 4, pp. 1936-1942, 1994.
[17] M.E. Baran and F.F. Wu, "Network Reconfiguration in Distribution System for Loss Reduction and Load Balancing," IEEE Transactions on Power Delivery, Vol. 4, No. 2, pp. 1401-1407, 1989.
[18] H.C. Chang and C.C. Kuo, "Network Reconfiguration in Distribution Systems Using Simulated Annealing," Electric Power Systems Research, Vol. 29, pp. 227-238, 1994.
[19] H.D. Chiang and J.J Rene, "Optimal Network Reconfiguration in Distribution Systems: Part 2: Solution Algorithms and Numerical Results," IEEE Transactions on Power Delivery, Vol. 5, No. 3, pp. 1568-1574, 1990.
[20] N. Metropolis, A.W. Rosebluth, M.N. Rosebluth, A.H. Teller, and E. Teller, "Equation of State Calculations by Fast Computing Machines," The Journal of Chemical Physics, Vol. 21, No. 6, pp. 1087-1092, 1953.
[21] S. Kirkpatrick, C.D. Gelatt, and M.P. Vechi, "Optimization by Simulated Anealing," Science 220, pp. 671-680, 1983.
[22] V. Cerny, "Thermodynamical Approach to the Traveling Salesman Problem: An Efficient Simulated Algorithm", Journal of Optimization Theory and Application, Vol. 45, pp. 41-51, 1985.
[23] R.F. Lee, "Grounding of Computers and Other Similar Sensitive Equipment", IEEE Transactions on Industry Applications, Vol. IA-23, No. 3, pp. 408-411, June 1987.
[24] K.P. Wong and C.C. Fung, "Simulated Annealing Based Economic Dispatch Algorithm," IEE Proceedings-C, Vol. 140, No. 6, pp. 509-515, November 1993.
[25] M.S. Fox, "Constraint-Directed Search: A Case Study of Job-Shop Scheduling," Technical Report CMU-CS-83-161, Carnegie-Mellon University, December 1983.
[26] A.K. Mackworth, "Consistency in Networks of Relations," AI Journal, Vol. 8, No. 1, pp. 99-118, 1977.
[27] H. Simonis, "Test Pattern Generation with Logic Programming," New Aspects of Research for Testing of VLSI Circuits, Ising, W. Germany, March 1988.
[28] H. Simonis and M. Dincbas, "Using an Extended Prolog for Digital Circuit Design," IEEE International Workshop on AI Applications to CAD Systems for Electronics, pp. 165-188, Munich, W. Germany, October 1987.
[29] H. Simonis and M. Dincbas, "Using Logic Programming for Fault Diagnosis in Digital Circuit," German Workshop on Artificial Intelligence (GWAI-87), pp. 139-148, Geseke, W. Germany, September 1987.
[30] B.J. Kuipers, "Qualitative Simulation," Artificial Intelligence, Vol. 29, No. 3, pp. 289-338, September 1986.
[31] A.K. Mackworth and E.C. Freuder, "The Complexity of some Polynomial Network Consistency Algorithms for Constraint Satisfaction Problems," Artificial Intelligence, Vol. 25, pp. 65-74, 1985.
[32] U. Montanari, "Networks of Constraints: Fundamental Properties and Applications to Picture Processing," Information Science, Vol. 7, No. 2, pp. 95-132, 1974.
[33] M. Kubale and D. Jackwski, "A Generalized Implicit Enumeration Algorithm for Graph Coloring," CACM, Vol. 28, No. 4, pp. 412-418, 1985.
[34] E.C. Freuder and R.J. Wallace, "Partial Constraint Satisfaction," Artificial Intelligence, Vol. 58, pp. 21-70, 1992.
[35] R.M. Haralick and G.L. Elliot, "Increasing Tree Search Efficiency for Constraint Satisfaction Problem," Artificial Intelligence, Vol. 14, pp. 263-313, 1980.
[36] V.H. Pascal, Constraint Satisfaction in Logic Programming, The Massachusetts Institute of Technology Press, 1989.
[37] S.K. Goswami and S.K. Basu, "A New Algorithm for the Reconfiguration of Distribution Feeders for Loss Minimization," IEEE Transactions on Power Delivery, Vol. 7, No. 3, pp. 1484-1491, 1992.
[38] H.D. Chiang and J.J Rene, "Optimal Network Reconfiguration in Distribution Systems: Part 2: Solution Algorithms and Numerical Results," IEEE Transactions on Power Delivery, Vol. 5, No. 3, pp. 1568-1574, 1990.