İki Amaçlı Çoklu Gezgin Satıcı Problemi için Üç Aşamalı Çözüm Yaklaşımı
Three-Step Solution Approach for the Two-Objective Multiple Traveling Salesman Problem
Yazar: Gunesen, Beyza; Kapanoğlu, Muzaffer
Dergi: Avrupa Bilim ve Teknoloji Dergisi No. 26, 2021
Anahtar kelimeler: Engineering ; Mühendislik ; Çoklu Gezgin Satıcı Problemi,K–ortalamalar,En Yakın Komşu Sezgiseli,2 – opt algoritması ; Multiple Traveling Salesman Problem,K – means,Nearest Neighbor,2 – opt algorithm.

Çoklu gezgin satıcı problemlerinin (ÇGSP) çözümünde karşılaşılan güçlükler literatürde oldukça uzun bir geçmişe sahiptir. Çoklu gezgin satıcı problemi çalışmalarında etkin ve başarılı sonuçların tespiti ve tartışılabilirliği için iki tür ölçüt kullanılmaktadır. Bunlar tüm satıcıların kat ettiği toplam uzaklık veya herhangi bir satıcının kat ettiği en uzun mesafe olabilmektedir. Toplam uzaklık temel alındığında satıcılar arasındaki iş yüklerinde önemli dengesizlikler meydana gelmektedir ki bu istenmeyen bir durumdur. En uzun mesafeyi kat eden satıcının kat ettiği mesafe azaltılmak istendiğinde dengesizlik ortadan kalkmakta fakat toplam mesafe (maliyet) dengeyi sağlamak amacıyla artmaktadır. Problem üstel artan bir çözüm uzayına sahip olup NP – zor sınıfında yer almaktadır.  Problemin eniyi çözüme ulaştırılmasında önerilen mevcut matematiksel modeller, günlük hayatta çok kısıtlı bir kullanıma sahiptir.  Bu durum, pratikte ele alınan probleme özel çözüm yöntemlerini ön plana çıkarmaktadır.  Bu bağlamda, üç servis aracı ile insan-topla-dağıt hizmeti yürüten bir işletmenin problemi üzerinde çalışılmıştır. Üçlü gezgin satıcı problemi, ÇGSP’nin satıcı sayısının üç olduğu hali olan bir alt kümesidir.  Bu çalışmada, iki enküçükleme amacını da gözeten ve etkin çözümlerin kısa sürelerde elde edilebileceği üç aşamalı çözüm yaklaşımı önerilmiş olup, kümeleme ve rotalama olmak üzere iki ana adımdan oluşmaktadır. Kümeleme adımı, uğrak noktalarını yakınlıklarına göre k – ortalamalar yöntemi ile önce üç gruba ayırmaktadır. Elde edilen kümeler için rotalar başlangıçta En Yakın Komşu Sezgiseli (EYK) ile oluşturulmakta ve daha sonra 2–opt algoritması ile iyileştirilmektedir. Bu çalışmada önerilen yaklaşım çoklu gezgin satıcı problemi için kullanılan test problemlerinde ve rassal türetilen problemlerde uygulanmış ve sonuçlar matematiksel model sonuçları ile karşılaştırılarak ortaya konulmuştur. Herhangi bir satıcının kat edeceği en uzun mesafe, toplam mesafe ve algoritma çözüm süresi, performans ölçütleri olarak belirlenmiştir. Sonuç olarak önerilen ardışık yaklaşım, ilk ölçütte %70–80 oranında en iyi çözümlere yakınsamış, diğer ölçütler de ise daha iyi performans sergilemiştir. Satıcılar arasındaki sapmaların ve toplam mesafenin paralel ödünleşerek enküçüklenmesi noktasında, elde edilen çözümler yüksek seviyeli olup, yaklaşımın koşma süresi polinom zamanlıdır.

The difficulties encountered in solving multi-traveling salesman problems (MTSP) have a long history in the literature. Two types of criteria are used to determine effective and successful outcomes and their arguability in multi-traveling salesman problem studies. These can be the sum of distances traveled by all salesman or the maximum distance traveled by any salesman. Significant imbalances occur in workloads between salesmen based on total distance, which is undesirable. When the distance traveled by the salesman who travels the maximum distance is desired to be reduced, the imbalance disappears, but the total distance (cost) increases to maintain the balance. The problem has an exponentially increasing solution space and is in the NP-hard class. The current mathematical models proposed for solving the problem at its optimum have very limited use in daily life. This brings to the fore the solution methods specific to the problem dealt with in practice. In this context, the problem of business management that runs people pick up and collect service with three vehicles has been studied. The triple traveling salesman problem is a subset of the MTSP where the number of salesmen is three. In this study, a three-phase solution approach, which considers both minimization objectives and which provides effective solutions in a short time, has been proposed. Clustering first divides the pick-up points into three groups according to their proximity with the k-means method. For the clusters obtained, the routes are initially created with the Nearest Neighbor Heuristic (NN) and then improved with the 2 – opt algorithm. The approach proposed in this study was applied to test problems used for the multiple traveling salesman problem and randomly generated problems, and the results were presented by comparing them with the results of the mathematical model. The maximum distance that any salesman will travel, total distance, and algorithm solution time are determined as performance criteria. As a result, the proposed sequential approach converged to the best solutions by 70–80% in the first criterion, outperforming other criteria. At the point where the deviations between salesmen and the total distance are minimized by parallel trade-off, the solutions obtained are of high level and the running time of the approach is polynomial time.