- Profesor William Cook dari University of Waterloo menghitung kasus pertama di dunia dari masalah salesman keliling (TSP) untuk rute terpendek yang mengunjungi 81.998 bar di Korea
- Dengan menggunakan Open Source Routing Machine (OSRM), dihitung sekitar 3,3 miliar pasangan waktu tempuh jalan kaki, dan dibuktikan optimal secara matematis
- Hasil perhitungan menunjukkan bahwa jika berjalan tanpa henti, total waktu yang dibutuhkan adalah 15.386.177 detik, yaitu 178 hari 1 jam 56 menit 17 detik
- Alat LKH dan Concorde digunakan untuk optimasi TSP, dengan penerapan metode cutting plane
- Ini merupakan kasus penyelesaian TSP berbasis jalan terbesar di dunia, melampaui rute Belanda dengan 57.912 titik yang sebelumnya memegang rekor
Masalah Salesman Keliling (Traveling Salesman Problem) untuk Berjalan ke Semua Bar di Korea
- Dihitung rute terpendek untuk mengunjungi semua 81.998 bar di Korea dan kembali ke titik awal
- Untuk pertama kalinya di dunia, masalah TSP dengan jumlah lokasi sebesar ini berhasil diselesaikan secara optimal
- Waktu tempuh jalan kaki untuk total 3.361.795.003 pasangan antarbar dihitung dengan OSRM - Open Source Routing Machine
- Secara matematis, tidak ada rute yang lebih pendek daripada rute ini
- Berdasarkan jumlah titik kunjungan, ini adalah masalah TSP terbesar sepanjang sejarah
Waktu yang Dibutuhkan untuk Rute Terpendek
- Jika mengikuti rute optimal yang dihitung dan berjalan tanpa henti, total waktu yang dibutuhkan adalah 15.386.177 detik
- Itu setara dengan 178 hari 1 jam 56 menit 17 detik
- Dalam praktiknya, akan sulit menyelesaikannya tepat seperti itu karena orang tentu akan beristirahat atau minum saat berjalan
- Berdasarkan waktu jalan kaki dari OSRM, ini adalah rute optimal yang tidak bisa dipersingkat bahkan 1 detik pun
Konteks Historis TSP dan Rekor Baru
- Rekor terbesar sebelumnya adalah rute sepeda di Belanda dengan 57.912 titik
- Rute korea81998 kali ini adalah contoh penyelesaian masalah TSP dengan skala yang lebih besar
- Perhitungan dilakukan di Roskilde University dan University of Waterloo dari Desember 2024 hingga Maret 2025
- Detail perhitungan dapat dilihat pada halaman perhitungan terpisah
Cara Visualisasi Rute
- Rute dapat dilihat melalui peta interaktif, dan dijelajahi dengan membaginya ke dalam 7 wilayah
- Tersedia berbagai mode visualisasi (peta jarak berwarna, grayscale, dan lain-lain)
- Beberapa gambar resolusi tinggi dari bagian rute juga disediakan secara terpisah
- Tampilan close-up per kota tersedia di halaman kota
Strategi Penyelesaian TSP dan Kesalahpahaman
- Sejumlah media memberitakan bahwa bahkan untuk “22 kota saja butuh 1000 tahun”, tetapi itu mengacu pada kasus mencoba semua rute secara acak
- Dalam kenyataannya, banyak titik tetap dapat diselesaikan dengan teknik optimasi tingkat lanjut
- Untuk
korea81998, jumlah rute yang mungkin mencapai angka 2 dengan 367.308 nol di belakangnya
- Penyelesaiannya menggunakan gabungan algoritme LKH (Lin-Kernighan Heuristic) dan Concorde TSP Solver - metode cutting plane
Ringkasan Konsep Metode Cutting Plane
- Berbasis pada pemrograman linear
- Alih-alih apakah sebuah jalan dipakai atau tidak, tingkat keterhubungan dinyatakan sebagai nilai antara 0 hingga 1
- Dengan menambahkan syarat pembatas secara bertahap, metode ini menemukan rute terpendek
- Penjelasan lebih rinci tersedia di Scientific American dan kuliah YouTube
Masalah P vs NP
- Masalah TSP adalah masalah NP-lengkap, contoh representatif dari persoalan P dan NP
- Diskusi menarik terkait hal ini diperkenalkan dalam makalah Profesor Lance Fortnow
- Ini adalah salah satu masalah tak terpecahkan paling terkenal dalam ilmu komputer
Makna Optimasi Matematis
- Proyek ini adalah eksperimen dalam metode optimasi umum sekaligus landasan untuk pengembangannya
- Potensi penerapannya tinggi di bidang industri, komersial, medis, dan lingkungan
- Pemodelan matematis adalah alat penting untuk menggunakan sumber daya yang terbatas secara efektif
Perkenalan Tim Peneliti
- William Cook: University of Waterloo, Kanada
- Daniel Espinoza: Alicanto Labs, Cile
- Marcos Goycoolea: Universidad Adolfo Ibáñez, Cile
- Keld Helsgaun: Roskilde University, Denmark
Ucapan Terima Kasih
- IBM CPLEX Optimizer: terima kasih atas penyediaan gratis untuk riset akademik
- Peta dibuat menggunakan Leaflet, OpenStreetMap, Carto, dan Stadia Maps
- Dr. Eom Sang-il menyediakan data lokasi bar di Korea berdasarkan data dari Badan Kepolisian Nasional Korea
- Perhitungan waktu jalan kaki memanfaatkan OSRM
Contoh Proyek TSP di Negara Lain
- Jepang: 40.426 minimarket
- Inggris: 49.687 pub
- Amerika Serikat: 49.603 lokasi bersejarah
- Belanda: 57.912 monumen
Materi Pembelajaran Tambahan
10 komentar
Halaman bahasa Inggrisnya ada di https://www.math.uwaterloo.ca/tsp/korea/index.html.
Tur ini jelas sangat tidak realistis. Sepertinya rute laut dengan kapal saat berpindah dari daratan ke Jeju atau Ulleungdo tidak diperhitungkan. Lihat saja gambar ini: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png
Tujuannya bukan menghitung secara akurat estimasi waktu yang dibutuhkan untuk berkunjung, melainkan menekankan makna bahwa TSP diterapkan pada data dunia nyata.
Bagaimana dengan perpindahan ke pulau? Jalan kaki juga?
Melihat tertulis
walking and ferry, sepertinya memang naik feri.Bagaimana dengan kasus yang muncul dan tutup secara real-time?
> Pada Maret 2024 saya dijadwalkan mengajar kuliah TSP di KAIST yang berlokasi di Daejeon, dan saya sedang mencari set data lokal untuk tur TSP Daejeon. Pada Desember 2023, Dr. Sang-il Oum mengirim email, "Apakah Anda memerlukan set data bar nasional yang dibuat oleh Kepolisian Nasional? File terbarunya berharga 1.000 won dan berisi 90.680 entri." Wah. Setelah terlebih dahulu memeriksa apakah 1.000 won lebih kecil dari 1 dolar (ada baiknya memastikan nilai tukarnya tidak terbalik), saya membalas, "Terima kasih!"
https://www.math.uwaterloo.ca/tsp/korea/sk_data.html
Wow, ternyata ada latar belakang seperti ini. Terima kasih sudah merangkum dan membagikannya.
Saya juga penasaran kenapa memilih Korea 👀
Fakta bahwa data berkualitas bisa didapat dengan 1000 won mungkin juga berperan :)
> Saya dijadwalkan memberikan kuliah TSP di KAIST yang berlokasi di Daejeon pada Maret 2024, dan sedang mencari dataset lokal untuk tur TSP Daejeon.
Mungkin saya mencari informasi terkait karena saya akan memberikan ceramah di Korea.
Apakah dijadikan topik karena bar di Korea terlalu banyak..