Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems
| Autor: | Burak Topçu, Vildan Özkır |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Mathematical optimization
kapasite kısıtsız araç rotalama lcsh:TA1-2040 Electromagnetism Heuristic (computer science) Computer science Key (cryptography) uncapacitated vehicle routing lcsh:Engineering (General). Civil engineering (General) traveling salesman problems Travelling salesman problem electromagnetism-like heuristic elektromanyetizma sezgiseli. gezgin satıcı problemi |
| Zdroj: | Pamukkale University Journal of Engineering Sciences, Vol 24, Iss 1, Pp 76-82 (2018) |
| ISSN: | 2147-5881 1300-7009 |
| DOI: | 10.5505/pajes.2017.85698 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|