Meta-heuristic solution approaches for traveling salesman and traveling repairman problems

Abstract

Gezgin satıcı problemi (GSP) uzun yıllardır yoğun bir şekilde çalışılan bir kombinatoryal optimizasyon problemidir. GSP, kat edilen toplam mesafeyi en aza indirmek için her noktaya sadece bir kez uğranılan bir Hamilton turu yaratma problemidir. Karınca kolonisi optimizasyonu (KKO), optimizasyon problemlerini çözmek için meta-sezgisel bir yaklaşımdır. Çalışmada, yerel arama sezgisellerinden yararlanan KKO tabanlı bir algoritma önerilmiştir. Önerilen algoritma iyi bilinen GSP veri setlerine uygulanmış ve sonrasında hesaplamalardan elde edilen sonuçlara göre algoritmanın performansı tartışılmıştır. Gezgin tamirci problemi (GTP) farklı konumlarda bulunan müşterilerin bekleme sürelerinin toplamını en aza indirmenin amaçlandığı bir Hamilton turu bulma problemidir. Genetik algoritmalar (GA) evrim sürecinden ilham alınarak yaratılmış meta-sezgisel çözüm yöntemleridir. İkinci çalışmada GTP'yi çözmek için genetik algoritmayı yerel arama sezgiseli ile birleştiren bir hibrit algoritma önerilmiştir. Önerilen algoritma literatürde çalışılmış bir dizi örneğe uygulanmıştır. Algoritmanın performansı hesaplama çalışmasının sonucuna göre değerlendirilmiştir. Bu çalışmaların amacı, büyük ölçekli GSP ve GTP problemlerini çözmek için gerçek hayat problemlerine uygulanabilen verimli ve etkili algoritmalar geliştirmektir. Üçüncü çalışma olarak, varsayımları temel alan bir kar felaketi durumu hakkında bir vaka çalışması GSP ve GTP olarak çalışılmıştır. Önerilen algoritmalar vakaya uygulanmış ve sonuçları tartışılmıştır. The traveling salesman problem (TSP) is a combinatorial optimization problem which has been extensively studied for years. TSP is the problem of creating a Hamiltonian cycle in which each node is visited only once to minimize total distance travelled. The ant colony optimization (ACO) is a meta-heuristic approach for solving optimization problems. In the study, an ACO based algorithm is proposed which utilizes local search heuristics. Proposed algorithm is applied to well-known TSP datasets and then the performance of the approach is discussed according to the results obtained from computations. The travelling repairman problem (TRP) is the problem of finding a Hamiltonian path in which the objective is to minimize total waiting time of all customers that are situated at different locations. Genetic algorithms (GA) are meta-heuristic solution methods which are created by taking inspiration from the evolution process. As a second study, a hybrid algorithm which combines genetic algorithm with a local search heuristic is proposed to solve TRP. Proposed algorithm is applied to a set of instances that have been studied in the literature. Performance of the approach is evaluated according to the results of the computational study. Aim of these studies is to develop efficient and effective algorithms that can be applicable to real life problems to solve large scale TSP and TRP problems. As the third study, a case study about a snow disaster situation based on some assumptions is examined as TSP and TRP. Proposed algorithms are applied to the case and results are discussed.