Tổng quan nghiên cứu

Quá trình đô thị hóa và gia tăng dân số nhanh chóng đang tạo ra áp lực khổng lồ lên hệ thống quản lý rác thải tại các thành phố lớn. Theo số liệu thống kê tại thành phố Sfax thuộc Tunisia vào năm 2016, chỉ có khoảng 70% tổng khối lượng chất thải rắn đô thị (Municipal Solid Waste - MSW) phát sinh được thu gom và chôn lấp hợp vệ sinh, trong khi tỷ lệ rác hữu cơ chiếm tới 68%, gây ô nhiễm môi trường nghiêm trọng và làm suy giảm mỹ quan đô thị. Vấn đề cốt lõi nằm ở khâu vận hành logistics: mạng lưới giao thông phức tạp, tải trọng xe thu gom có hạn và việc phân bổ tuyến đường chưa khoa học khiến các đơn vị môi trường lãng phí từ 15% đến 25% chi phí nhiên liệu cùng thời gian di chuyển.

Mục tiêu cụ thể của luận văn là nghiên cứu, thiết kế và ứng dụng thuật toán di truyền (Genetic Algorithm - GA) kết hợp thuật toán tìm kiếm cục bộ Dijkstra cải tiến nhằm giải quyết bài toán định tuyến xe (Vehicle Routing Problem - VRP), tối ưu hóa tổng thời gian và lộ trình thu gom chất thải rắn đô thị cho đội xe gồm 4 phương tiện chuyên dụng. Nghiên cứu sử dụng nguồn dữ liệu không gian thực tế thu thập tại thành phố Sfax giai đoạn 2016 - 2017 thông qua phần mềm ArcGIS. Ý nghĩa thực tiễn của đề tài thể hiện qua việc cắt giảm hơn 21% thời gian vận hành mạng lưới xe chở rác, nâng cao hiệu suất tải trọng thùng xe lên trên 92% và giảm thiểu đáng kể lượng khí thải độc hại ra môi trường đô thị.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên ba trụ cột lý thuyết toán học và khoa học máy tính chuyên sâu:

  • Lý thuyết Định tuyến Xe (Vehicle Routing Problem - VRP) và Người đưa hàng (Travelling Salesman Problem - TSP): Bài toán VRP trong luận văn là bài toán tối ưu hóa tổ hợp NP-hard. Mô hình yêu cầu lập lịch trình di chuyển cho đội xe xuất phát từ trạm trung tâm (Depot - ký hiệu node 1), đi qua mạng lưới các điểm tập kết rác (Gather sites - từ node 4 trở đi) và đổ rác tại các trạm trung chuyển (Transfer stations - node 2 và 3) trước khi trở về Depot, đảm bảo tổng chi phí hoặc tổng thời gian là nhỏ nhất.
  • Lý thuyết Thuật toán Di truyền (Genetic Algorithm - GA): Dựa trên nguyên lý tiến hóa tự nhiên do John Holland công bố năm 1962 và hoàn thiện năm 1975, GA mô phỏng quá trình chọn lọc tự nhiên qua các toán tử: khởi tạo quần thể (kích thước từ 20 đến 50 cá thể), đánh giá hàm thích nghi (Fitness function), chọn lọc xếp hạng (Ranking Selection), lai ghép tái tổ hợp cạnh (Edge Recombination - ERX) và đột biến hoán vị (Swap Mutation) với xác suất từ 1% đến 5%.
  • Lý thuyết Đồ thị và Thuật toán Tìm đường: Sử dụng đồ thị trọng số không âm G = (V, E) và thuật toán Dijkstra cải tiến để tính toán khoảng cách đường đi ngắn nhất giữa các nút mạng giao thông thực tế.

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

  • Nguồn dữ liệu: Dữ liệu thực nghiệm được thu thập trực tiếp từ cơ quan quản lý chất thải và hệ thống bản đồ số tại thành phố Sfax, Tunisia năm 2016 - 2017, bao gồm ma trận tọa độ, khoảng cách và thời gian di chuyển giữa các nút thông qua công cụ ArcGIS Network Analyst.
  • Cỡ mẫu và phương pháp chọn mẫu: Nghiên cứu chọn mẫu có chủ đích (purposive sampling) với mạng lưới gồm 1 Depot trung tâm, 2 trạm trung chuyển rác, 30 đến 45 điểm tập kết rác đô thị (Gather sites) và đội phương tiện gồm 4 xe tải chuyên dụng (sức chứa định mức từ 3.500 kg đến 8.000 kg mỗi xe). Lượng rác tại mỗi điểm dao động từ 100 kg đến 850 kg.
  • Phương pháp phân tích và lý do lựa chọn: Nghiên cứu sử dụng phương pháp mô phỏng tính toán tiến hóa. Lý do lựa chọn GA kết hợp Dijkstra cải tiến là vì không gian tìm kiếm của bài toán có hơn 10 mũ 25 phương án hoán vị; thuật toán GA có khả năng vượt trội trong việc tránh điểm cực tiểu địa phương, trong khi Dijkstra cải tiến giải quyết tức thời các ràng buộc nghiêm ngặt về sức chứa thùng xe tại từng thời điểm.
  • Timeline nghiên cứu: Quá trình thu thập số liệu, mã hóa mô hình và chạy thực nghiệm được thực hiện liên tục trong thời gian 12 tháng.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

  • Cắt giảm 21,5% tổng thời gian di chuyển của đội xe: Thực nghiệm đối sánh lộ trình của 4 xe chuyên dụng cho thấy thuật toán di truyền GA giúp giảm tổng thời gian thu gom toàn mạng lưới từ 342 phút (khi sử dụng thuật toán Dijkstra truyền thống) xuống còn 268 phút, tiết kiệm 74 phút vận hành mỗi ngày.
  • Tăng 18,4% hiệu suất khai thác tải trọng phương tiện: Thuật toán Dijkstra cải tiến đã xử lý hoàn hảo các ràng buộc về dung tích thùng xe, nâng hệ số lấp đầy tải trọng của 4 xe từ 74,2% lên mức 92,6%, loại bỏ hoàn toàn các chuyến xe chạy rỗng hoặc quay đầu sớm.
  • Cân bằng tải giữa các phương tiện: Sự chênh lệch thời gian hoạt động giữa xe chạy nhiều nhất và xe chạy ít nhất giảm mạnh từ 48 phút xuống dưới 14 phút, giúp phân bổ khối lượng công việc đồng đều cho các tài xế và giảm hao mòn máy móc.
  • Phân loại thành phần chất thải phục vụ ưu tiên tuyến đường: Kết quả phân tích cơ cấu rác tại Sfax xác định 68% là chất thải hữu cơ, 11% nhựa, 10% giấy/bìa cứng, 5% kim loại, 4% thủy tinh và 2% chất thải khác, làm cơ sở để thuật toán ưu tiên gom trước tại các điểm rác hữu cơ có nguy cơ phân hủy cao.

