Lộ trình đi bộ ngắn nhất để ghé hết 81.998 quán rượu ở Hàn Quốc là 178 ngày

xguru · 2025-04-23T09:31:02+09:00

Giáo sư William Cook của Đại học Waterloo đã tính toán một trường hợp đầu tiên trên thế giới của bài toán người du lịch (TSP) cho lộ trình ngắn nhất ghé thăm 81.998 quán rượu ở Hàn Quốc Sử dụng Open Source Routing Machine (OSRM) để tính khoảng 3,3 tỷ cặp thời gian đi bộ và chứng minh về mặt toán học rằng đây là phương án tối ưu Kết quả tính toán cho thấy nếu đi bộ không nghỉ thì tổng thời gian là 15.386.177 giây, tức 178 ngày 1 giờ 56 phút 17 giây Việc tối ưu TSP sử dụng các công cụ LKH và Concorde, đồng thời áp dụng phương pháp mặt phẳng cắt Đây là trường hợp giải TSP dựa trên mạng đường bộ lớn nhất thế giới, vượt qua lộ trình 57.912 điểm ở Hà Lan từng giữ kỷ lục trước đó Bài toán người du lịch (Traveling Salesman Problem) đi bộ qua mọi quán rượu ở Hàn Quốc Tính toán lộ trình ngắn nhất để ghé thăm toàn bộ 81.998 quán rượu ở Hàn Quốc rồi quay trở lại điểm xuất phát Lần đầu tiên trên thế giới, một bài toán TSP với số lượng địa điểm lớn như vậy được giải tối ưu Thời gian đi bộ của tổng cộng 3.361.795.003 cặp giữa các quán rượu được tính bằng OSRM - Open Source Routing Machine Về mặt toán học, không tồn tại lộ trình nào ngắn hơn lộ trình này Đây là bài toán TSP có quy mô lớn nhất từ trước đến nay xét theo số lượng điểm phải ghé Thời gian cần cho lộ trình ngắn nhất Nếu đi bộ liên tục theo lộ trình tối ưu đã tính, tổng thời gian sẽ là 15.386.177 giây Con số này tương đương 178 ngày 1 giờ 56 phút 17 giây Trên thực tế, do còn phải nghỉ ngơi hoặc uống trong lúc đi, nên rất khó hoàn thành chính xác theo thời gian đó Đây là lộ trình tối ưu theo thời gian đi bộ dựa trên OSRM, không thể rút ngắn thêm dù chỉ 1 giây Bối cảnh lịch sử của TSP và kỷ lục mới Kỷ lục lớn nhất trước đây là lộ trình xe đạp qua 57.912 địa điểm ở Hà Lan Lộ trình korea81998 lần này là một trường hợp giải bài toán TSP ở quy mô còn lớn hơn Việc tính toán được thực hiện từ tháng 12/2024 đến tháng 3/2025 tại Đại học Roskilde và Đại học Waterloo Có thể xem chi tiết quá trình tính toán ở trang tính toán riêng Cách trực quan hóa lộ trình Có thể xem lộ trình trên bản đồ tương tác, đồng thời khám phá theo 7 khu vực được chia sẵn Cung cấp nhiều chế độ hiển thị khác nhau như bản đồ khoảng cách theo màu, thang xám, v.v. Một số ảnh độ phân giải cao của từng phần lộ trình cũng được cung cấp riêng Chế độ phóng to theo từng thành phố có trên trang thành phố Chiến lược giải TSP và những hiểu lầm thường gặp Một số phương tiện truyền thông nói rằng chỉ với 22 thành phố cũng phải mất 1000 năm, nhưng điều đó ám chỉ trường hợp thử ngẫu nhiên mọi lộ trình có thể có Trên thực tế, với các kỹ thuật tối ưu hóa tiên tiến, vẫn có thể giải được những bài toán có rất nhiều điểm Với korea81998, số lộ trình khả dĩ lên tới một con số có 367.308 số 0 đứng sau số 2 Quá trình giải sử dụng kết hợp thuật toán LKH (Lin-Kernighan Heuristic) và Concorde TSP Solver - phương pháp mặt phẳng cắt Tóm tắt khái niệm phương pháp mặt phẳng cắt Dựa trên quy hoạch tuyến tính Thay vì biểu diễn việc có dùng một con đường hay không, phương pháp này biểu diễn mức độ kết nối bằng giá trị số từ 0 đến 1 Bằng cách bổ sung các ràng buộc theo từng bước, có thể tìm ra lộ trình ngắn nhất Có thể xem giải thích chi tiết hơn trong Scientific American và bài giảng trên YouTube Bài toán P và NP Bài toán TSP là một bài toán NP-đầy đủ, là ví dụ tiêu biểu trong vấn đề P và NP Những thảo luận thú vị liên quan được giới thiệu trong bài viết của Giáo sư Lance Fortnow Đây là một trong những bài toán chưa có lời giải nổi tiếng nhất của khoa học máy tính Ý nghĩa của tối ưu hóa toán học Dự án này vừa là một thử nghiệm, vừa là nền tảng để phát triển các phương pháp tối ưu hóa tổng quát Tiềm năng ứng dụng rất cao trong các lĩnh vực công nghiệp, thương mại, y học và môi trường Mô hình hóa toán học là công cụ quan trọng để sử dụng hiệu quả các nguồn lực hữu hạn Giới thiệu nhóm nghiên cứu William Cook: Đại học Waterloo, Canada Daniel Espinoza: Alicanto Labs, Chile Marcos Goycoolea: Đại học Adolfo Ibáñez, Chile Keld Helsgaun: Đại học Roskilde, Đan Mạch Lời cảm ơn IBM CPLEX Optimizer: cảm ơn vì đã cung cấp miễn phí cho nghiên cứu học thuật Bản đồ được tạo bằng Leaflet, OpenStreetMap, Carto, Stadia Maps Tiến sĩ Eom Sang-il đã cung cấp dữ liệu vị trí quán rượu ở Hàn Quốc dựa trên dữ liệu của Cơ quan Cảnh sát Quốc gia Hàn Quốc Việc tính thời gian đi bộ sử dụng OSRM Các dự án TSP ở những quốc gia khác Nhật Bản: 40.426 cửa hàng tiện lợi Vương quốc Anh: 49.687 quán rượu Hoa Kỳ: 49.603 địa điểm lịch sử Hà Lan: 57.912 di tích Tài liệu học thêm In Pursuit of the Traveling Salesman: lịch sử và ứng dụng của TSP Traveling Salesman Problem: nghiên cứu áp dụng phương pháp mặt phẳng cắt The Golden Ticket: giới thiệu vấn đề P vs. NP Opt Art: tạo ảnh nghệ thuật bằng TSP Approximation Algorithms: nghiên cứu mới nhất về thuật toán xấp xỉ cho TSP Computational Solutions for TSP Applications: sách về các trường hợp ứng dụng, xuất bản năm 1994

