Trong bài Phân tích không gian với lớp dữ liệu di sản thế giới trên BecaGIS OpenData, chúng ta đã thực hành một số phép phân tích không gian (spatial analysis) thú vị với phần mềm mà nguồn mở QGIS và BecaGIS Plugin. Trong bài viết này, chúng ta sẽ tiếp tục tìm hiểu và giải quyết bài toán Traveling Salesman Problem với lớp dữ liệu World Heritages trên BecaGIS OpenData sử dụng phần mềm QGIS và core plugin của QGIS là GRASS GIS Provider.
1. Download lớp World Heritages trên BecaGIS OpenData
Truy cập World Heritages trên BecaGIS OpenData, hoặc có thể tìm kiếm trên trang chủ BecaGIS OpenData, Chọn Download/ Dataset
Chọn File Format là Shapefile
Mở lớp World Heritages trong QGIS:
2. Bài toán Traveling Salesman Problem
2.1 Giới thiệu
Traveling Salesman Problem (TSP) – bài toán người giao hàng, hay bài toán người du lịch là một trong những bài toán tối ưu kinh điển trong lĩnh vực khoa học máy tính và vận trù học, được ứng dụng trong rất nhiều lĩnh vực. Bài toán được phát biểu và nghiên cứu từ những năm 1930 với nội dung như sau:
Cho trước một danh sách các thành phố và chi phí di chuyển giữa chúng, cần tìm một chu trình có chi phí di chuyển thấp nhất, thăm mỗi thành phố đúng một lần và quay về thành phố xuất phát ban đầu.
“Chi phí” ở đây có thể là khoảng cách/ thời gian di chuyển/ chi phí đi lại, hoặc một trọng số nào đó, tuỳ theo ngữ cảnh của bài toán.
2.2 Phân tích bài toán
TSP thuộc lớp bài toán NP-hard (NP: Non-deterministic Polynomial-time, thuật toán bất định trong thời gian đa thức).
Để giải bài toán này, giải pháp mà chúng ta có thể nghĩ ngay đến là cách tiếp cận “ngây thơ” (naive), hay chiến thuật “vét cạn” (burte force): chọn 01 thành phố xuất phát, lần lượt tính chi phí của tất cả các lộ trình để đến n-1 thành phố còn lại và chọn ra lộ trình có chi phí thấp nhất. Dễ thấy con số này sẽ là tổng số hoán vị của (n-1) phần tử, tức (n-1)!, hay nói cách khác, độ phức tạp của thuật toán lên đến O(n!)
Trong trường hợp của World Heritages, với n = 1157 thì số phép tính để tìm kiếm một chu trình tối ưu có thể lên đến con số 5.3551129941 × 10^(3043). Đây rõ ràng là một cách tiếp cận phi thực tế để giải bài toán.
Giải thuật Nearest Neighbor: Tại điểm xuất phát bất kỳ, tìm điểm gần nhất (có trọng số thấp nhất) và di chuyển đến đó, sau đó tiếp tục tìm điểm gần nhất. Phương pháp này dễ triển khai và phù hợp với các bài toán có n nhỏ.
Ngoài ra còn có các cách tiếp cận khác như Christofides Algorithm, Simulated Annealing, hoặc Genetic Algorithm.
2.3 Giải bài toán
Trong phạm vi bài viết này không quá đi sâu vào tìm hiểu cách giải bài toán mà chủ yếu sử dụng các thuật toán đã được xây dựng sẵn để tìm TSP cho một cấu trúc đồ thị cho trước. Cụ thể, chúng ta sẽ sử dụng công cụ v.net.salesman của GRASS – là một core plugin của QGIS. Công cụ này sử dụng thuật toán heuristic để giải quyết bài toán TSP nên kết quả có thể chưa phải là lời giải tối ưu.
Delaunay Triangulation
Dealaunay Triangulation là một cấu trúc đối ngẫu của Voronoi Diagram đã được đề cập ở bài trước. Tính chất quan trọng của Delaunay Triangulation là: các cạnh của Delaunay Triangulation chính là các ứng viên cho khoảng cách gần nhất đến các điểm khác từ một điểm bất kỳ trong một tập điểm cho trước. Dựa vào đặc điểm này, đầu tiên chúng ta có thể tạo và trích lọc các cạnh Dealaunay của tập điểm. Lúc đó chúng ta sẽ có được một cấu trúc đồ thị gồm các cung là cạnh Delaunay và các nút chính là tập điểm ban đầu, sau đó áp dụng bài toán TSP trên cấu trúc đồ thị này.
3. Áp dụng TSP với lớp dữ liệu World Heritages
Giả sử bạn muốn lên kế hoạch thự hiện một hành trình để đời là viếng thăm tất cả 1157 di sản thế giới. Câu hỏi đặt ra là: lộ trình nào là tối ưu? Lộ trình tối ưu thông thường là lộ trình viếng thăm lần lượt các di sản và quay về nơi xuất phát với khoảng cách ngắn nhất. Để đơn giản hoá bài toán, khoảng cách này được tính bằng đường chim bay, với kỳ vọng là nếu khoảng cách đường chim bay ngắn thì khoảng cách di chuyển thực tế cũng ngắn.
Bài toán này có thể giải quyết bằng cách tạo Delaunay Triangulation cho tập điểm bằng cách sử dụng công cụ Delaunay Triangulation trong Processing Toolbox. Tiếp theo cần trích lọc các cạnh Delaunay theo các bước sau: chuyển Delaunay dạng Polygon sang Polyline (Polygons to Lines), Explode Lines và Delete duplicate geometries.
Sau đó, tìm kiếm với từ khoá salesman để tìm TSP cho tập điểm World Heritages.
Kết quả:
Theo kết quả này, để tham quan đủ 1157 di sản và trở về vị trí xuất phát, bạn phải thực hiện 1190 chuyến đi với khoảng 350.550 km, mỗi hành trình có chiều dài trung bình 295 km. Giả sử vận tốc di chuyển trung bình là 100 km/h, bạn sẽ mất thời gian khoảng 146 ngày chỉ riêng cho việc di chuyển. Nếu chi phí cho mỗi km là $1 thì bạn sẽ phải chuẩn bị ít nhất $350.550 cho việc di chuyển. Quả là một hành trình tốn kém về thời gian và chi phí, nhưng cũng rất xứng đáng vì bạn sẽ có tên trong sách kỷ lục Guiness thế giới.
4. Thay lời kết
Bài viết đã hướng dẫn ứng dụng thuật toán TSP để tìm lộ trình tối ưu viếng thăm tất cả các di sản thế giới trong lớp dữ liệu World Heritages trên BecaGIS OpenData, với sự hỗ trợ của phần mềm mã nguồn mở QGIS và công cụ v.net.salesman của GRASS plugin trong QGIS. Đây chỉ là bài toán mang tính gợi mở để có thể áp dụng trong các ứng dụng thực tế thuộc nhiều lĩnh vực khác nhau. Hi vọng qua bài viết này, các bạn có thể tham khảo và nghiên cứu áp dụng trong các ứng dụng chuyên ngành cụ thể của mình.
>>> TÌM HIỂU THÊM: PHÂN TÍCH KHÔNG GIAN VỚI LỚP DỮ LIỆU DI SẢN THẾ GIỚI TRÊN BECAGIS OPENDATA
