Từ khoá: LSCP, spopt, pulp, networkx, GIS.

Đặt vấn đề

Hệ thống sông ngòi, kênh rạch trong TP. Hồ Chí Minh sở hữu tiềm năng phát triển lớn, đóng vai trò quan trọng trong việc phát triển các dịch vụ du lịch, vận chuyển, và chống ngập. Một ví dụ điển hình là sự kiện Lễ hội Sông nước TP. Hồ Chí Minh lần thứ 2 năm 2024, minh chứng cho các hoạt động trên hệ thống thủy hệ. Trong bối cảnh đó, vấn đề nạo vét kênh rạch cần được xây dựng kế hoạch và thực hiện hiệu quả nhất. Khi triển khai công tác nạo vét, ngoài các thiết bị di chuyển trên sông, nhiều thiết bị và tài nguyên khác được bố trí trên bờ để hỗ trợ và có thể là nơi vận chuyển chất thải nạo vét. Để tối ưu hóa các vị trí đặt các thiết bị hỗ trợ nạo vét trên bờ, chẳng hạn như các “thùng rác”, cần bố trí hợp lý, phù hợp với vị trí và giảm thiểu các di chuyển không cần thiết. Mục tiêu chính của nghiên cứu này là áp dụng bài toán LSCP để triển khai mô hình hệ thống bố trí các trạm trên bờ, phục vụ công tác nạo vét trên các tuyến giao thông đường thủy tại TP. Hồ Chí Minh. 

Thuật toán LSCP

Tập bao phủ điểm (Location Set Covering Problem - LSCP) lần đầu tiên được mô tả bởi Toregas và các cộng sự (1971) [1], trong đó chỉ ra rằng các dịch vụ khẩn cấp cần phải được bố trí sao cho thời gian phản hồi tối ưu, nhằm đảm bảo khả năng phục vụ trong khoảng thời gian tối đa cho phép để xử lý các tình huống khẩn cấp. Đến năm 2018, mô hình LSCP được Church và Murray [2] đề xuất với mục tiêu xác định và bố trí số lượng trạm dịch vụ tối thiểu, sao cho mọi khu vực có nhu cầu đều được đáp ứng trong khoảng thời gian hoặc khoảng cách tối đa đã được xác định trước.

Áp dụng bài toán LSCP với các phương pháp lập trình quy hoạch nguyên nhằm chọn ra một tập các điểm trạm sao cho đảm bảo phủ hết các điểm yêu cầu, với mục tiêu tối thiểu hóa số lượng các điểm trạm được chọn. Thuật toán LSCP sử dụng các biến nhị phân để quyết định việc chọn trạm, cùng với các ràng buộc nhằm đảm bảo tính khả thi, hiệu quả và chính xác trong quá trình lựa chọn vị trí các trạm trên bờ phục vụ công tác nạo vét. Mô hình bài toán LSCP có thể được biểu diễn như sau:

Tối thiểu:

Ràng buộc:        

 Trong đó:

•    i là chỉ số của điểm/khu vực/đối tượng yêu cầu trong tập I

•    j là chỉ số các điểm trạm được chọn trong tập J

•    S là khoảng cách hoặc thời gian hỗ trợ tối đa có thể chấp nhận được 

•    di j là khoảng cách hoặc thời gian ngắn nhất giữa đỉnh i và j

• Nj là tập 

• Yj    

Phương pháp thực hiện

Trước tiên, cần xác định các biến số và ràng buộc cho thuật toán, sau đó xây dựng ma trận chi phí (cost_matrix) bằng thư viện NetworkX và thực hiện các bước khởi tạo với công cụ spopt. Tiếp theo, tiến hành tính toán bằng PuLP kết hợp với các công cụ khác để giải bài toán.

Dưới đây là mã giả khái quát quá trình khởi chạy thuật toán của mô hình, giúp bạn đọc dễ hình dung:

Input: firstStation: mã trạm đầu trong khu vực,

lastStation: mã trạm cuối trong khu vực,

facility_points: các vị trí có thể đặt trạm,

P-FACILITIES: số lượng trạm trên bờ phục vụ công tác nạo vét cần xác định

Output: selected_facilities_df: DataFrame chứa danh sách vị trí đề xuất đặt các trạm trên bờ phục vụ công tác nạo vét

Hình 1. TP. Thủ Đức và một phần thuỷ hệ được chọn tại TP. Thủ Đức (vẽ bằng QGIS)

Begin

Bước 1: Nhập firstStation, lastStation và số lượng các trạm trên bờ phục vụ công tác nạo vét cần tìm P-FACILITIES 

Bước 2: Chuyển đổi mạng lưới (network) của (firstStation - lastStation) từ network_distance

Bước 3: Tính toán điểm có thể đặt trạm trên bờ phục vụ công tác nạo vét (facility_points) từ mạng lưới network

Bước 4: Tạo pivot_table từ dữ liệu mạng

Bước 5: Chuyển pivot_table thành cost_matrix, điền giá trị thiếu bằng 0 và chuyển thành số nguyên

Bước 6: Tính total_net_length (tổng chiều dài mạng lưới) từ cột net_length của dữ liệu mạng

Bước 7: Tính bán kính phục vụ SERVICE_RADIUS = total_net_length / (P-FACILITIES * 2)

Bước 8: Khởi tạo mô hình LSCP từ cost_matrix và SERVICE_RADIUS

