Gezgin Satıcı Problemi, optimizasyon literatürünün en bilinen ve en zorlu problemlerinden biridir. Klasik biçimiyle problem basit görünür: Bir satıcı belirli şehirlerin her birini tam bir kez ziyaret edecek, sonra başlangıç noktasına dönecek ve toplam mesafeyi en düşük yapacaktır. Ancak şehir sayısı arttıkça olası rota sayısı çok hızlı büyür. Bu yüzden TSP, NP-hard bir problem olarak kabul edilir.

Çalışmanın odağındaki problem ise TSP’nin daha zor bir sürümü olan Asymmetric Traveling Salesman Problem, yani ATSPdir. Klasik simetrik TSP’de iki şehir arasındaki mesafe her iki yönde aynıdır. ATSP’de ise yön önemlidir. A’dan B’ye gitmenin maliyeti ile B’den A’ya gitmenin maliyeti farklı olabilir. Bu fark gerçek dünyada çok yaygındır. Tek yönlü yollar, trafik yoğunluğu, rüzgâr yönü, zaman pencereleri, teleskopların gökyüzündeki hedeflere erişim sırası, DNA parçalarının yön bağımlı örtüşmeleri veya üretim hatlarında işlem sıraları asimetrik maliyetler doğurabilir.

Bu nedenle ATSP yalnızca matematiksel bir oyun değildir. Lojistikte teslimat sıralarını, astronomide gözlem planlarını, genomikte dizileme ve montaj süreçlerini, endüstride üretim akışlarını ve büyük ölçekli ağ planlamalarını etkileyen temel bir optimizasyon problemidir. Fakat ATSP’nin yön bağımlılığı, çözüm uzayını daha karmaşık hale getirir. Simetrik TSP için geliştirilmiş bazı yöntemler doğrudan ATSP’ye uygulanamaz veya ciddi uyarlama gerektirir.

Çalışmanın ana problemi şudur: Büyük ölçekli ATSP örnekleri, standart bilgisayarlarda hem hızlı hem de kesin biçimde çözülebilir mi? Buradaki “kesin” ifadesi önemlidir. Birçok sezgisel yöntem hızlı çözüm üretir, ama bu çözümün global optimum olduğu garanti edilmez. Buna karşılık exact MIP çözücüleri teorik olarak optimumu bulabilir, fakat büyük ATSP örneklerinde işlem süresi ve bellek tüketimi hızla büyür. Çalışma, bu iki uç arasında bir köprü kurmayı hedefler: sezgisel hız ile exact solver doğruluğunu aynı mimaride birleştirmek.

Yazarların önerdiği yöntem GTA olarak adlandırılır. GTA, Gurobi Tabu Algorithm ifadesinin kısaltmasıdır. Adından da anlaşılacağı gibi yöntem, ticari ve yaygın bir MIP çözücüsü olan Gurobi ile Tabu Search sezgisini bir araya getirir. Ancak çalışma, bu bileşenleri yalnızca yan yana koyduğunu değil, büyük ölçekli ATSP için stratejik biçimde yeniden düzenlediğini savunur.

GTA’nın merkezinde üçlü bir yapı vardır:

• Tabu Search warm start: Çok kısa sürede iyi bir başlangıç turu üretir. Çalışmada bu başlangıç çözümlerinin genellikle 1%–5% optimality gap aralığında, muhafazakâr olarak 10% altında olduğu belirtilir.
• Gurobi MIP çözümü: Başlangıç turunu kullanarak exact arama yapar ve 0% optimality gap hedefine ulaşmaya çalışır.
• MTZ’siz subtour elimination: Miller–Tucker–Zemlin kısıtları yerine lazy constraint callback kullanılarak alt turlar dinamik biçimde elenir.

Bu üç bileşenin birlikte çalışması önemlidir. Tabu Search tek başına hızlı ama yaklaşık sonuç üretir. Gurobi tek başına büyük ATSP’de soğuk başlangıçla çok uzun sürebilir. MTZ kısıtları ise klasik TSP formülasyonlarında alt turları engellemek için kullanılsa da büyük problemlerde model boyutunu ve çözüm yükünü artırabilir. GTA, iyi bir başlangıç turu vererek Gurobi’nin arama ağacını daraltır; MTZ kısıtlarını kaldırarak modelin yapısını hafifletir; lazy constraints ile yalnızca gerektiğinde subtour kesitleri ekler.

