Gezgin satıcı problemi i?çin yeni bir çözüm yaklaşımı: TPORT

Abstract

Bu çalışmada,yöneylem araştırması alanının en çok çalışılan problemlerden 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. Bu yöntem gezgin satıcı problemini daha etkin çözmek için yıllardır süren araştırmalarabir katkı sağlamak için önerilmiştir. Önerilen yöntemde gezgin satıcı uzaklık matrisi,bir ulaştırma tablosu gibi ele alınarak, matris üzerinde yapılan özel bir normalizasyonişlemi ile gezgin satıcı problemi için başlangıç çözümü elde edilmektedir. Daha sonra, elde edilen başlangıççözümünün performansı 2-Opt algoritmasıile geliştirilmektedir. 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 doğrudan başlangıç çözümüne uygulanan 2-Opt algoritması 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 grupproblemile analiz edilmiştir. Ortalama çözüm değeri optimalden %26 sapma gösterirken, En Yakın Komşu algoritması için optimalden sapma %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ınınçözüm performansı açısından rekabetçi olduğu ileri sürülebilir. Ayrıcaçö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 çözüm hızı açısından üstün,çözüm kalitesi bakımından kıyaslanan yöntemlere göre rekabetçiolduğ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 üstelbir eğilim göstermiştir.