AI Summary & Key Takeaways
AI InsightIn particular, as the problem size is increased, the solution time of the comparable methods is almost constant, while the solution time of the nearest neighbor algorithm shows an asymptotic trend.
📌 3 Key Takeaways
Abstract
In this study, a novel solution algorithm taking advantage of the relationship between traveling salesman and transportation problems that are the most studied problems of operations research field since 1800s, is proposed. Many initial solution algorithms have been proposed for transportation problems. In this study, an approach called TPORT is proposed for the initial solution for the symmetric traveling salesman problem with similar approach and intuition. The performance of the initial solutions is developed with 2-Opt algorithm. As the developed heuristic has similarities with the nearest neighbor algorithm, the solution performances of the traveling salesman problems were compared with the solutions of the nearest neighbor algorithm and 2-Opt. The proposed approach has been analyzed by the well-known traveling salesman test instances and a group of test instances from the literature. The average solution performance of the proposed method was 26%, while the performance of the nearest neighbor algorithm was 16%. However, when the solutions of TPORT and nearest neighbor algorithm were developed with 2-Opt, the average deviation was obtained as 4% and 3%, respectively. In this context, it can be argued that the proposed solution approach is competitive in terms of solution performance. Also, there is a huge difference between the proposed method and the nearest neighbor algorithm in terms of solution times. As a result, it has been shown that the proposed method with 2-Opt improvement is superior for both the solution speed and the quality of the solutions. In particular, as the problem size is increased, the solution time of the comparable methods is almost constant, while the solution time of the nearest neighbor algorithm shows an asymptotic trend.
Özet
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.