ATSP’nin standart MIP mantığını açıklamak için temel formülasyon şu şekilde düşünülebilir. Bu formül çalışmanın kullandığı MTZ’siz MIP yaklaşımını anlamaya yardımcı olan arka plan anlatımıdır:

\[ \min \sum_{i=1}^{N}\sum_{j=1, j\neq i}^{N} c_{ij}x_{ij} \]

Burada N, düğüm sayısıdır. c_ij, i düğümünden j düğümüne gitmenin maliyetidir. ATSP’de genellikle c_ij ≠ c_ji olabilir. x_ij, i’den j’ye gidilip gidilmediğini gösteren ikili değişkendir. Eğer rota i’den j’ye geçiyorsa [ x_{ij}=1 ], geçmiyorsa [ x_{ij}=0 ] olur.

Her düğümden tam bir çıkış olmasını sağlayan temel derece kısıtı:

\[ \sum_{j=1, j\neq i}^{N} x_{ij} = 1 \quad \forall i \]

Her düğüme tam bir giriş olmasını sağlayan kısıt:

\[ \sum_{i=1, i\neq j}^{N} x_{ij} = 1 \quad \forall j \]

Bu iki kısıt, her düğümün bir kez çıkış ve bir kez giriş almasını sağlar. Ancak bunlar tek başına yeterli değildir. Çünkü çözüm, tüm düğümleri kapsayan tek bir tur yerine birden fazla küçük döngüye, yani subtourlara ayrılabilir. Örneğin 1-2-3-1 ve 4-5-6-4 gibi iki ayrı kapalı rota oluşabilir. TSP/ATSP’nin asıl zorluğu, tüm düğümleri tek bir Hamilton turunda birleştirmektir.

Klasik MTZ yaklaşımı, ek sıralama değişkenleriyle bu alt turları engellemeye çalışır. Ancak büyük ölçeklerde bu ek değişkenler ve kısıtlar çözümü ağırlaştırabilir. Çalışmanın önerdiği yaklaşımda MTZ kısıtları yerine lazy constraint callback kullanılır. Bu mantıkta solver önce derece kısıtlarıyla bir çözüm üretir; eğer çözüm alt turlardan oluşuyorsa, sadece o alt turları kesen yeni kısıtlar sonradan eklenir. Genel subtour elimination mantığı şu arka plan formülle anlatılabilir:

\[ \sum_{i\in S}\sum_{j\in S, j\neq i} x_{ij} \leq |S|-1 \quad \forall S \subset \{1,\ldots,N\},\; 2\leq |S| < N \]

Burada S, tüm düğümlerin yalnızca bir alt kümesidir. Bu kısıt, S kümesi içindeki düğümlerin kendi içinde kapalı küçük bir tur oluşturmasını engeller. Ancak tüm olası S kümeleri için bu kısıtları baştan eklemek pratik değildir. Lazy constraint yaklaşımı tam bu yüzden kullanılır: yalnızca solver’ın bulduğu çözümde gerçekten ortaya çıkan alt turlar kesilir.

Çalışmanın GTA’yı güçlü kıldığını savunduğu nokta budur. MIP çözücü, çok büyük bir çözüm uzayında sıfırdan dolaşmaya başlamaz. Tabu Search önce iyi bir rota verir. Bu rota Gurobi için incumbent yani başlangıç çözümü olur. Eğer incumbent optimuma yakınsa, branch-and-cut araması daha dar bir alanda çalışabilir; kötü dallar daha erken budanabilir; cut generation daha etkili hale gelebilir. Çalışma, warm start kalitesinin bu nedenle kritik olduğunu vurgular.

Yazarlar, zayıf warm start çözümlerinin yarardan çok zarar verebileceğini özellikle belirtir. Çalışmada 10%–15%’ten büyük gap’e sahip başlangıçların MIP çözücüyü yanıltabileceği, hatta soğuk başlangıçtan daha kötü performans üretebileceği ifade edilir. Bunun nedeni, kötü incumbent’ın arama ağacını yanlış yönlendirmesi, daha iyi çözümlerin erken bulunmasını engellemesi ve solver’ın iç sezgilerini baskılamasıdır. Bu nedenle GTA için yalnızca “bir başlangıç çözümü” değil, yapısal olarak tutarlı ve yeterince yakın bir başlangıç turu gerekir.

