Tổng quan nghiên cứu

Quá trình đô thị hóa nhanh chóng đang tạo ra áp lực khổng lồ lên hạ tầng xử lý chất thải rắn đô thị trên toàn cầu. Tại các đô thị thuộc các quốc gia đang phát triển, lượng chất thải sinh hoạt bình quân dao động khoảng 0,815 kg/người/ngày với tốc độ tăng trưởng xấp xỉ 2,5% mỗi năm. Điển hình tại thành phố Sfax, đô thị lớn thứ hai của Tunisia, tỷ lệ rác hữu cơ chiếm tới 68%, nhựa dẻo chiếm 11%, giấy bìa chiếm 10%, trong khi chỉ có khoảng 70% tổng khối lượng chất thải được đưa đi chôn lấp hợp vệ sinh. Vấn đề nghiên cứu trọng tâm của luận văn là giải quyết bài toán định tuyến phương tiện thu gom chất thải rắn (Vehicle Routing Problem - VRP) với đội xe không đồng nhất và nhiều ràng buộc phức tạp về dung tích, thời gian và địa lý.

Mục tiêu cụ thể của đề tài là thiết kế và hiện thực hóa giải thuật di truyền (Genetic Algorithm - GA) cải tiến nhằm tối thiểu hóa tổng thời gian di chuyển và quãng đường vận hành của hệ thống xe thu gom. Phạm vi không gian của nghiên cứu được triển khai thực nghiệm tại quận Elboustene thuộc thành phố Sfax, khu vực có diện tích 315 hecta với 17.446 hộ gia đình, 217 cơ sở công nghiệp và lượng rác thải phát sinh ở mức 0,944 kg/người/ngày. Luận văn tập trung vào giai đoạn một của chu trình quản lý chất thải trong ca làm việc 7 tiếng ban ngày từ 6 giờ sáng đến 13 giờ chiều. Ý nghĩa nghiên cứu thể hiện rõ nét qua các chỉ số định lượng: tối ưu hóa 100% khối lượng rác thu gom tại 39 điểm tập kết, giảm thiểu thời gian chờ tại 2 trạm trung chuyển và cắt giảm đáng kể chi phí nhiên liệu cũng như lượng khí phát thải nhà kính trong vận tải đô 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 trên nền tảng lý thuyết tối ưu hóa tổ hợp và bài toán định tuyến phương tiện (Vehicle Routing Problem - VRP), một dạng mở rộng của bài toán người đưa hàng (Traveling Salesman Problem - TSP) và bài toán định tuyến nút (Node Routing Problem - NRP). Trong cấu trúc này, không gian tìm kiếm là tập hợp các hoán vị đường đi qua nhiều điểm nút có ràng buộc sức chứa tối đa của phương tiện.

Trọng tâm lý thuyết của đề tài là Giải thuật Di truyền (Genetic Algorithm) do John Holland khởi xướng vào năm 1975, mô phỏng quá trình chọn lọc tự nhiên và tiến hóa sinh học. Mô hình nghiên cứu vận dụng các khái niệm nền tảng bao gồm: cấu trúc nhiễm sắc thể biểu diễn thứ tự các hành trình, hàm thích nghi (Fitness Function) đo lường tổng thời gian di chuyển, toán tử chọn lọc theo thứ hạng (Ranking Selection), toán tử lai ghép kết hợp cạnh (Edge Recombination Crossover) và toán tử đột biến hoán vị (Swap Mutation). Đồng thời, lý thuyết đường đi ngắn nhất thông qua thuật toán Dijkstra kinh điển được tích hợp để giải quyết bài toán tìm kiếm địa phương trên đồ thị có trọng số.

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

Nguồn dữ liệu của luận văn được thu thập từ Cơ quan Quốc gia về Quản lý Chất thải Tunisia (ANGed) và cơ sở dữ liệu số hóa hạ tầng đô thị thành phố Sfax. Tập dữ liệu không gian bao gồm tọa độ địa lý chính xác của 1 trạm trung tâm (Depot), 2 trạm trung chuyển (Transfer stations) và 39 điểm gom chất thải (Gather sites) với khối lượng phát sinh trung bình 0,4 tấn tại mỗi điểm.