Thảo luận kết quả

Hiệu quả vượt trội của mô hình bắt nguồn từ việc tích hợp kỹ thuật lai ghép chéo cạnh (Edge Recombination). Kỹ thuật này bảo tồn tối đa các liên kết lân cận hợp lệ giữa các điểm thu gom, giúp thuật toán GA duy trì tính đa dạng của quần thể và đạt tốc độ hội tụ cao sau 150 đến 200 thế hệ lặp. Hàm mục tiêu Fitness được xây dựng chuẩn xác theo tổng thời gian di chuyển thực tế từ tiện ích ArcGIS Network Analyst, phản ánh chính xác điều kiện giao thông tại từng thời điểm.

So với các nghiên cứu trước đây chỉ sử dụng công cụ GIS đơn thuần (mức tiết kiệm khoảng 9,4%), giải pháp kết hợp GA và GIS trong luận văn nâng cao hiệu quả tiết kiệm lên hơn 21%. Khi so sánh với thuật toán bầy đàn hạt (Particle Swarm Optimization - PSO) từng áp dụng tại Đà Nẵng, mô hình này cho tốc độ xử lý nhanh hơn 18% trong cùng điều kiện phần cứng.

Các kết quả này được trình bày trực quan thông qua bảng ma trận khoảng cách giữa các node, đồ thị biểu diễn hàm thích nghi Fitness qua từng thế hệ và sơ đồ đường đi trực quan của từng xe (từ Xe 1 đến Xe 4) trên nền bản đồ số ArcGIS. Việc áp dụng mô hình giúp chính quyền đô thị tiết kiệm từ 15% đến 20% ngân sách vận hành vệ sinh môi trường hàng năm.

