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

Abstract

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.

Keywords

• Elektromanyetizma sezgiseli. Gezgin satıcı problemi,Kapasite kısıtsız araç rotalama

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

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.

Keywords

• Electromagnetism-like heuristic,Traveling salesman problems,Uncapacitated vehicle routing

References

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, Javadi B. “An Electromagnetism-like algorithm for cell formation and layout problem”. Expert Systems with Applications, 39, 2172-2182, 2012.
17. Jun-Man K, Yi Z. “Application of an Improved Ant Colony Optimization on Generalized Traveling Salesman Problem”. Expert Systems with Applications, 17, 319-325, 2012.
18. Lin Y, Yeh CH, Huang PS. “A hybrid ant-tabu algorithm for solving a multistate flow network reliability maximization problem”. Applied Soft Computing, 13(8), 3529-3543, 2013.
19. Lin Y, Bian Z, Liu X. “Developing a dynamic neighborhood structure for an adaptive hybrid simulated annealing-tabu search algorithm to solve the symmetrical traveling salesman problem”. Applied Soft Computing, 49, 937-952, 2016.
20. Mantawy AH, Abdel-Magid YL, Selim SZ. “A new genetic-based tabu search algorithm for unit commitment problem”. Electric Power Systems Research, 49(2), 71-78, 1999.
21. Maenhout B, Vanhoucke M. “An electromagnetic meta-heuristic for the nurse-scheduling problem”. Journal of Heuristics, 13, 359-385, 2007.
22. Masutti TAS, Castro LND. “A self-organizing neural network using ideas from the immune system to solve the traveling salesman problem”. Information Sciences, 179(10), 1454-1468, 2009
23. Naji-Azimi Z, Toth P, Galli L. “An electromagnetism metaheuristic for the unicost set covering problem”. European Journal of Operational Research, 205, 290-300, 2010.
24. Nagata Y, Soler D. “A new genetic algorithm for the asymmetric traveling salesman problem”. Expert Systems with Applications, 39, 8947-8953, 2012.
25. Osaba E, Yang XS, Diaz F, Lopez-Garcia P, Carballedo R. “An improved discrete bat algorithm for symmetric and asymmetric traveling salesman problems”. Engineering Applications of Artificial Intelligence, 48, 59-71, 2016.
26. Pasti R, Castro LND. “A neuro-immune network for solving the traveling salesman problem”. International Joint Conference on Neural Networks, Vancouver, Canada, 16-21 July 2006.
27. Pedro O, Saldanha R. “A Tabu Search Approach for the Prize Collecting Traveling Salesman Problem”. Electronic Notes in Discrete Mathematics, 41, 261-268, 2013.
28. Ramtake D, Kumar S, Patle VK. “Route Optimization by Ant Colony Optimization Technique”. Procedia Computer Science, 92, 48-55, 2016.
29. Rego C, Gamboa D, Glover F, Osterman, C. “Traveling salesman problem heuristics: Leading methods, implementations and latest advances”. European Journal of Operational Research, 211, 3, 2011, 427-441, 2011.
30. Sels V, Vanhoucke M. “A hybrid Electromagnetism-like Mechanism/tabu search procedure for the single machine-scheduling problem with a maximum lateness objective”. Computers and Industrial Engineering, 67, 44-55, 2010.
31. Shi XH, Liang YC, Lee HP, Lu C, Wang QX. “Particle swarm optimization-based algorithms for TSP and generalized TSP”. Information Processing Letters, 103, 169-176, 2007.
32. Snyder LV, Daskin MS. “A random-key genetic algorithm for the generalized traveling salesman problem”. European Journal of Operational Research, 174(1) 38-53, 2006.
33. Somhom S, Modares A, Enkawa T. “A self-organizing model for the traveling salesman problem”. Journal of the Operational Research Society, 48(4-6), 919-928, 1997.
34. Taheri SH, Ghazvini H, Saberi-Nadjafi J, Biazar J. “A hybrid of the restarted Arnoldi and electromagnetism meta-heuristic methods for calculating eigenvalues and eigenvectors of a non-symmetric matrix”. Applied Mathematics and Computation, 191, 79-88, 2007.
35. Tasgetiren MF, Sevkli M, Liang YC, Gencyilmaz G. “Particle swarm optimization algorithm for makespan and total flowtime minimization in permutation flowshop sequencing problem”. European Journal of Operational Research, 177(3), 1930-1947, 2007.
36. Teimouri M, Zaretalab A, Niaki STA, Mani Sharifi M. “An efficient memory-based electromagnetism-like mechanism for the redundancy allocation problem”. Applied Soft Computing, 38, 423-436, 2016.
37. Wang KJ, Adrian AM, Chen KH, Wang KM. “An improved electromagnetism-like mechanism algorithm and its application to the prediction of diabetes mellitus”. Journal of Biomedical Informatics, 54, 220-229, 2015.
38. Wu P, Yang KJ, Huang BY. “A revised EM-like mechanism for solving the vehicle routing problems”. 2nd International Conference on Innovative Computing, Information and Control 2007-ICICIC '07 Proceedings 181, Kumamoto, 5-7 September 2007.
39. Yıldırım T, Kalaycı CB, Mutlu Ö. “A novel metaheuristic for traveling salesman problem: blind mole-rat algorithm”. Pamukkale Üniversitesi Mühendislik Bilimleri Dergisi, 22(1), 2016, 67-70.
40. Yurtkuran A, Emel E. “A new hybrid electromagnetism-like algorithm for capacitated vehicle routing problems”. Expert Systems with Applications, 37, 3427-3433, 2010.
41. Zhang H, Zhou J. “Dynamic multiscale region search algorithm using vitality selection for traveling salesman problem”. Expert Systems with Applications, 60, 81-95, 2016.