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

Tevfik YILDIRIM; Can Berk KALAYCI; Özcan MUTLU

Makale detayları

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

Yazarlar:

Tevfik YILDIRIM | Can Berk KALAYCI | Özcan MUTLU

Yayıncı:

Pamukkale University

Dergi:

Pamukkale University Journal of Engineering Sciences 2016 Vol.22 Issue 1, pp.64-70

Belge Tipi:

Makale

Yayın Tarihi:

2/2016

Belge Dili:

İngilizce

Document ID (Org No.):

2000577162

Sıklık:

İki Aylık

eISSN:

2147-5881

pISSN:

1300-7009

Özet:

 


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 (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.

.

Makale detayları

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

Yazarlar: Tevfik YILDIRIM | Can Berk KALAYCI | Özcan MUTLU

Yayıncı: Pamukkale University

Dergi: Pamukkale University Journal of Engineering Sciences 2016 Vol.22 Issue 1, pp.64-70

Belge Tipi: Makale

Yayın Tarihi: 2/2016

Belge Dili: İngilizce

Document ID (Org No.): 2000577162

Sıklık: İki Aylık

eISSN: 2147-5881

pISSN: 1300-7009

Sayı

Yazarlar:

Tevfik YILDIRIM | Can Berk KALAYCI | Özcan MUTLU

Yayıncı:

Pamukkale University

Dergi:

Pamukkale University Journal of Engineering Sciences 2016 Vol.22 Issue 1, pp.64-70

Belge Tipi:

Makale

Yayın Tarihi:

2/2016

Belge Dili:

İngilizce

Document ID (Org No.):

2000577162

Sıklık:

İki Aylık

eISSN:

2147-5881

pISSN:

1300-7009