Nghiên cứu kết hợp lý thuyết đồ thị và thuật toán di truyền

NGHIÊN CỨU KẾT HỢP LÝ THUYẾT ĐỒ THỊ VÀ THUẬT TOÁN DI TRUYỀN NHẰM TỐI ƯU HÓA SƠ ĐỒ LẮP ĐẶT CÁC NOISE LOGGER TRONG PHƯƠNG PHÁP TIỀN ĐỊNH VỊ KHI THỰC HIỆN DÒ TÌM RÒ RỈ TRÊN ĐƯỜNG ỐNG CẤP NƯỚC 

Tóm tắt

Hiện nay, nhiều phương pháp và thiết bị đã được nghiên cứu phát triển nhằm hỗ trợ cho công tác dò tìm rò rỉ trên đường ống cấp nước. Trong nghiên cứu này, đề xuất một phương pháp nhằm đưa ra sơ đồ bố trí lắp đặt tối ưu bộ thiết bị tiền định vị, bao gồm các thiết bị noise logger ghi nhận âm thanh rò rỉ trên mạng lưới cấp nước, nhằm tìm kiếm hoặc dự báo rò rỉ tại một khu vực phân vùng tách mạng. Phương pháp sử dụng kết hợp giữa lý thuyết đồ thị và thuật toán di truyền để đưa ra tổ hợp bố trí tối ưu, trong đó dữ liệu đồ thị được xây dựng theo dữ liệu mô hình thủy lực mạng lưới từ Epanet, với các đỉnh đại diện cho nút và các cạnh đại diện cho đường ống trong mạng lưới. Các kết quả thử nghiệm được tiến hành tại ba khu vực nghiên cứu cho thấy phương pháp đề xuất có khả năng xác định tổ hợp bố trí lắp đặt noise logger một cách hiệu quả, có khả năng triển khai áp dụng thực tiễn trong quản lý và vận hành hệ thống cấp nước.

Từ khóa: dò tìm rò rỉ, thiết bị tiền định vị, noise logger, lý thuyết đồ thị, thuật toán di truyền.

ĐẶT VẤN ĐỀ

Nước không doanh thu (NKDT) đã và đang là một vấn đề được ưu tiên hàng đầu đối với các công ty cấp nước (CTCN). Việc quản lý NKDT cho phép các CTCN có thể mở rộng và cải thiện dịch vụ đồng thời với nâng cao hiệu suất tài chính [1].

Giải pháp phổ biến trong việc giảm NKDT là thực hiện thiết lập các phân vùng tách mạng (DMA, District Metered Area) [1], [2]. Trong mỗi DMA, tỷ lệ NKDT thông thường sẽ bao gồm 02 thành phần chính là thất thoát thực (lượng nước rò rỉ trên mạng lưới) và thất thoát biểu kiến (như sai số đồng hồ nước, tiêu thụ không ghi nhận). Để giảm thất thoát do rò rỉ tại các DMA, có 03 phương pháp phổ biến có hiệu quả cao là: i) sử dụng máy khuếch đại nghe âm trực tiếp; ii) sử dụng thiết bị tương quan âm và iii) sử dụng bộ thiết bị tiền định vị (gồm các noise logger, thiết bị ghi và phân tích âm thanh rò rỉ). Trong đó, phương pháp (i) và (ii) là các phương pháp nhằm xác định vị trí nghi ngờ gần với vị trí có xảy ra rò rỉ nhất; phương pháp (iii) lại nhằm khoanh vùng đường ống nghi ngờ có rò rỉ, hỗ trợ cho các phương pháp còn lại đạt hiệu quả cao nhất. Hình 1 mô tả mối tương quan giữa các phương pháp [2].

