A novel metaheuristic for traveling salesman problem: blind mole-rat algorithm

Traveling Salesman Problem (TSP) is the problem of finding a minimum distance tour of cities beginning and ending at the same city and that each city are visited only once. As the number of cities increases, it is difficult to find an optimal solution by exact methods in a reasonable duration. Therefore, in recent five decades many heuristic solution methods inspired of nature and biology have been developed. In this paper, a new metaheuristic method inspired of the by-passing the obstacle strategy of blind mole rats living in their individual tunnel systems under the soil is designed for solving TSP. The method is called as Blind Mole-rat Algorithm. The proposed algorithm is tested on different size of symmetric TSP problems and the results are compared to the best known results. Initial test results are promising although proposed metaheuristic is not yet competitive enough among other algorithms in the literature.

Gezgin satýcý problemi için yeni bir meta-sezgisel: kör fare algoritmasý

Gezgin Satýcý Problemi (GSP), baþlangýç ve bitiþ þehirleri ayný olan ve her þehrin sadece bir kez ziyaret edildiði minimum mesafeli turu bulma problemidir. Þehir sayýsý arttýkça, kesin yöntemler ile kabul edilebilir sürelerde bir optimum çözüm bulunmasý zordur. Bu nedenle, son elli yýlda GSP’nin çözümü için doðadan ve biyolojiden esinlenen birçok meta-sezgisel yöntem geliþtirilmiþtir. Bu çalýþmada, toprak altýndaki bireysel tünel sistemlerinde yaþayan kör farelerin toprak altýndaki engelleri geçme stratejisinden esinlenilerek GSP’nin çözümü için yeni bir meta-sezgisel tasarlanmýþtýr. Geliþtirilen yönteme Kör Fare Algoritmasý adý verilmiþtir. Bu yeni sezgisel ile farklý boyutlardaki simetrik test veri setleri için deneyler yapýlmýþ ve sonuçlarý bilinen en iyi sonuçlar ile kýyaslanmýþtýr. Önerilen meta-sezgisel henüz literatürdeki diðer algoritmalarla yarýþabilecek düzeyde olmamasýna raðmen, baþlangýç test çözümlerinin umut verici olduðu söylenebilir.