Çalışmada Tabu Search warm start’ın genellikle saniyeler içinde 1%–9% aralığında gap ürettiği, çoğu durumda 5% altında kaldığı savunulur. Aynı metinde genetik algoritma ve simulated annealing gibi diğer sezgisellerin büyük ATSP örneklerinde 30 dakikayı aşabilen süreler sonunda bile 50%’yi aşan gap’ler verebildiği belirtilir. Bu nedenle yazarlar, GTA mimarisinde Tabu Search seçiminin tesadüfi olmadığını, warm start kalitesi ve hız dengesinden kaynaklandığını savunur.

Çalışmanın performans iddiaları oldukça güçlüdür. Tablo 1’de GTA’nın 5.000 düğümlü ATSP için N^2.01–N^2.03 aralığında ampirik karmaşıklık gösterdiği ve 350–850 saniye içinde 0% optimality gap elde ettiği raporlanır. Buna karşılık warm start olmadan Gurobi lazy-constraint yaklaşımı için N^2.1–N^2.2 ve 3.750–6.750 saniye aralığı verilir. Bu karşılaştırma, GTA’nın yalnızca Gurobi kullanmaktan ibaret olmadığını; warm start ve model tasarımının çalışma süresini ciddi biçimde etkilediğini göstermek için kullanılır.

Ancak burada dikkatli bir bilimsel ayrım yapılmalıdır. Çalışmada verilen N^2.01–N^2.03 davranışı formal bir algoritmik karmaşıklık ispatı değildir. Yazarlar da bunu açıkça belirtir: yakın-kuadratik davranış, farklı düğüm sayıları üzerinde yapılan deneysel çalışma zamanı verilerinin log-log regresyonla modellenmesinden elde edilmiştir. NP-hard ATSP için bu tür ampirik ölçekleme raporları literatürde yaygın olsa da, bunlar matematiksel worst-case karmaşıklık garantisi yerine deneysel benchmark olarak okunmalıdır.

Çalışmanın ilk önemli görsel karşılaştırması, GTA’yı exact ve heuristic çözücülerle konumlandıran runtime grafiğidir. Bu grafikte exact solver kategorisi yeşil, heuristic yöntemler mavi, GTA ise ATSP için çok daha düşük süreyle gösterilir. Metne göre GTA, 5.000 düğümlü ATSP’de yaklaşık 600 saniyelik ortalama çalışma zamanı seviyesinde konumlandırılırken, exact solverlar ve heuristiklerin farklı trade-off’ları olduğu anlatılır. Bu görsel, çalışmanın ana iddiasını sade biçimde sunar: GTA, heuristic hızına yaklaşırken exact optimality yani 0% gap hedefini korumaya çalışır.

Çalışmadaki log-log ve lin-log performans grafikleri, düğüm sayısı arttıkça GTA runtime verilerinin geleneksel exact yöntemlere göre daha düşük eğimli bir ölçekleme gösterdiğini anlatır. Log-log grafikte GTA verileri kırmızı noktalarla, heuristik 50% gap eğrisi ve best-case exact 0% gap eğrisiyle karşılaştırılır. Bu görsel, GTA’nın ampirik olarak yaklaşık [ y = 10^{-5}x^{2.0368} ] çizgisine yakın davranış gösterdiği iddiasını desteklemek için kullanılır. Yine de bu, deneysel veri uydurmasıdır; tüm ATSP örnekleri için teorik garanti değildir.

Çalışmanın kendi Gurobi karşılaştırması da önemlidir. Bir grafikte GTA, lazy constraint kullanan Gurobi ve MTZ tabanlı çözümle karşılaştırılır. GTA eğrisi, hem lazy-only hem de MTZ yaklaşımına göre daha aşağıda kalır. Metin, warm start olmadan Gurobi’nin lazy constraint ile bile bazı durumlarda 24 saati aşabildiğini, MTZ formülasyonunun ise büyük ölçeklerde daha da ağırlaştığını ifade eder. Bu, GTA’daki performansın asıl kaynağının bileşenlerin sinerjisi olduğu iddiasını güçlendirmek için kullanılır.

