- Avrupa Bilim ve Teknoloji Dergisi
- Issue: 26 - Ejosat Special Issue: 2021 (HORA) Special Issue
- İki Amaçlı Çoklu Gezgin Satıcı Problemi için Üç Aşamalı Çözüm Yaklaşımı
İki Amaçlı Çoklu Gezgin Satıcı Problemi için Üç Aşamalı Çözüm Yaklaşımı
Authors : Beyza Gunesen, Muzaffer Kapanoğlu
Pages : 325-331
Doi:10.31590/ejosat.952103
View : 7 | Download : 2
Publication Date : 2021-07-31
Article Type : Other
Abstract :Ç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.Keywords : Çoklu Gezgin Satıcı Problemi, K–ortalamalar, En Yakın Komşu Sezgiseli, 2 – opt algoritması