PHẦN MỞ ĐẦU 1. Lý do chọn đề tài Hiện nay, vấn đề bảo vệ môi trường luôn là mối quan tâm hàng đầu của nhiều quốc gia trên thế giới. Đã có nhiều phương án cũng như nhiều chiến dịch, cam kết được mở ra để khắc phục, giảm thiểu đi hậu quả ô nhiễm môi trường như sự kiện “Giờ Trái Đất”, cam kết của các quốc gia giảm lượng phát thải khí nhà kính, hạn chế sử dụng túi nilon, đồ nhựa… Bảo vệ môi trường đồng nghĩa với việc tự bảo vệ cho sức khỏe của chính bản thân mình, gia đình và xã hội. Hành động tự ý thức của mỗi cá nhân có vai trò rất lớn đối với công tác bảo vệ môi trường, bảo vệ Trái Đất.
Việt Nam sau hơn 30 năm đổi mới, kinh tế đất nước phát triền, nhiều khu công nghiệp được thành lập. Sau Vedan năm 2008, Formusa Hà tĩnh năm 2016 sẽ còn không ít các công ty, tập đoàn khác có tên trong danh sách gây ô nhiễm môi trường nghiêm trọng. Tại các khu công nghiệp, rác thải cần được thu gom và đưa đi xử lý tại các bãi khá nhiều. Quản lý rác thải ở khu công nghiệp (RTCN) hiệu quả là một trong những trọng tâm của những chính sách phát triển môi trường bền vững.
Việc quản lý kém hiệu quả RTCN, đặc biệt ở khu vực KCN, là mối đe dọa tới sức khỏe cộng đồng, làm ô nhiễm môi trường dẫn tới giảm chất lượng cuộc sống của người dân. Hơn nữa, quản lý RTCN không khoa học làm phát sinh không chỉ nhiều chi phí tốn kém trong hiện tại mà còn về lâu dài. Qua khảo sát thì chưa có nhiều đề tài hướng tới giải quyết bài toán tối ưu thu gom rác thải trong Khu công nghiệp. Tổng quan về vấn đề nghiên cứu Luận văn sẽ tập trung nghiên cứu các bài toán định tuyến xe, và biến thể của chúng.
Để từ đó áp dụng cho bài toán thu gom rác thải khu công nghiệp, với các ràng buộc liên quan đến thể tích xe cuốn ép rác, quãng đường phải đi, giới hạn khung thời gian thu gom. Đối tượng và phạm vi nghiên cứu - Giải pháp đưa ra sẽ được áp dụng thử nghiệm cho việc thu gom rác thải tại khu công nghiệp. - Phạm vi: Tìm hiểu các giải thuật tối ưu tìm đường đi ngắn nhất có ràng buộc về thời gian. Áp dụng bài toán thu gom rác thải ràng buộc thời gian theo ca làm việc.
Xây dựng thử nghiệm hệ thống đề xuất đường đi thu gom rác thải trong khu công nghiệp có tính các ràng buộc thời gian, hệ thống nhận đầu vào là các bản đồ điểm đổ rác, lưu lượng rác tại các điểm, số lượng xe, dung lượng thùng xe, thời gian cần phải xong. Đầu ra là quãng đường tối ưu. Phương pháp nghiên cứu - Nghiên cứu lý thuyết: - Thực hiện tìm hiểu một số giải thuật áp dụng cho bài toán định tuyến xe VRP (Vehicle Routing Problem – VRP). - Bài toán định tuyến xe với cửa sổ thời gian VRPTW (Vehicle Routing Problem with Time Windows).
- Nghiên cứu thực nghiệm: Dữ liệu thực tế được hỗ trợ từ đề tài cấp Sở HN. Để tính toán đề các yếu tố động, đề tài cũng phát triển một mô hình dựa trên tác tử (Agent Based Model - ABM) để mô phỏng lộ trình tối ưu trong ngữ cảnh động. Từ đó đối chiếu và so sánh hai kết quả với nhau. TỔNG QUAN VỀ BÀI TOÁN ĐỊNH TUYẾN XE 3 1.
Tổng quan về lĩnh vực tối ưu hóa tổ hợp. Tối ưu hóa bản chất là một ngành Toán học và được ứng dụng hiệu quả trong nhiều ngành khác nhau. Bài toán tối ưu tổ hợp là bài toán chỉ quan tâm đến một cấu hình “tốt nhất” theo một nghĩa nào đấy. Đây là bài toán có nhiều ứng dụng trong thực tiễn và lý thuyết tổ hợp đã đóng góp một phần đáng kể trong việc xây dựng những thuật toán hữu hiệu.
Từ các lĩnh vực như Công nghệ thông tin, điều khiển tự động, thiết kế chế tạo máy đến các lĩnh vực khác như quản trị kinh doanh, quy hoạch tài nguyên, kiến trúc đô thị, … đều có rất nhiều ứng dụng, đặc biệt trong việc xây dựng hệ hỗ trợ ra quyết định và phát triển các hệ thống lớn. Do đó, các lĩnh vực của tối ưu hóa ngày càng trở nên đa dạng. Bài toán tối ưu tổ hợp có thể phát biểu dưới hình thức toán học như sau: Tìm X∈ D : f (X) →min (max) (1.1) Trong đó D là tập hữu hạn, gồm các cấu hình thỏa mãn điều kiện của bài toán. Hàm f được gọi là hàm mục tiêu.
Tập hợp D được gọi là miền xác định hay miền phương án. Mỗi phần tử của D được gọi là một phương án. Phương án tốt nhất được gọi là phương án tối ưu. Giá của phương án tối ưu được gọi là giá trị tối ưu.
Chú ý rằng do D hữu hạn nên phương án tối ưu bao giờ cũng tồn tại. Có thể có nhiều phương án tối ưu, nhưng giá trị tối ưu là duy nhất. Trong mỗi bài toán cụ thể, ta phải chỉ rõ các điều kiện xác định D và cách tính hàm f (hàm f có thể tính bằng một công thức hoặc bằng một thủ tục). Bài toán người bán hàng (traveling salesman problem – TSP) và bài toán cây khung nhỏ nhất (minimum spanning tree problem - MST) là bài toán nổi tiếng trong lĩnh vực tối ưu tổ hợp.
Bài toán định tuyến xe và một số biến thể 1.1 Phát biểu bài toán định tuyến xe Bài toán Người bán hàng (Travelling Salesman Problem - gọi tắt là TSP) chính là trường hợp đơn giản nhất của bài toán định tuyến xe (Vehicle Routing Problem - VRP) với một xe giao hàng duy nhất - người bán hàng. Bài toán yêu cầu tìm đường đi ngắn nhất cho nhân viên bán hàng (traveling salesman), nhân viên bán hàng xuất phát từ một thành phố, đi qua lần lượt tất cả các thành phố có trong lộ 4 trình duy nhất một lần và quay về thành phố ban đầu với chi phí thấp nhất. Nhiệm vụ của bài toán là phải tìm một lộ trình tối ưu nhất (ví dụ như tổng độ dài quãng đường dịch chuyển là nhỏ nhất) để người bán hàng đi giao hàng cho tất cả thành phố theo dự định, mỗi thành phố được ghé thăm duy nhất một lần. Bài toán TSP có thể được mô hình hóa bằng một đồ thị, trong đó các đỉnh của đồ thị tương ứng với các thành phố, các cạnh tương ứng với đường đi giữa các thành phố, khoảng cách giữa các thành phố là trọng số tương ứng của các cạnh nối chúng.
Lời giải tối ưu của bài toán TSP là một đường đi ngắn nhất nối tất cả các điểm trên đồ thị hay còn gọi là một chu trình Hamilton ngắn nhất.1 Ví dụ cho bài toán Người bán hàng– TSP Trên cơ sở mở rộng bài toán TSP, bài toán VRP cơ bản bao gồm một tập các xe được tập kết tại kho hàng và mỗi khách hàng có các yêu cầu vận chuyển khác nhau. Vấn đề đặt ra là phải tìm cách định tuyến cho tập các xe phục vụ được tất cả khách hàng với chi phí vận chuyển là nhỏ nhất.2 Mô phỏng bài toán VRP Hình 1.2 mô phỏng một bài toán VRP trong đó hình bên trái thể hiện các xe được tập kết tại Depot, mỗi khách hàng được biểu diễn bởi một điểm chấm đen với yêu cầu vận chuyển của họ. Các cạnh nối giữa các điểm diễn tả đường đi giữa chúng. Hình bên phải diễn tả lời giải cho bài toán, trong đó các chu trình nối bởi các đường nét đậm diễn tả lộ trình của các tuyến xe phục vụ các khách hàng.
Trong một bài toán định tuyến xe cơ bản, các xe sẽ xuất phát từ các kho hàng, đi giao hàng hoặc nhận hàng từ khách hàng và quay trở về điểm xuất phát. Các khái niệm được sử dụng trong bài toán bao gồm: ✔ Xe (Vehicle): phương tiện được dùng để vận chuyển hàng hóa. Trong thực tế hầu như các xe là không đồng nhất, chúng được phân loại dựa vào các đặc điểm như sức chứa của xe (tức tải trọng hàng hóa tối đa xe có thể đáp ứng), loại hàng hóa mà xe có thể vận chuyển (hàng hóa đông lạnh, hàng hóa khô…), chi phí vận chuyển (có hai loại chi phí thông dụng: chi phí cố định – chi phí cần thiết ban đầu để xe có thể khởi hành, chi phí này không phụ thuộc vào quãng đường mà xe phải đi; chi phí động – là chi phí tiêu tốn mà xe phải đi trên từng đơn vị quãng đường ) … ✔ Kho hàng (Depot): là nơi cất trữ hàng hóa hay cũng có thể là địa điểm xuất phát/quay về của các xe. Trong một số bài toán, hàng hóa cần giao có thể được cất trữ trong một vài kho hàng.
6 ✔ Khách hàng (Customer): có thể đón hàng do xe giao tới hoặc chuyển hàng lên xe để vận chuyển về kho hoặc cả hai. Mỗi khách hàng yêu cầu một lượng hàng hóa nhất định, có thể đưa ra một số yêu cầu khác về thời gian cho phép xe đến giao hàng, thời gian cho phép bốc dỡ hàng… ✔ Lộ trình (Route): mỗi hành trình bắt đầu đi từ điểm xuất phát rồi quay trở về điểm ban đầu (kho hàng) của một xe được coi là một lộ trình. Bài toán định tuyến xe được xem là một trong những bài toán phức tạp và kinh điển nhất của Vận trù học. Có thể phát biểu bài toán VRP cơ bản một cách đơn giản như sau: Có một tập hợp 𝑀 xe giống nhau cùng xuất phát tại một kho hàng đi làm nhiệm vụ giao hàng cho 𝑁 khách hàng, mỗi khách hàng đòi hỏi cung cấp một lượng hàng nhất định.
Yêu cầu đặt ra của bài toán là tìm đường đi ngắn nhất cho 𝑀 xe đáp ứng được tất cả các đòi hỏi của khách hàng. Các biến thể của bài toán định tuyến xe Bài toán VRP có rất nhiều biến thể dựa trên các yêu cầu vận chuyển cụ thể của các bài toán thực tế và được phân chia theo từng đặc điểm cụ thể như đặc điểm về đội xe, về yêu cầu vận chuyển hay về vấn đề lợi nhuận. Cụ thể như sau: 1. Dựa vào cấu trúc đường đi - Bài toán VRP có các khách hàng được biểu diễn bởi các cạnh (Arc Routing Problem – ARP) là một bài toán đặc biệt, thay vì các khách hàng được biểu diễn bằng các điểm trong đồ thị như trong các bài toán VRP thông thường thì sẽ được biểu diễn bằng các cạnh, tương ứng với các đoạn đường đi trong thực tế.