Rute jalan kaki terpendek untuk mengunjungi 81.998 bar di Korea

• Masalah Traveling Salesman (TSP) adalah persoalan mencari rute terpendek untuk mengunjungi 81.998 bar di Korea, dan diselesaikan menggunakan Open Source Routing Machine (OSRM)
• Rute ini merupakan rute optimal yang memerlukan waktu lebih dari 178 hari, dan hal ini dibuktikan melalui perhitungan OSRM
• Dengan menggunakan kode LKH dan kode Concorde, diterapkan cutting-plane method untuk menyelesaikan masalah TSP berskala besar
• Optimisasi matematis dan riset operasi berfokus pada pengembangan alat untuk meningkatkan efisiensi sumber daya
• Penelitian ini dilakukan di Roskilde University dan University of Waterloo, dengan menggunakan IBM CPLEX Optimizer dan pustaka Leaflet

---

Rute terpendek untuk mengunjungi 81.998 bar di Korea

• Masalah Traveling Salesman (TSP) adalah persoalan mencari rute terpendek untuk mengunjungi 81.998 bar di Korea, dan diselesaikan menggunakan Open Source Routing Machine (OSRM)
• Rute ini merupakan rute optimal yang memerlukan waktu lebih dari 178 hari, dan hal ini dibuktikan melalui perhitungan OSRM
• Dengan menggunakan kode LKH dan kode Concorde, diterapkan cutting-plane method untuk menyelesaikan masalah TSP berskala besar

Menyelesaikan masalah TSP berskala besar

• Optimisasi matematis dan riset operasi berfokus pada pengembangan alat untuk meningkatkan efisiensi sumber daya
• Penelitian ini dilakukan di Roskilde University dan University of Waterloo, dengan menggunakan IBM CPLEX Optimizer dan pustaka Leaflet

Tim peneliti dan ucapan terima kasih

• Tim peneliti terdiri dari William Cook, Daniel Espinoza, Marcos Goycoolea, dan Keld Helsgaun
• Penelitian dilakukan dengan menggunakan CPLEX Optimizer dari IBM dan pustaka Leaflet
• Lokasi bar di Korea diperoleh melalui basis data Badan Kepolisian Nasional Korea

[xguru]

Saya memposting artikel Rute jalan kaki terpendek untuk mengunjungi semua 81.998 bar di Korea adalah 178 hari ke Hacker News menggunakan akun GeekNews.
Karena mendapat banyak upvote, artikel itu sempat berada di posisi teratas selama 6 jam, lalu menjadi postingan populer dan akhirnya diimpor kembali ke GN+.

Karena artikel tersebut juga tersedia dalam bahasa Inggris, saya mencoba melakukannya, dan ke depannya saya akan sesekali mencoba memposting artikel yang menyertakan versi bahasa Inggris ke Hacker News.

[GN⁺]

Komentar Hacker News

• Solusi TSP yang mencakup 133 juta edge sangat mengesankan
  • Tur tersebut memiliki panjang 1,0038 kali rute terpendek
  • Penasaran seberapa buruk hasilnya jika menggunakan algoritme probabilistik dari Bell Labs
• Penjelasan pendekatan TSP klasik
  • Menghubungkan semua node dengan jalur acak
  • Memotong jalur di dua titik untuk membuat tiga bagian
  • Menyusun ulang tiga bagian itu dalam enam kemungkinan cara dan memilih yang paling pendek
  • Mengulangi langkah 2-3 sampai tidak ada peningkatan lagi
  • Tidak menjamin hasil optimal, tetapi pada sebagian besar masalah dunia nyata hasilnya optimal atau sangat mendekati
• Aneh karena total jaraknya tidak disebutkan
  • Tujuannya memang menyelesaikan waktu tempuh, tetapi mengetahui jarak tempuh sebenarnya juga akan menarik
  • Bisa menghitung kalori yang terbakar atau memeriksa seberapa jauh menyimpang dari rute jarak terpendek
• Terasa luar biasa memikirkan bahwa ada hampir 82 ribu bar di negara sebesar Ohio
• Saat masa COVID, saya memakai CityStrides dengan target berjalan di semua jalan di kota saya
  • Aplikasi itu melacak jarak yang sudah ditempuh dan memberi tahu berapa persen kota yang sudah dijalani
  • Saya tidak mengoptimalkan rute, tetapi mencoba berjalan sejauh mungkin tanpa duplikasi adalah teka-teki mental yang menyenangkan
  • Alat otomatis mungkin juga menyenangkan, tetapi mengerjakannya secara manual adalah bagian dari perjalanannya
  • Saat menjelajahi situs CityStrides, Anda bisa melihat LifeMaps milik orang lain
  • Beberapa orang berjalan dalam jumlah yang luar biasa banyak
• Mengingatkan pada pertanyaan yang dulu ditanyakan di tentara Irlandia pada tahun 60-an
  • "Bagaimana pergi dari Bachelor's Walk ke Collins Barracks tanpa melewati bar?"
  • Jawabannya adalah "masuk ke semua bar"
• Menemukan dataset ini memang mengesankan, tetapi tidak lebih sulit
  • Ini adalah keseimbangan tipis antara memecahkan rekor terbaik traveling salesman terakhir dan tidak pernah berhasil menyelesaikan komputasinya
• NP kembali terlihat seperti P
  • Di sekolah saya belajar bahwa 13 adalah batas maksimum, lalu pada tahun 80-an profesor saya meningkatkannya menjadi 15
  • Setelah itu menjadi 20, 20.000, dan kali ini terbukti 80.000
  • Di halaman World TSP, rekornya adalah 1 juta
  • Nilai optimal terbukti terbesar saat ini adalah 3.178.031
  • Harus pakai CUDA, jangan C biasa
• Branch-and-bound adalah algoritme "yang ada di buku"
  • Jika menganggap solver LP sebagai kotak hitam, pada dasarnya ini sangat sederhana tetapi sangat berguna
• Sepertinya ada beberapa bar baru yang buka dan beberapa yang tutup
  • Saatnya menghitung ulang