Traveling Salesman Problem Optimization with Local Search Section Updated Bees Algorithm

Abstract

Solving traveling salesman problems with many connections with classical optimization methods is challenging. In this context, meta-heuristic algorithms that direct their searches to an optimum solution are preferred. In this study, the Bee Algorithm, one of these meta-heuristic algorithms inspired by the foraging methods of honey bees, was examined. The study aims to increase the Bees Algorithm's effectiveness in solving traveling salesman problems. The Variable Multiple Insertion operator has been added to the Classical Bee Algorithm, and optimizations have been made for different traveling salesman problems by searching within close neighborhood regions. As a result of the tests, it was seen that much better results were obtained with this algorithm compared to other Bee Algorithms in the literature. The algorithm has reduced from 1.40-2.80% to 0.11-0.50% in problems of 100 cities and from 8.10-9.67% to 2.00-2.79% in issues of 200 cities.

Keywords

• The bees algorithm
• Optimization
• The traveling salesman problem
• Variable multiple insertion
• neighborhood

Yerel Arama Bölümü Güncellenmiş Arı Algoritması ile Gezgin Satıcı Problemi Optimizasyonu

Abstract

Klasik optimizasyon yöntemleri ile çok sayıda bağlantıya sahip gezgin satıcı problemlerinin çözülebilmesi zordur. Bu kapsamda, aramalarını optimum bir çözüme yönlendiren meta-sezgisel algoritmalar tercih edilmektedir. Bu çalışmada, bu meta-sezgisel algoritmalardan biri olan ve bal arılarının yiyecek arama yöntemlerinden esinlenerek geliştirilen Arı Algoritması incelenmiştir. Çalışmanın amacı, Arı Algoritmasının gezgin satıcı problemlerinin çözümüne yönelik etkinliğinin artırılmasıdır. Klasik Arı Algoritması içerisine Değişken Çoklu Ekleme operatörü eklenmiş ve yakın komşuluk bölgeleri içerisinde arama yapılarak, farklı gezgin satıcı problemleri için testler yapılmıştır. Yapılan testler sonucunda bu algoritma ile literatürdeki diğer Arı Algoritmalarına göre çok daha iyi sonuçlar elde edildiği görülmüştür. Geliştirilen algoritma ile 100 şehirlik problemlerde sapma değerleri %1,40-2,80 aralığından %0,11-0,50 aralığına ve 200 şehirlik problemlerde de %8,10-9,67 aralığından %2.00-2,79 aralığına indirildiği gözlemlenmiştir.

Keywords

• Arı algoritması
• Değişken çoklu ekleme
• Gezgin satıcı problemi
• Komşuluk
• Optimizasyon

References

1. Acar, O., Kalyoncu, M., Hassan, A. (2018). The Bees’ Algorithm for Design Optimization of a Gripper Mechanism, Journal of Selcuk-Technic (ICENTE’18) Special Issue, 69-86.
2. Ahmed, Z. H. (2010). Genetic Algorithm for the Traveling Salesman Problem Using Sequential Constructive Crossover Operator. International Journal of Biometrics ve Bioinformatics (IJBB), 3(6), 96–105. doi: 10.14569/IJACSA.2020.0110275.
3. Al-Furhud, M. A., Ahmed, Z. H. (2020). Genetic Algorithms for the Multiple Travelling Salesman Problem. (IJACSA) International Journal of Advanced Computer Science and Applications, Vol. 11, No. 7, pp. 553-560.
4. Alzaqebah, M., Jawarneh, S., Sarim, H. M., Abdullah, S. (2018). Bees Algorithm for Vehicle Routing Problems with Time Windows, International Journal of Machine Learning and Computing, Vol. 8, No. 3, 236-240.
5. Baronti, L., Castellani, M., Pham, D. T. (2020). An analysis of the search mechanisms of the bees algorithm, Swarm and Evolutionary Computation, 59, 100746.
6. Bayraktar, T., Ersöz, F., & Kubat, C. (2021). Effects of Memory and Genetic Operators on Artificial Bee Colony Algorithm for Three-Dimensional Bin Packing Problem (No. 5754). EasyChair.
7. Braiwish, N. Y., Anayi, F. J., Fahmy, A. A., Eldukhri, E. E. (2014). Design optimisation of Permanent Magnet Synchronous Motor for electric vehicles traction using the Bees Algorithm, 49th International Universities Power Engineering Conference (UPEC), Cluj-Napoca, Romania.
8. Daoqing, Z., Mingyan, J. (2020). Parallel Discrete Lion Swarm Optimization Algorithm for Solving Traveling Salesman Problem. Journal of Systems Engineering and Electronics, Vol. 31, No. 4, pp.751 – 760.

