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.
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.
Primary Language | English |
---|---|
Subjects | Engineering |
Journal Section | Research Article |
Authors | |
Publication Date | February 27, 2018 |
Published in Issue | Year 2018 Volume: 24 Issue: 1 |