- Waterloo Üniversitesi'nden Prof. William Cook, 81.998 barı ziyaret eden en kısa rotaya yönelik gezgin satıcı problemi (TSP) hesabını dünyanın ilk örneği olarak gerçekleştirdi
- Open Source Routing Machine (OSRM) kullanılarak yaklaşık 3,3 milyar çift için yürüme süreleri hesaplandı ve sonucun matematiksel olarak optimal olduğu kanıtlandı
- Hesaplama sonucuna göre hiç durmadan yüründüğünde toplam 15.386.177 saniye, yani 178 gün 1 saat 56 dakika 17 saniye sürüyor
- TSP optimizasyonunda LKH ve Concorde araçları kullanıldı, ayrıca cutting-plane yöntemi uygulandı
- Daha önceki en büyük ziyaret rotası olan Hollanda'daki 57.912 duraklı rotayı aşan, dünya çapında en büyük yol tabanlı TSP çözüm örneği oldu
Kore'deki tüm barları yürüyerek dolaşma gezgin satıcı problemi (Traveling Salesman Problem)
- Kore'deki 81.998 barın tamamını ziyaret edip başlangıç noktasına geri dönen en kısa rota hesaplandı
- Dünyada ilk kez, bu kadar çok noktayı içeren bir TSP problemi optimal olarak çözüldü
- Barlar arasındaki toplam 3.361.795.003 çift için yürüme süreleri OSRM - Open Source Routing Machine ile hesaplandı
- Matematiksel olarak bu rotadan daha kısa bir rota yok
- Bu problem, ziyaret noktası sayısı bakımından TSP tarihinde bugüne kadarki en büyük ölçekli örnek
En kısa rotanın süresi
- Hesaplanan optimal rotada hiç durmadan yürünürse toplam 15.386.177 saniye gerekiyor
- Bu da 178 gün 1 saat 56 dakika 17 saniye anlamına geliyor
- Gerçekte yürürken dinlenmek veya bir şeyler içmek gerekeceğinden tam olarak bu sürede bitirmek zor
- OSRM tabanlı yürüme süresi ölçümüne göre 1 saniye bile kısaltılamayan optimal rota
TSP'nin tarihsel bağlamı ve kırılan rekor
- Önceki en büyük rekor, Hollanda'da 57.912 noktalı bisiklet rotasıydı
- Bu kezki korea81998 rotası, ondan daha büyük ölçekli bir TSP çözüm örneği
- Hesaplama, 2024 Aralık ile 2025 Mart arasında Roskilde Üniversitesi ve Waterloo Üniversitesi'nde yapıldı
- Ayrıntılı hesaplama içeriği ayrı bir hesaplama sayfasında görülebilir
Rotayı görselleştirme yöntemi
- Rota etkileşimli harita üzerinden görülebiliyor ve 7 bölgeye ayrılarak incelenebiliyor
- Farklı görselleştirme modları (renkli mesafe haritası, gri tonlama vb.) sunuluyor
- Rotanın bazı yüksek çözünürlüklü görselleri ayrıca sağlanıyor
- Şehir bazlı yakın plan görünüm şehir sayfasında sunuluyor
TSP çözüm stratejisi ve yanlış anlamalar
- Bazı medya organları, "yalnızca 22 şehir için bile 1000 yıl gerekir" diye haber yapıyor; ancak bu, tüm rotaları rastgele deneme durumunu ifade ediyor
- Gerçekte gelişmiş optimizasyon teknikleriyle çok sayıda nokta da çözülebiliyor
korea81998 için mümkün rota sayısı, 2'nin ardından 367.308 sıfır gelen bir sayı düzeyinde- Çözümde LKH(Lin-Kernighan Heuristic) algoritması ile Concorde TSP Solver - cutting-plane yöntemi birlikte kullanıldı
Cutting-plane yönteminin kısa özeti
- Doğrusal programlamayı temel alır
- Bir yolun kullanılıp kullanılmadığı yerine bağlantı derecesini 0 ile 1 arasında bir değerle ifade eder
- Aşama aşama kısıtlar ekleyerek en kısa rotayı bulur
- Ayrıntılı açıklama Scientific American ve YouTube konferansında görülebilir
P ve NP problemi
- TSP, NP-tam problem olup P ve NP sorusunun en bilinen örneklerinden biri
- Konuyla ilgili ilgi çekici tartışmalar Prof. Lance Fortnow'un makalesinde yer alıyor
- Bu soru, bilgisayar biliminin en ünlü çözülememiş problemlerinden biri
Matematiksel optimizasyonun anlamı
- Bu proje, genel amaçlı optimizasyon yöntemlerinin bir deneyi ve geliştirilmesi için temel niteliğinde
- Sanayi, ticaret, tıp ve çevre alanlarında uygulama potansiyeli yüksek
- Matematiksel modelleme, sınırlı kaynakların etkili kullanımı için önemli bir araç
Araştırma ekibi
- William Cook: Kanada, Waterloo Üniversitesi
- Daniel Espinoza: Şili, Alicanto Labs
- Marcos Goycoolea: Şili, Adolfo Ibáñez Üniversitesi
- Keld Helsgaun: Danimarka, Roskilde Üniversitesi
Teşekkür
- IBM CPLEX Optimizer: ücretsiz akademik araştırma kullanımı sağladığı için teşekkür edildi
- Haritalar Leaflet, OpenStreetMap, Carto, Stadia Maps ile oluşturuldu
- Dr. Eom Sang-il, Kore Ulusal Polis Ajansı verilerine dayalı bar konumu verilerini sağladı
- Yürüme süresi hesaplamalarında OSRM kullanıldı
Diğer ülkelerdeki TSP proje örnekleri
- Japonya: 40.426 market
- Birleşik Krallık: 49.687 bar
- ABD: 49.603 tarihî mekân
- Hollanda: 57.912 anıt
Ek öğrenme kaynakları
10 yorum
İngilizce sayfa: https://www.math.uwaterloo.ca/tsp/korea/index.html
Turun kesinlikle gerçekçi olmadığı açık. Anakaradan Jeju Adası ya da Ulleungdo'ya geçerken gemiyle kullanılan deniz rotalarının hesaba katılmadığı anlaşılıyor. Şu görsele bakmanız yeterli: https://www.math.uwaterloo.ca/tsp/korea/img/full_line.png
Amacın ziyaret için gereken tahmini süreyi tam olarak hesaplamak değil, TSP'nin gerçek dünyadaki verilerle çözülmüş olmasına anlam yüklemek olduğunu söylemek gerekir.
Adalar arası geçiş nasıl olacak? Yürüyerek mi?
"walking and ferry" yazdığına bakılırsa galiba feribotla gidiyorlar.
Gerçek zamanlı olarak açılan ve kapanan yerler için ne yapmak gerekir?
> Mart 2024'te Daejeon'daki KAIST'ta TSP dersi vermem planlanmıştı ve Daejeon TSP turu için yerel bir veri seti arıyordum. Aralık 2023'te Dr. Sang-il Eom bana şu e-postayı gönderdi: "Ulusal Polis Ajansı'nın hazırladığı ülke çapındaki içki mekânları veri setine mi ihtiyacınız var? En güncel dosya 1.000 won ve 90.680 kayıt içeriyor." Vay canına. Önce 1.000 wonun 1 dolardan daha az olup olmadığını kontrol ettikten sonra (kurun ters dönmediğinden emin olmak iyi oldu), "Teşekkürler!" diye yanıt verdim.
https://www.math.uwaterloo.ca/tsp/korea/sk_data.html
Vay canına, demek böyle bir arka planı varmış. Derleyip paylaştığınız için teşekkürler.
Neden hedef olarak Kore'nin seçildiğini de merak ediyorum 👀
1000 won karşılığında kaliteli veri elde edilebilmesi de bunda pay sahibi olmuştur :)
> 2024 Mart'ında Daejeon'daki KAIST'te TSP dersi vermem planlanmıştı ve Daejeon TSP turu için yerel bir veri seti arıyordum.
Muhtemelen Kore'de konuşma yapacak olmam nedeniyle ilgili bilgileri arıyordum diye düşünüyorum.
Kore'de bar çok diye mi bunu konu seçmişler..