Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Pamukkale University
2018-02-01
|
| Series: | Pamukkale University Journal of Engineering Sciences |
| Subjects: | |
| Online Access: | https://dergipark.org.tr/tr/pub/pajes/issue/35876/400799 |
| _version_ | 1797914596297670656 |
|---|---|
| author | Vildan Özkır Burak Topçu |
| author_facet | Vildan Özkır Burak Topçu |
| author_sort | Vildan Özkır |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-10T12:28:55Z |
| format | Article |
| id | doaj.art-7459dbca78ef45389e5d5e6b334d1dec |
| institution | Directory Open Access Journal |
| issn | 1300-7009 2147-5881 |
| language | English |
| last_indexed | 2024-04-10T12:28:55Z |
| publishDate | 2018-02-01 |
| publisher | Pamukkale University |
| record_format | Article |
| series | Pamukkale University Journal of Engineering Sciences |
| spelling | doaj.art-7459dbca78ef45389e5d5e6b334d1dec2023-02-15T16:15:01ZengPamukkale UniversityPamukkale University Journal of Engineering Sciences1300-70092147-58812018-02-012417682218Application of the random key based electromagnetism-like heuristic for solving travelling salesman problemsVildan ÖzkırBurak TopçuAmong 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.https://dergipark.org.tr/tr/pub/pajes/issue/35876/400799electromagnetism-like heuristictraveling salesman problemsuncapacitated vehicle routingelektromanyetizma sezgiseli. gezgin satıcı problemikapasite kısıtsız araç rotalama |
| spellingShingle | Vildan Özkır Burak Topçu Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems Pamukkale University Journal of Engineering Sciences electromagnetism-like heuristic traveling salesman problems uncapacitated vehicle routing elektromanyetizma sezgiseli. gezgin satıcı problemi kapasite kısıtsız araç rotalama |
| title | Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems |
| title_full | Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems |
| title_fullStr | Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems |
| title_full_unstemmed | Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems |
| title_short | Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems |
| title_sort | application of the random key based electromagnetism like heuristic for solving travelling salesman problems |
| topic | electromagnetism-like heuristic traveling salesman problems uncapacitated vehicle routing elektromanyetizma sezgiseli. gezgin satıcı problemi kapasite kısıtsız araç rotalama |
| url | https://dergipark.org.tr/tr/pub/pajes/issue/35876/400799 |
| work_keys_str_mv | AT vildanozkır applicationoftherandomkeybasedelectromagnetismlikeheuristicforsolvingtravellingsalesmanproblems AT buraktopcu applicationoftherandomkeybasedelectromagnetismlikeheuristicforsolvingtravellingsalesmanproblems |