Çalışmada ağ görselleştirme bölümü de vardır. Düğüm sayısı 10, 100, 1.000 ve 2.000 olduğunda optimal rota haritaları gösterilir. 10 düğümlü örnek kolayca izlenebilirken, 100 düğümde bağlantılar sıklaşır; 1.000 ve 2.000 düğümde rota yoğun bir ağ görünümüne dönüşür. Büyük yeşil ve mavi noktalar başlangıç ve orta yol düğümlerini temsil eder. Bu görseller, TSP/ATSP’nin düğüm sayısıyla nasıl görsel ve yapısal olarak karmaşıklaştığını anlatır.

Bu görselleştirme yalnızca estetik bir ek değildir. Çalışma, rota haritalarının kullanıcıya çözümün uzamsal yapısını, kümelenme davranışını, başlangıç-orta yol ilişkisini ve düğümlerin optimal sıradaki konumunu sezgisel biçimde anlamada yardımcı olduğunu savunur. Lojistik planlama, gözlem çizelgeleme ve biyolojik veri sıralama gibi alanlarda, kullanıcı yalnızca toplam maliyeti değil, rotanın nasıl oluştuğunu da görmek isteyebilir. GTA arayüzünün bu nedenle gerçek zamanlı iterasyon takibi ve rota yoğunluğu görselleştirmesi sunduğu belirtilir.

Çalışmanın bir diğer önemli test grubu, seed değişimiyle ilgilidir. ATSP maliyet matrisi rastgele üretilir ve seed değiştiğinde maliyet katsayıları, dolayısıyla global optimum ve arama alanı değişir. Eğer bir algoritma yalnızca belirli bir seed’de hızlı çalışıyor, başka seed’lerde bozuluyorsa güvenilir sayılmaz. Çalışmada önce S = 42 ve S = 65 seed değerleri, ardından 133, 29 ve 7 seed değerleriyle farklı düğüm sayılarında çalışma süreleri karşılaştırılmıştır.

Seed değişimi sonuçları, GTA’nın çalışma süresinin farklı rastgele maliyet matrislerinde yakın ölçekleme gösterdiğini savunur. Grafiklerde küçük düğüm sayılarında küçük dalgalanmalar görülürken, büyük düğüm sayılarında runtime eğrileri birbirine yaklaşır. Bu bulgu, çalışmada runtime seed-invariance olarak yorumlanır. Yani algoritmanın performansı, rastgele maliyet matrisinin belirli bir özel biçimine bağlı görünmemektedir.

Fakat burada da dikkatli olmak gerekir. Çalışma, farklı seed’lerle rastgele üretilmiş ATSP örneklerinde kararlı performans gösterdiğini savunur; ancak bu, tüm gerçek dünya ATSP örneklerinin aynı kolaylıkla çözüleceği anlamına gelmez. Gerçek uygulamalardaki maliyet matrisleri rastgele ve bağımsız dağılımlı olmayabilir; coğrafi, zamansal, operasyonel veya biyolojik bağımlılıklar taşıyabilir. Dolayısıyla seed dayanıklılığı önemli bir mühendislik göstergesidir, ama gerçek veri benchmarklarının yerini tamamen tutmaz.

Çalışmada maliyet katsayılarının ölçeği de test edilir. Önce maliyetler [1,10] aralığında, sonra [10,100] aralığında üretilir. Yazarlar, bu ölçek değişiminin teorik olarak normalize edilebileceğini kabul eder; ancak pratikte daha büyük katsayı aralıklarının solver davranışını etkileyebileceğini belirtir. Figure 6’da iki aralıktaki runtime eğrileri log-log, log-lin ve lin-lin görünümlerle karşılaştırılır. Çalışmanın yorumu, GTA’nın maliyet katsayısı ölçeğine karşı büyük ölçüde kararlı olduğudur.

Bu sonuç uygulama açısından önemlidir. Gerçek dünyada maliyetler farklı birimlerde olabilir: kilometre, dakika, yakıt, risk skoru, astronomik görünürlük katsayısı, genetik örtüşme puanı veya öncelik ağırlığı. Eğer algoritma belirli bir sayısal aralık için hassassa, her uygulamada özel normalizasyon ve parametre ayarı gerekir. Çalışma, GTA’nın [1,10] ile [10,100] aralıklarında benzer davranış gösterdiğini belirterek bu tür ek ön işlemlere daha az ihtiyaç duyulabileceğini savunur.

