Gezgin Satıcı Problemi İçin Yeni Bir Çözüm Yaklaşımı: TPORT

Authors : Kenan KARAGÜL

Pages : 819-832

Doi:10.21205/deufmd.2019216312

View : 13 | Download : 5

Publication Date : 2019-09-20

Article Type : Research Paper

Abstract :Bu çalışmada, 1800’lü yıllardan bu yana, yöneylem araştırması alanının en çok çalışılan problemlerinden biri olan gezgin satıcı ve ulaştırma problemleri üzerinde durulmakta ve aralarındaki ilişkiden faydalanan yeni bir çözüm algoritması önerilmektedir. Ulaştırma problemleri için bir çok başlangıç çözüm algoritması önerilmiştir. Benzer bir mantık ve sezgi ile simetrik gezgin satıcı problemine başlangıç çözümü üretmek için TPORT adı verilen bir yaklaşım önerilmiştir. Elde edilen başlangıç çözümünün performansı 2-Opt   sezgiseli ile geliştirilmiştir. Geliştirilen sezgisel En Yakın Komşu algoritması ile yakınlık gösterdiği için gezgin satıcı problemlerinin çözüm performansları En Yakın Komşu algoritması ve 2-Opt sezgisellerinin çözümleri ile karşılaştırılmıştır. Önerilen yaklaşım sıklıkla kullanılan gezgin satıcı test problemleri ve bilimsel yazında yer alan bir grup ile analiz edilmiştir. Ortalama çözüm değeri %26 optimalden uzak iken, En Yakın Komşu algoritması için %16 olarak gerçekleşmiştir. Ancak 2-Opt ile hem TPORT hem de En Yakın Komşu algoritmalarının çözümleri geliştirildiğinde, sırasıyla %4 ve %3 optimalden ortalama sapma elde edilmiştir. Bu bağlamda önerilen çözüm yaklaşımı çözüm performansı açısından rekabetçi olduğu ileri sürülebilir. Ancak çözüm süreleri açısından yapılan karşılaştırmalarda önerilen yöntemle En Yakın Komşu algoritması arasında önemli düzeyde fark vardır. Sonuç olarak, önerilen yöntemin hem çözüm hızı hem de çözüm kalitesi bakımından kıyaslanan yöntemlere göre iyi olduğu gösterilmiştir. Özellikle, problem boyutu büyüdükçe kıyaslanan yöntemlerin çözüm süresi neredeyse sabit bir seviyede seyrederken En Yakın Komşu algoritmasının çözüm süreleri asimptotik bir eğilim göstermiştir.
Keywords : Gezgin Satıcı Problemi, Ulaştırma Problemi, En Yakın Komşu Algoritması, 2 Opt