MỞ ĐẦU Bài toán định tuyến phương tiện (Vehicle Routing Problem – VRP) đã xuất hiện trên thế giới từ khá lâu trong hàng thập niên và có nhiều biến thể khác nhau tùy thuộc vào từng kịch bản nội dung cụ thể. Vận chuyển rác thải có thể coi như một bài toán định tuyến tìm đường đi có chi phí thấp nhất đi qua các điểm tập kết rác, nhằm giảm tổng chi phí quản lý thu gom, vận chuyển rác thải. So với bài toán VRP cổ điển, bài toán vận chuyển rác thải có thêm hai ràng buộc mới: (i) ràng buộc về trọng tải của các xe cuốn ép rác; và (ii) ràng buộc về thứ tự các điểm phải viếng thăm, cụ thể tất cả xe cuốn ép rác cần phải quay về điểm xử lý rác (bãi rác), trước khi quay về điểm xuất phát. Xe cuốn ép rác có sức chứa giới hạn, kết hợp với thể tích rác tại các điểm thu gom có thể thay đổi, do đó xảy ra trường hợp khi chỉ mới hoàn thành gom rác được một phần trên tuyến đường định sẵn thì xe cuốn ép rác đã đầy và phải thực hiện di chuyển tới điểm xử lý rác, sau đó xe cuốn ép rác tiếp tục di chuyển lại đến điểm thu gom tiếp theo trên lộ trình đã định sẵn.
Vấn đề này làm tăng quãng đường di chuyển của xe cuốn ép rác. Nên có thể đường đi ngắn nhất, nhưng chưa hẳn là đường đi có chi phí tối ưu nhất. Do đó, dưới sự hướng dẫn của TS. Nguyễn Trọng Khánh tôi tìm hiểu đề tài “Nghiên cứu bài toán định tuyến xe, ứng dụng trong tối ưu hóa thu gom rác thải đô thị”.
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 rắn đô thị, với 2 ràng buộc cụ thể về giới hạn thể tích xe cuốn ép rác, và điểm kết thúc bắt buộc (điểm xử lý rác) trước khi quay lại điểm xuất phát. 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 thành phố Hà Giang. GIỚI THIỆU VỀ BÀI TOÁN ĐỊNH TUYẾN XE 1.
Tổng quan về lĩnh vực tối ưu hóa tổng 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. Từ các lĩnh vực gần gũi với Toán học như Công nghệ thông tin, thiết kế chế tạo máy đến các lĩnh vực ít gần gũi hơn như quy hoạch tài nguyên, điều khiển tự động, quản trị kinh doanh, 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. Một cách tổng quát, bài toán được phát biểu như sau: Cho trước một hàm 𝑓: 𝐴 → 𝑅 (từ tập A tới tập số thực R), tìm một phần tử x0 thuộc A sao cho 𝑓 (𝑥0 ) ≤ 𝑓(𝑥) với mọi x thuộc A (tìm cực tiểu hóa) hoặc sao cho 𝑓 (𝑥0 ) ≥ 𝑓(𝑥) với mọi x thuộc A (tìm cự đại hóa).
Tối ưu hóa tổng hợp (Combinatorial optimization) quan tâm tới các bài toán mà trong đó tập các lời giải khả thi là rời rạc hoặc có thể rút gọn về một tập rời rạc. Trong toán học ứng dụng và lý thuyết khoa học máy tính, tối ưu hóa tổng hợp là một chủ đề về việc tìm kiếm một đối tượng tối ưu từ một tập hợp hữu hạn của các đối tượng. Trong các bài toán tối ưu hóa tổng hợp, tìm kiếm tập lời giải đầy đủ nhiều khi không khả thi trong thời gian thực của cuộc sống, bằng cách khác, lĩnh vực tối ưu hóa tổng hợp quan tâm tới các bài toán mà phạm vi mà các lời giải khả thi là rời rạc hoặc có thể rút gọn về một tập rời rạc với mục tiêu là tìm ra lời giải tốt nhất. Một số bài toán nổi tiếng trong lĩnh vực tối ưu hóa tổng hợp là 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) 1.
Bài toán định tuyến xe và một số biến thể Để xem xét bài toán định tuyến xe (Vehicle Routing Problem – VRP) đầu tiên ta xem xét một trường hợp đặc biệt của nó, đó là bài toán người bán hàng (Traveling Salesman Problem –TSP). Bài toán người bán hàng (TSP) và một số 8 biến thể của nó, như bài toán người bán hàng tổng quát GTSP (Generalized Traveling Salesman Problem), bài toán người bán hàng bao trùm CSP (Covering Salesman Problem), bài toán người bán hàng bao trùm tổng quát GCSP (Generalized Covering Salesman Problem) [8] là những bài toán thuộc lớp các bài toán NP-khó, thuộc thể loại tối ưu rời rạc hay tổng hợp được nghiên cứu trong lý thuyết tối ưu hoặc lý thuyết khoa học máy tính. Bài toán được phát biểu như sau. Có một người giao hàng cần đi giao hàng tại n thành phố.
Anh ta xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, khoảng cách từ một thành phố đến các thành phố khác đã được biết trước. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh của chu trình là nhỏ nhất. Bài toán được nêu ra lần đầu tiên năm 1930 và là một trong những bài toán được nghiên cứu sau nhất trong tối ưu hóa.
Nó thường được dùng làm thước đo cho nhiều phương pháp tối ưu hóa. Mặc dù bài toán rất khó giải trong trường hợp tổng quát, có nhiều phương pháp giải chính xác cũng như các phương pháp heuristic đã được tìm ra để giải quyết một số trường hợp có rất nhiều thành phố, lên tới hàng chục ngàn. Ngay trong hình thái đơn giản nhất của bài toán, bài toán người bán hàng đã có nhiều ứng dụng trong công tác lập kế hoạch, thiết kế vi mạch, … Theo các lý thuyết về độ phức tạp tính toán, bài toán người bán hàng với phiên bản cơ bản nhất là tìm chu trình đi qua tất cả các đỉnh đúng một lần và có độ dài nhỏ hơn L cho trước thuộc lớp NP-đầy đủ. Bởi vậy, có rất nhiều khả năng thời gian tính toán xấu nhất của bất kỳ biến thể thuật toán người bán hàng nào đều tăng theo sấp số nhân cùng chiều với số lượng thành phố.
Bài toán người bán hàng có rất nhiều ứng dụng thực tế, thậm chí trong dạng thức nguyên thủy của nó cũng có rất nhiều ứng dụng như lập kế hoạch, lĩnh vực vận tải hàng hóa (logistic), sản xuất các bộ vi xử lý, bảng mạch, … Thay đổi một chút, bài toán người bán hàng hay xuất hiện dưới dạng thức như là một bài toán con trong rất nhiều lĩnh vực như việc phân tích gen trong sinh học. Trong những ứng dụng này, khái niệm thành phố có thể thay đổi thành các đối tượng khác, như các điểm hàn trên bảng mạch, các mảng DNA trong GEN, và khái niệm khoảng 9 cách có thể biểu diễn bởi thời gian du lịch hay giá thành, hay giống như sự so sánh giữa các mảng DNA với nhau. Trong nhiều ứng dụng, các hạn chế truyền thống như giới hạn tài nguyên hay giới hạn thời gian còn làm cho bài toán trở nên khó hơn. Bài toán người bán hàng tổng quát (Generalized Traveling Salesman Problem - GTSP) được biết đến như một biến thể của bài toán người bán hàng TSP.
Cũng như trong TSP, ta xem xét n thành phố và khoảng cách giữa n thành phố biết trước. Biến thể GTSP có đôi chút khác biệt là tập hợp n thành phố được phân chia thành m cụm các thành phố. Một giải pháp tối ưu GTSP là tìm chu trình có khoảng cách nhỏ nhất mà người bán hàng chỉ thăm đúng một nút của mỗi cụm. Bài toán GTSP có nhiều ứng dụng thực tế như định tuyến máy bay, giao thư, định tuyến phương tiện, tổ chức tập tin trong máy tính, … Tìm kiếm các giải pháp hiệu quả đối với các bài toán GTSP tổng hợp được coi là rất quan trọng trong nhiều ngành, đặc biệt là các tổ chức luôn phải cân nhắc tới vấn đề về chi phí vận chuyển do giá nhiên liệu tăng cao.
Bài toán người bán hàng bao trùm (Covering Salesman Problem - CSP) là một biến thể của bài toán TSP. Trong bài toán CSP mục tiêu là tìm kiếm chu trình có chiều dài nhỏ nhất của một tập con của n thành phố, mà sao cho mỗi nút không nằm trong chu trình thì nằm trong một khoảng cách giới hạn đã được định nghĩa trước d từ một thành phố bất kỳ thuộc chu trình. Ví dụ trong hình sau đây mô tả rõ hơn bài toán CSP, ô vuông viền màu đen đậm là kho hàng, các ô vuông màu trắng là các cơ sở bán hàng, các hình tròn nhỏ là khách hàng. Đối với bài toán TSP, ta phải tìm chu trình có chiều dài nhỏ nhất đi qua tất cả các khách hàng, đối với bài toán CSP, ta tìm chu trình nhỏ nhất đi qua tất cả các cơ sở bán hàng, các khách hàng mà nằm trong phạm vi bán kính di của cơ sở bán hàng i thì ta không quan tâm nữa, do đó độ khó của bài toán CSP được giảm xuống so với bài toán TSP.
Ví dụ bài toán người bán hàng bao trùm CSP Bài toán người bán hàng bao trùm tổng quát (Generalized Covering Salesman Problem – GCSP). Tương tự bài toán CSP, tuy nhiên mỗi thành phố i cần phải viếng thăm ít nhất ki lần, và đó là một chi phí tương ứng với mỗi thành phố được viếng thăm. Ta cần tìm kiếm một lộ trình có chi phí nhỏ nhất mà mỗi thành phố i được viếng thăm ít nhất ki lần. Bài toán GCSP cũng có một số thể thức phổ biến được đề cập, thể thức đầu tiên, mỗi thành phố chỉ được viếng thăm một lần, thể thức thứ hai, mỗi thành phố được viếng thăm hơn một lần nhưng không được phép ở lại “qua đêm” (có nghĩa là để viếng thăm lại một thành phố thì phải đến một thành phố khác trước khi trở về thành phố này), thể thức thứ 3 có thể viếng thăm mỗi thành phố nhiều hơn một lần một cách dồn dập (không cần tới thành phố khác trước khi quay trở lại thành phố này).
11 Theo lý thuyết toán học của độ phức tạp tính toán, phiên bản chính của bài toán người bán hàng (ràng buộc độ dài chu trình nhỏ hơn số L cho trước) thuộc lớp NP-đầy đủ. Vì vậy, không có lời giải hiệu quả nào cho việc giải bài toán người bán hàng.