9. Coban, R., Ercin, O. (2012). Multi-objective Bees Algorithm to Optimal Tuning of PID Controller, Çukurova University Journal of the Faculty of Engineering and Architecture, 27(2), 13-26.
10. Dong, X., Lin, Q., Xu, M., Cai, Y. (2019). Artificial bee colony algorithm with generating neighbourhood solution for large scale coloured traveling salesman problem. IET Intelligent Transport Systems, Vol. 13 Iss. 10, pp. 1483-1491.
11. Erdem, E., Aydın, T., & Erkayman, B. (2021). Flight scheduling incorporating bad weather conditions through big data analytics: A comparison of metaheuristics. Expert Systems, 38(8), e12752.
12. Hussain, K., Salleh, M. N. M., Cheng, S., Shi, Y. (2019). Metaheuristic research: a comprehensive survey, Artificial Intelligence Review, volume 52, 2191–2233.
13. Internet: The TSPLIB Symmetric Traveling Salesman Problem Instances, http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsp/index.html, 22.12.2020.
14. Ismail, A. H., Hartono, N., Zeybek, S., Pham, D. T. (2020). Using the Bees Algorithm to solve combinatorial optimisation problems for TSPLIB, IOP Conf. Series: Materials Science and Engineering 847, 1-9.
15. Karaboga, D., Gorkemli, B. (2019). Solving Traveling Salesman Problem by Using Combinatorial Artificial Bee Colony Algorithms, International Journal on Artificial Intelligence Tools Vol. 28, No. 1, 1950004, 1-28.
16. Khan, S., Asjad, M., Ahmad, A., (2015). Review of Modern Optimization Techniques. International Journal of Engineering and Technical Research V4(04), 984-988.
17. Koc E. (2010). Bees algorithm: theory, improvements and applications Thesis (Cardiff University, UK).
18. Manea,D., Titan, E., Serban, R. R., Mihai, M. (2019). Statistical applications of optimization methods and mathematical programming. Proceedings of the International Conference on Applied Statistics 1(1), 312-328.
19. Mavrovouniotis, M., Müller, F. M., Yang, S. (2017). Ant Colony Optimization With Local Search for Dynamic Traveling Salesman Problems. IEEE Transactions on Cybernetics, Vol. 47, No. 7, pp. 1743-1756.
20. Mollabakhshi, N., Eshghi, M. (2013). Combinational circuit design using bees algorithm, IEEE Conference Anthology, China.
21. Nafchi, A. M., Moradi, A., Ghanbarzadeh, A., Yaghoubi, S., Moradi, M. (2012). An Improved Bees Algorithm For Solving Optimization Mechanical Problems, 20th Annual International Conference on Mechanical Engineering-ISME, School of Mechanical Eng., Shiraz University, Shiraz, Iran.
22. Otri S. (2011). Improving the bees algorithm for complex optimisation problems Thesis (Cardiff University, UK).
23. Pham, D.T., Ghanbarzadeh, A., Koc, E., Otri, S., Rahim, S., Zaidi, M. (2006). The Bees Algorithm-A Novel Tool for Complex Optimisation Problems, Intelligent production machines and systems, 454-459.
24. Rao, S., S. (2019). Engineering Optimization Theory and Practice. John Wiley & Sons, New Jersey, A.B.D.
25. Xie, J., Carrillo, L. R. G., Jin, L. (2019). An Integrated Traveling Salesman and Coverage Path Planning Problem for Unmanned Aircraft Systems. IEEE Control Systems Letters, Vol. 3, No. 1, pp. 67-72.
26. Wang, L., Cai, R., Lin, M., Zhong, Y. (2019). Enhanced List-Based Simulated Annealing Algorithm for Large-Scale Traveling Salesman Problem. IEEE Access Year: 2019 | Volume: 7, pp. 144366-144380.
27. Yuce, B., Mastrocinque, E., Lambiase, A., Packianather, M. S., Pham, D. T. (2014). A multi-objective supply chain optimisation using enhanced Bees Algorithm with adaptive neighbourhood search and site abandonment strategy, Swarm and Evolutionary Computation Volume 18, October, 71-82.
28. Zarchi, M., Attaran, B. (2017). Performance improvement of an active vibration absorber subsystem for an aircraft model using a bees algorithm based on multi-objective intelligent optimization, Engineering Optimization Volume 49, Issue 11, 1905-1921.
29. Zeybek S., A. H. Ismail, N. Hartono, M. Caterino, K. Jiang. (2021). An Improved Vantage Point Bees Algorithm to Solve Combinatorial Optimization Problems from TSPLIB, Macromolecular Symposia, 396, 2000299, pp. 1–4.