Tuy nhiên, bộ thiết bị tiền định vị thường được sản xuất với số lượng hữu hạn trong một bộ (thông thường là 08 noise logger/bộ), ngoài ra các CTCN do vấn đề về chi phí nên cũng không thể trang bị với số lượng lớn. Do đó, khi áp dụng lắp đặt trên mạng lưới với số lượng hữu hạn các logger, cần thiết phải xem xét và xác định các vị trí lắp đặt (phổ biến là lắp đặt trên các van) sao cho khả năng thu thập dữ liệu là cao nhất, từ đó tối ưu khả năng phân tích và khoanh vùng nghi ngờ có rò rỉ.

Theo đó, việc nghiên cứu phương pháp xác định tối ưu hóa sơ đồ lắp đặt bộ thiết bị tiền định vị với số lượng hữu hạn các noise logger, kết hợp với các phương pháp khác, nhằm tìm ra mô hình lắp đặt tối ưu có thể ứng dụng lắp đặt tại thực tế tại các DMA phục vụ dự báo rò rỉ là cần thiết.

CƠ SỞ LÝ THUYẾT

Âm thanh rò rỉ và nguyên lý hoạt động của các noise logger

Tại một vị trí rò rỉ, khi nước thoát/chảy ra tại một vị trí mở trên thân ống hoặc phụ tùng, sẽ tạo ra dao động và hình thành âm thanh. Mỗi âm thanh ghi nhận sẽ có một loại chỉ số về ‘âm lượng’ và ‘tần số’ được hình thành do nhiều yếu tố cộng hưởng với nhau như: áp lực nước, hình dạng điểm rò rỉ, âm ma sát giữa nước với vật liệu; tần số rung động và khả năng lan truyền âm theo vật liệu; môi trường xung quanh…

Phương pháp tiền định vị sẽ dựa vào khả năng ghi nhận âm thanh của các noise logger, đặt tại các vị trí có khả năng thu nhận âm thanh trực tiếp từ mạng lưới [4], [5] (ví dụ như đầu van, hầm đồng hồ). Âm rò rỉ được xác định bởi mỗi logger riêng lẻ, dựa trên tiếng ồn trong ống chung một "tần số" hoặc "âm thanh" và lớn hơn tiếng ồn nền. Sau đó, truyền âm về lại người quản lý (thu thập trực tiếp hoặc truyền tín hiệu về bộ tổng hợp), phần mềm cung cấp kèm theo sẽ biểu diễn âm thanh ‘ồn’ theo một giao diện đồ họa hỗ trợ người vận hành. Các logger thường được cài đặt để ghi nhận dữ liệu vào khoảng thời gian ban đêm, để có thể hạn chế các tiếng ồn khác như giao thông và khách hàng dùng nước, và ban đêm cũng là thời gian có áp lực cao nên khả năng tạo và truyền âm thanh rò rỉ cũng thuận lợi.

Do âm thanh sẽ bị suy giảm (hấp thụ) theo khoảng cách lan truyền âm, nên việc ghi nhận âm thanh phụ thuộc vào khả năng truyền âm từ điểm rò rỉ đến logger. Theo đặc tính, âm thanh khi truyền đến 01 logger sẽ tương đương với khoảng cách ngắn nhất từ điểm rò rỉ đó theo các đường ống cấp nước nối với nhau về lại logger. Như vậy, khả năng ghi nhận âm thanh tốt nhất nghĩa là vị trí các noise logger được bố trí tại vị trí sao cho khả năng âm được truyền đến các logger ngắn nhất, nhằm giảm độ triệt tiêu suy giảm âm khi truyền đi. Để giải quyết bài toán này, nghiên cứu sẽ ứng dụng kết hợp giữa sơ đồ mạng lưới với lý thuyết đồ thị và thuật toán di truyền như trình bày trong phần sau.

Lý thuyết đồ thị

