ON THE RECURSIVE ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM ON THE BASIS OF THE DATA FLOW OPTIMIZATION METHOD

Authors

  • E. V. Ivohin Taras Shevchenko National University of Kyiv, Kyiv, Ukraine , Ukraine
  • V. V. Gavrylenko National Transport University, Kyiv, Ukraine, Ukraine
  • K. E. Ivohina National Transport University, Kyiv, Ukraine, Ukraine

DOI:

https://doi.org/10.15588/1607-3274-2023-3-14

Keywords:

traveling salesman problem, resource allocation method, recursive backtracking scheme, greedy approach

Abstract

Context. The article considers a technique for the sequential application of flow schemes for distributing a homogeneous resource for solving the traveling salesman problem, which is formulated as the problem of finding a route to visit a given number of cities without repetitions with a minimum duration of movement. The task of formalizing the algorithm for solving the traveling salesman problem by the method of streaming resource distribution using the backtracking scheme is posed. The use of Orlin’s method to optimize the flow distribution on the graph is proposed.

Objective. The goal of the work is to develop an algorithm for solving the traveling salesman problem based on the implementation of the method of streaming resource distribution and the backtracking scheme with the minimum duration of movement along the route.

Method. This paper proposes a method for solving the traveling salesman problem by the method of streaming resource distribution with the backtracking scheme. A scheme for formalizing the procedure for solving the traveling salesman problem with the minimum duration of movement along the route is described. A variant of accelerating the speed of the developed algorithm is proposed, which consists in using a greedy technique in the procedure for selecting route sections: planning each subsequent stage of movement is determined based on the choice of the fastest direction of movement. The results of the proposed algorithm for calculating solutions to the traveling salesman problem with minimization of the duration of movement are presented, the obtained solutions are compared with the solutions found by other exact and heuristic methods.

Results. The method for solving the traveling salesman problem using the method of streaming resource allocation and using the backtracking scheme is developed. A variant of accelerating the speed of the developed algorithm is proposed, which consists in using a greedy technique in the procedure for selecting route sections: planning each subsequent stage of movement is determined based on the choice of the fastest direction of movement. The application of the greedy approach makes it possible to obtain a constructive scheme for solving the traveling salesman problem. The results of the proposed algorithm for calculating solutions to the traveling salesman problem with minimization of the duration of movement are presented, the obtained solutions are compared with the solutions found by other exact and heuristic methods.

Conclusions. The paper considers a method for formalizing the algorithm for solving the traveling salesman problem using the method of streaming resource allocation and the backtracking scheme. The use of Orlin’s method to optimize the flow distribution on the graph is proposed. The scheme of formalization of the procedure for using the method with the implementation of the backtracking scheme for solving the traveling salesman problem with the minimum duration of movement along the route is briefly described. A variant of accelerating the speed of the developed algorithm is proposed.

Author Biographies

E. V. Ivohin, Taras Shevchenko National University of Kyiv, Kyiv, Ukraine

Dr. Sc., Professor, Professor of the Department of System Analysis and Decision Support Theory

V. V. Gavrylenko, National Transport University, Kyiv, Ukraine

Dr.Sc., Professor, Professor of the Department of Information Systems and Technologies

K. E. Ivohina, National Transport University, Kyiv, Ukraine

PhD Student of the Department of Information Systems and Technologies

References

Christopher M., Peck H. Building the Resilient Supply Chain, The Intern. Journal of Logistics Management, 2004, Vol. 15, No. 2, pp. 1–14. DOI:10.1108/09574090410700275

Alan Harrison, Remko van Hoek Logistics Management and Strategy. Financal Times Management, 3d edition, 2005, 308 р. ISBN: 978-0-273-71276-3

Ghiani G., Laporte G., Musmanno R. Introduction to Logistics Systems Planning and Control. John Wiley & Sons, Ltd, 2013, 377 р. DOI:10.1002/9781118492185

Vajda S. Linear programming. Dordrecht, Springer, 1981, 15 p. DOI: 10.1007/978-94-011-6924-0_1

Schrijver А. Theory of Linear and Integer Programming. Wiley, 1998, 484 p. DOI: 10.2307/253980

Vanderbei R. J. Linear programming: Foundations and extensions. Springer, 2014, 414 р. DOI: 10.1007/978-3-030-39415-8

Korte B., Vygen J. Combinatorial Optimization: Theory and Algorithms (Algorithms and Combinatorics). Berlin, Heidelberg, Springer, 2018, 455 p. DOI: 10.1007/978-3-662-56039-6

Moss L. T., Atre Shaku Business Intelligence Roadmap: The Complete Project Lifecycle for Decision-Support Applications. Addison-Wesley Professional, 2003, 576 p. ISBN: 978-0-20178420-6

Buontempo F. Genetic Algorithms and Machine Learning for Programmers. Pragmatic Bookshelf, 2019, 236 p. ISBN: 9781680506204

Kshemkalyani A. D., Singhal Mukesh Distributed Computing: Principles, Algorithms, and Systems. Cambridge University Press, 2008, 756 р. DOI: 10.1017/CBO9780511805318

Rai S., Ettam R. K. Simulation-based optimization using simulated annealing for optimal equipment selection within print production environments, 2013 Winter Simulation Conference: Simulation: Making Decisions in a Complex World, December, 2013: proceedings, 2013, pp. 1097–1108. DOI: 10.1109/WSC.2013.6721499

Orlin J. B. A Faster strongly polynomial minimum cost flow algorithm, Operations research, 1993, V. 41, Iss.2, pp. 338– 350. DOI: 10.1145/62212.62249

Watson D. A Practical Approach to Compiler Construction. Springer, 2017, 254 р. DOI: 10.1007/978-3-319-52789-5

Chvatal V., Cook W. J., Dantzig G. B., Dantzig G. B., Fulkerson D. R., Johnson S. M. Solution of a large-scale travelingsalesman problem, In 50 Years of Integer Programming 1958–2008. From the Early Years to the State-of-the-Art, 2010, pp. 7– 28. DOI: 10.1007/978-3-540-68279-0_1

Downloads

Published

2023-10-13

How to Cite

Ivohin, E. V., Gavrylenko, V. V., & Ivohina, K. E. (2023). ON THE RECURSIVE ALGORITHM FOR SOLVING THE TRAVELING SALESMAN PROBLEM ON THE BASIS OF THE DATA FLOW OPTIMIZATION METHOD. Radio Electronics, Computer Science, Control, (3), 141. https://doi.org/10.15588/1607-3274-2023-3-14

Issue

No. 3 (2023): Radio Electronics, Computer Science, Control

Section

Progressive information technologies

License

Copyright (c) 2023 Є. В. Івохін, В. В. Гавриленко, К.Є. Івохіна

Creative Commons License

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

Creative Commons Licensing Notifications in the Copyright Notices

The journal allows the authors to hold the copyright without restrictions and to retain publishing rights without restrictions.

The journal allows readers to read, download, copy, distribute, print, search, or link to the full texts of its articles.

The journal allows to reuse and remixing of its content, in accordance with a Creative Commons license СС BY -SA.

Authors who publish with this journal agree to the following terms:

  • Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License CC BY-SA that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

  • Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  • Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.