Lộ trình đi bộ ngắn nhất để ghé thăm 81.998 quán bar ở Hàn Quốc

• Bài toán người bán hàng du lịch (TSP) là bài toán tìm lộ trình ngắn nhất để ghé thăm 81.998 quán bar ở Hàn Quốc, và đã được giải bằng Open Source Routing Machine (OSRM)
• Lộ trình này là lộ trình tối ưu kéo dài hơn 178 ngày, và đã được chứng minh thông qua phép tính của OSRM
• Sử dụng mã LKH và mã Concorde để áp dụng cutting-plane method, qua đó giải quyết bài toán TSP quy mô lớn
• Tối ưu hóa toán học và nghiên cứu vận hành tập trung vào việc phát triển các công cụ nhằm nâng cao hiệu quả sử dụng tài nguyên
• Nghiên cứu được thực hiện tại Roskilde University và University of Waterloo, sử dụng IBM CPLEX Optimizer và thư viện Leaflet

---

Lộ trình ngắn nhất để ghé thăm 81.998 quán bar ở Hàn Quốc

• Bài toán người bán hàng du lịch (TSP) là bài toán tìm lộ trình ngắn nhất để ghé thăm 81.998 quán bar ở Hàn Quốc, và đã được giải bằng Open Source Routing Machine (OSRM)
• Lộ trình này là lộ trình tối ưu kéo dài hơn 178 ngày, và đã được chứng minh thông qua phép tính của OSRM
• Sử dụng mã LKH và mã Concorde để áp dụng cutting-plane method, qua đó giải quyết bài toán TSP quy mô lớn

Giải bài toán TSP quy mô lớn

• Tối ưu hóa toán học và nghiên cứu vận hành tập trung vào việc phát triển các công cụ nhằm nâng cao hiệu quả sử dụng tài nguyên
• Nghiên cứu được thực hiện tại Roskilde University và University of Waterloo, sử dụng IBM CPLEX Optimizer và thư viện Leaflet

Nhóm nghiên cứu và lời cảm ơn

• Nhóm nghiên cứu gồm William Cook, Daniel Espinoza, Marcos Goycoolea và Keld Helsgaun
• Nghiên cứu được thực hiện với CPLEX Optimizer của IBM và thư viện Leaflet
• Vị trí các quán bar ở Hàn Quốc được xác định thông qua cơ sở dữ liệu của Cơ quan Cảnh sát Quốc gia Hàn Quốc

[xguru]

Tôi đã đăng bài Lộ trình đi bộ ngắn nhất để ghé qua toàn bộ 81.998 quán rượu ở Hàn Quốc là 178 ngày lên Hacker News bằng tài khoản GeekNews.
Bài nhận được rất nhiều phiếu bầu, giữ vị trí top trong 6 giờ rồi trở thành bài nổi bật, nên lại được nhập khẩu(?) về GN+.

Vì bài đó cũng có sẵn bản tiếng Anh nên tôi đã thử làm vậy, và thỉnh thoảng những bài có kèm tiếng Anh như thế này tôi sẽ thử đăng lên phía Hacker News.

[GN⁺]

Ý kiến trên Hacker News

• Ấn tượng với lời giải TSP bao gồm 133 triệu cạnh
  • Hành trình đó dài gấp 1.0038 lần đường đi ngắn nhất
  • Tò mò nếu dùng thuật toán xác suất của Bell Labs thì kết quả sẽ tệ đến mức nào
• Giải thích cách tiếp cận TSP cổ điển
  • Nối tất cả các nút thành một lộ trình ngẫu nhiên
  • Cắt lộ trình ở hai chỗ để tạo thành ba phần
  • Sắp xếp lại ba phần theo sáu cách có thể và chọn cách ngắn nhất
  • Lặp lại bước 2-3 cho đến khi không còn cải thiện
  • Không đảm bảo kết quả tối ưu, nhưng với hầu hết bài toán thực tế thì ra kết quả tối ưu hoặc rất gần tối ưu
• Việc không nhắc đến tổng quãng đường có vẻ lạ
  • Mục tiêu là giải quyết thời gian di chuyển, nhưng biết quãng đường thực tế cũng sẽ thú vị
  • Có thể tính lượng calo tiêu hao hoặc kiểm tra đã lệch bao xa khỏi lộ trình ngắn nhất
• Choáng ngợp khi nghĩ rằng một đất nước cỡ Ohio lại có gần 82 nghìn quán bar
• Trong thời kỳ COVID, đã đặt mục tiêu đi bộ qua mọi con đường trong thị trấn bằng CityStrides
  • Nó theo dõi quãng đường đã đi và cho biết đã đi được bao nhiêu phần trăm thị trấn
  • Dù không tối ưu hóa lộ trình, việc đi được nhiều nhất có thể mà không lặp lại vẫn là một bài toán tinh thần thú vị
  • Công cụ tự động hóa cũng có thể vui, nhưng làm thủ công là một phần của hành trình
  • Có thể xem LifeMaps của mọi người khi khám phá trang CityStrides
  • Một số người đi bộ với khối lượng đáng kinh ngạc
• Gợi nhớ đến câu hỏi mà quân đội Ireland từng hỏi vào thập niên 60
  • "Làm sao đi từ Bachelor's Walk đến Collins Barracks mà không đi ngang qua quán bar nào?"
  • Đáp án là "ghé vào tất cả các quán bar"
• Việc tìm ra bộ dữ liệu này rất ấn tượng, nhưng không hẳn khó hơn
  • Đó là sự cân bằng mong manh giữa việc phá kỷ lục tốt nhất cuối cùng của người bán hàng rong và việc không thể hoàn tất phép tính
• NP lại trông giống P
  • Hồi đi học tôi được dạy rằng 13 là mức tối đa, rồi đến thập niên 80 giáo sư nâng lên 15
  • Sau đó là 20, 20.000, và lần này đã chứng minh được 80.000
  • Trang World TSP ghi nhận kỷ lục là 1 triệu
  • Giá trị tối ưu đã được chứng minh lớn nhất hiện nay là 3.178.031
  • Phải làm bằng CUDA chứ không thể bằng C thông thường
• Branch-and-bound là thuật toán đúng kiểu "trong sách giáo khoa"
  • Nếu xem LP solver như một hộp đen thì về cơ bản nó rất đơn giản nhưng cực kỳ hữu ích
• Có vẻ vài quán bar mới đã mở và vài quán khác đã đóng
  • Đến lúc tính lại rồi