Lý thuyết đồ thị (LTĐT) là một ngành của toán học và khoa học máy tính nghiên cứu về đồ thị, là cấu trúc dữ liệu bao gồm tập hợp các đỉnh (hay nút) và cạnh (liên kết giữa các đỉnh). LTĐT đã được nghiên cứu ứng dụng trong việc dò tìm rò rỉ trên mạng lưới cấp nước dựa trên sơ đồ mạng lưới (topology network) và dữ liệu đo thực tế. Điển hình với phương pháp xử lý tín hiệu trên đồ thị (Graph signal), trên cơ sở phân tích dữ liệu thay đổi áp lực và lưu lượng [6]; hoặc phương pháp phân hoạch đồ thị (Graph Partitioning) mà trong đó mạng lưới có khả năng rò rỉ sẽ được phân chia thành hai hoặc nhiều mạng nhỏ, và áp dụng phương pháp bảng cân bằng nước được sử dụng để truy vết rò rỉ đến một trong các mạng nhỏ này [7].

Trong nghiên cứu này sẽ nghiên cứu theo hướng ứng dụng LTĐT với thuật toán Dijkstra, là bài toán tìm đường đi giữa hai đỉnh sao cho tổng các trọng số của các cạnh tạo nên đường đi là nhỏ nhất, áp dụng cho đồ thị có hướng hoặc vô hướng, với các cạnh có trọng số (khoảng cách) không âm [8], tương tự với cấu trúc của mạng lưới cấp nước được biểu diễn dưới dạng đồ thị. Hướng nghiên cứu này chỉ yêu cầu cấu trúc sơ đồ của mạng lưới mà không yêu cầu dữ liệu áp lực hay lưu lượng. Tuy nhiên các nút phải được chia sao cho đảm bảo có khả năng mô phỏng gần đúng rò rỉ xảy ra bất kỳ vị trí nào trên mạng lưới.

Phương pháp nghiên cứu

Khi có rò rỉ xảy ra tại một nút bất kỳ trên mạng lưới, khả năng phân tích để nhận biết rò rỉ của bộ tiền định vị hiệu quả nhất khi có tối thiểu 02 hoặc 03 logger thu được âm rò rỉ phát ra liên tục trong một khoảng thời gian. Với việc giới hạn về số lượng hữu hạn các logger trong một bộ thiết bị tiền định vị và rò rỉ có thể xảy ra tất bất kỳ nút nào, nên việc bố trí tổ hợp các logger sao cho khả năng thu được âm/nhận biết dự báo rò rỉ cao nhất tương đương với bài toán tối ưu tổ hợp các nút bố trí logger, với mục tiêu tổng khoảng cách từ từng nút còn lại trong mạng lưới đến từng vị trí noise logger là nhỏ nhất.

Để xem xét hàm mục tiêu, xét ví dụ MLCN (Graph) đơn giản như trong Hình 4, bao gồm 9 nút (nodes) và 9 cạnh (edges) có chiều dài (trọng số) khác nhau, trường hợp đơn giản có 03 noise logger đặt tại các nút (4, 5, 8).

Tổng chiều dài L_TH của từng nút (9 nút) trong tổ hợp đến từng logger đặt tại các nút (4, 5, 8) là:

Trong đó, L _n,4 L _n,5 L _n,6 là các khoảng cách ngắn nhất của từng nút thứ n trong mạng lưới về lại nút i, L_TH là chiều dài của tổ hợp đang xét. Yêu cầu trong bài toán này là L_TH đạt giá trị nhỏ nhất nhằm đảm bảo các điều kiện về truyền âm cũng như nhận biết rò rỉ trên mạng lưới như đã trình bày ở phần trên, tương đương với các giá trị L _n,4 L _n,5 L _n,6 cũng phải đạt giá trị nhỏ nhất.

Tổng quát cho các trường hợp tính toán, hàm mục tiêu khi f(L_TH)  được xây dựng như sau:

Trong đó: i - số lượng noise logger, i ≥ 3 nhằm đảm bảo khả năng nhận biết âm và i_max = số lượng logger trong một bộ do nhà sản xuất cung cấp (thông thường có lớn nhất là 08 logger); n - số lượng nút trong Graph; L ^min _n,1 - chiều dài ngắn nhất từ nút n đến logger i; L_TH - tổng chiều dài của các nút trong Graph đến từng noise logger. Biến số quyết định của f(L_TH) là chiều dài của các đoạn ống nối các nút trong sơ đồ mạng lưới và khả năng kết nối giữa các nút (mạng vòng, mạng cụt).

Bài toán tối ưu khi f(L_TH) -> min, tương ứng với tổng khoảng cách của từng nút trong đồ thị về lại từng logger là nhỏ nhất. Do khối lượng tính toán lớn, trong nghiên cứu đề xuất áp dụng thuật toán tìm đường đi ngắn nhất Dijkstra theo LTĐT kết hợp với thuật toán di truyền (TTDT) đơn mục tiêu nhằm tìm ra lời giải tối ưu trong điều kiện thời gian tính toán cho phép.

Sơ đồ nghiên cứu thực hiện kết hợp giữa mạng lưới cấp nước (thông qua dữ liệu sơ đồ cấu trúc mạng lưới được xây dựng từ phần mềm Epanet), lý thuyết đồ thị với thuật toán Dijkstra và TTDT nhằm tìm tổ hợp vị trí lắp đặt các logger tối ưu được trình bày trong Hình 5.

Các bước thực hiện nghiên cứu sử dụng ngôn ngữ lập trình Python được mô tả tóm tắt như sau:

Bước 1: sử dụng QGIS biên tập dữ liệu MLCN tạo sơ đồ mạng lưới trong Epanet.

Bước 2: từ tập tin của Epanet, xử lý xuất dữ liệu để tạo bảng dữ liệu sơ đồ mạng lưới (topology network) theo cấu trúc đồ thị nút-cạnh (Nodes, Edges), và dữ liệu các nút có thể đặt noise logger (vị trí van).

Bước 3: ứng dụng thư viện Networkx [9] tạo đồ thị (Graph) theo dữ liệu nút và cạnh.

Bước 4: định nghĩa hàm mục tiêu tìm tổng đường đi ngắn nhất của từng tổ hợp theo công thức (2), ứng dụng thuật toán Dijkstra.

Bước 5: ứng dụng TTDT, sử dụng thư viện PyGAD [10] tạo các hàm và khai báo các thông số TTDT, các thông số về số lượng các thế hệ, số lượng tổ hợp, hàm thích nghi. Khai báo phương thức chọn lọc, xác suất để di truyền, xác suất lai ghép; cách thức đột biến và xác suất cho đột biến… Hiệu chỉnh nhằm đạt kết quả xem xét tối ưu. Điều kiện dừng khi đã đạt số lượng các thế hệ hoặc kết quả không cải thiện sau giá trị m vòng lặp cho trước (m>1). Sử dụng dịch vụ máy chủ đám mây miễn phí của Kaggle để tính toán.

Bước 6: sử dụng kết quả ứng dụng bố trí sơ đồ lắp đặt bộ thiết bị tiền định vị.

ÁP DỤNG NGHIÊN CỨU

Vùng nghiên cứu

Áp dụng nghiên cứu tại 03 khu vực DMA thực tế tại Quận 3, Quận 5 và Quận Gò Vấp, Thành phố Hồ Chí Minh (Hình 6), và thông số dữ liệu như trong Bảng 1. DMA 1 có đặc tính là mạng vòng ở ngoài biên và tuyến ống chính chạy dọc ở giữa; DMA 2 chủ yếu là mạng vòng và DMA3 có tỷ lệ mạng lưới cụt cao và tổng chiều dài các tuyến ống cũng lớn hơn các DMA 1 và 2. Nhằm đạt tính khả thi khi áp dụng vào thực tế, trong nghiên cứu này chỉ xem xét vị trí lắp đặt các logger là tại các van trên đường ống cấp nước.