Çalışmanın en dikkat çekici iddialarından biri, darboğazın algoritmik karmaşıklıktan RAM’e kaymasıdır. Tartışma bölümünde deneylerin 16 GB RAM’li standart bilgisayarlar üzerinde, GPU veya paralelleştirme olmadan yürütüldüğü belirtilir. Kullanılan sistemlerden biri 4 çekirdek ve 8 logical processor içeren Intel makine; doğrulama için ise 12. nesil i5, 8 çekirdek ve 16 processor yapısıdır. Yazarlar, büyük örneklerde runtime’ın yataya yakın davranmaya başladığını ve artık ana sınırlayıcının RAM/sistem belleği olduğunu savunur.

Bu iddia bilimsel olarak önemlidir, ama dikkatle ifade edilmelidir. ATSP gibi NP-hard bir problemde “algoritmik karmaşıklık ortadan kalktı” demek doğru olmaz. Çalışmanın iddiası daha sınırlı okunmalıdır: GTA’nın mühendislik tasarımı, incelenen rastgele ATSP örneklerinde Gurobi’nin arama uzayını o kadar daraltmaktadır ki pratik darboğaz, belirli büyük N değerlerinde işlem süresinden çok bellek yönetimine kaymaktadır. Bu, worst-case teorik karmaşıklık iddiası değil, deneysel performans gözlemidir.

Sürekli iyileştirme bölümünde, GTA kodundan grafik arayüz katmanının ve diagonal değişkenlerin çıkarılmasıyla çalışma sürelerinde önemli düşüş elde edildiği belirtilir. GUI’nin kodun yaklaşık 30%–35%’ini oluşturduğu, kullanıcı dostu kullanım için önemli olduğu ama RAM gereksinimini artırdığı savunulur. Ayrıca diagonal girişlere büyük M değeri vermek yerine bu değişkenlerin hiç oluşturulmaması önerilir.

Bu nokta mühendislik açısından çok somuttur. N = 2.000 için tam matris yaklaşımı 2.000 × 2.000 = 4.000.000 değişken oluşturabilir. Diagonal değişkenler çıkarıldığında bu sayı 3.998.000 olur. Sayısal fark yalnızca 2.000 gibi görünse de, solver’ın değişken oluşturma, matris saklama, presolve ve bellek yönetimi açısından etkileri daha büyük olabilir. Çalışmada GUI ve diagonal değişkenlerin çıkarılmasıyla ortalama yaklaşık 50% runtime iyileşmesi raporlanır.

Figure 7 bu iyileştirmeyi gösterir. Üst panelde farklı düğüm sayıları için başlangıç GTA süreleri ile GUI/diagonal çıkarılmış sürümün süreleri karşılaştırılır. Alt panelde başlangıç GTA verisi ile optimize edilmiş sürümün runtime eğrileri görülür. Metin, algoritmanın temel iterasyonlarının aynı kaldığını, asıl farkın kod sadeleştirme ve problem formülasyonu optimizasyonundan geldiğini belirtir. Bu da çalışmanın “darboğaz RAM ve problem temsilidir” iddiasını desteklemek için kullanılır.

Çalışmanın uygulama alanları geniş biçimde tartışılır. Lojistikte ATSP, yön bağımlı teslimat ve rota planlama için önemlidir. Astronomide teleskop gözlem sıralaması, gökyüzündeki hedeflerin görünürlük pencereleri, konum kısıtları ve bilimsel öncelik ağırlıklarıyla TSP/ATSP türevlerine dönüşebilir. Genomikte DNA dizileme veya assembly problemleri, yön bağımlı örtüşme ve sıralama yapıları nedeniyle ATSP benzeri optimizasyonlara bağlanabilir. Çalışma, GTA’nın zaman pencereleri, görünürlük ve pozisyon kısıtları gibi varyantlara genişletilebileceğini ifade eder.

