АЛГОРИТМ ПОСЛЕДОВАТЕЛЬНОЙ ГИБРИДИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧИ КОММИВОЯЖЕРА

Е. Е. Полупанова; А.А. Рыбалко

Е. Е. Полупанова Кубанский государственный университет
А.А. Рыбалко Кубанский государственный университет

Ключевые слова: Задача коммивояжера, гибридный алгоритм, метод ближайшего соседа, алгоритм имитации отжига, веб-приложение, маршрут, навигатор, Typescript, react-leaflet

Аннотация

Задача коммивояжера является задачей комбинаторной оптимизации. В статье при-
водится постановка данной задачи и предлагается графовая математическая модель, в ко-
торой вершины соответствуют городам, а рёбра – это пути между городами, причем пред-
полагается, что граф взвешен. Решение задачи коммивояжёра состоит в нахождении га-
мильтонова цикла минимального веса в полном взвешенном графе. Задача является NP-
трудной, поэтому для решения данной задачи используется эвристический подход для полу-
чения решения задачи на больших объёмах входных данных. Эвристика заключается в приме-
нении для решения задачи коммивояжера гибридизации двух алгоритмов: алгоритма имита-
ции отжига и алгоритма ближайшего соседа. Для решения задачи коммивояжера использу-
ется последовательная схема гибридизации. Основная идея заключается в том, что на
стартовом наборе решений запускается метод ближайшего соседа, а затем лучшее реше-
ние, полученное на первом этапе, подается на вход алгоритму имитации отжига. В статье
подробно освещены построение, блок-схемы гибридного алгоритма, алгоритма имитации
отжига и метода ближайшего соседа. Далее в статье приводится описание пользователь-
ского интерфейса приложения, написанного на Typescript. Приложение использует реальную
карту местности для решения задачи коммивояжера. В последней части статьи освещает-
ся сравнительный анализ эффективности работы алгоритмов: сравнение точности и време-
ни работы разработанного гибридного алгоритма, алгоритма имитации отжига и метода
ближайшего соседа на различных входных наборах данных. Удалось установить, что разра-
ботанный гибридный алгоритм находится на втором месте по скорости работы и на пер-
вом по качеству решения среди реализованных алгоритмов. Кроме того, разработанное ре-
шение имеет высокую экономическую и практическую ценность ввиду того, что приложение
для решения задачи коммивояжера, а следовательно, приложение для навигации по маршру-
ту может заменить существующие аналоги или же оно может быть использовано в каких-
либо узконаправленных областях, а также в логистике.

Литература

1. Mudrov V.I. Zadacha o kommivoyazhere [The problem of a traveling salesman]. Moscow:
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).