Mở rộng lưới điện truyền tải bằng mặt cắt tối thiểu dựa trên lý thuyết đồ thị

Nội dung text: Mở rộng lưới điện truyền tải bằng mặt cắt tối thiểu dựa trên lý thuyết đồ thị

1. MỞ RỘNG LƯỚI ĐIỆN TRUYỀN TẢI BẰNG MẶT CẮT TỐI THIỂU DỰA TRÊN LÝ THUYẾT ĐỒ THỊ PGS.TS Trương Việt Anh Ngô Ngọc Bích Đại Học Sư Phạm Kỹ Thuật Tp.HCM Đại Học Sư Phạm Kỹ Thuật Tp.HCM tvanhspkt@gmail.com ngongocbichpy@gmail.com +84-97-741-8527 ABSTRACT General introduction about the role, requirements and goals of transmission expansion planning and methods used for transmission expansion planning. Proposing new method to solve the transmission expansion planning problem as well as specified the objectives. Introduction and classification of mathematical programming problems and presentation detailed about planning methods to solve the transmission expansion planning problem such as Mathematical optimization methods (DC model, AC model, and The branch and bound algorithm and Benders decomposition), meta-heuristic methods (Tabu Search, Genetic Algorithm, Particle Swarm Optimization). Presented the theoretical basis of min-cut algorithm and built min-cut max-flow algorithm to apply to the electric system and calculate on Garver 6 bus diagram. 1. GIỚI THIỆU CHUNG Quy hoạch mở rộng lưới điện TEP (Transmission expansion planning) là một phần quan trọng của quy hoạch hệ thống điện, gắn liền với quy hoạch mở rộng nguồn phát GEP (Generation expansion planning) và sự tăng trưởng của phụ tải. Sau khi có vị trí địa lý của các nhà máy điện và trung tâm phụ tải, cần phải quy hoạch lưới điện với nguyên lý cơ bản là cực tiểu cấu trúc lưới điện và chi phí vận hành nhằm thỏa mãn yêu cầu phân phối điện năng an toàn, liên tục và tin cậy. Các giải pháp quy hoạch cơ bản khi nghiên cứu TEP được đề cập bao gồm: (i) Xây dựng các đường dây truyền tải và trạm biến áp mới song song tại vị trí nghẽn mạch; (ii) Xây dựng các đường dây truyển tải và trạm biến áp mới trên các hướng tuyến mới để chia sẻ luồng công suất tại điểm nghẽn mạch; (iii) Lắp đặt thiết bị bù công suất phản kháng để giảm lượng công suất ảo trên lưới điện; (iv) Lắp đặt TCSC (Thyristor controlled series capacitor) để phân bố lại công suất qua điểm nghẽn mạch; (v) Điều chỉnh công suất nguồn phát nhằm thay đổi luồng công suất qua điểm nghẽn mạch. (vi) Lắp thêm máy phát DG tại những vị trí tậm phụ tải Trang 1
2. Tùy thuộc vào mục tiêu quy hoạch (nâng cao độ tin cậy, ổn định của hệ thống, hiệu quả thị trường điện, hoặc chi phí đầu tư thấp, ) mà có thể chọn biện pháp quy hoạch ưu tiên phù hợp. Trên cơ sở kết quả của các công trình nghiên cứu trước đây đã đạt được, đề tài “Mở rộng lưới truyền tải bằng mặt cắt tối thiểu dựa trên lý thuyết đồ thị” với mục đích nghiên cứu, áp dụng thuật toán mặt cắt tối thiểu "Maximum flow – Min cut" nhằm giới hạn không gian tìm kiếm, rút ngắn thời gian mô phỏng trong bài toán quy hoạch mở rộng lưới điện truyền tải. 2. CƠ SỞ LÝ THUYẾT MẶT CẮT TỐI THIỂU Mạng là đồ thị có hướng G = (V, E), trong đó có duy nhất một đỉnh A không có cung đi vào gọi là điểm phát, duy nhất một đỉnh B không có cung đi ra gọi là đỉnh thu và giá trị của một luồng là: Tổng luồng trên các cung đi ra khỏi đỉnh phát bằng tổng luồng trên các cung đi vào đỉnh thu. Ta gọi lát cắt (X, Y) là một cách phân hoạch tập đỉnh V của mạng thành hai tập rời nhau X và Y, trong đó X chứa đỉnh phát A và Y chứa đỉnh thu B. Khả năng thông qua của lát cắt (X, Y) là tổng tất cả các khả năng thông qua của các cung (u, v) có u ∈X và v ∈Y. Lát cắt với khả năng thông qua nhỏ nhất gọi là lát cắt hẹp nhất "Min cut". Định lý Ford-Fulkerson phát biểu: "Giá trị luồng cực đại trên mạng đúng bằng khả năng thông qua của lát cắt hẹp nhất/cực tiểu". Vậy bài toán mặt cắt tối thiểu là bài toán đi tìm lát cắt có luồng nhỏ nhất. Thuật toán "min cut" Mechtild Stoer và Frank Wagner [17] dựa trên định lý Ford-Fulkerson thiết lập thuật toán xác định mặt cắt tối thiểu "min cut" để xác định lát cắt nhỏ nhất của mạng bằng cách chia tập hợp các đỉnh của mạng thành hai phần riêng biệt, với trọng số của lát cắt là tổng trọng số của các cạnh mà lát cắt đi qua. Cho đồ thị vô hướng W(1.,2) =2 3 5 1 3 2 2 6 2 2 1 3 7 2 3 3 2 4 2 8 4 Trang 2
3. Hình 1. Chọn đỉnh t, s tùy ý; sau lát cắt đầu tiên (G, w, a), a = 2 chia hai phần gồm các đỉnh {1}, {2, 3, 4, 5, 6, 7, 8} với trọng số là w = 5 như Hình 3.2 s 3 5 1 t 2 3 2 f 6 2 2 a 1 3 d 7 2 3 b 2 3 4 2 8 4 c e Hình 2. Đỉnh t(1) và s(5) và lát cắt đầu tiên đi qua t(1)-a(2), t(1)-s(5) Lát cắt thứ hai chia các đỉnh thành hai phần bao gồm {8}, {1, 2, 3, 4, 5, 6, 7} với trọng số là w = 5 như hình 3.3 b 1,5 3 4 c 6 2 2 a 1 3 s 7 2 3 b 2 3 4 2 8 4 c t Hình 3. Lát cắt thứ 2 đi qua t(8)-e(4), t(8)-s(7) Lát cắt thứ ba chia các đỉnh thành hai phần gồm {7,8}, {1, 2, 3, 4, 5, 6} với trọng số là w = 7 như hình 3.4 Trang 3
4. b 1,5 3 4 c 6 2 2 a 1 3 t 7,8 2 3 b 4 4 4 c Hình 4. Lát cắt thứ 3 đi qua t(7,8)-d(3), t(8)-s(4) Lát cắt thứ 4 chia các đỉnh thành hai phần bao gồm {4, 7, 8}, {1, 2, 3, 5, 6} với trọng số là w = 7 và lát cắt thứ 5 chia các đỉnh thành hai phần bao gồm {3, 4, 7, 8} và {1, 2, 5, 6} với trọng số là w = 4 như hình 3.5 b 1,5 3 4 c 6 2 2 a 1 3 t 7,8, 6 3 b 4 b 1,5 3 4 s 6 2 2 a 1 3 3,4, t 7,8 Hình 5. Lát cắt thứ 4 đi qua t(4,7,8)-c(6), t(4,7,8)-s(3); lát cắt thứ 5 đi qua t(3,4,7,8)-s(6), t(3,4,7,8)-a(2) Lát cắt thứ 6 chia các đỉnh thành hai phần bao gồm {1, 5}, {2, 3, 4, 6, 7, 8} với trọng số là w = 7 và lát cắt thứ 7 chia đồ thị thành hai phần {2}, V\{2} với trọng số là w = 9 như hình 3.6 Trang 4
5. b 1,5 3 4 s 6,7, 5 2 a 8,3,4 t v/2 9 2 s Hình 6. Lát cắt thứ 6 đi qua t(1,5)-a(2), t(1,5)-s(3,4,6,7,8); lát cắt thứ 7 đi qua t(V\2)-s(2) Như vậy qua 7 lát cắt, trọng số tại lát cắt thứ 5 w = 4 là nhỏ nhất. Và đây chính là lát cắt tối thiểu. 3. ÁP DỤNG GIẢI THUẬT Thành lập ma trận A=Anxn Là ma trận tổng trọng số (thông lượng) có thể truyền giữa các nút đối với hệ thống n nút. Trong đó thành phần đường chéo chính aii=0; các thành phần còn lại aij là thông lượng liên kết giữa hai nút i-j có giá trị đối xứng nhau qua đường chéo chính (aij= aji). Những nút không nối với nhau có giá trị aij=0. 푠 1 2 푡 푠 푠푠 푠1 푠2 푠푡 1 [ 1푠 11 21 1푡] 2 2푠 21 22 2푡 푡 푡푠 푡1 푡2 푡푡 Trang 5
6. Start A = [A]nxn S={s}, T={t} Di chuyển nút i vào Di chuyển nút i vào Σsi=Σasi Σit=Σait tổ hợp S={s,i} tổ hợp T={t,i} Thêm tổ hợp Csi,Cit, Σsi, Σit vào listcut Y Max=max[asi] Σsi > Σit N Y Σsi < Σit Max=max[ait] N In ra danh Y A = [A] sách listcut 2x2 End Max=max[asi,ait] Y max = ait N Hình 7. Lưu đồ giải thuật xác định luồng công suất cực đại Các trường hợp xảy ra tại vị trí lát cắt Trường Lát cắt cực tiểu Ghi chú hợp t Nguồn không đáp ứng 1 c= csi Thuộc tập nguồn i 1 Lưới đáp ứng i s s Nguồn đáp ứng 2 c= cit Thuộc tập tải i 1 Lưới đáp ứng it Trang 6
7. Trường Lát cắt cực tiểu Ghi chú hợp n Nguồn đáp ứng 3 c=  cij Thuộc tập nhánh ij,1 Lưới không đáp ứng ij t Nguồn chưa xác định 4 c= csi + Thuộc tập nguồn và nhánh i 1 Lưới chưa xác định i s s Nguồn đáp ứng 5 c= cit + Thuộc tập tải và nhánh i 1 Lưới không đáp ứng it Nguồn chưa xác định c= + c= + c= 6 Lưới chưa xác định Thuộc tập nguồn, tải và nhánh 4. ÁP DỤNG TRÊN SƠ ĐỒ ĐIỂN HÌNH Trong nghiên cứu của mình, Len L.Garver [7] đưa ra sơ đồ 6 thanh cái hiện hành và kế hoạch mở rộng nguồn, tải (Hình 3.11); các thông số nguồn và tải cho ở Bảng 3.3, các thông số lưới hiện hành cho ở Bảng 3.4 240 MW 150 MW Bus 5 Bus 1 360 MW Bus 2 Bus 3 40 MW 240 MW 600 MW Bus 4 Bus 6 160 MW Trang 7
8. Hình 8. Sơ đồ Garver 6 bus Bảng 1. Các thông số nguồn và phụ tải lưới Garver 6 bus Bus Công suất nguồn (MW) Công suất tải (MW) 1 150 80 2 0 240 3 360 40 4 0 160 5 0 240 6 600 0 Tổng 1,110 760 Xây dựng ma trận thông lượng [A] liên kết các bus trong hệ thống như sau: Bảng 2. Ma trận thông lượng lưới Garver 6 bus 0 6 7 1 2 3 4 5 (s) (t) 0 15 36 60 0 0 0 0 0 (s) 0 0 0 15 10 10 0 1 0 0 80 80 0 0 0 10 10 10 10 24 2 0 0 0 0 0 0 0 0 36 10 10 0 3 0 0 0 40 0 0 0 10 10 16 4 0 80 0 0 0 0 0 0 10 10 0 24 5 0 0 0 0 0 0 0 60 10 10 0 6 0 0 0 0 0 0 0 Trang 8
9. 0 6 7 1 2 3 4 5 (s) (t) 7 24 16 24 0 0 80 40 0 (t) 0 0 0 Xuất phát từ cắt nguồn và cắt tải, theo thuật toán MaxFlow-Min-Cut, giải và xác định được các mặt cắt trong bảng 3.7. Bảng 3. Tập hợp các mặt cắt lưới Garver 6 bus hiện trạng No Cut Capa Passed Secsion Set (MW) Gens Loads Branches 1 Gens 1,110 1, 2, 6 2 Loads 760 1, 2, 3, 4, 5 3 Min- 710 1, 3 2-6, 4-6 cut 4 CUT 720 1, 2, 3-5, 1-5 2 3, 4 5 CUT 880 1, 2, 3 3-5, 2-6, 2-3, 3 1-5, 1-2, 2-4 6 CUT 830 1 3, 4 3-5, 2-6, 2-3, 4 1-4, 2-4 Trang 9
10. Hình 9. Mô phỏng lưới điện Garver 6 bus khi chưa phân bố công suất Kết quả tính toán nhận được 2 điểm thắt cổ chai là: . Min-cut: có tổng thông lượng là 710 MW, đi qua các nguồn 1, 3 và đi qua các nhánh 2-6 và 4-6. . Cut-2: tổng thông lượng là 720 MW, đi qua các tải 1, 2, 3, 4 và đi qua các nhánh 1-5 và 3-5. 5. PHƯƠNG ÁN KÉO THÊM TUYẾN DÂY SONG SONG VỚI TUYẾN DÂY CŨ Bảng 4. Tập hợp nguồn và tải sau khi phân bố công suất Bus 1 2 3 4 5 6 Nguồn 150 270 340 (MW) Kéo thêm 1-5 4-6 3-5 2-6 tuyến dây mới song song với tuyến cũ Tải (MW) 80 240 40 160 240 Trang 10
11. Hình 10. Kết quả sau khi kéo thêm đường dây mới và giảm công suất phát G6 6. MỞ RỘNG LƯỚI ĐIỆN BẰNG DÂY DẪN SIÊU NHIỆT Chỉ cần thay dây với tiết diện như cũ nhưng khả năng mang tải tăng gấp 1,6-2,0 lần so với dây hiện hữu, không cần thay thế các kết cấu đã có sẵn (móng cột, cột ). Sử dụng công nghệ vật liệu mới: chỉ cần thay dây với tiết diện như cũ nhưng khả năng mang tải tăng gấp 1,6-2,0 lần so với dây hiện hữu, không cần thay thế các kết cấu đã có sẵn (móng cột, cột ) . Chi phí thay dây siêu nhiệt trên nhánh 2-6, 4-6 푠푛 1= 0 (퐿4−6 + 퐿2−6) 0 = 0.3 (tr $) 푠푛1 =0.3(30 +30) = 18 (tr $ ) Trang 11
12. Hình 11. Mô phỏng sau khi phân bố công suất Ngoài dùng dây dẫn siêu nhiệt ta không thể dùng tụ bù để điều khiển dòng công suất qua các nhánh khác , do tuyến dây 2-4, 4-6, đã đến hết năng lực mang tải phương án kéo thêm tuyến dây mới song song với tuyến dây cũ 7. CHI PHÍ KÉO THÊM TUYẾN DÂY MỚI 퐿3−5 = 20 ( mile) Chi phí cả cho làm trụ điện ,nhân công , thiết bị điện, giải tỏa mặt bằng cho tuyến dây mới 1mile =0.74 (tr $ ) 2 = 20 x 0.74= 14.8 (tr $ ) Tiến hành bù trên nhánh 2-3 (2−3) = 30 Mvar 1 =(30x 6000) = 0.18 (tr $ ) Với 1 0 = 6000 $ Trang 12
13. Tổng chi phí Σ2 = 1 + 1=14.8 +0.18 = 14.98 (tr $ ) Hình 12. Mô phỏng sau khi tiến hành bù 2-3 và kéo thêm dây 3-5 8. HƯỚNG PHÁT TRIỂN TIẾP THEO CỦA ĐỀ TÀI Bên cạnh các kết quả đạt được, thuật toán Min-cut Max-flow vẫn còn những hạn chế như: Chưa có hàm chi phí, chưa tính đến các ràng buộc về điện áp, phân bố tối ưu công suất Để tiếp tục phát triển đề tài, cần nghiên cứu bổ sung thêm vào thuật toán hàm chi phí, các ràng buộc về điện áp, phân bố công suất; cũng như kết hợp với các phương pháp quy hoạch khác (như TS, PSO ) trong đó thuật toán Min-cut Max-flow là phép tính ban đầu để hạn chế không gian tìm kiếm. Trang 13
14. TÀI LIỆU THAM KHẢO [1] Võ Văn Tuấn Dũng. (2007). Giáo trình quy hoạch tuyến tính. NXB Thống kê, tr. 3- 6. [2] Nguyễn Lân Tráng. (2007). Giáo trình quy hoạch phát triển hệ thống điện. NXB Khoa học và Kỹ thuật, tr. 179-183. [3] C. W. Lee, Simon K. K. Ng, J. Zhong, and Felix F. Wu. (2006). Transmission Expansion Planning From Past to Future. Proc. Power Systems Conf. Expo. (PSCE 06), pp.257-265. [4] Reza Hemmati, Rahmat-Allah Hooshmand, Amin Khodabakhshian. (2013). State- of-the-art of transmission expansion planning: Comprehensive review. Renewable and Sustainable Energy Reviews 23 (2013), pp.312–319. [5] S. H. M. Hashimoto, R. Romero and J. R. S. Mantovani. (2003). Efficient linear programming algorithm for the transmission network expansion planning problem. Proc. IEE-Gen. Transm. Dist. Vol.150, pp. 536-542, Sept. 2003. [6] Tohid Akbari, Mohammad Tavakoli Bina, Ali Abedini. (2012). AC-OPF Based Static Transmission Expansion Planning: A Multiobjective Approach. 20th Iranian Conference on Electrical Engineering, (ICEE2012), Tehran, Iran, May. 2012. [7] Len L. Garver. (1970). Transmission Network Estimation Using Linear Programming. IEEE Transactions on power apparatus and systems. Vol.PAS-89, No.7, pp. 1688-1697. September/October 1970. [8] S.Haffner, A.Monticelli, A.Garcia, J.Mantovani and R.Romero. (2001). Branch and bound algorithm for transmission system expansion planning using a transportation model. IEE Proceedings-Generation, Transmission and Distribution. Vol.147, No.3, pp. 149-156. May. 2001. [9] F. Wen and C. S. Chang. (1997). Transmission network optimal planning using the Tabu Search method. Electric Power Systems Research. No. 42, pp.153–163, Aug. 1997. Trang 14
15. [10] Edson Luiz da Silva, Jorge Mauricio Areiza Ortiz, Gerson Couto de Oliveira, and Silvio Binato. (2001). Transmission Network Expansion Planning Under a Tabu Search Approach. IEEE Transactions on Power systems. Vol. 16, No. 1, pp. 62-68. Feb. 2001. [11] I. J. De Silva, M. J. Rider, R. Romero, and C. A. Murari. (2006). Genetic algorithm of Chu and Beasley for static and multistage transmission expansion planning. IEEE Power Engineering Society General Meeting (PES '06). Montreal, Canada, June 2006. [12] Jin YX, Cheng HZ, Yan JY M, Zhang L. (2006). New discrete method for particle swarm optimization and its application in transmission network expansion planning. Elect Power Syst Res 77(2007):227–233. April 2006. [13] Shayeghi H, Mahdavi M, Bagheri A. (2010). Discrete PSO algorithm based optimization of transmission lines loading in TNEP problem. Energy Convers Manage. 51, pp. 112–21, 2010. [14] I. Miranda de Mendonça, I. Chaves Silva Junior, A. L. M. Marcato. (2014). Static planning of the expansion of electrical energy transmission systems using particle swarm optimization. International Journal of Electrical Power & Energy Systems, Vol. 60, pp. 234-44. Sept. 2014. [15] Thanhlong Duong, Jiangang Yao, Vietanh Truong. (2012). Optimal placement of TCSC based on min-cut algorithm for congestion management in deregulated electricity market. Journal of Electrical Engineering and Technology (IJEET), ISSN 0976 – 6545(Print), ISSN 0976 – 6553(Online) Volume 3, Issue 1. January-June 2012. [16] ThanhLong Duong, Yao JianGang, Tong Kang. (2014). Optimal Location of Thyristor-controlled-series-capacitor using Min Cut Algorithm. TELKOMNIKA Indonesian Journal of Electrical Engineering Vol.12, No.5, pp. 3649-3661. May 2014. Trang 15
16. TRANSMISSION EXPANSION PLANNING USING MIN CUT ALGORITHM PGS.TS Trương Việt Anh Ngô Ngọc Bích Đại Học Sư Phạm Kỹ Thuật Tp.HCM Đại Học Sư Phạm Kỹ Thuật Tp.HCM tvanhspkt@gmail.com ngongocbichpy@gmail.com +84-97-741-8527 ABSTRACT General introduction about the role, requirements and goals of transmission expansion planning and methods used for transmission expansion planning. Proposing new method to solve the transmission expansion planning problem as well as specified the objectives. Introduction and classification of mathematical programming problems and presentation detailed about planning methods to solve the transmission expansion planning problem such as Mathematical optimization methods (DC model, AC model, and The branch and bound algorithm and Benders decomposition), meta-heuristic methods (Tabu Search, Genetic Algorithm, Particle Swarm Optimization). Key words: Transmission Expansion Planning Using Min Cut Algorithm TÀI LIỆU THAM KHẢO [1] Võ Văn Tuấn Dũng. (2007). Giáo trình quy hoạch tuyến tính. NXB Thống kê, tr. 3- 6. [2] Nguyễn Lân Tráng. (2007). Giáo trình quy hoạch phát triển hệ thống điện. NXB Khoa học và Kỹ thuật, tr. 179-183. [3] C. W. Lee, Simon K. K. Ng, J. Zhong, and Felix F. Wu. (2006). Transmission Expansion Planning From Past to Future. Proc. Power Systems Conf. Expo. (PSCE 06), pp.257-265. [4] Reza Hemmati, Rahmat-Allah Hooshmand, Amin Khodabakhshian. (2013). State- of-the-art of transmission expansion planning: Comprehensive review. Renewable and Sustainable Energy Reviews 23 (2013), pp.312–319. Thông tin liên hệ tác giả: xác nhận của GVHD Họ tên: Ngô Ngọc Bích Điện Thoại :0977418527 Email : Ngongocbichpy@gmail.com Trang 16
17. BÀI BÁO KHOA HỌC THỰC HIỆN CÔNG BỐ THEO QUY CHẾ ĐÀO TẠO THẠC SỸ Bài báo khoa học của học viên có xác nhận và đề xuất cho đăng của Giảng viên hướng dẫn B n ti ng Vi t ©, T NG I H C S PH M K THU T TP. H CHÍ MINH và TÁC GI Bản quếy n táệc ph mRƯ ãỜ cĐ bẠ o hỌ b Ưi Lu tẠ xu t Ỹb n vàẬ Lu t S hỒ u trí tu Vi t Nam. NgẢhiêm c m m i hình th c xu t b n, sao ch p, phát tán n i dung khi c a có s ng ý c a tác gi và ả ng ề i h ẩ pđh đưm ợK thuả tộ TP.ở H ậChí Mấinh.ả ậ ở ữ ệ ệ ấ ọ ứ ấ ả ụ ộ hư ự đồ ủ ả Trườ Đạ ọCcÓ Sư BÀI BạÁO KHỹ OA ậH C T ồT, C N CHUNG TAY B O V TÁC QUY N! ĐỂ Ọ Ố Ầ Ả Ệ Ề Th c hi n theo MTCL & KHTHMTCL h c 2017-2018 c a T vi n ng i h c S ph m K thu t Tp. H Chí Minh. ự ệ Năm ọ ủ hư ệ Trườ Đạ ọ ư ạ ỹ ậ ồ