A Novel Heuristic For The Traveling Salesman Problem: maxS

Authors : Kenan KARAGÜL, Gürhan GÜNDÜZ

Pages : 665-677

Doi:10.21205/deufmd.2022247129

View : 14 | Download : 9

Publication Date : 2022-05-16

Article Type : Research Paper

Abstract :Bu çalışmada, gezgin satıcı problemi için yeni bir başlangıç çözüm sezgiseli önerilmiştir. Önerilen maxS metodu, üzerinde çalışılan problemin mesafe matrisinin maksimum satır değerine göre normalize edilmesiyle elde edilen yeni mesafe matrisi ile çalışır. Önerilen metot, Hougardy ve Zhong tarafından tavsiye edilen ve optimal çözümü zor olan 20 küçük ve 11 büyük ölçekte problem üzerinde test edilmiştir. Aynı problemler, Concorde yazılımı üzerinde çalışan Greedy, Boruvka, Quick-Boruvka, Nearest-Neighborhood and Lin-Kernighan sezgiselleri ile de çözülmüştür. Çözümler karşılaştırıldığında küçük ölçekli problemler için maxS sezgiselinin performansının Greedy ve Nearest-Neighborhood sezgisellerinden daha iyi olduğu ve Boruvka ile benzer performansta olduğu gözlenmiştir. Benzer karşılaştırmalar büyük ölçekli problemler için yapıldığında maxS, Quick Boruvka ve Nearest-Neighborhood sezgisellerinden ortalama olarak daha iyi performans göstermiştir. Çözüm zamanları açısından çok etkili olan maxS sezgiseli, gelecek vaadeden başlangıç çözüm yöntemi olarak önerilebilir.
Keywords : Gezgin Satıcı Problemi, maxS, Boruvka, Nearest Neighbourhood, Lin Kernighan, başlangıç çözümü