K-means++ hiyerarşik kümeleme ve sinirsel kombinatoryal ağlar kullanarak çoklu-depo kapalı yol çoklu gezgin satıcı problemini çözme

Daha akıllı rotalar için çok sayıda sürücü

Kargo vanlarından teslimat dronlarına ve afet yardım konvoylarına kadar planlamacılar sık sık şu bilmeceyle karşılaşır: farklı yerlerden başlayan birkaç araç, yüzlerce ya da binlerce noktayı ziyaret etme işini yakıt veya zaman israfı olmadan nasıl paylaşabilir? Bu makale, bilgisayarların verimli rotaları dakikalar ya da saatler yerine saniyeler içinde oluşturabilmesi için klasik bir kümeleme hilesini modern bir sinir ağıyla birleştiren yeni bir böl-ve-yönet yaklaşımı sunuyor.

Birden çok depo ve çok sayıda sürücünün zorluğu

Çalışma, ünlü gezgin satıcı (traveling salesperson) bilmecesinin talepkar bir versiyonuyla ilgileniyor: tek bir gezgin yerine her biri kendi merkezinde başlayıp biten birçok gezgin var. Birlikte her şehri tam olarak bir kez ziyaret etmeli ve toplam mesafeyi mümkün olduğunca kısa tutmalılar. Bu düzen, kamyon filolarını, robot gruplarını veya bir bölge üzerinde işi paylaşan hava dronlarını koordine etme gibi görevleri taklit eder. Şehirlerin ve sürücülerin sayısı arttıkça olası rota kombinasyonlarının sayısı patladığı için kesin yöntemler çok yavaşlar ve geleneksel deneme-yanılma arama yöntemleri genellikle zorlanır veya hız uğruna çözüm kalitesinden ödün vermek zorunda kalır.

Klasik arama ve basit bölmenin sınırları

Yıllardır mühendisler genetik algoritmalar, karınca kolonisi araması ve parçacık sürüleri gibi “meta-sezgisel” yaklaşımlara bel bağladılar. Bunlar doğal süreçleri taklit ederek birçok aday rotayı keşfeder ve bunları kademeli olarak iyileştirir. Esnek olabilirler ama iki büyük dezavantajları vardır: bir çözümün ne kadar iyi olduğuna dair sağlam garantiler vermezler ve her yeni görev için aramanın yeniden başlatılması gerektiğinde büyük haritalarda çok yavaş olabilirler. Yaygın bir hızlandırma yöntemi, önce şehirleri k-means gibi araçlarla bölgelere ayırmak ve sonra her küme içinde daha küçük bir problemi çözmektir. Bu böl-ve-çöz stratejisi yardımcı olsa da, nihai kalite yine temel arama yönteminin sınırlarıyla kısıtlanır ve daha iyi rotalar hedeflendiğinde genellikle çalışma zamanının daha da uzaması gerekir.

Bir ağı rota çıkarmaya öğretmek, sonra ölçeklendirmesine yardım etmek

Son yıllar farklı bir fikir getirdi: bir sinir ağını doğrudan iyi rotalar üretmeye eğitmek. Birçok örnek şehir düzeni üzerinde öğrendikten sonra böyle bir ağ, dili modelleyen bir modele benzer şekilde tek bir ileri geçişte tam bir tur önerebilir. Bu sinirsel çözücüler, tek sürücülü ve orta büyüklükteki problemlerde etkileyici performans gösterir, ancak çok sayıda sürücüyü koordine etmesi istendiğinde veya şehir kümesi eğitimdekinden çok daha büyük olduğunda tökezlerler. Yazarların kilit hamlesi, böyle bir sinirsel çözücüyü ağın rahatça halledebileceği birçok daha küçük, tanıdık altprobleme yeniden şekillendiren dikkatli iki aşamalı bir sürecin içine sarmaktır.

İki aşamalı yöntemin nasıl çalıştığı

Önerilen yöntem KHC-NCN, şehirleri farklı depolara ve sürücülere atamak için iyileştirilmiş bir k-means kümeleme versiyonunu kullanmakla başlar. Ortaya çıkan bir bölgede sinirsel çözücünün güvenle işleyebileceğinden çok fazla şehir varsa, yöntem o bölgeyi ağın eğitim sırasında gördüğüne yakın boyutlarda daha küçük parçalara otomatik olarak böler. Her parçadaki koordinatlar standart bir kareye yeniden ölçeklendirilir, böylece eğitim verisine daha da çok benzer hale gelirler. Ardından sinir ağı her küçük parça için bir rota üretir. Son olarak, birleştirme adımı bu alt-rotaları her sürücü için tek bir döngüye diker; parçaları birbirine bağlarken en az ek mesafe ekleyen basit geometrik kurallar kullanılır.

Gerçek karşılaştırma haritalarında hız ve kalite

Yazarlar yöntemlerini rota araştırmalarında yaygın olarak kullanılan halka açık bir benchmark setinden geniş bir standart harita koleksiyonunda test ediyorlar. Birçok yerleşik arama tekniğiyle ve hem önde gelen el yapımı bir çözücü hem de başka bir sinirsel yaklaşımla karşılaştırıyorlar. Farklı harita boyutları ve sürücü sayıları içeren 44 test vakası boyunca yöntemleri vakaların neredeyse dörtte üçünde toplam rotaları daha kısa buluyor ve aynı zamanda sıklıkla büyüklük sırasıyla çok daha hızlı çalışıyor. Yöntem, şehir sayısı yüzlere ya da binlere çıkınca özellikle iyi dayanıyor; bu durumda birçok klasik yaklaşım yavaşlıyor veya daha zayıf rotalar veriyor.

Gerçek dünya yönlendirmesi için bunun anlamı

Basitçe söylemek gerekirse çalışma, hızlı bir sinir ağının birçok küçük, iyi biçimlenmiş altproblemi ele almasının tek büyük bir problemi çözmeye çok zaman harcamaktan daha iyi olabileceğini gösteriyor. Şehirleri ağın konfor aralığını gözeterek kümelendirip, sonra kısmi cevapları akıllıca birleştirerek yöntem hem kısa hem de hızlı hesaplanan rotalar sunuyor. Lojistik, çok-robot planlaması ve acil müdahale gibi uygulamalar için bu, araçları ve enerjiyi mevcut birçok araçtan daha iyi kullanan neredeyse gerçek zamanlı rota planları elde etmeye yönelik pratik bir yol gösteriyor.

Atıf: Zhao, CS., Wong, LP. & Fung, C. Solving multi-depot closed-path multiple traveling salesman problem using k-means++ hierarchical clustering and neural combinatorial networks. Sci Rep 16, 15631 (2026). https://doi.org/10.1038/s41598-026-45824-3

Anahtar kelimeler: araç yönlendirme, sinir ağları, kümeleme, optimizasyon, lojistik