Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2018.05.003

Upr. sist. maš., 2018, Issue 5 (277), pp. 3-12.

UDC 519.816

Tymofijeva Nadezhda К., Doctor of Engineering Sciences, International Research and Training Centre of Information Technologies and Systems of the NAS and MES of Ukraine, Glushkov ave., 40, Kyiv, 03187, Ukraine, E-mail: tymnad@gmail.com 

On some properties of the set of solutions of the salesman problem

Introduction. For a salesman problem, a method is described for ordering the routes (respectively and permutations) by subsets, which does not depend on the structure of the input data of a particular problem. For the resulting ordering, a strategy for determining those subsets that contain a global solution is developed.

Formulation of the problem. Known methods for finding an optimal solution in combinatorial optimization problems are to develop a strategy for removing ineffective solutions and to establish the dependence of the objective function value on input data that are random in nature. As their analysis shows in the process of these approaches, the same problem arises, namely: the development of a strategy for partitioning the set of values of the objective function into a subset, followed by the exclusion of those subsets that do not contain an optimal solution.

The proposed approach. In this article, a strategy for eliminating ineffective solutions is developed, which consists in not splitting the set of values of the objective function into a subset, but the set of routes of the salesman problem independently of the input data. It is shown that depending on various combinations of elements of the matrix, which is the input data, the set of routes in the salesman problem is divided into the same subset for different individual problems with different structure of input data. Accordingly, a similar set of subsets arranges a set of permutations. Routes for which the objective function acquires either the largest or the smallest values can be in different such subsets. They can contain elements of the matrix, selected from its various cells, that is, do not intersect. A number of theorems are presented, which prove that the use of this property allows to narrow the search domain of the optimal solution. The subclasses of solvable problems show how the global result varies depending on the structure of the input data. Depending on the input data, the global minimum and maximum may belong to different subsets. It is proved that for similar structures the global minimum and maximum for the salesman problem are found in the same subsets.

Conclusion. Studying the regularity of changing the values of the objective function from different inputs data allows us to develop strategies for finding the same subsets that contain a global solution for similar structures. In developing algorithms based on the method of “closest city” (or “greedy algorithm”), it is necessary to search for an optimal solution for all subsets, since these approaches can find the result far from optimal.

Download full text! (In Ukrainian).

Keywords: symmetry of combinatorial sets, traveling salesman problem, combinatorial configuration, combinatorial optimization, objective function.

1. Sigal, I.Kh., 1990. Diskretnyye modeli i metody resheniya zadach tipa kommivoyazhera bol’shoy razmernosti: issledovaniye, kombinirovannyye algoritmy, vychislitel’nyy eksperiment, primeneniya. Avtoref. dis. … dokt. tekhn. nauk. Vychislitel’nyy tsentr RAN. M., 33 p. (In Russian).
2. Belov, I.S., 2004. “Al’ternirovannaya zadacha kommivoyazhera”. Dop. NAN Ukrainy, 8, pp. 15-19. (In Russian).
3. Sergeyev, S.I., 1994. “Vychislitel’nyye algoritmy resheniya zadachi kommivoyazhera. 1. Obshchaya skhema klassifikatsii”. Avtomatika i telemekhanika, 5, pp. 66–79. (In Russian).
4. Timofeyeva, N.K., 1990. “O gamil’tonovom tsikle i zadache kommivoyazhera”. In-t kibernetiki im.V.M. Glushkova AN USSR. K., 29 p. [Dep. v VINITI 14.11.90, n 5742–V90. Ref. v: Matematika, 1991]. (In Russian).
5. Timofeyeva, N.K., 1990. “Optimizatsiya funktsii tseli v zadache kommivoyazhera”. In-t kibernetiki im.V.M. Glushkova NAN USSR. K., 35 p. [Dep. v VINITI 12.90, n 6499–V90. Ref. v: Matematika. 1991. 5]. (In Russian).
6. Kabadi Santosh N, 2002. “New polynomially solvable classes and a new henristic for the travelling salesman problem and its generalization”. Discrete Appl. Math., 119, 1–2, pp. 149–167.
7. Oda Yoshiaki, 2002. “An asymmetric analog of van der Veen conditions and the traveling salesman problem”. II. Eur. J. Oper. Res., 138 (1), pp. 43-62.
   https://doi.org/10.1016/S0377-2217(01)00141-2
8. Jonsson Hakan, 2002. “The travelling salesman problem for lines in the plane”. Inf. Process. Lett., 82 (3), pp. 137–142.
   https://doi.org/10.1016/S0020-0190(01)00259-9
9. Vagner, G., 1972. Osnovy issledovaniya operatsiy. Per. s angl. V 2 t. M.: Mir, T.1. 336 p.; T. 2. 488 p.
10. Papadimitriu, Kh., Stayglits, K., 1985. Kombinatornaya optimizatsiya. Algoritmy i slozhnost’. Per. s angl. M.: Mir, 510 p. (In Russian).
11.  Bellman, R., 1960. Dinamicheskoye programmirovaniye. M.: Izd-vo inostrannoy literatury, 400 p. (In Russian).
12.  Korbut, A.A., Finkel’shteyn, Yu.Yu., 1969. Diskretnoye programmirovaniye. M.: Nauka, 368 p. (In Russian).
13.  Sergiyenko, I.V., Shilo, V.P., 2003. Zadachi diskretnoy optimizatsii. Problemy, metody resheniya, issledovaniya. K.: Nauk. dumka, 261 p. (In Russian).
14. Tymofiyeva, N.K., 2007. Teoretyko-chyslovi metody rozv’yazannya zadach kombinatornoyi optymizatsiyi. Dysertatsiya na zdobuttya naukovoho stupenya doktora tekhnichnykh nauk za spetsialʹnistyu 05.02 – matematychne modelyuvannya ta obchyslyuvalʹni metody. Rukopys. IK im. V.M. Hlushkova NAN Ukrayiny, Kyyiv, 374 p. (In Ukrainian).
15. Zykov, A.A., 1987. Osnovy teorii grafov. M.: Nauka, 381 p. (In Russian).

Received 12.11.18