Cỡ mẫu nghiên cứu bao gồm toàn bộ mạng lưới 42 nút giao thông trên địa bàn 315 hecta và đội phương tiện gồm 4 xe chuyên dụng không đồng nhất: 1 xe ép rác trọng tải lớn 7,4 tấn, 1 xe thùng lật 2,3 tấn và 2 xe kéo nông nghiệp 1,6 tấn. Phương pháp chọn mẫu là khảo sát toàn bộ các điểm phát sinh rác thải sinh hoạt và thương mại trong phạm vi quận nghiên cứu. Phương pháp phân tích kết hợp giữa hệ thống thông tin địa lý ArcGIS Network Analyst để trích xuất ma trận khoảng cách, thời gian thực và thuật toán di truyền tự lập trình để tối ưu hóa lộ trình. Lý do lựa chọn giải pháp lai ghép này là vì thuật toán Dijkstra giúp tạo ra quần thể ban đầu khả thi thỏa mãn các ràng buộc tải trọng, trong khi thuật toán di truyền có khả năng tìm kiếm toàn cục vượt trội, khắc phục triệt để nhược điểm rơi vào điểm tối ưu cục bộ của các phương pháp heuristic truyền thống. Quá trình thu thập và xử lý dữ liệu được hoàn thiện trong giai đoạn 2016 - 2017.

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

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

Quá trình mô phỏng thực nghiệm và đối sánh thuật toán đã mang lại những phát hiện quan trọng có giá trị thực tiễn cao:

Thứ nhất, giải thuật di truyền thiết kế mới cho thấy khả năng rút ngắn tổng thời gian thu gom chất thải vượt bậc so với phương pháp định tuyến Dijkstra cải tiến thuần túy. Lộ trình của 4 phương tiện được tối ưu hóa toàn diện, giúp giảm thiểu đáng kể các đoạn đường chạy rỗng giữa các điểm thu gom và 2 trạm trung chuyển.

Thứ hai, mô hình phân bổ tải trọng đạt hiệu quả tối ưu giữa các xe có sức chứa khác nhau. Phương tiện trọng tải lớn 7,4 tấn đảm nhận các cụm điểm tập kết có mật độ rác dày đặc, trong khi 2 xe nông nghiệp 1,6 tấn và 1 xe thùng lật 2,3 tấn phục vụ các tuyến phố hẹp, hoàn thành trọn vẹn việc vận chuyển hơn 15,6 tấn rác phát sinh mỗi ngày trong khung giờ quy định từ 6 giờ đến 13 giờ mà không bị quá tải.

Thứ ba, kỹ thuật lai ghép cạnh Edge Recombination chứng minh tính ưu việt khi duy trì được 75% cấu trúc liên kết cạnh tốt giữa các thế hệ cha mẹ, ngăn chặn hiện tượng phá vỡ các chuỗi hành trình hợp lý và tăng tốc độ hội tụ nhanh hơn khoảng 20% so với các phương pháp lai ghép cắt điểm thông thường.

Thứ tư, việc kết hợp thuật toán Dijkstra cải tiến trong khâu khởi tạo quần thể ban đầu và kiểm tra ràng buộc giúp loại bỏ 100% các nhiễm sắc thể không hợp lệ, đảm bảo mọi hành trình tạo ra đều thỏa mãn điều kiện phương tiện quay về xả tải tại trạm trung chuyển trước khi vượt quá sức chứa cho phép.

+-------------------------------------------------------------------------+
|                  BIỂU ĐỒ SO SÁNH HIỆU QUẢ ĐỊNH TUYẾN                   |
+-------------------------------------------------------------------------+
| Tiêu chí đánh giá         | Thuật toán Dijkstra | Thuật toán Di truyền  |
+---------------------------+---------------------+-----------------------+
| Tổng thời gian di chuyển  | Mức cơ sở (100%)    | Giảm khoảng 12 - 15%  |
| Cân bằng tải trọng đội xe | Chênh lệch lớn      | Cân bằng tối ưu       |
| Khả năng thoát bẫy cục bộ | Kém                 | Xuất sắc              |
| Độ phức tạp tính toán     | Thấp                | Vừa phải              |
+-------------------------------------------------------------------------+

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự vượt trội của giải thuật di truyền nằm ở cơ chế tìm kiếm đa điểm đồng thời trong không gian nghiệm. Thuật toán Dijkstra bản chất là thuật toán tham lam cục bộ, chỉ chọn nút kế tiếp có khoảng cách ngắn nhất mà không đánh giá được tổng thể chu trình dài hạn, dẫn đến việc các xe có thể bị dồn tải vào cuối ca làm việc hoặc phải di chuyển quãng đường xa bất hợp lý để về trạm trung chuyển. Ngược lại, giải thuật di truyền với việc duy trì 50% cá thể tốt nhất, giữ lại 25% cá thể ngẫu nhiên và sinh mới 25% cá thể qua toán tử lai ghép cạnh đã tạo ra sự cân bằng hoàn hảo giữa việc khai thác nghiệm tốt và khám phá không gian mới.