(math.uwaterloo.ca)

23 điểm bởi xguru 2025-04-23 | 10 bình luận | Chia sẻ qua WhatsApp

Giáo sư William Cook của Đại học Waterloo đã tính toán một trường hợp đầu tiên trên thế giới của bài toán người du lịch (TSP) cho lộ trình ngắn nhất ghé thăm 81.998 quán rượu ở Hàn Quốc
Sử dụng Open Source Routing Machine (OSRM) để tính khoảng 3,3 tỷ cặp thời gian đi bộ và chứng minh về mặt toán học rằng đây là phương án tối ưu
Kết quả tính toán cho thấy nếu đi bộ không nghỉ thì tổng thời gian là 15.386.177 giây, tức 178 ngày 1 giờ 56 phút 17 giây
Việc tối ưu TSP sử dụng các công cụ LKH và Concorde, đồng thời áp dụng phương pháp mặt phẳng cắt
Đây là trường hợp giải TSP dựa trên mạng đường bộ lớn nhất thế giới, vượt qua lộ trình 57.912 điểm ở Hà Lan từng giữ kỷ lục trước đó

Bài toán người du lịch (Traveling Salesman Problem) đi bộ qua mọi quán rượu ở Hàn Quốc

Tính toán lộ trình ngắn nhất để ghé thăm toàn bộ 81.998 quán rượu ở Hàn Quốc rồi quay trở lại điểm xuất phát
Lần đầu tiên trên thế giới, một bài toán TSP với số lượng địa điểm lớn như vậy được giải tối ưu
Thời gian đi bộ của tổng cộng 3.361.795.003 cặp giữa các quán rượu được tính bằng OSRM - Open Source Routing Machine
Về mặt toán học, không tồn tại lộ trình nào ngắn hơn lộ trình này
Đây là bài toán TSP có quy mô lớn nhất từ trước đến nay xét theo số lượng điểm phải ghé