Để có thể mô phỏng rò rỉ có thể xảy ra bất kỳ trên mạng lưới, các nút được chia sao cho chiều dài các ống giữa 02 nút tương ứng là 30 mét. Mỗi tổ hợp bố trí logger chính là vị trí ngẫu nhiên của 08 logger lắp đặt tại các nút có van. Tuy nhiên nhằm để giảm số lượng tổ hợp và thời gian tính toán, các van lân cận tại cùng một vị trí (như tại tê, thập) hoặc rất gần nhau sẽ chỉ được gán 01 van đại diện tại 01 nút.

Kết quả và nhận xét

Với phương pháp thực hiện như trên, kết quả mô phỏng tối ưu cho việc bố trí 08 logger của một bộ thiết bị tiền định vị tại các khu vực nghiên cứu được trình bày trong Hình 7.

Thời gian tính toán bị ảnh hưởng theo các thông số của TTDT, và cũng phụ thuộc vào số lượng nút được mô phỏng sao cho khả năng diễn tả được rò rỉ xảy ra bất kỳ tại khu vực nào trên MLCN (trung bình 15 phút/1 kết quả bố trí tối ưu). Nếu tăng chiều dài giữa 02 nút hoặc chỉ mô phỏng các nút là tại các điểm giao hoặc phụ tùng được lắp đặt, thì thời gian tính toán có thể giảm rất nhanh nhưng lại không thể có tính tổng quát mô phỏng rò rỉ.

Các kết quả nghiên cứu bước đầu cho thấy các logger được bố trí hợp lý dựa theo đặc tính mạng lưới (tỷ lệ mạng lưới cụt, tỷ lệ mạng lưới vòng). Có thể thấy rằng các logger được bố trí tại van nằm trên các tuyến ống vòng mang tính trung tâm của mạng lưới, điều này phù hợp với thực tế khi mạng vòng với khả năng kết nối cao sẽ có khả năng truyền âm thanh rò rỉ về lại các logger với khoảng cách ngắn nhất có thể.

Nghiên cứu được thực hiện thí điểm với việc giả sử chỉ lắp đặt 01 bộ thiết bị tiền định vị với 08 noise logger trong mỗi DMA. Trong trường hợp DMA có thể được cô lập tạm trong thời gian ban đêm để giảm kích thước mạng lưới thì việc ứng dụng tối ưu sơ đồ lắp đặt càng hiệu quả hơn trong việc dò tìm rò rỉ đang diễn ra. Hoặc nếu có thể trang bị nhiều hơn một bộ tiền định vị, việc bố trí tối ưu các sơ đồ có thể hỗ trợ đắc lực cho việc dò tìm và dự báo rò rỉ.

Với mỗi DMA, qua quá trình tính toán sẽ có nhiều sơ đồ bố trí theo thứ tự ưu tiên xét theo hàm thích nghi. Qua các lần mô phỏng cho thấy các tổ hợp có các noise logger gần khu vực tập trung nhiều nút với nhiều đường ống thì sẽ có xu thế được lựa chọn, do thực tế chiều dài ngắn nhất từ các nút trong khu vực này đến các logger sẽ nhỏ, nên sẽ có xác suất được lựa chọn để di truyền cao hơn. Tuy nhiên yếu tố này cũng sẽ gây khả năng bố trí các logger lệch về khu vực tập trung nhiều nút và đường ống, do đó người quản lý mạng lưới cần xem xét điều chỉnh nếu cần để có kết quả tối ưu hơn.

Ngoài ra, đối với một số DMA có mạng lưới dài và một số khu vực không có mạng lưới vòng, có thể sẽ ảnh hưởng đến tiêu chí giới hạn khoảng cách truyền âm của ống (như ống nhựa uPVC hoặc HDPE). Điều này có thể được khắc phục bằng cách xem xét cô lập tạm mạng lưới hoặc bố trí các logger tại gần khu vực này.