Đề xuất và khuyến nghị

  • Triển khai hệ thống giám sát thời gian thực tích hợp IoT và GPS: Lắp đặt thiết bị cảm biến mức rác tại 100% các điểm tập kết (Gather sites) và gắn định vị GPS trên toàn bộ xe gom rác trong vòng 6 đến 12 tháng tới. Chủ thể thực hiện: Doanh nghiệp dịch vụ môi trường đô thị phối hợp cùng Sở Thông tin và Truyền thông.
  • Tự động hóa lập lịch trình trên nền tảng đám mây: Xây dựng phần mềm chạy thuật toán GA tự động tính toán lộ trình tối ưu trước 05:00 sáng mỗi ngày, hướng tới mục tiêu giảm 25% thời gian lập kế hoạch điều phối trong quý 1 năm tiếp theo. Chủ thể thực hiện: Đội ngũ kỹ sư công nghệ thông tin và phòng điều hành vận tải.
  • Hiện đại hóa và đồng bộ đội xe chuyên dụng: Đầu tư nâng cấp đội xe gồm cả xe dumper truck và xe ép rác compactor vehicles có tải trọng từ 5 tấn đến 10 tấn phù hợp với từng cung đường ngõ hẹp, mục tiêu nâng tỷ lệ thu gom rác thải đô thị từ mức 70% hiện tại lên trên 90% trong giai đoạn 2 đến 3 năm. Chủ thể thực hiện: Ban Quản lý Đô thị và Ủy ban nhân dân thành phố.
  • Đẩy mạnh chính sách phân loại rác tại nguồn: Ban hành quy chế thu gom riêng biệt 68% rác hữu cơ và 21% rác tái chế (nhựa, giấy) để giảm áp lực lên các trạm trung chuyển (Transfer stations), phấn đấu giảm 30% chi phí xử lý chôn lấp trong kế hoạch trung hạn 5 năm. Chủ thể thực hiện: Sở Tài nguyên và Môi trường cùng cộng đồng dân cư.

Đối tượng nên tham khảo luận văn

  • Nhà quản lý đô thị và cơ quan hoạch định chính sách: Cung cấp cơ sở khoa học để tối ưu hóa ngân sách vận tải công cộng, áp dụng mô hình định tuyến VRP để xây dựng đề án quản lý chất thải rắn cho các đô thị có quy mô dân số từ 500.000 đến 2.000.000 người.
  • Doanh nghiệp dịch vụ môi trường và công ty logistics: Giúp doanh nghiệp tái cấu trúc lộ trình phương tiện, cắt giảm từ 15% đến 25% chi phí nhiên liệu và kéo dài tuổi thọ động cơ cho đội xe từ 10 đến 50 phương tiện.
  • Kỹ sư phần mềm và chuyên gia hệ thống thông tin địa lý (GIS): Hướng dẫn chi tiết cách thức lập trình tích hợp ArcGIS Network Analyst với các thuật toán tiến hóa Meta-heuristic để phát triển giải pháp giao thông thông minh (Smart Transportation).
  • Giảng viên, học viên cao học và sinh viên CNTT: Tài liệu tham khảo giá trị về phương pháp mô hình hóa toán học, kỹ thuật mã hóa nhiễm sắc thể và thực nghiệm giải thuật tối ưu hóa tổ hợp trên dữ liệu thế giới thực.

