Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems

Among network optimization problems, travelling salesman problem is widely studied one in the literature. Since the problem is computationally hard, many heuristics have been developed to obtain the optimal solution in reasonable time. This paper introduces a hybrid electromagnetism-like heuristics to solve symmetric travelling salesman problems. Originally, electromagnetism-like heuristic is a population based global search algorithm that is inspired by electromagnetism theory in Physics. The proposed mechanism is based on the principle of encouraging randomly generated particles to move toward to optimal solution in the feasible area. In this paper, random-key approach is adapted to electromagnetism-like heuristic to solve vehicle routing problems. Regarding 15 benchmark instances, proposed heuristic procedure produces optimal solutions for small instances. Moreover, as the number of vertices increase in the network, the proposed algorithm generates near optimal solutions. Efficiency of results shows that the proposed algorithm can be evaluated for the solution of combinatorial optimization problems.

Gezgin satýcý problemlerinin çözümü için rassal anahtar temelli elektromanyetizma sezgiselinin uygulanmasý

Að optimizasyonu problemleri içerisinde, gezgin satýcý problemi literatürde yaygýn bir þekilde çalýþýlan problemlerden biridir. Problemin hesaplama açýsýndan zor olmasý dolayýsýyla, optimal çözümü elveriþli zamanda elde edebilmek için pek çok sezgisel algoritma geliþtirilmiþtir. Bu çalýþma, simetrik gezgin satýcý problemlerinin çözümü için melez bir elektro-manyetizma sezgiseli sunmaktadýr. Esasýnda, elektro-manyetizma sezgiseli, fizikteki elektromanyetizma teorisinden ilham alan, popülasyon tabanlý global bir arama algoritmasýdýr. Önerilen mekanizma, fizibil alanda rassal olarak oluþturulan partikülleri optimal çözüme yaklaþtýrma prensibine dayanýr. Bu çalýþmada, araç rotalama problemlerini çözebilmek için rassal anahtar yaklaþýmý elektromanyetizma sezgiseline adapte edilmiþtir. 15 kýyaslama örneði üzerinde test edilen sezgisel yöntem küçük boyuttaki problemler için en iyi çözümleri üretmektedir. Ayrýca, aðdaki nokta sayýsý arttýkça, önerilen algoritma optimale yakýn çözümler üretmektedir. Sonuçlarýn etkinliði, önerilen algoritmanýn kombinatoryal optimizasyon problemleri çözümü için de deðerlendirilebileceðini göstermektedir.