SavedAdd your journal

Journals / Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi / 2018 / Cilt: 24 - Sayı: 1

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

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

Vildan Özkır
Burak Topçu
Pages
76–82
Publication Date
2018-02-27
DOI
—
🏛️Bibliographic metadata and full text access for this article are provided via DergiPark.
DergiPark Record ↗
✨

AI Summary & Key Takeaways

AI Insight
⚡ TL;DR(Too Long; Didn't Read)

Efficiency of results shows that the proposed algorithm can be evaluated for the solution of combinatorial optimization problems.

📌 3 Key Takeaways

🎯
Objective & Hypothesis:Among network optimization problems, travelling salesman problem is widely studied one in the literature.
📊
Key Findings & Data:The proposed mechanism is based on the principle of encouraging randomly generated particles to move toward to optimal solution in the feasible area.
💡
Conclusion & Impact:Efficiency of results shows that the proposed algorithm can be evaluated for the solution of combinatorial optimization problems.
🔬Design:Modeling & Simulation
📍Scope:Comprehensive Sample
⚙️Variables:Elektromanyetizma sezgiseli. Gezgin satıcı problemi · Kapasite kısıtsız araç rotalama · Electromagnetism-like heuristic

Abstract

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.

Özet

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.

🔖

Cite This Article

Özkır, V., Topçu, B. (2018). Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, Cilt: 24 - Sayı: 1, 76–82. https://ajindex.com/articles/42406

📄 Full Text PDF Viewer

📄

PDF görüntüleyici hazırlanıyor...

References (16)

  1. Abd Aziz Z. “Ant colony hyper-heuristics for travelling salesman problem”. Procedia Computer Science, 76, 534-538, 2015.
  2. Aras N, Altinel KI, Oommen J. “A kohonen-like decomposition method for the traveling salesman problem: KNIESDECOMPOSE”. 14th European Conference on Artificial Intelligence (ECAI), Berlin, Germany, 20-25 August 2000.
  3. Angeniol B, Vaubois GDLC, Texier JYL. “Self-organizing feature maps and the traveling salesman problem”. Neural Networks, 1(4), 289-293, 1988
  4. Bean JC. “Genetic algorithms and random keys for sequencing and optimization”. ORSA Journal on Computing, 6(2), 154-160, 1994.
  5. Birbil Sİ, Fang SC. “An electromagnetism-like mechanism for global optimization”. Journal of Global Optimization, 25(3), 263-282, 2003.
  6. Birbil Sİ, Fang SC, Sheu RL. “On the convergence of a population-based global optimization algorithm”. Journal of Global Optimization, 30(2-3), 301-318, 2004.
  7. Blum C, Puchinger J, Raidl GR, Roli A. “Hybrid metaheuristics in combinatorial optimization: A survey”. Applied Soft Computing, 11(6), 4135-4151, 2011.
  8. Chang PC, Chen SH, Fan CY. “A hybrid electromagnetism-like algorithm for single machine scheduling problem”. Expert Systems with Applications, 36, 1259-1267, 2009.
  9. Chao CW, Liao CJ. “A discrete electromagnetism-like mechanism for single machine total weighted tardiness problem with sequence-dependent setup times”. Applied Soft Computing, 12, 3079-3087, 2012.
  10. Chen SH, Chang PC, Chan CL, Mani V. “A hybrid electromagnetism like algorithm for the single machine-scheduling problem”. Lecture notes in Computer Sciences, 4682, 543-552, 2007.
  11. Cochrane EM, Aras N. “The co-adaptive neural network approach to the euclidean travelling salesman problem”. Neural Networks 16(10), 1499-525, 2004.
  12. Debels D, Vanhoucke M. “The electromagnetism meta-heuristic applied to the resource-constrained project-scheduling problem”. Lecture Notes in Computer Science, 3871, 259-270, 2006.
  13. Filipovic V, Kartelj A, Matic D. “An electromagnetism metaheuristic for solving the maximum betweenness Problem”. Applied Soft Computing, 13, 1303-1313, 2013.
  14. Gendreau M, Laporte G, Semet F. “A tabu search heuristic for the undirected selective travelling salesman problem”, European Journal of Operational Research, 106, 539-545, 1998.
  15. Geng X, Chen Z, Yang W, Zhao, K. “Solving the traveling salesman problem based on an adaptive simulated annealing algorithm with greedy search”. Applied Soft Computing, 11, 3680–3689, 2011.
  16. Jolai F, Tavakkoli-Moghaddam R, Golmohammadi A, Ja