Ancak bu uygulama iddiaları da dikkatli ayrılmalıdır. Çalışma, bu alanlardaki tüm gerçek veri problemlerini çözmüş değildir. Bazı varyantların tasarlanmış veya mevcut olduğu belirtilir; bazıları ise gelecekteki uyarlama olarak sunulur. Özellikle multi-agent TSP ve gene overlap sequencing gibi alanlarda GTA’nın doğrudan test edilmediği metinde ifade edilir. Dolayısıyla bu alanlar, kanıtlanmış sonuçlardan çok potansiyel uygulama alanları olarak okunmalıdır.

Çalışmanın güçlü yönlerinden biri, pratik mühendislik ayrıntılarına önem vermesidir. Sadece “yeni bir teorik algoritma” sunmak yerine, solver parametreleri, warm start kalitesi, GUI, diagonal değişkenler, seed değişimi, maliyet ölçekleme, runtime logları ve görselleştirme gibi gerçek kullanımda performansı etkileyen unsurları tartışır. Bu yaklaşım, optimizasyon yazılımlarında çoğu zaman gözden kaçan ama uygulamada belirleyici olan ayrıntılara odaklanır.

Bir diğer güçlü yön, ATSP’nin simetrik TSP’den ayrılmasını sürekli vurgulamasıdır. Literatürde Concorde ve TSPLIB gibi benchmarkların çoğu simetrik TSP için güçlüdür; ancak ATSP tarafında 5.000 düğümlü standart benchmarkların eksik olduğu belirtilir. Çalışma, GTA’yı bu boşluğu dolduran aday bir çerçeve olarak sunar. Özellikle TSPLIB’deki büyük simetrik örneklerle ATSP sonuçlarının doğrudan aynı şey olmadığını vurgulaması metodolojik açıdan yerindedir.

Sınırlılıklar da nettir. Birincisi, çalışma hakemliği metin üzerinden doğrulanamayan bir taslaktır. İkincisi, yakın-kuadratik çalışma zamanı için formal teorik ispat yoktur; sonuç ampirik regresyon temellidir. Üçüncüsü, 5.000 düğümlü ATSP için doğrudan standart dış benchmark eksik olduğundan karşılaştırmalar simetrik TSP benchmarkları veya yazarların kendi Gurobi varyantlarıyla yapılmaktadır. Dördüncüsü, rastgele üretilmiş maliyet matrisleri gerçek endüstriyel, biyolojik veya astronomik veri yapılarının tümünü temsil etmeyebilir.

Beşinci sınırlılık, Gurobi gibi ticari bir solver’a bağımlılıktır. Çalışma Gurobi’yi açık erişim felsefesi ve ATSP’ye uygunluğu nedeniyle tercih ettiğini belirtir; ancak Gurobi lisansı, kullanıcı erişimi ve solver sürüm farkları reprodüksiyonu etkileyebilir. Altıncı olarak, çalışmada “source code and variants are or will be made open-access” ifadesi yer alır; bu, kodun erişilebilirliği ve bağımsız tekrar için kritik bir noktadır. Kod, parametreler ve loglar gerçekten açık biçimde sağlandığında iddiaların doğrulanması daha güçlü hale gelecektir.

Çalışmanın söylediği şey ile söylemediği şey net ayrılmalıdır. Çalışma, GTA’nın büyük rastgele ATSP örneklerinde standart donanım üzerinde 0% gap’e hızlı ulaştığını raporlar. Tabu Search warm start, Gurobi MIP ve lazy subtour elimination birleşiminin güçlü bir mühendislik sinerjisi oluşturduğunu savunur. Ancak çalışma, ATSP’nin worst-case NP-hard zorluğunu ortadan kaldırdığını teorik olarak kanıtlamaz. Tüm gerçek dünya ATSP örneklerinde aynı süreleri garanti etmez. Gurobi’den bağımsız, solver-agnostic bir algoritma sunduğunu da söylemez. En doğru okuma şudur: GTA, büyük ölçekli ATSP için pratik, deterministik, mühendislik odaklı ve güçlü performans iddiaları olan bir hibrit çözüm çerçevesidir; bu iddiaların değeri bağımsız tekrarlanabilirlik ve gerçek veri benchmarklarıyla daha da netleşecektir.

Çalışmanın Yöntemi ve Bulguları