Khi so sánh với các công bố khoa học tương tự tại Đài Loan sử dụng thuật toán đàn kiến (Ant Colony Optimization - ACO) hay nghiên cứu tại thành phố Đà Nẵng kết hợp PSO với ArcGIS, giải thuật di truyền trong luận văn này đạt được sự tương thích vượt trội đối với các mô hình xe hỗn hợp (Heterogeneous Fleet). Dữ liệu nghiên cứu được trình bày chi tiết thông qua các bảng ma trận khoảng cách thời gian từ ArcGIS Network Analyst và bản đồ trực quan hóa từng tuyến đường của 4 phương tiện, cung cấp bằng chứng thực nghiệm rõ ràng về tính khả thi của giải pháp.

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

Dựa trên kết quả nghiên cứu thực nghiệm, luận văn đưa ra 4 khuyến nghị then chốt nhằm hoàn thiện hệ thống quản lý và thu gom rác thải đô thị:

Thứ nhất, tích hợp trực tiếp module giải thuật di truyền vào phần mềm giám sát GIS của cơ quan quản lý môi trường. Giải pháp này hướng tới mục tiêu cắt giảm 15% đến 20% chi phí tiêu hao nhiên liệu của đội xe thu gom trong vòng 6 đến 12 tháng tới, do Sở Giao thông Công chính và Công ty Môi trường Đô thị địa phương chủ trì thực hiện.

Thứ hai, số hóa và chuẩn hóa cơ sở dữ liệu vị trí các điểm tập kết cùng hệ thống cảm biến tải trọng thông minh. Mục tiêu là cập nhật chính xác 98% khối lượng chất thải theo thời gian thực tại 39 điểm thu gom, thời gian triển khai trong vòng 3 đến 6 tháng bởi các doanh nghiệp dịch vụ công ích.

Thứ ba, tái cơ cấu và hiện đại hóa đội phương tiện vận tải rác. Cần thay thế dần các loại máy kéo nông nghiệp dung tích nhỏ 1,6 tấn bằng các dòng xe ép rác tự động dung tích từ 5 đến 7,4 tấn nhằm tăng năng suất vận chuyển thêm 30%, thực hiện theo lộ trình 24 tháng dưới sự điều phối của Ủy ban Nhân dân và cơ quan tài chính thành phố.

Thứ tư, thiết lập quy trình điều hành lộ trình động thích ứng với tình trạng ùn tắc giao thông giờ cao điểm. Giải pháp nhằm triệt tiêu hoàn toàn tình trạng ứ đọng rác thải tại các khu vực thương mại đông đúc, tiến hành thử nghiệm trong 3 tháng trước khi đưa vào vận hành chính thức tại các trung tâm điều hành đô thị thông minh.

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

Công trình nghiên cứu mang lại giá trị học thuật và thực tiễn sâu rộng cho 4 nhóm đối tượng chính:

Nhóm thứ nhất là các nhà nghiên cứu, nghiên cứu sinh và học viên cao học chuyên ngành Khoa học Máy tính, Hệ thống Thông tin và Vận trù học. Tài liệu cung cấp cơ sở lý thuyết chuẩn xác về bài toán VRP, kỹ thuật mã hóa nhiễm sắc thể dạng danh sách liên kết và thuật toán lai ghép cạnh Edge Recombination.

Nhóm thứ hai là các nhà hoạch định chính sách, cán bộ quản lý môi trường tại các Sở Tài nguyên và Môi trường, Công ty Môi trường Đô thị (URENCO). Tài liệu hỗ trợ việc xây dựng phương án đấu thầu, định mức kinh tế kỹ thuật và tối ưu hóa ngân sách vận chuyển rác sinh hoạt.

Nhóm thứ ba là các kỹ sư hệ thống, chuyên gia phát triển phần mềm bản đồ số và GIS. Luận văn là tài liệu tham khảo giá trị trong việc kết nối dữ liệu ArcGIS Network Analyst với các thuật toán tối ưu tiến hóa để xây dựng giải pháp đô thị thông minh.

Nhóm thứ tư là các doanh nghiệp vận tải, logistics và quản lý chuỗi cung ứng. Mô hình định tuyến xe không đồng nhất có thể được chuyển giao trực tiếp để giải quyết bài toán giao hàng đa điểm chặng cuối với chi phí tối thiểu.

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

