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

Authors : Vildan Özkır, Burak Topçu

Pages : 76-82

View : 16 | Download : 8

Publication Date : 2018-02-27

Article Type : Research Paper

Abstract :Normal 0 false false false TR X-NONE X-NONE /* Style Definitions */ table.MsoNormalTable {mso-style-name:`Normal Tablo`; mso-tstyle-rowband-size:0; mso-tstyle-colband-size:0; mso-style-noshow:yes; mso-style-priority:99; mso-style-parent:``; mso-padding-alt:0cm 5.4pt 0cm 5.4pt; mso-para-margin-top:0cm; mso-para-margin-right:0cm; mso-para-margin-bottom:10.0pt; mso-para-margin-left:0cm; line-height:115%; mso-pagination:widow-orphan; font-size:11.0pt; font-family:`Calibri`,sans-serif; mso-ascii-font-family:Calibri; mso-ascii-theme-font:minor-latin; mso-hansi-font-family:Calibri; mso-hansi-theme-font:minor-latin; mso-bidi-font-family:`Times New Roman`; mso-bidi-theme-font:minor-bidi; mso-ansi-language:TR;} 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.
Keywords : Elektromanyetizma sezgiseli Gezgin satıcı problemi, Kapasite kısıtsız araç rotalama