Görüntüleme
15
İndirme
4
Ç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 multiple traveler seller problems (CGSP) have a quite long history in literature. Two types of criteria are used for the detection and controversiality of effective and successful results in multiple traveler seller problem studies. These can be the total distance that all sellers double or the longest distance that any sellers double. On the basis of the total distance, significant imbalances in the workload between the sellers occur, which is an unwanted situation. When the distance of the seller that has the longest distance is requested to be reduced, the imbalance disappears but the total distance (cost) increases in order to ensure the balance. The problem has an increasing solution space and is ranked in the NP - difficult class. The existing mathematical models recommended in bringing the problem to the best solution have a very limited use in everyday life. This situation puts the specific methods of solving the problems addressed in practice in the forefront. In this context, the problem of a business that operates human-collective-distribution services with three service tools has been worked on. The triple traveler seller problem is a subset in which the number of seller in the CGSP is three. In this study, a three-step solution approach is proposed, which also observes the two purposes of decoction and in which effective solutions can be achieved in a short period of time, and consists of two main steps: accumulation and rotating. The grouping step divides the points of destination into three groups first by the method of k-mediates according to their proximity. Routes for obtained sets are initially created with the Nearest Neighbor Intelligence (EYK) and then improved with the 2-opt algorithm. The approach suggested in this study was applied to the test problems and racial issues used for the multiple traveler seller problem and the results were found by comparing with the results of the mathematical model. The longest distance that any seller will double, the total distance and the algorithm solution time are determined as performance standards. As a result, the follow-up approach proposed was 70% to 80% closer to the best solutions in the first measurement, while the other measurements showed better performance. At the point of deformation of the deviations between the sellers and the total distance by parallel deformation, the achieved solutions are high levels, and the duration of the approach is polinom time.
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.
Alan : Fen Bilimleri ve Matematik; Mühendislik
Dergi Türü : Uluslararası
Makale Detay 
Benzer Makaleler
PDF Görüntüle
Dergi Bilgisi
Eseri Dinleyin
Alıntı Yap
Bu Sayfayı Yazdırın
Paylaş
Mendeley