Câu hỏi thường gặp

  • Thuật toán Dijkstra cổ điển gặp hạn chế gì khi giải bài toán thu gom rác? Thuật toán Dijkstra cổ điển chỉ tìm đường đi ngắn nhất giữa hai điểm độc lập mà không xử lý được các ràng buộc phức tạp như tải trọng giới hạn 5.000 kg của xe, điểm xuất phát Depot cố định hay quy định phải qua trạm trung chuyển. Khi áp dụng vào thực tế, Dijkstra cổ điển làm xe quá tải hoặc chạy rỗng tới 30% quãng đường.
  • Kỹ thuật lai ghép Edge Recombination (ERX) mang lại lợi ích gì cho thuật toán GA? Kỹ thuật ERX tập trung bảo toàn tối đa các cạnh nối liền kề giữa các điểm gom rác từ nhiễm sắc thể cha mẹ, hạn chế sinh ra các đoạn đường ngẫu nhiên không hợp lệ. Trong bài toán với hơn 40 điểm gom, ERX giúp tỷ lệ tạo ra cá thể con hợp lệ đạt trên 95%, tăng tốc độ hội tụ gấp 1,5 lần so với phép lai thông thường.
  • Dữ liệu không gian từ phần mềm ArcGIS đóng vai trò như thế nào trong mô hình? Công cụ ArcGIS Network Analyst cung cấp ma trận khoảng cách và thời gian di chuyển chính xác dựa trên hạ tầng đường sá thực tế thay vì tính theo đường chim bay. Nhờ đó, sai số giữa thời gian mô phỏng và thực tế giảm xuống dưới 3%, đảm bảo kế hoạch điều phối 4 xe đạt độ chính xác rất cao.
  • Kết quả nghiên cứu tại Sfax có thể chuyển giao áp dụng cho các đô thị tại Việt Nam không? Mô hình hoàn toàn có thể chuyển giao vì đặc thù rác thải đô thị tại Việt Nam có nhiều nét tương đồng, đặc biệt là tỷ lệ rác hữu cơ chiếm từ 60% đến 70%. Mô hình tương tự từng thử nghiệm trên 13 tuyến đường tại Đà Nẵng đã chứng minh khả năng tiết kiệm từ 10% đến 20% chi phí vận hành.
  • Cần chuẩn bị những tham số đầu vào nào để vận hành thuật toán này? Hệ thống yêu cầu 4 nhóm thông số chính gồm: tọa độ điểm Depot, tọa độ các trạm trung chuyển (Transfer stations), tọa độ và lượng rác dự báo tại từng điểm tập kết (Gather sites từ 100 kg đến 1.000 kg), cùng bảng thông số kỹ thuật về tải trọng định mức của đội xe từ 3 đến 10 tấn.

Kết luận

  • Luận văn đã mô hình hóa thành công bài toán thu gom chất thải rắn đô thị (MSW) dưới dạng bài toán định tuyến xe đa ràng buộc (VRP).
  • Thiết kế hoàn chỉnh thuật toán di truyền GA kết hợp kỹ thuật lai ghép Edge Recombination và thuật toán tìm kiếm cục bộ Dijkstra cải tiến.
  • Kiểm nghiệm thực tế tại thành phố Sfax với 4 xe tải chuyên dụng chứng minh thời gian di chuyển giảm 21,5% so với phương pháp truyền thống.
  • Tối ưu hóa hiệu suất sử dụng tải trọng thùng xe đạt trên 92%, giải quyết triệt để tình trạng lãng phí hành trình.
  • Tích hợp thành công dữ liệu không gian từ ArcGIS Network Analyst vào quy trình ra quyết định tự động.

Đóng góp chính của luận văn là cung cấp một giải pháp công nghệ thông tin toàn diện, khả thi và hiệu quả cao cho bài toán logistics đô thị. Hướng phát triển tiếp theo của đề tài là tích hợp mô hình định tuyến động (Dynamic VRP) với dữ liệu cảm biến thời gian thực trong vòng 12 đến 24 tháng tới. Các nhà quản lý đô thị và doanh nghiệp môi trường hãy nhanh chóng ứng dụng giải pháp tối ưu hóa thông minh này để nâng cao chất lượng môi trường sống và phát triển đô thị bền vững!