Research Article
BibTex RIS Cite

Gezgin Hırsız Problemi için Matematiksel Model ve Genetik Algoritma

Year 2024, Issue: 53, 71 - 83, 15.02.2024

Abstract

Bu makalede, iyi bilinen iki kombinatoryal optimizasyon problemi, yani Gezgin Satıcı Problemi (GSP) ve Sırt Çantası Probleminin (SÇP) birleşimi olan Gezgin Hırsız Problemi (GHP) ele alınmıştır. Bu tür çok bileşenli optimizasyon problemlerinin çözülmesi sadece içerdiği katı optimizasyon problemleri nedeniyle değil, özellikle farklı bileşenler arasındaki karşılıklı bağımlılıklar nedeniyle de zordur. Bu problemin amacı, bir hırsızın tüm şehirleri ziyaret ettiği ve maksimum faydayı elde etmek için hangi şehirden hangi eşyanın alınması gerektiğini belirleyen bir toplama planını oluşturmaktır. Ele alınan problem için matematiksel model geliştirilmiş ve büyük boyutlu problemlerin önerilen matematiksel model ile çözülememesi nedeniyle iki farklı genetik algoritma geliştirilmiştir. Geliştirilen algoritmaların performansları farklı özelliklerdeki test problemleri kullanılarak test edilmiştir.

References

  • Klamroth, K., Mostaghim, S., Naujoks, B., Poles, S., Purshouse, R., Rudolph, G., Ruzika, S., Sayın, S., Wiecek, M.M., Yao, X., 2017. Multiobjective optimization for interwoven systems. Journal of MultiCriteria Decision Analysis 24, 71–81.
  • Bonyadi, M.R., Michalewicz, Z., Wagner, M., Neumann, F., 2019. Evolutionary Computation for Multicomponent Problems: Opportunities and Future Directions. Springer. pp. 13–30.
  • Michalewicz Z (2012) Quo vadis, evolutionary computation? On a growing gap between theory and practice. In: Advances in computational intelligence. Lecture notes in computer science, vol. 7311. Springer, Berlin, pp 98–121
  • Bonyadi M, Michalewicz Z, Barone L (2013) The travelling thief problem: the first step in the transition from theoretical problems to realistic problems. In: Proceedings of the 2013 IEEE congress on evolutionary computation, Cancun, Mexico, pp 1037–1044
  • Polyakovskiy et al. (2014) Polyakovskiy S, Bonyadi MR, Wagner M, Michalewicz Z, Neumann F. A comprehensive benchmark set and heuristics for the traveling thief problem. In: Arnold DV, editor. Genetic and Evolutionary Computation Conference, GECCO ’14. New York: ACM; 2014. pp. 477–484.
  • Reinelt (1991) Reinelt G. TSPLIB: a traveling salesman problem library. INFORMS Journal of Computing. 1991;3(4):376–384. doi: 10.1287/ijoc.3.4.376.

Mathematical Model and Genetic Algorithm for the Traveling Thief Problem

Year 2024, Issue: 53, 71 - 83, 15.02.2024

Abstract

In this article, two well-known combinatorial optimization problems are discussed, namely the Traveling Thief Problem (TTP), which is a combination of the Traveling Salesman Problem (TSP) and the Knapsack Problem (KP). Deciphering such multicomponent optimization problems is difficult not only because of the strict optimization problems involved, but also because of the interdependencies between the different components in particular. The purpose of this problem is to form a collection plan, according to which a thief visits all cities and determines which items should be taken from which city in order to get the maximum benefit. A mathematical model has been developed for the problem under consideration, and two different genetic algorithms have been developed because large-sized problems cannot be solved with the proposed mathematical model. The performances of the developed algorithms were tested using test problems of different properties.

References

  • Klamroth, K., Mostaghim, S., Naujoks, B., Poles, S., Purshouse, R., Rudolph, G., Ruzika, S., Sayın, S., Wiecek, M.M., Yao, X., 2017. Multiobjective optimization for interwoven systems. Journal of MultiCriteria Decision Analysis 24, 71–81.
  • Bonyadi, M.R., Michalewicz, Z., Wagner, M., Neumann, F., 2019. Evolutionary Computation for Multicomponent Problems: Opportunities and Future Directions. Springer. pp. 13–30.
  • Michalewicz Z (2012) Quo vadis, evolutionary computation? On a growing gap between theory and practice. In: Advances in computational intelligence. Lecture notes in computer science, vol. 7311. Springer, Berlin, pp 98–121
  • Bonyadi M, Michalewicz Z, Barone L (2013) The travelling thief problem: the first step in the transition from theoretical problems to realistic problems. In: Proceedings of the 2013 IEEE congress on evolutionary computation, Cancun, Mexico, pp 1037–1044
  • Polyakovskiy et al. (2014) Polyakovskiy S, Bonyadi MR, Wagner M, Michalewicz Z, Neumann F. A comprehensive benchmark set and heuristics for the traveling thief problem. In: Arnold DV, editor. Genetic and Evolutionary Computation Conference, GECCO ’14. New York: ACM; 2014. pp. 477–484.
  • Reinelt (1991) Reinelt G. TSPLIB: a traveling salesman problem library. INFORMS Journal of Computing. 1991;3(4):376–384. doi: 10.1287/ijoc.3.4.376.
There are 6 citations in total.

Details

Primary Language Turkish
Subjects Engineering
Journal Section Articles
Authors

Kübra Yıldırım 0000-0002-1022-0416

Muzaffer Kapanoğlu 0000-0002-8217-7517

Early Pub Date February 6, 2024
Publication Date February 15, 2024
Published in Issue Year 2024 Issue: 53

Cite

APA Yıldırım, K., & Kapanoğlu, M. (2024). Gezgin Hırsız Problemi için Matematiksel Model ve Genetik Algoritma. Avrupa Bilim Ve Teknoloji Dergisi(53), 71-83.