Kore'deki 81.998 barı dolaşan en kısa yürüyüş rotası

• Gezgin satıcı problemi (TSP), Kore'deki 81.998 barı ziyaret eden en kısa rotayı bulma problemi olup, Open Source Routing Machine (OSRM) kullanılarak çözüldü
• Bu rota, 178 günden uzun süren optimal rota olup, OSRM hesaplamalarıyla kanıtlandı
• LKH kodu ve Concorde kodu kullanılarak cutting-plane method uygulandı ve büyük ölçekli TSP problemi çözüldü
• Matematiksel optimizasyon ve operasyon araştırması, kaynak verimliliğini artırmaya yönelik araçlar geliştirmeye odaklanıyor
• Araştırma Roskilde University ve University of Waterloo'da yürütüldü; IBM CPLEX Optimizer ve Leaflet kütüphanesi kullanıldı

---

Kore'deki 81.998 barı ziyaret eden en kısa rota

• Gezgin satıcı problemi (TSP), Kore'deki 81.998 barı ziyaret eden en kısa rotayı bulma problemi olup, Open Source Routing Machine (OSRM) kullanılarak çözüldü
• Bu rota, 178 günden uzun süren optimal rota olup, OSRM hesaplamalarıyla kanıtlandı
• LKH kodu ve Concorde kodu kullanılarak cutting-plane method uygulandı ve büyük ölçekli TSP problemi çözüldü

Büyük ölçekli TSP problemini çözmek

• Matematiksel optimizasyon ve operasyon araştırması, kaynak verimliliğini artırmaya yönelik araçlar geliştirmeye odaklanıyor
• Araştırma Roskilde University ve University of Waterloo'da yürütüldü; IBM CPLEX Optimizer ve Leaflet kütüphanesi kullanıldı

Araştırma ekibi ve teşekkürler

• Araştırma ekibi William Cook, Daniel Espinoza, Marcos Goycoolea, Keld Helsgaun'dan oluşuyor
• Araştırma, IBM'in CPLEX Optimizer'ı ve Leaflet kütüphanesi kullanılarak yürütüldü
• Kore'deki barların konumları, Kore Ulusal Polis Teşkilatı veritabanı üzerinden elde edildi

[xguru]

Kore'nin 81.998 barının tamamını dolaşan en kısa yürüme rotası 178 gün yazısını Hacker News'e GeekNews hesabıyla paylaşmıştım.
Çok oy alınca 6 saat boyunca zirvede kaldı, ardından popüler bir yazı oldu ve tekrar GN+'a ithal edilmiş(?) oldu.

İlgili yazının İngilizce sürümü de olduğu için böyle denedim; zaman zaman İngilizce içeren yazıları Hacker News tarafına da göndermeyi düşünüyorum.

[GN⁺]

Hacker News görüşleri

• 133 milyon yıldız içeren TSP çözümü etkileyici
  • Söz konusu tur, en kısa yolun 1.0038 katı uzunluğunda
  • Bell Labs'in olasılıksal algoritması kullanılırsa sonucun ne kadar kötü olacağını merak ediyorum
• Klasik TSP yaklaşımının açıklaması
  • Tüm düğümleri rastgele bir yolla bağla
  • Yolu iki yerden kesip üç parçaya ayır
  • Üç parçayı olası altı farklı şekilde yeniden düzenle ve en kısasını seç
  • İyileşme kalmayana kadar 2-3. adımları tekrarla
  • En iyi sonucu garanti etmez ama çoğu gerçek problemde optimumdur ya da ona çok yakındır
• Toplam mesafeden bahsetmemeleri garip
  • Amaç seyahat süresini çözmek olsa da gerçek seyahat mesafesini bilmek de ilginç olurdu
  • Harcanan kaloriyi hesaplayabilir veya en kısa mesafe rotasından ne kadar sapıldığını görebilirdik
• Ohio büyüklüğünde bir ülkede neredeyse 82 bin bar olması fikri karşısında afalladım
• COVID döneminde CityStrides kullanarak kasabamdaki tüm sokakları yürümeyi hedeflemiştim
  • Yürüdüğün mesafeyi takip ediyor ve kasabanın yüzde kaçını yürüdüğünü gösteriyor
  • Rotayı optimize etmiyordu ama tekrar etmeden mümkün olduğunca çok yol yürümek eğlenceli bir zihinsel bulmacaydı
  • Otomasyon araçları da eğlenceli olabilir ama bunu elle yapmak yolculuğun bir parçasıydı
  • CityStrides sitesinde dolaşırken insanların LifeMaps'lerini görebilirsin
  • Bazı insanlar inanılmaz miktarda yürüyor
• 60'larda İrlanda ordusunda sorulan bir soruyu hatırlattı
  • "Bachelor's Walk'tan Collins Barracks'a, bir barın önünden geçmeden nasıl gidersin?"
  • Cevap "Tüm barlara girerek" idi
• Bu veri setini bulmuş olmaları etkileyici ama daha zor değil
  • Son gezgin satıcı rekorunu kırmakla hesabı bitirememek arasında ince bir denge var
• NP yine P gibi görünmeye başladı
  • Okulda en fazla 13 olduğunu öğrenmiştim, 80'lerde profesörüm bunun 15'e çıktığını söylemişti
  • Sonra 20, 20.000 ve şimdi de 80.000'in kanıtlandığını gördük
  • World TSP sayfasında rekor 1 milyon
  • Şu anda kanıtlanmış en büyük optimum değer 3,178,031
  • Bunu sıradan C ile değil, CUDA ile yapmak lazım
• Branch-and-bound "kitaptan çıkmış" bir algoritma
  • LP çözücüyü bir kara kutu olarak görürsen temelde çok basit ama çok kullanışlı
• Görünüşe göre birkaç yeni bar açılmış, bazıları da kapanmış
  • Yeniden hesaplama zamanı