Proceeding of the Faculty of technical Sciences, Novi Sad

Mechatronics

Vol. 40 No. 11 (2025): Proceedings of the Faculty of Technical Sciences

GENETIC ALGORITHM FOR THE TIME-LIMITED PRIZE-COLLECTING TRAVELING SALESMAN PROBLEM

  • Јелена Ћурчић
DOI:
https://doi.org/10.24867/32IH02Curcic
Submitted
November 10, 2025
Published
2026-03-09

Abstract

This paper analyzes the synthesis of an optimal strategy for the Eurobot robotics competition using a genetic algorithm. The primary objectives of the research are the development of an efficient algorithm and the optimization of the strategy for specific tasks. The tasks and constraints that must be integrated into the generated strategy are defined. The problem is modeled as a variation of the prize collecting traveling salesman problem. Various cases with different types of constraints and parameters of the genetic algorithm were analyzed, and their effectiveness was compared.

References

  1. [1] M. Sipser, „Introduction to the Theory of Computation“, 3rd ed., Cengage Learning, 2012
  2. [2] M. Garey, S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-Completeness”, 1st ed., W. H. Freeman, 1979
  3. [3] T. Baker, J. Gill, R. Solovay, „Relativizations of P =? NP question“, SIAM Journal on Computing, vol. 4, no. 4, pp. 431–442, Dec. 1975, doi: https://doi.org/10.1137/0204037.
  4. [4] D. S. Johnson, “The NP-Completeness Column: An Ongoing Guide”, Journal of Algorithms, vol. 7, no. 4, pp. 584–601, Dec. 1986, doi: https://doi.org/10.1016/0196-6774(86)90020-9.
  5. [5] EUROBOT 2024 rules, https://www.eurobot.org/eurobot-contest/eurobot-2024/ (приступ: септембар 2024)
  6. [6] B. Bryson, “The Body”, Anchor, 2019
  7. [7] Ж. Кановић, З. Јеличић, М. Рапаић, „Еволутивни оптимизациони алгоритми у инжењерској пракси“, Нови Сад, ФТН, 2017.
  8. [8] Наставни материјали из предмета Методе оптимизације, http://www.automatika.ftn.uns.ac.rs/nastavni-materijali-mo-meh-geo (приступ: септембар 2024)