Çalışmanın yöntemi; rastgele asimetrik maliyet matrisleri üretme, Tabu Search ile yüksek kaliteli warm start oluşturma, MTZ’siz Gurobi MIP modeli kurma, lazy constraint callback ile subtour elimination uygulama, runtime/optimality gap/iteration/node metadata kaydetme ve farklı seed, maliyet ölçeği, problem boyutu ve kod sadeleştirme koşullarında performansı karşılaştırma adımlarından oluşur.

1. Problem türü ve veri üretimi

2. ATSP’nin temel MIP mantığı

Çalışmanın kullandığı MTZ’siz Gurobi yaklaşımını açıklamak için standart ATSP hedefi şu temel ilişkiyle anlaşılabilir:

\[ \min \sum_{i=1}^{N}\sum_{j=1, j\neq i}^{N} c_{ij}x_{ij} \]

Çıkış kısıtı:

\[ \sum_{j=1, j\neq i}^{N} x_{ij}=1 \quad \forall i \]

Giriş kısıtı:

\[ \sum_{i=1, i\neq j}^{N} x_{ij}=1 \quad \forall j \]

Subtour elimination mantığı:

\[ \sum_{i\in S}\sum_{j\in S, j\neq i}x_{ij} \leq |S|-1 \]

3. GTA’nın algoritmik bileşenleri

4. Warm start kalitesi

5. Tablo 1 performans karşılaştırması

6. Şekillerin teknik anlamı

• Tablo 1 ve ilk performans grafiği: GTA’nın exact solver ve heuristic yöntemler arasında konumlandırıldığını gösterir. Çalışma, GTA’nın ATSP’de 0% gap ile heuristic hızına yakın runtime sunduğunu savunur.
• Log-log ve lin-log performans grafikleri: GTA runtime verilerinin düğüm sayısına karşı ampirik olarak yakın-kuadratik ölçekleme gösterdiği iddiasını destekler. Bu sonuç formal ispat değil, regresyon temelli deneysel gözlemdir.
• GTA-LAZY-MTZ karşılaştırması: Warm start ve MTZ’siz lazy subtour elimination birleşiminin, warm start’sız lazy ve MTZ yaklaşımlarından daha düşük runtime verdiğini gösterir.
• Optimal route haritaları: 10, 100, 1.000 ve 2.000 düğüm için rota karmaşıklığının görsel olarak nasıl büyüdüğünü gösterir. Büyük yeşil ve mavi noktalar başlangıç ve orta yol düğümlerini temsil eder.
• Seed invariance grafiği: S = 42, 65, 7, 29 ve 133 gibi farklı seed değerlerinde runtime eğrilerinin benzer davrandığını gösterir.
• Cost range grafiği: [1,10] ve [10,100] maliyet aralıklarında çalışma süresinin benzer ölçekleme gösterdiğini savunur.
• GUI ve diagonal değişken çıkarma grafiği: Kod sadeleştirme ve modelden diagonal değişkenlerin kaldırılmasıyla ortalama yaklaşık 50% runtime iyileşmesi raporlanır.

7. Seed ve maliyet ölçeği testleri

8. RAM ve kod sadeleştirme etkisi

9. Uygulama alanları

10. Çalışmanın ana bulguları

• GTA, Tabu Search warm start ile Gurobi MIP exact çözümünü birleştirir.
• MTZ kısıtları yerine lazy constraint callback ile subtour elimination uygulanır.
• Çalışmada 5.000 düğüme kadar ATSP örneklerinde 0% optimality gap raporlanır.
• Tablo 1’de GTA için 5.000 düğümlü ATSP’de 350–850 saniye aralığı verilir.
• Warm start olmadan Gurobi lazy constraints yaklaşımı için 3.750–6.750 saniye aralığı bildirilir.
• Yakın-kuadratik N^2.01–N^2.03 davranış ampirik log-log regresyonla savunulur.
• Farklı seed değerlerinde runtime ölçeklemesinin benzer kaldığı raporlanır.
• [1,10] ve [10,100] maliyet aralıklarında runtime kararlılığı gösterilir.
• GUI ve diagonal değişkenlerin çıkarılmasıyla yaklaşık 50% runtime iyileşmesi raporlanır.
• Yazarlar, büyük ölçeklerde asıl darboğazın hesaplama süresinden RAM/sistem belleğine kaydığını savunur.