Hình 7. Kết quả nghiên cứu bố trí các noise logger; a. Tại DMA 1, b. Tại DMA 2, c. Tại DMA 3

KẾT LUẬN

Từ kết quả nghiên cứu, cho thấy phương pháp luận và quy trình thực hiện kết hợp giữa sơ đồ mạng lưới từ Epanet, LTĐT và TTDT có tính khả thi, hiệu quả, có khả năng triển khai áp dụng thực tiễn trong quản lý và vận hành MLCN. Các khu vực phân vùng DMA tại các CTCN hoàn toàn có thể ứng dụng phương pháp thực hiện trong nghiên cứu này để bố trí các sơ đồ phù hợp, nhằm đạt hiệu quả cao nhất trong việc giảm NKDT và hiệu quả đầu tư thiết bị.

Tuy nhiên, do được xây dựng theo phương pháp tìm khoảng cách ngắn nhất truyền âm từ một vị trí rò rỉ về lại các logger nên vẫn còn hạn chế chưa xem xét giới hạn chiều dài truyền âm trong đường ống nước. Để giảm các hạn chế này, thực tế có thể xem xét điều chỉnh quy mô khu vực bố trí các logger, hoặc tăng số lượng noise logger.

Lời cảm ơn: nghiên cứu được thực hiện với sự hỗ trợ dữ liệu từ các Công ty Cổ phần Cấp nước Bến Thành, Chợ Lớn và Trung An.

TÀI LIỆU THAM KHẢO

[1] C. Ong, C. Tortajada, and O. Arora, Urban Water Demand Management A Guidebook for ASEAN. Springer, 2023. doi: 10.1007/978-981-19-8677-2_3.

[2] M. Farley, G. Wyeth, Z. B. M. Ghazali, and A. Istandar, The Manager’s Non-Revenue Water Handbook. Ranhill Utilities Berhad and the United States Agency for International Development (USAID), 2011.

[3] L. Romero-Ben, D. Alves, J. Blesa, G. Cembrano, V. Puig, and E. Duviella, Leak detection and localization in water distribution networks: Review and perspective, vol. 55. 2023. doi: 10.1016/j.arcontrol.2023.03.012.

[4] I. A. Tijani, S. Abdelmageed, A. Fares, K. H. Fan, Z. Y. Hu, and T. Zayed, "Improving the leak detection efficiency in water distribution networks using noise loggers," Sci. Total Environ., vol. 821, p. 153530, 2022, doi: https://doi.org/10.1016/j.scitotenv.2022.153530.

[5] Hamilton & Charalambous, Leak Detection Technology and Implementation. IWA Publishing, New York. 2013.

[6] D. B. Barros, R. G. Souza, G. Meirelles, and B. Brentan, "Leak detection in water distribution networks based on graph signal processing of pressure data," J. Hydroinformatics, vol. 25, no. 6, pp. 2281–2290, 2023, doi: 10.2166/hydro.2023.047.

[7] A. Rajeswaran, S. Narasimhan, and S. Narasimhan, "A graph partitioning algorithm for leak detection in water distribution networks," Comput. Chem. Eng., vol. 108, pp. 11–23, 2018, doi: 10.1016/j.compchemeng.2017.08.007.

[8] S. Saha Ray, Graph Theory with Algorithms and its Applications. Springer, 2013. doi: 10.1007/978-81-322-0750-4.

[9] A. Hagberg, D. Schult, and P. Swart, "NetworkX - Network Analysis in Python." [Online]. Available: https://networkx.org/

[10] A. F. Gad, "PyGAD: Genetic Algorithm in Python," Github. [Online]. Available: https://github.com/ahmedfgad/GeneticAlgorithmPython

Tác giả: Phạm Thị Tuyết Ngọc ¹ , Hồ Minh Thông ^[1],[2]

[1] Tổng công ty Cấp nước Sài Gòn - TNHH MTV

[2] Liên hệ thông tin: thong.hm@sawaco.com.vn