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

Vildan Özkır; Burak Topçu

Makale detayları

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

Yazarlar:

Vildan Özkır | Burak Topçu

Yayıncı:

Pamukkale University

Ana Başlıklar:

Uygulamalı fizik

Dergi:

Pamukkale University Journal of Engineering Sciences 2018 Vol.24 Issue 1, pp.76-82

Belge Tipi:

Makale

Yayın Tarihi:

2/2018

Belge Dili:

İngilizce

Document ID (Org No.):

2000576473

Sıklık:

İki Aylık

eISSN:

2147-5881

pISSN:

1300-7009

Özet:

 


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.

.

 


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.

.

Makale detayları

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

Yazarlar: Vildan Özkır | Burak Topçu

Yayıncı: Pamukkale University

Ana Başlıklar: Uygulamalı fizik

Dergi: Pamukkale University Journal of Engineering Sciences 2018 Vol.24 Issue 1, pp.76-82

Belge Tipi: Makale

Yayın Tarihi: 2/2018

Belge Dili: İngilizce

Document ID (Org No.): 2000576473

Sıklık: İki Aylık

eISSN: 2147-5881

pISSN: 1300-7009

Sayı

Yazarlar:

Vildan Özkır | Burak Topçu

Yayıncı:

Pamukkale University

Ana Başlıklar:

Uygulamalı fizik

Dergi:

Pamukkale University Journal of Engineering Sciences 2018 Vol.24 Issue 1, pp.76-82

Belge Tipi:

Makale

Yayın Tarihi:

2/2018

Belge Dili:

İngilizce

Document ID (Org No.):

2000576473

Sıklık:

İki Aylık

eISSN:

2147-5881

pISSN:

1300-7009