Chương 1 – Giới thiệu bài toán tối ưu thu gom chất thải rắn đô thị. Chƣơng này giới về bài toán tối ƣu thu gom chất thải rắn đô thị và các nghiên cứu liên quan. 2 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chương 2 –Thiết kế thuật toán di truyền cho bài toán tối ưu thu gom chất thải rắn đô thị Nội dung của chƣơng này tổng quan về thuật toán di truyềnvà thiết kếthuật toán di truyền để giải bài toán tối ƣu thu gom chất thải rắn đô thị. Chương 3 – Ứng dụng thuật toán di truyền trong bài toán tối ưu thu gom chất thải rắn đô thị tại thành phố Sfax,Tunisia 3 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 1: GIỚI THIỆU BÀI TOÁN TỐI ƢUTHU GOM CHẤT THẢI RẮN ĐÔ THỊ 1.
Các loại chất thải đô thị và nhu cầu thu gom Trong những năm gần đây, cùng với sự phát triển kinh tế - xã hội, các ngành sản xuất kinh doanh dịch vụ ở các đô thị và khu công nghiệp đƣợc mở rộng và phát triển nhanh chóng, một mặt đóng góp tích cực cho sự phát triển của quốc gia, mặt khác lƣợng rác thải, chất thải thải ra ngoài môi trƣờng ngày càng nhiều và ảnh hƣởng rất lớn đến môi trƣờng xung quanh là nguồn gốc chính gây ô nhiễm môi trƣờng. Từ đó đặt ra yêu cầu cấp bách cho chính quyền địa phƣơng và ngƣời dân là phải có kế hoạch làm sạch, thu gom, vận chuyển, xử lý thƣờng xuyên các loại chất thải rắn ở các khu nhà ở cũng nhƣ khu đô thị và khu công nghiệp. Đó là các loại chất thải sinh hoạt, thức ăn dƣ thừa, các loại chất thải đƣờng phố. Thành phần của chất thải bao gồm chất thải hữu cơ, nhựa dẻo, giấy/bìa cứng, kim loại, thủy tinh và chất thải khác.
Khối lƣợng chất thải rắn đô thị rất lớn nhƣng chỉ có 70% lƣợng chất thải đƣợc đem đi chôn lấp. 5% 4% 2% hữu cơ 10% nhựa giấy/ bìa cứng 11% kim loại 68% thủy tinh chất thải khác Hình 1.1: Ví dụ về các loại rác thải tại Sfax, Tunisia năm 2016 4 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Chất thải rắn là một mối quan tâm mang tính cấp thiết tại bất kỳ đô thị nào trên thế giới. Chất thải rắn là một trong những yếu tố chính gây biến đổi khí hậu và sự nóng lên của toàn cầu [3, 4]. Nó không chỉ làm ô nhiễm môi trƣờng mà còn gián tiếp ảnh hƣởng đến ách tắc giao thông, tài chính ngân sách và chất lƣợng cuộc sống.
Ngày nay, hầu hết các nƣớc đang phát triển trên thế giới hiện đang trong quá trình đô thị hóa và công nghiệp hóa, dẫn đến việc gia tăng lƣợng chất thải. Chính vì vậy mà việc thu thập và xử lý chất thải rắn, đặc biệt là trong bối cảnh các nƣớc đang phát triển thực sự là một yêu cầu cấp thiết để bảo vệ môi trƣờng, chất lƣợng cuộc sống và tuổi thọ của con ngƣời. Chất thải rắn nếu không đƣợc quản lý và xử lý nghiêm túc sẽ có khả năng gây suy thoái môi trƣờng nghiêm trọng đẫ tới nhiều hệ lụy. Do đó, nhu cầu thu gom chất thải rắn đã trở thành vấn đề bức xúc đối với toàn xã hội và cần đƣợc quan tâm quản lý thu gom triệt để.
Nhu cầu thu gom chất thải rắn thì cấp bách cực kỳ tuy nhiên khối lƣợng chất thải rắn phát sinh lớn và tỷ lệ thu gom còn hạn chế nên chất thải rắn sinh ra chƣa đƣợc thu gom và xử lý triệt để. Vì vậy, bài toán tối ƣu thu gom chất thải rắn đô thị đang là bài toán khó với hầu hết các quốc gia trên thế giới. Bài toán tối ƣu thu gom chất thải rắn đô thị Tối ƣu thu gom chất thải rắn đô thị mang nhiều ý nghĩa về mặt môi trƣờng, phát triển cảnh quan và tiết kiệm kinh tế. Tại mỗi thành phố sẽ có các phƣơng tiện vẩn chuyển chất thải, những bãi đỗ xe của các xe làm nhiệm vụ, các điểm đổ chất thải tập trung, các điểm trung chuyển chất thải và các bãi đổ chất thải lớn.
Tùy vào yêu cầu về thời gian, phƣơng tiện vận chuyển và tuyến đƣờng đi của các xe mà mỗi một thành phố sẽ có những kịch bản riêng cho việc thu gom chất thải. Bài toán tối ƣu có thể là tối ƣu về lƣợng chất thải thải thu thập đƣợc, hoặc thời gian đi thu thập, hoặc là quãng đƣờng đi thu thập là tối ƣu nhất, hoặc là tối ƣu chi phí vận chuyển. Từ kịch bản cụ thể, xây dựng mô hình cho bài toán để tìm ra các phƣơng pháp giải quyết. 5 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
Các nghiên cứu liên quan Vấn đề tối ƣu thu gom MSW có thể đƣợc mô tả bởi mô hình định tuyến xe (VR) với các ràng buộc cơ bản nhƣ sức chứa và ràng buộc mạng lƣới định tuyến xe. Nghiên cứu trong [12] và [20] cho thấy sự khác nhau giữa các tuyến đƣờng dân cƣ và các tuyến đƣờng thƣơng mại. Giải pháp point – to- point là chấp nhận đƣợc cho các tuyến đƣờng thƣơng mại nhƣng các tuyến đƣờng dân cƣ đòi hỏi phải sử dụng giải pháp định tuyến phù hợp. Các nghiên cứu trong [6], [7],[10],[11],[21] cũng đồng quan điểm trên.
Bài toán thu gom chất thải cũng có thể đƣợc xây dựng nhƣ Node Routing Problem (NRP), tức là các xe phải đi qua một số các điểm [6],[13],[21], [22]. Tuy nhiên các phƣơng pháp giải là rất rộng rãi và không có phƣơng pháp hoàn hảo nào để giải quyết vấn đề về định tuyến xe. Một số tác giả sử dụng phƣơng pháp giải chính xác cho mô hình thu gom chất thải nhƣ [7] sử dụng lý thuyết đồ thị và các công cụ lập trình toán học. Tác giả đã đề xuất phƣơng pháp giảm thiểu khoảng cách đi thăm cho mỗi xe và giảm thiểu tổng công việc cho các xe.
Tác giả [10] sử dụng phƣơng pháp Heuristic để chia hệ thống quản lý chất thải thành ba cấp độ. Mỗi cấp độ sử dụng bộ sƣu tập riêng biệt hoặc chiến lƣợc vận chuyển để thu gom và vận chuyển chất thải. Mỗi giai đoạn đã đƣợc tối ƣu hóa. Tác giả đã đề xuất thuật toán Heuristic để giảm thiểu độ dài quãng đƣờng vận chuyển và có một mục tiêu chính là xác định tối ƣu việc thu gom và tuyến đƣờng vận chuyển, để giảm chi phí vận chuyển trong hệ thống quản lý chất thải.
Phƣơng pháp này có thể giảm hơn 30% tổng quãng đƣờng vận chuyển. Các tác giả [13] sử dụng phƣơng pháp meta-Heuristic trong thu gom chất thải thải tại Đài Loan. Có hai bƣớc để xác định khoảng cách đi thu thập. Bƣớc đầu tiên là tối ƣu kế hoạch thu thập tại các điểm bao gồm tất cả các khu vực dân cƣ và bƣớc thứ hai là áp dụng thuật toán Heuristics ACO để giải quyết tối thiểu các xe sử dụng và khoảng cách tối thiểu đi thu gom chất thải.
Tác giả [20] cải thiện kết quả sử dụng hệ thống thông tin địa lý GIS. Nó đƣợc chứng minh là một công cụ mạnh mẽ với 6 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com khả năng cung cấp các thông tin không gian chi tiết và sử dụng hiệu quả các thuật toán định tuyến có sẵn nhƣ Dijkstra trong các phần mềm GIS cho việc tìm kiếm các giải pháp tối ƣu. Một vài ví dụ đƣợc liệt kê nhƣ tác giả [20] sử dụng ArcGIS Network Analyst [27] để xác định tuyến đƣờng tốt nhất cho việc thu thập chất thải thải đô thị. Tác giả [15] nghiên cứu quản lý chất thải đô thị ở Port Said, Ai Cập thông qua phần mềm MPL V4.
Tác giả [18] dựa vào MapInfo [9] để tìm các tuyến đƣờng tối ƣu trong thành phố Trabzon, Thổ Nhĩ Kỳ. Tác giả [4] cho rằng ArcGIS có khả năng cập nhật và hiển thị các thông tin cần thiết. ArcGIS sử dụng thuật toán định tuyến dựa trên Dijkstra cho việc tìm kiếm các giải pháp tối ƣu, mục tiêu là giảm thiểu tổng khoảng cách thu thập, sử dụng 13 tuyến đƣờng kết nối 13 phƣờng và một trạm trung chuyển [22]. Kết quả của phƣơng pháp đã tiết kiệm đƣợc đến 9.93% cho quãng đƣờng.
Tác giả [22] áp dụng ArcGIS để giải quyết vấn đề thu gom chất thải đô thị ở thành phố Đã Nẵng, Việt Nam. Tác giả trình bày một mô hình định tuyến xe mới để tối ƣu hóa lƣợng chất thải thải thu đƣợc thông qua phƣơng pháp lai mới giữa Chaotic Particle Swarm Optimization và ArcGIS để tạo ra giải pháp tối từ mô hình định tuyến xe ở Đà nẵng. Mục tiêu nghiên cứu Để giải quyết bài toán tối ƣu thu gom chất thải rắn đô thị, luận văn nghiên cứu tổng quan về thuật toán di truyền - là một thuật toántrong nhóm các thuật toán tối ƣu tiến hóa nhằm tìm kiếm giải pháp thích hợp cho các bài toán tối ƣu, từ đó ứng dụng xây dựng phƣơng pháp tối ƣu thời gian thu gom chất thải. Đó là thiết kế thuật toán di truyền cho bài toán tối ƣu thu gom chất thải rắn.
Để kiểm chứng tính hiệu quả của thuật toán, luận văn sẽ triển khai ứng dụng dựa trên trên kịch bản, dữ liệu thu thập và yêu cầu tại thành phố Sfax, Tunisia - là thành phố lớn thứ hai và là một trong những thành phố có lƣợng rác thải bình quân theo đầu ngƣời lớn nhất ở Tunisia. 7 LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Tổng kết chƣơng Chƣơng 1 đã trình bày bài toán tổng quan thu gom chất thải rắn. Có thể nhận thấy bài toán tối ƣu thu gom chất thải rắn là một mối quan tâm mang tính cấp thiết tại bất kỳ đô thị nào trên thế giới.
Nó mang nhiều ý nghĩa về mặt môi trƣờng, phát triển cảnh quan và tiết kiệm kinh tế. Để giải quyết khó khăn này, luận vănxây dựng phƣơng pháp tối ƣu thời gian thu gom chất thải. Đó là thiết kế thuật toán di truyền cho bài toán tối ƣu thu gom chất thải rắn ở chƣơng sau. 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com CHƢƠNG 2: THIẾT KẾ THUẬT TOÁN DI TRUYỀN CHO BÀI TOÁN TỐI ƢU THU GOM CHẤT THẢIRẮN ĐÔ THỊ 2.
Tổng quan về thuật toán di truyền Hiện nay và trong tƣơng lai, trí tuệ nhân tạo đã, đang và sẽ đƣợc nghiên cứu, phát triển rất mạnh mẽ và đƣợc ứng dụng rộng rãi. Đây là một mảng chuyên môn rất lớn trong khoa học máy tính, bao gồm nhiều lĩnh vực khác nhau. Một trong những lĩnh vực đó là kỹ thuật tính toán thông minh trong đó có Thuật toán di truyền đã đem lại những phƣơng mới để giải bài toán mà nếu áp dụng những phƣơng pháp truyền thống sẽ gặp nhiều khó khăn[1].