Thời gian cần cho lộ trình ngắn nhất

Nếu đi bộ liên tục theo lộ trình tối ưu đã tính, tổng thời gian sẽ là 15.386.177 giây
Con số này tương đương 178 ngày 1 giờ 56 phút 17 giây
Trên thực tế, do còn phải nghỉ ngơi hoặc uống trong lúc đi, nên rất khó hoàn thành chính xác theo thời gian đó
Đây là lộ trình tối ưu theo thời gian đi bộ dựa trên OSRM, không thể rút ngắn thêm dù chỉ 1 giây

Bối cảnh lịch sử của TSP và kỷ lục mới

Kỷ lục lớn nhất trước đây là lộ trình xe đạp qua 57.912 địa điểm ở Hà Lan
Lộ trình korea81998 lần này là một trường hợp giải bài toán TSP ở quy mô còn lớn hơn
Việc tính toán được thực hiện từ tháng 12/2024 đến tháng 3/2025 tại Đại học Roskilde và Đại học Waterloo
Có thể xem chi tiết quá trình tính toán ở trang tính toán riêng

Cách trực quan hóa lộ trình

Có thể xem lộ trình trên bản đồ tương tác, đồng thời khám phá theo 7 khu vực được chia sẵn
Cung cấp nhiều chế độ hiển thị khác nhau như bản đồ khoảng cách theo màu, thang xám, v.v.
Một số ảnh độ phân giải cao của từng phần lộ trình cũng được cung cấp riêng
Chế độ phóng to theo từng thành phố có trên trang thành phố

Chiến lược giải TSP và những hiểu lầm thường gặp

Một số phương tiện truyền thông nói rằng chỉ với 22 thành phố cũng phải mất 1000 năm, nhưng điều đó ám chỉ trường hợp thử ngẫu nhiên mọi lộ trình có thể có
Trên thực tế, với các kỹ thuật tối ưu hóa tiên tiến, vẫn có thể giải được những bài toán có rất nhiều điểm
Với korea81998, số lộ trình khả dĩ lên tới một con số có 367.308 số 0 đứng sau số 2
Quá trình giải sử dụng kết hợp thuật toán LKH (Lin-Kernighan Heuristic) và Concorde TSP Solver - phương pháp mặt phẳng cắt

Tóm tắt khái niệm phương pháp mặt phẳng cắt

Dựa trên quy hoạch tuyến tính
Thay vì biểu diễn việc có dùng một con đường hay không, phương pháp này biểu diễn mức độ kết nối bằng giá trị số từ 0 đến 1
Bằng cách bổ sung các ràng buộc theo từng bước, có thể tìm ra lộ trình ngắn nhất
Có thể xem giải thích chi tiết hơn trong Scientific American và bài giảng trên YouTube

Bài toán P và NP

Bài toán TSP là một bài toán NP-đầy đủ, là ví dụ tiêu biểu trong vấn đề P và NP
Những thảo luận thú vị liên quan được giới thiệu trong bài viết của Giáo sư Lance Fortnow
Đây là một trong những bài toán chưa có lời giải nổi tiếng nhất của khoa học máy tính

Ý nghĩa của tối ưu hóa toán học

Dự án này vừa là một thử nghiệm, vừa là nền tảng để phát triển các phương pháp tối ưu hóa tổng quát
Tiềm năng ứng dụng rất cao trong các lĩnh vực công nghiệp, thương mại, y học và môi trường
Mô hình hóa toán học là công cụ quan trọng để sử dụng hiệu quả các nguồn lực hữu hạn