11. Güçlü yönler

• ATSP’nin simetrik TSP’den farklı ve daha zor bir problem olduğunu açık biçimde vurgular.
• Sezgisel hız ile exact MIP optimality hedefini aynı mimaride birleştirir.
• Warm start kalitesinin MIP performansı üzerindeki etkisini pratik biçimde ele alır.
• MTZ’siz lazy subtour elimination ile model boyutu ve çözüm yükünü azaltmayı hedefler.
• Seed, maliyet aralığı ve kod sadeleştirme testleriyle mühendislik dayanıklılığı göstermeye çalışır.
• Rota görselleştirme ve kullanıcı arayüzüyle yöntemi yalnızca teorik değil, uygulanabilir bir araç olarak sunar.

12. Sınırlılıklar

• Çalışma hakemliği metin üzerinden doğrulanamayan araştırma taslağı / preprint niteliğindedir.
• Yakın-kuadratik karmaşıklık formal teorik ispatla değil, ampirik runtime regresyonuyla desteklenir.
• 5.000 düğümlü ATSP için doğrudan standartlaştırılmış dış benchmark eksikliği vardır.
• Karşılaştırmaların bir kısmı simetrik TSP benchmarklarıyla yapılır; bu veriler ATSP ile birebir aynı problem sınıfı değildir.
• Rastgele üretilen maliyet matrisleri gerçek lojistik, genomik veya astronomi verilerindeki bağımlılık yapısını tam temsil etmeyebilir.
• GTA’nın başarısı Gurobi solver’a, solver parametrelerine, RAM kapasitesine ve warm start uygulamasına bağlıdır.
• Kodun ve solver loglarının açık erişimi, bağımsız tekrar için kritik önemdedir; metinde açık erişim niyeti belirtilir.
• Multi-agent TSP, gene overlap sequencing ve bazı ileri varyantlar bu çalışmada tam test edilmiş sonuçlar olarak sunulmaz.

Kaynak ve Yöntem Notu

Bu makale, Wissam Nakhle, Gaby Abou Haidar, Elie Al Ahmar ve Roger Achkar tarafından hazırlanan “GTA - An ATSP Method: Shifting the Bottleneck from Algorithm to RAM” başlıklı çalışmaya dayanarak hazırlanmıştır. Çalışmada yazar bağlantıları Concordia University, American University of Science and Technology, Université La Sagesse ve Antonine University olarak verilmiştir.

Kaynak türü, metin yapısı ve sunum biçimi dikkate alındığında akademik araştırma makalesi taslağı / preprint niteliğinde teknik çalışma olarak değerlendirilmelidir. Metin içinde hakemli dergi kabulü, DOI, konferans kabulü veya açık hakem değerlendirmesi bilgisi doğrulanamadığı için bu çalışma için hakemliği metin üzerinden doğrulanamayan çalışma ifadesi kullanılmalıdır.

Bu içerik hazırlanırken çalışmada verilen GTA mimarisi, Tabu Search warm start yaklaşımı, Gurobi MIP kullanımı, MTZ’siz lazy subtour elimination stratejisi, ATSP’nin simetrik TSP’den farkı, Tablo 1 performans karşılaştırması, log-log ve lin-log runtime grafiklerinin yorumu, seed değişimi, maliyet aralığı ölçekleme, ağ görselleştirme, GUI/diagonal değişken sadeleştirme deneyleri ve sonuç bölümündeki iddia ve sınırlılıklar esas alınmıştır.

Metinde bulunmayan bağımsız doğrulama, hakemli yayın kabulü, tüm gerçek dünya ATSP örnekleri için garanti, worst-case teorik karmaşıklık ispatı, Gurobi’den bağımsız başarı, tüm TSP varyantlarında otomatik çalışma veya kesin ticari/operasyonel başarı gibi iddialar eklenmemiştir. Çalışmanın bulguları, büyük ölçekli rastgele ATSP örneklerinde GTA’nın güçlü ve tekrarlanabilir performans gösterebileceğini savunmaktadır; ancak bu iddiaların bilimsel güvenilirliği açık kod, tam solver logları, bağımsız tekrarlar ve gerçek veri benchmarklarıyla daha da güçlendirilmelidir.