Bước 9: Giải quyết bài toán LSCP sử dụng solve(pulp.PULP_CBC_CMD(msg=False))

Bước 10: Lấy giá trị objective từ bài toán

Bước 11: Tạo danh sách selected_facilities chứa các vị trí được chọn

For i từ 0 đến từng phần tử lscp.fac_vars - 1:

If lscp.fac_vars[i].varValue == 1:

Thêm i vào danh sách selected_facilities

Bước 12: Tạo DataFrame từ danh sách selected_facilities từ facility_points, reset index

Bước 13: Trả về DataFrame dưới dạng dictionary to_dict (orient=”records”)

End.

Kết quả thực nghiệm

Các số liệu về vị trí địa lý được lấy mẫu dọc theo hệ thống thủy hệ với 102 đối tượng (vị trí), nhằm đảm bảo tính khách quan và phạm vi nhỏ, đáp ứng yêu cầu thử nghiệm tính toán trong khu vực TP. Thủ Đức. Các vị trí này được chọn sao cho phù hợp với các tuyến giao thông đường thủy và đặc điểm địa lý của khu vực, nhằm đảm bảo hiệu quả trong việc triển khai mô hình và kiểm thử thuật toán LSCP. Kết quả thực nghiệm sẽ được đánh giá dựa trên khả năng tối ưu hóa số lượng trạm và khoảng cách di chuyển của các thiết bị hỗ trợ nạo vét, cũng như độ chính xác trong việc đáp ứng các yêu cầu đã đề ra.

Thêm vào đó, để giảm thiểu sai số, trong giai đoạn thử nghiệm, các trạm dự kiến sẽ được bố trí sao cho mỗi trạm cách nhau 10 mét. Phương pháp này giúp đảm bảo tính chính xác của hệ thống trong quá trình triển khai, đồng thời tạo điều kiện phát hiện nhanh chóng các ràng buộc mới hoặc các điểm tiêu cực có thể phát sinh khi khởi chạy mô hình. Qua đó, quá trình đánh giá và điều chỉnh mô hình sẽ được tối ưu hóa, đảm bảo hiệu quả và khả năng áp dụng thực tế tại khu vực TP. Thủ Đức. 

Một số hình ảnh dữ liệu mẫu khi thực thi:

Hình 2. File networkDistance.csv chứa độ dài và tổng chiều dài của các cạnh nối các điểm trạm

Hình 3. Một phần nhỏ dữ liệu trong cost_matrix

Hình 4. File facilityPoints.csv chứa DataFrame biểu thị vị trí địa lý của các điểm trạm trên bờ phục vụ công tác nạo vét bằng hệ toạ độ VN-2000

Hình 5. Kết quả được thể hiện trên web

Cuối cùng, với một trang WebGIS được xây dựng, hệ thống tính toán cho mô hình bố trí các trạm trên bờ phục vụ công tác nạo vét sẽ được thể hiện trực quan. Các trạm dự kiến sẽ được hiển thị trên bản đồ trực tuyến, hỗ trợ việc theo dõi và quản lý trong suốt quá trình triển khai.

Kết luận

Thuật toán LSCP đã chứng minh tính hiệu quả khi được áp dụng trên một tập dữ liệu lớn hơn, với gần 10.000 trạm trên bờ phục vụ công tác nạo vét dự kiến. Bằng cách xác định số lượng trạm tối thiểu cần thiết, LSCP đảm bảo rằng mọi điểm yêu cầu trên bờ phục vụ công tác nạo vét đều được bao phủ.

Việc triển khai LSCP vào mô hình hệ thống hỗ trợ phân hoạch để đặt trạm trên bờ phục vụ công tác nạo vét tại TP. Hồ Chí Minh, trên một khu vực rộng lớn bao gồm cả các đoạn kênh rạch nhỏ, đã cho thấy tính khả thi và hiệu quả cao. Phương pháp này có thể đóng góp quan trọng vào công tác hoạch định tối ưu cho các dự án nạo vét trên hệ thống giao thông đường thủy.

Tài liệu tham khảo

1. Toregas and et al, “The location of emergency service facilities,” Operations research, vol. 19, no. 6, pp. 1363-1373, 1971;

2. G. Barcelos and et al, The Location Set Covering Problem (LSCP), Feng and et al, 2021;

3. RL Church and AT Murray, “Location covering models: history, applications and advancements (Advances in Spatial Science),” Cham, Switzerland, Springer, vol. 33, no. 11, pp. 2334-2335, 2018;

4. H. T. K Anh, “Đề xuất mô hình hệ thống bố trí lực lượng hỗ trợ y tế trên các tuyến giao thông đường thuỷ tại Thành phố Hồ Chí Minh,” Báo Tài nguyên và Môi trường, pp. 39-41, 2024;

5. H. T. K. Anh, N. H. N. An, “Triển khai bài toán P-center trên hệ thống bố trí trạm cứu hộ y tế đường thuỷ tại thủ đức,” Kỷ yếu Hội thảo Ứng dụng GIS toàn quốc, pp. 51-61, 2024.

HOÀNG THỊ KIỀU ANH¹
1 Đại học Thuỷ Lợi - Email: hoangkieuanh@tlu.edu.vn
Nguồn: Tạp chí Tài nguyên và Môi trường số 23 (Kỳ 1 tháng 12) năm 2024