Bu tez çalışmasında kombinatoryal optimizasyon problemlerinden biri olan gezgin satıcı problemi (GSP) kullanılmıştır. GSP'de amaç, lojistik süreçlerde, sürecin daha verimli devam ettirilmesi ve taşıma maliyetini eniyilemektir. Problem, belli bir başlangıç düğümünden başlayarak gidilecek olan diğer düğümlere yalnızca bir defa uğranarak en son tekrar başlangıç düğümüne dönülmesi ve bu amaç ile en uygun rotanın hesaplanmasıdır. En kısa rotanın elde edilmesinin asıl amacı turun tamamlanması sırasında en düşük maliyeti elde etmektir. Bu problemin çözümü için genetik algoritma (GA) çözüm yöntemi kullanılmıştır. GSP için kullanılan GA'ya ek olarak kullanılacak olan oyun teorisi yardımı ile oyuncular (şirketler) arasında işbirliği durumu incelenmiştir. Bu durumda oluşacak koalisyonlar için elde edilcek en kısa mesafeler yardımı ile her oyuncunun kendi başına ödemesi gereken maliyet değeri ile koalisyon durumunda ödemesi gereken maliyet değerinin karşılaştırılmasının yapılması için işbirlikçi oyun teorisindeki maliyet tahsis yöntemleri kullanılmıştır. Shapley değeri, nükleolus, eşit kâr yöntemi ve ε- çekirdek yöntemleri maliyet tahsis değerlendirmesi için kullanılmıştır. Elde edilen sonuçlar çerçevesinde bu dört farklı maliyet tahsis yöntemlerinin incelenmesinin ardından uygulanan problem için en uygun maliyet tahsis yönteminin Shapley değeri olduğu sonucuna varılmıştır. Anahtar Kelimeler: Gezgin Satıcı Problemi, İşbirlikçi Oyun Teorisi, Genetik Algoritma, Shapley Değeri, Nükleolus, Eşit Kâr Yöntemi, 𝜀-Çekirdek.
In this thesis, one of the combinatorial optimization problems, traveling salesman problem (TSP) is used. The purpose of TSP is to continue the process more efficiently in logistics processes and to optimize the transportation cost. The problem is that starting from a certain starting node, other nodes to be navigated only once, return to the starting node and calculate the most suitable route for this purpose. The main purpose of obtaining the shortest route is to obtain the lowest cost during the completion of the tour. Genetic algorithm (GA) solution method is used to solve this problem. Cooperation between the players (companies) and the game theory to be used in addition to the GA used for GSP has been examined. In this case, the cost allocation methods in the cooperative game theory are used to compare the shortest distances to be obtained for the coalitions to be formed and the cost value that each player should pay on his own with the cost value that should be paid in the case of a coalition. Shapley value, nucleolus, equal profit method and ε -core methods are used for cost allocation evaluation. After examining these four different cost allocation methods within the framework of the results obtained, it is concluded that the most appropriate cost allocation method for the applied problem is Shapley value. Keywords: Travelling Salesman Problem, Cooperative Game Theory, Genetic Algorithm, Shapley value, Nucleolus, Equal Profit Method, 𝜀-core.
Tez (Yüksek Lisans) - Süleyman Demirel Üniversitesi, Fen Bilimleri Enstitüsü, Endüstri Mühendisliği Anabilim Dalı, 2021.
Kaynakça var.
Bu tez çalışmasında kombinatoryal optimizasyon problemlerinden biri olan gezgin satıcı problemi (GSP) kullanılmıştır. GSP'de amaç, lojistik süreçlerde, sürecin daha verimli devam ettirilmesi ve taşıma maliyetini eniyilemektir. Problem, belli bir başlangıç düğümünden başlayarak gidilecek olan diğer düğümlere yalnızca bir defa uğranarak en son tekrar başlangıç düğümüne dönülmesi ve bu amaç ile en uygun rotanın hesaplanmasıdır. En kısa rotanın elde edilmesinin asıl amacı turun tamamlanması sırasında en düşük maliyeti elde etmektir. Bu problemin çözümü için genetik algoritma (GA) çözüm yöntemi kullanılmıştır. GSP için kullanılan GA'ya ek olarak kullanılacak olan oyun teorisi yardımı ile oyuncular (şirketler) arasında işbirliği durumu incelenmiştir. Bu durumda oluşacak koalisyonlar için elde edilcek en kısa mesafeler yardımı ile her oyuncunun kendi başına ödemesi gereken maliyet değeri ile koalisyon durumunda ödemesi gereken maliyet değerinin karşılaştırılmasının yapılması için işbirlikçi oyun teorisindeki maliyet tahsis yöntemleri kullanılmıştır. Shapley değeri, nükleolus, eşit kâr yöntemi ve ε- çekirdek yöntemleri maliyet tahsis değerlendirmesi için kullanılmıştır. Elde edilen sonuçlar çerçevesinde bu dört farklı maliyet tahsis yöntemlerinin incelenmesinin ardından uygulanan problem için en uygun maliyet tahsis yönteminin Shapley değeri olduğu sonucuna varılmıştır. Anahtar Kelimeler: Gezgin Satıcı Problemi, İşbirlikçi Oyun Teorisi, Genetik Algoritma, Shapley Değeri, Nükleolus, Eşit Kâr Yöntemi, 𝜀-Çekirdek.
In this thesis, one of the combinatorial optimization problems, traveling salesman problem (TSP) is used. The purpose of TSP is to continue the process more efficiently in logistics processes and to optimize the transportation cost. The problem is that starting from a certain starting node, other nodes to be navigated only once, return to the starting node and calculate the most suitable route for this purpose. The main purpose of obtaining the shortest route is to obtain the lowest cost during the completion of the tour. Genetic algorithm (GA) solution method is used to solve this problem. Cooperation between the players (companies) and the game theory to be used in addition to the GA used for GSP has been examined. In this case, the cost allocation methods in the cooperative game theory are used to compare the shortest distances to be obtained for the coalitions to be formed and the cost value that each player should pay on his own with the cost value that should be paid in the case of a coalition. Shapley value, nucleolus, equal profit method and ε -core methods are used for cost allocation evaluation. After examining these four different cost allocation methods within the framework of the results obtained, it is concluded that the most appropriate cost allocation method for the applied problem is Shapley value. Keywords: Travelling Salesman Problem, Cooperative Game Theory, Genetic Algorithm, Shapley value, Nucleolus, Equal Profit Method, 𝜀-core.