2024, issue 2, p. 31-38
Received 11.03.2024; Revised 25.04.2024; Accepted 28.05.2024
Published 09.06.2024; First Online 14.06.2024
https://doi.org/10.34229/2707-451X.24.2.3
On One Implementation of a Natural Approach to Solving the Traveling Salesman Problem
Dmitri Terzi 
Moldova State University, Chisinau, Moldova
Correspondence: This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduction. The relevance of the traveling salesman problem is associated with the need to develop computational schemes for use in situations that require the analysis of information of a sufficiently large volume. The versatility of research on the traveling salesman problem makes it possible to reveal many properties and identify the necessary conditions for the optimality of the solution. One of the approaches to theoretical and practical research is based on computer technology of the modified distribution method
Purpose. The goal of the work is to develop conditions for the optimality of the solution and the concept of three-element replacement operations to construct the corresponding algorithm and obtain an acceptable solution for a small number of operations used.
Results. The concept of a three-element replacement operation is introduced. A necessary condition for the optimality of this solution and a special method for constructing an admissible cyclic solution to the transport problem corresponding to the traveling salesman problem are given. The search for an optimal solution can be represented as a transition from one cyclic solution to another cyclic solution using three-element replacement operations. Such replacement operations are performed for zero elements of an admissible solution with a positive value of the evaluation matrix.
Conclusions. Due to the emergence of discrete optimization problems with the need to analyze a sufficiently large amount of information, the development of new computational schemes that give consistently good results is required. Research in this direction is carried out on the example of the traveling salesman problem, for which, with the use of three-element replacement operations, it is possible to obtain an acceptable solution to the problems.
Keywords: modified distribution method, three-element replacement operation, natural approach, traveling salesman problem.
Cite as: Terzi D. On One Implementation of a Natural Approach to Solving the Traveling Salesman Problem. Cybernetics and Computer Technologies. 2024. 2. P. 31–38. https://doi.org/10.34229/2707-451X.24.2.3
References
1. Lazarev A.A., Werner F., et al. Special Issue “Recent Advances of Discrete Optimization and Scheduling”. Mathematics. 2024. 12. 793. https://doi.org/10.3390/math12060793
2. https://www.researchgate.net/topic/Travelling-Salesman-Problem/publications (accessed: 01.03.2024)
3. Minu M. Mathematical programming. Theory and algorithms. M.: Nauka, 1990.
4. Terzi D. A Natural Approach to Solving the Traveling Salesman Problem. Cybernetics and Computer Technologies. 2023. No. 4. P. 43–51. https://doi.org/10.34229/2707-451X.23.4.6
5. MATLAB Programming Fundamentals, R2023a, MathWorks, 2023. https://www.mathworks.com/products/ matlab.html (accessed: 01.03.2024)
ISSN 2707-451X (Online)
ISSN 2707-4501 (Print)