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


Özkır V. , Topçu B.

PAMUKKALE UNIVERSITY JOURNAL OF ENGINEERING SCIENCES-PAMUKKALE UNIVERSITESI MUHENDISLIK BILIMLERI DERGISI, cilt.24, ss.76-82, 2018 (ESCI İndekslerine Giren Dergi) identifier

  • Cilt numarası: 24 Konu: 1
  • Basım Tarihi: 2018
  • Doi Numarası: 10.5505/pajes.2017.85698
  • Dergi Adı: PAMUKKALE UNIVERSITY JOURNAL OF ENGINEERING SCIENCES-PAMUKKALE UNIVERSITESI MUHENDISLIK BILIMLERI DERGISI
  • Sayfa Sayıları: ss.76-82

Ö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, randomkey 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.