SEQUENTIAL HYBRIDIZATION ALGORITHM FOR THE TRAVELING SALESMAN PROBLEM SOLVING
Abstract
The traveling salesman problem is a combinatorial optimization problem. The article presents
a statement of this problem and proposes a graph mathematical model in which vertices
correspond to cities, and edges are paths between cities, and it is assumed that the graph is
weighted. The solution of the traveling salesman problem consists in finding the minimum weight
Hamiltonian cycle in a complete weighted graph. The problem is NP-hard, so a heuristic approach
is used to solve this problem and speed up the solution of the problem on large volumes of
input data. The heuristic consists in applying hybridization of two algorithms to solve the traveling
salesman problem: the annealing simulation algorithm and the nearest neighbor algorithm. Sequential
hybridization scheme is used to solve the traveling salesman problem. The basic idea is
that the nearest neighbor method is launched on the initial set of solutions, and then the best solution
of the first stage is fed to the annealing simulation algorithm. The article details the construction,
flowcharts of the hybrid algorithm, the annealing simulation algorithm, and the nearest
neighbor method. The article goes on to describe the user interface of the application written in
Typescript. The application uses an area map as a solution to the traveling salesman problem. In
the last part of the article, a comparative analysis of the algorithms' performance is highlighted: a
comparison of the accuracy and operating time of the developed hybrid algorithm, the annealing simulation algorithm, and the nearest neighbor method for different input data sets. It was established
that the developed hybrid algorithm is in second place in terms of speed and in first place in
terms of solution quality among the implemented algorithms. In addition, the developed solution
has a high economic and practical value because an application for solving the traveling salesman
problem, and therefore an application for route navigation, can replace existing analogues or it
can be used in any narrowly focused areas, as well as in logistics.
References
Znanie, 1969, 64 p.
2. Karpenko A.P. Sovremennye algoritmy poiskovoy optimizatsii. Algoritmy, vdokhnovlennye
prirodoy [Modern search engine optimization algorithms. Algorithms inspired by nature].
Moscow: MGTU im. N.E. Baumana, 2014, 446 p.
3. Gladkov L.A., Kureychik V.V., Kureychik V.M. Geneticheskie algoritmy: ucheb. posobie [Genetic
algorithms: training manual]. 2nd ed. Moscow: Fizmatlit, 2006, 368 p.
4. Saymon D. Algoritmy evolyutsionnoy optimizatsii [Evolutionary optimization algorithms].
Moscow: Izd-vo: DMK Press, 2020, 1002 p.
5. Boroznov V.O. Issledovanie resheniya zadachi kommivoyazhera [Investigation of the solution
of the traveling salesman problem], Vestnik Astrakhanskogo gosudarstvennogo tekhnicheskogo
universiteta. Seriya: Upravlenie, vychislitel'naya tekhnika i informatika [Vestnik of Astrakhan
State Technical University. Series: Management, Computer Sciences and Informatics], 2009,
No. 2, pp. 147-151.
6. Kolesnikov A.V., Kirikov I.A., Listopad S.V. Reshenie slozhnykh zadach kommivoyazhera
metodami funktsional'nykh gibridnykh intellektual'nykh sistem [Listopad Solving complex
problems of a traveling salesman by methods of functional hybrid intelligent systems], ed. by
A.V. Kolesnikova. Moscow: IPI RAN, 2011, 295 p.
7. Morán-Mirabal L.F., González-Velarde J.L., Resende M.G.C. Randomized heuristics for the
family traveling salesperson problem, International Transactions in Operational Research,
2014, Vol. 21, Issue 1, pp. 41-57. DOI: 10.1111/itor.12026.
8. Nagata Y. High-Order Entropy-Based Population Diversity Measures in the Traveling Salesman
Problem, Evolutionary Computation, 2020, Vol. 28, Issue 4, pp. 595-619.
DOI: 10.1162/evco_a_00268.
9. Pop P., Matei O., Pintea C. A two-level diploid genetic based algorithm for solving the family
traveling salesman problem, Proceedings of the Genetic and Evolutionary Computation Conference
(GECCO'18). Association for Computing Machinery, New York, NY, USA, 2018, pp.
340-346. DOI: 10.1145/3205455.3205545.
10. Bernardino R., Paias A. Solving the family traveling salesman problem, European Journal of Operational
Research, 2018, Vol. 267, Issue 2, pp. 453-466. DOI: 10.1016/j.ejor.2017.11.063.
11. Cacchiani V., Muritiba A.E.F., Negreiros M., Toth P. A multistart heuristic for the equality
generalized traveling salesman problem, Networks, 2011, Vol. 57, Issue 3, pp. 231-239.
DOI: 10.1002/net.20421.
12. Garn W. Balanced dynamic multiple travelling salesmen: Algorithms and continuous approximations,
Computers & Operations Research, 2021, Vol. 136, Article 105509. DOI:
10.1016/j.cor.2021.105509.
13. Rybalko A.A., Polupanova E.E. Polialgoritm resheniya zadachi kommivoyazhera
[Polyalgorithm of solving the traveling salesman problem], Sovremennye problemy
matematiki, informatiki i modelirovaniya: Mater. III Vserossiyskoy nauchno-prakticheskoy
konferentsii molodykh uchenykh; Krasnodar: Krasnodarskiy TSNTI - filial FGBU "REA"
Minenergo Rossii, 2021 [Modern problems of mathematics, computer science and modeling –
materials of the III All-Russian Scientific and Practical Conference of Young Scientists, Krasnodar,
Krasnodar Central Research Institute - Branch of the Federal State Budgetary Institution
"REA" of the Ministry of Energy of Russia, 2021], Vol. 1, pp. 208-213.
14. Polupanova E.E., Polyakov A.S. Populyatsionnyy algoritm resheniya zadachi kommivoyazhera
[Population algorithm for solving the traveling salesman problem], Sovremennye informatsionnye
tekhnologii i IT-obrazovanie; Moskva: Fond sodeystviya razvitiyu internet-media, ITobrazovaniya,
chelovecheskogo potentsiala Liga internet-media, 2021 [Modern Information
Technologies and IT Education; Moscow, Foundation for the Promotion of Internet Media, IT
Education, Human Potential, Internet Media League, 2021], Vol. 17, No. 2, pp. 324-333.
15. Kureychik V.M., Gogokhiya L.R. Resheniya zadachi kommivoyazhera s primeneniem
geneticheskogo operatora stareniya [Gogohia Solving the traveling salesman problem using
the genetic operator of aging], Tr. mezhdunarodnogo nauchno-tekhnicheskogo kongressa
"intellektual'nye sistemy i informatsionnye tekhnologii - 2020" ("IS & IT-2020", "is&it'20"):
nauchnoe izdanie [Proceedings of the International Scientific and Technical Congress "Intelligent
Systems and Information Technologies - 2020" ("IS & IT-2020", "is&it'20"). scientific
publication]: in 2nd vol., 2020, pp. 7-16.
16. Sergienko I.V., Gulyanitskiy L.F., Sirenko S.I. Klassifikatsiya prikladnykh metodov
kombinatornoy optimizatsii [Classification of applied methods of combinatorial optimization],
Kibernetika i sistemnyy analiz [Cybernetics and system analysis], 2009, No. 5, pp. 71-83.
17. Metod otzhiga [Annealing method]. Available at: http://www.math.spbu.ru/user/gran/sb1/
lopatin.pdf (accessed 10 May 2023).
18. Kirsanov M.N. Grafy v Maple. Zadachi, algoritmy, programmy [Graphs in Maple. Tasks, algorithms,
programs]. Moscow: Izd-vo Fizmatlit, 2007, 167 p.
19. Osovskiy S. Neyronnye seti dlya obrabotki informatsii [Neural networks for information processing].
Moscow: Finansy i statistika, 2002, 343 p.
20. React.js. Available at: https://ru.reactjs.org/ (accessed 07 May 2023).