Thuật toán di truyền giải quyết bài toán định tuyến xe thu gom rác như thế nào? Thuật toán mã hóa các lộ trình xe thành chuỗi nhiễm sắc thể, sử dụng hàm thích nghi để đo lường tổng thời gian di chuyển. Qua các thế hệ tiến hóa với phép chọn lọc, lai ghép cạnh và đột biến hoán vị, thuật toán tự động sàng lọc để tìm ra phương án phân bổ tuyến đường có thời gian ngắn nhất và tải trọng cân bằng nhất.

Tại sao nghiên cứu phải cải tiến thuật toán Dijkstra cổ điển? 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 thể xử lý các ràng buộc thực tế như sức chứa giới hạn của xe hay việc xe phải rẽ vào trạm trung chuyển để xả rác. Thuật toán cải tiến giúp kiểm soát tải trọng lũy kế và làm bộ sinh nghiệm ban đầu cho thuật toán di truyền.

Kỹ thuật lai ghép cạnh Edge Recombination có điểm gì vượt trội? Kỹ thuật lai ghép cạnh tập trung bảo tồn các liên kết lân cận giữa các điểm gom rác từ hai nhiễm sắc thể cha mẹ. Điều này giúp giữ lại những đoạn hành trình ngắn đã được tối ưu, giảm thiểu tối đa các đột biến ngẫu nhiên gây phá vỡ cấu trúc hợp lý của lộ trình so với phép lai ghép điểm cắt truyền thống.

Mô hình trong luận văn có thể áp dụng cho các đô thị tại Việt Nam không? Hoàn toàn khả thi vì các đô thị tại Việt Nam như Hà Nội, Thành phố Hồ Chí Minh hay Đà Nẵng đều có đặc điểm mạng lưới ngõ hẻm phức tạp, sử dụng nhiều loại phương tiện thu gom từ xe đẩy tay đến xe ép rác lớn và chịu áp lực lớn về thời gian thu gom tránh giờ cao điểm.

Đội xe không đồng nhất ảnh hưởng như thế nào đến việc tính toán lộ trình? Sự khác biệt về tải trọng giữa xe ép rác 7,4 tấn, xe thùng 2,3 tấn và xe kéo 1,6 tấn đòi hỏi thuật toán phải tính toán chính xác thời điểm xe đầy tải để điều hướng về trạm trung chuyển gần nhất, đảm bảo tối đa hóa hệ số sử dụng tải trọng của từng loại xe trong suốt ca làm việc.

Kết luận

Luận văn đã giải quyết xuất sắc bài toán tối ưu hóa thu gom chất thải rắn đô thị thông qua việc thiết kế và thực nghiệm thành công giải thuật di truyền lai ghép với thuật toán tìm kiếm địa phương:

  • Mô hình hóa thành công bài toán định tuyến phương tiện không đồng nhất với đầy đủ các ràng buộc thực tế về tải trọng, thời gian phục vụ và hệ thống trạm trung chuyển.
  • Sáng tạo trong việc kết hợp thuật toán Dijkstra cải tiến để sinh quần thể ban đầu chất lượng cao và áp dụng toán tử lai ghép cạnh Edge Recombination giúp tăng tốc độ hội tụ nghiệm tối ưu.
  • Kết quả thực nghiệm tại quận Elboustene, thành phố Sfax đã chứng minh tính ưu việt rõ rệt của thuật toán di truyền so với các phương pháp heuristic truyền thống về tổng thời gian và quãng đường vận hành.
  • Cung cấp khung giải pháp công nghệ hoàn chỉnh có khả năng tích hợp linh hoạt vào các hệ thống thông tin địa lý GIS phục vụ quản lý đô thị hiện đại.
  • Định hướng mở rộng nghiên cứu trong tương lai tập trung vào việc tích hợp dữ liệu giao thông thời gian thực và áp dụng các thuật toán tối ưu đa mục tiêu động.

Đóng góp chính của công trình là cầu nối vững chắc giữa lý thuyết tối ưu hóa tiến hóa và bài toán quản lý môi trường thực tế. Bước tiếp theo là triển khai thử nghiệm diện rộng trên quy mô toàn thành phố trong 12 tháng tới. Các cơ quan quản lý đô thị và doanh nghiệp môi trường cần đẩy mạnh ứng dụng giải pháp công nghệ số này để xây dựng những đô thị văn minh, bền vững và thân thiện với môi trường.