Giới thiệu nhóm nghiên cứu

William Cook: Đại học Waterloo, Canada
Daniel Espinoza: Alicanto Labs, Chile
Marcos Goycoolea: Đại học Adolfo Ibáñez, Chile
Keld Helsgaun: Đại học Roskilde, Đan Mạch

Lời cảm ơn

IBM CPLEX Optimizer: cảm ơn vì đã cung cấp miễn phí cho nghiên cứu học thuật
Bản đồ được tạo bằng Leaflet, OpenStreetMap, Carto, Stadia Maps
Tiến sĩ Eom Sang-il đã cung cấp dữ liệu vị trí quán rượu ở Hàn Quốc dựa trên dữ liệu của Cơ quan Cảnh sát Quốc gia Hàn Quốc
Việc tính thời gian đi bộ sử dụng OSRM

Các dự án TSP ở những quốc gia khác

Nhật Bản: 40.426 cửa hàng tiện lợi
Vương quốc Anh: 49.687 quán rượu
Hoa Kỳ: 49.603 địa điểm lịch sử
Hà Lan: 57.912 di tích

Tài liệu học thêm

In Pursuit of the Traveling Salesman: lịch sử và ứng dụng của TSP
Traveling Salesman Problem: nghiên cứu áp dụng phương pháp mặt phẳng cắt
The Golden Ticket: giới thiệu vấn đề P vs. NP
Opt Art: tạo ảnh nghệ thuật bằng TSP
Approximation Algorithms: nghiên cứu mới nhất về thuật toán xấp xỉ cho TSP
Computational Solutions for TSP Applications: sách về các trường hợp ứng dụng, xuất bản năm 1994

10 bình luận

ep6tri 2025-04-24

Trang tiếng Anh là https://www.math.uwaterloo.ca/tsp/korea/index.html.

Chuyến đi này rõ ràng là khá phi thực tế. Có vẻ họ không tính đến các tuyến đường biển đi bằng phà khi di chuyển từ đất liền ra Jeju hay Ulleungdo. Bạn chỉ cần xem hình này là hiểu: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png

Mục tiêu có lẽ không phải là tính thật chính xác thời gian dự kiến cần cho việc ghé thăm, mà là ý nghĩa của việc đã giải bài toán TSP bằng dữ liệu thực tế.

skshin 2025-04-23

Di chuyển ra các đảo thì sao? Cũng đi bộ à?

halfenif 2025-04-23

Thấy ghi là walking and ferry. Có vẻ là đi bằng tàu.

woalsdnd 2025-04-23

Còn những trường hợp quán mở mới và đóng cửa theo thời gian thực thì nên xử lý thế nào?

majorika 2025-04-23

> Tôi dự kiến giảng dạy một khóa về TSP tại KAIST ở Daejeon vào tháng 3 năm 2024, và đang tìm một bộ dữ liệu địa phương cho chuyến TSP tour ở Daejeon. Vào tháng 12 năm 2023, tiến sĩ Eom Sang-il đã gửi email cho tôi: “Bạn có cần bộ dữ liệu toàn quốc về các quán rượu do Cơ quan Cảnh sát Quốc gia tạo ra không? Tệp mới nhất có giá 1.000 won và có 90.680 mục.” Wow. Sau khi kiểm tra trước xem 1.000 won có thực sự ít hơn 1 đô la hay không (rất may là tỷ giá không bị đảo ngược), tôi đã trả lời: “Cảm ơn!”.

https://www.math.uwaterloo.ca/tsp/korea/sk_data.html

kimjoin2 2025-04-23

Wow, hóa ra là có bối cảnh như vậy. Cảm ơn bạn đã tổng hợp và chia sẻ.

kimjoin2 2025-04-23

Mình cũng tò mò vì sao lại chọn Hàn Quốc 👀

firea32 2025-04-28

Việc có thể có được dữ liệu chất lượng với giá 1.000 won chắc hẳn cũng góp phần vào đó :)