Application of the random key based electromagnetism-like heuristic for solving travelling salesman problems
| Autor: | Vildan Özkır, Burak Topçu |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2016 |
| Předmět: |
kapasite kısıtsız araç rotalama
Elektromanyetizma sezgiseli. Gezgin satıcı problemi Kapasite kısıtsız araç rotalama Engineering lcsh:TA1-2040 Electromagnetism-like heuristic Traveling salesman problems Uncapacitated vehicle routing Mühendislik uncapacitated vehicle routing lcsh:Engineering (General). Civil engineering (General) traveling salesman problems electromagnetism-like heuristic elektromanyetizma sezgiseli. gezgin satıcı problemi |
| Zdroj: | Volume: 24, Issue: 1 76-82 Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi Pamukkale University Journal of Engineering Sciences, Vol 24, Iss 1, Pp 76-82 (2018) |
| ISSN: | 1300-7009 2147-5881 |
| Popis: | Ağ optimizasyonuproblemleri 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 çoksezgisel 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 ilhamalan, popülasyon tabanlı global bir arama algoritmasıdır. Önerilen mekanizma,fizibil alanda rassal olarak oluşturulan partikülleri optimal çözümeyaklaştırma prensibine dayanır. Bu çalışmada, araç rotalama problemleriniçözebilmek için rassal anahtar yaklaşımı elektromanyetizma sezgiseline adapteedilmiştir. 15 kıyaslama örneği üzerinde test edilen sezgisel yöntem küçük boyuttakiproblemler 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ınetkinliği, önerilen algoritmanın kombinatoryal optimizasyon problemleri çözümüiçin de değerlendirilebileceğini göstermektedir. Amongnetwork optimization problems, travelling salesman problem is widely studiedone in the literature. Since the problem is computationally hard, manyheuristics have been developed to obtain the optimal solution in reasonabletime. This paper introduces a hybrid electromagnetism-like heuristics to solvesymmetric travelling salesman problems. Originally, electromagnetism-likeheuristic is a population based global search algorithm that is inspired byelectromagnetism theory in Physics. The proposed mechanism is based on theprinciple of encouraging randomly generated particles to move toward to optimalsolution in the feasible area. In this paper, random-key approach is adapted toelectromagnetism-likeheuristic 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 proposedalgorithm generates near optimal solutions. Efficiency of results shows that theproposed algorithm can be evaluated for the solution of combinatorialoptimization problems. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|