Parameter optimisation of the polynomial randomised algorithm for the asymmetric travelling salesman problem

  • Maksim S. Barketau United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surganava Street, Minsk 220012, Belarus

Abstract

The asymmetric travelling salesman problem without metric restrictions is herein considered. The polynomial randomised algorithm depending on the set of parameters is proposed similar to the one developed by the author in the article «Polinomial randomised algorithm for the asymmetric travelling salesman problem» (Doklady of the National Academy of Sciences of Belarus. 2022. Vol. 66, No. 5. P. 489 – 494). The difference of the proposed algorithm is in different parametrisation. The parameter optimisation is arranged with the help of the polynomial preprocessing algorithm.

Author Biography

Maksim S. Barketau, United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surganava Street, Minsk 220012, Belarus

PhD (physics and mathematics), docent; senior researcher at the laboratory of mathematical cybernetics

References

  1. Barketau MS. Polynomial randomised algorithm for the asymmetric travelling salesman problem. Doklady of the National Academy of Sciences of Belarus. 2022;66(5):489–494. Russian. DOI: 10.29235/1561-8323-2022-66-5-489-494.
  2. Arora S. Polynomial time approximation schemes for Euclidean TSP and other geometric problems. In: Proceedings of 37th Annual symposium on foundations of computer science; 1996 October 14–16; Burlington, USA. Los Alamitos: IEEE Computer Society Press; 1996. p. 2–11. DOI: 10.1109/sfcs.1996.548458.
  3. Svensson O. Approximating ATSP by relaxing connectivity. In: Proceedings of 2015 IEEE 56th Annual symposium on foundations of computer science (FOCS-2015); 2015 October 17–20; Berkeley, USA. Los Alamitos: Conference Publishing Services of the IEEE Computer Society; 2015. p. 1–19. DOI: 10.1109/focs.2015.10.
  4. Burke EK, Cowling PI, Keuthen R. Effective local and guided variable neighbourhood search methods for the asymmetric travelling salesman problem. In: Boers EJW, Cagnoni S, Gottlieb J, Hart E, Lanzi PL, Raidl GR, et al., editors. Applications of evolutionary computing. EvoWorkshops-2001: EvoCOP, EvoFlight, EvoIASP, EvoLearn, and EvoSTIM; 2001 April 18–20; Como, Italy. Berlin: Springer; 2001. p. 203–212 (Goos G, Hartmanis J, van Leeuwen J, editors. Lecture notes in computer science; volume 2037). DOI: 10.1007/3-540-45365-2_21.
  5. Fischetti M, Lodi A, Toth P. Exact methods for the asymmetric traveling salesman problem. In: Gutin G, Punnen AP, editors. The traveling salesman problem and its variations. New York: Springer; 2007. p. 169–205 (Du D-Z, Pardalos PM, editors. Combinatorial optimization; volume 12). DOI: 10.1007/0-306-48213-4_4.
  6. Grötschel M, Lovász L, Schrijver A. Geometric algorithms and combinatorial optimization. 2nd edition. Berlin: Springer-Verlag; 2012. XII, 362 p. (Graham RL, Korte B, Lovász L, editors. Algorithms and combinatorics; volume 2).
Published
2024-07-23
Keywords: combinatorial optimisation, probability theory, randomised algorithm, approximation algorithm, asymmetric travelling salesman problem
Supporting Agencies This work was carried out with partial financial support from the Belarusian Republican Foundation for Fundamental Research (projects F21-010 and F23RNF-017).
How to Cite
Barketau, M. S. (2024). Parameter optimisation of the polynomial randomised algorithm for the asymmetric travelling salesman problem. Journal of the Belarusian State University. Mathematics and Informatics, 2, 113-118. Retrieved from https://journals.bsu.by/index.php/mathematics/article/view/6327
Issue
No 2 (2024): Journal of the Belarusian State University. Mathematics and Informatics
Section
Short Communications

Copyright (c) 2024 Journal of the Belarusian State University. Mathematics and Informatics

Creative Commons License

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.

The authors who are published in this journal agree to the following:

  1. The authors retain copyright on the work and provide the journal with the right of first publication of the work on condition of license Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. The authors retain the right to enter into certain contractual agreements relating to the non-exclusive distribution of the published version of the work (e.g. post it on the institutional repository, publication in the book), with the reference to its original publication in this journal.
  3. The authors have the right to post their work on the Internet (e.g. on the institutional store or personal website) prior to and during the review process, conducted by the journal, as this may lead to a productive discussion and a large number of references to this work. (See The Effect of Open Access.)