Solution and Development of the Travelling Salesman Problem and Data Allocation Problem by Using Heuristic Algorithms

Abstract

Bu tez çalışmasında, iki önemli optimizasyon problemi ele alınmıştır. İlk problem olarak Gezgin Satıcı Problemi (TSP) hibrit bir yöntemle çözülmeye çalışılmıştır. Önerilen yöntemde Karınca Kolonisi Optimizasyonu (KKO) algoritmasının parametreleri Parçacık Sürü Optimizasyonu (PSO) ile optimize edilmiştir. Daha sonra yerel minimumlardan kaçınmak için 3-Opt algoritması kullanılmıştır. İkinci problem olarak Veri Tahsis Problemi (VTP) literatürde daha önce uygulanmamış olan PSO algoritması ile çözülmeye çalışılmıştır. Ayrıca, VTP için açgözlü bir yöntem önerilmiştir. TSP, standart optimizasyon problemlerinden biri olarak optimizasyon algoritmalarının verimliliğini ölçmek için kullanılmaktadır. KKO algoritması, ayrık optimizasyon problemlerini çözmek için kullanılmaktadır. Bu tez çalışmasında, TSP'nin çözümü için yeni bir hibrit yöntem önerilmektedir. PSO algoritması aracılığıyla KKO algoritmasının giriş parametreleri bulunmakta ve son olarak tur esnasında oluşan çapraz kenarları kaldırmak için 3-OPT algoritması kullanılmaktadır. KKO algoritmasında yer alan α and β parametrelerinin optimal değerleri PSO algoritması ile bulunmaktadır. KKO algoritması, kenarların kesişim noktasını çözmede başarısız olmasından dolayi tur sırasında seçilen şehirlerin seçimini iyileştirmek için 3-Opt algoritması kullanılmıştır. Önerilen yöntem ile literatürde yer alan algoritmaların sonuçlarını karşılaştırmak için 10 adet standart veri seti üzerinde test yapılmıştır. VTP, optimizasyon algoritmalarının verimliliğini ölçmek için kullanılan bir başka optimizasyon problemidir. Bu tahsis işleminde, yürütme süresinin ve sorguların işlem maliyetinin minimize edilmesi hedeflenmektedir. Bu problemi çözmek için literatürde daha önce kullanılmamış olan PSO yöntemi kullanılmıştır. Ayrıca üçüncü bir yöntem olarak aç gözlü bir yöntem önerilmiştir. PSO tabanlı ve açgözlü yöntemlerin performansları 20 farklı test kullanılarak kıyaslanmıştır. Elde edilen sonuçlar sunulan yöntemlerin, literatürdeki yöntemlere göre uygulama süresi ve toplam maliyet bakımından daha iyi olduğunu göstermiştir.

In this thesis, two important optimization problems are discussed. The first problem was solved by a hybrid method. In the proposed method, the parameters of the Ant Colony Optimization (ACO) algorithm was optimized with Particle Swarm Optimization (PSO). The 3-Opt algorithm used to avoid local minimums. The second problem was the Data Allocation Problem(DAP), solved by the PSO algorithm, which was not used previously in the literature. In addition, a greedy method for DAP was proposed.TSP is used as a standard optimization problem to measure the efficiency of optimization algorithms. The ACO algorithm is used to solve discrete optimization problems. In this thesis, a new hybrid method is proposed for the solution of TSP. The ACO algorithm has input parameters via the PSO algorithm. Finally, the 3-OPT algorithm is used to remove the crossed edges in the round. With the PSO algorithm, the optimal values of the α and β parameters in the ACO algorithm are decided. The 3-Opt algorithm is used to improve the selection of selected cities during the tour when the ACO algorithm fails to resolve this intersection point of the edges. 10 standard data sets were tested to compare the proposed method and the results of the algorithms in the literature.The DAP is another optimization problem used to measure the efficiency of optimization algorithms. Main purpose of this allocation process is minimizing the execution time and the transaction costs of the queries. In order to solve this problem, the PSO method has been applied which is not used in the literature. A third method has also been proposed as a greedy method. The performances of the PSO-based and greedy methods have been examined in 20 different test problems. The results showed that the methods presented were better than the results of the methods in the literature in terms of execution time and total cost.