Н.В. Блохин1, К.А. Зиновьева2, Р.А. Кочкаров3

1–3 ФГОБУ ВО «Финансовый университет при Правительстве Российской Федерации» (Москва, Россия)
1 nvblokhin@fa.ru, 2 215888@edu.fa.ru, 3 rkochkarov@fa.ru

Постановка проблемы. Решение задачи коммивояжера с использованием обучения с подкреплением является актуальной проблемой. Данная задача заключается в поиске оптимального маршрута, который проходит через указанные города хотя бы один раз и затем возвращается в исходный город. Задача коммивояжера относится к классу NP-трудных задач, в связи с чем нахождение точного решения для достаточно больших наборов данных с применением классических математических методов оказывается невозможным за разумное время.

Цель. Исследовать возможность повышения эффективности и скорости решения задачи коммивояжера с большим количество вершин путем использования метода обучения с подкреплением.

Результаты. Рассмотрен вариант решения задачи коммивояжера с использованием алгоритма Q-learning, позволяющего агенту обучаться оптимальной стратегии поведения в процессе взаимодействия со средой, которая представляет собой набор городов и дорог между ними, моделируемых в виде графа. Разработан программный комплекс для решения задачи коммивояжера с применением обучения с подкреплением. Проведены серии экспериментов, связанных с появлением непредвиденных условий, усложняющих работу коммивояжера, таких как появление «проблемных» зон или зон, прохождение через которые дает сокращение времени решения задачи. Показаны возможности разработанного алгоритма по адаптации к изменениям и препятствиям среды. Отмечено, что этот алгоритм более устойчивый и надежный по сравнению с алгоритмами, полученными классическими методами решения.

Практическая значимость. Решение рассмотренной задачи может быть использовано на практике во множестве реальных ситуаций, включая оптимизацию поставок или сетевой маршрутизации, помощь в работе отделов логистики различных транспортных, почтовых и курьерских служб.

Блохин Н.В., Зиновьева К.А., Кочкаров Р.А. Решение задачи коммивояжера с использованием обучения с подкреплением // Нелинейный мир. 2024. Т. 22. № 2. С. 18–25. DOI: https://doi.org/10.18127/j20700970-202402-02

1. Сайт Проблемно-ориентированной информационно-вычислительной системы [Электронный ресурс]. URL: http://poivs.tsput.ru/ru/Math/DiscreteMath/GraphTheory/ProblemOfTheTravelingSalesman (дата обращения 24.08.2023 г.)
2. Marco Dorigo, Thomas Stutzle Ant colony optimization / «A Bradford book». Massachusetts Institute of Technology. 2004. 321 р. aco-book.pdf. [Электронный ресурс]. URL: cmu.edu (дата обращения 20.08.2023 г.)
3. Конспекты университета ИТМО [Электронный ресурс]. URL: https://neerc.ifmo.ru/wiki/index.php?title=%D0%9E% D0%B1%D1%83%D1%87%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D0%BF%D0%BE%D0%B4%D0%BA%D1%80%D0%B5%D0%BF%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5%D0%BC (дата обращения 26.08.2023)
4. Q-Learning introduction and Q Table – Reinforcement Learning w/ Python Tutorial p.1, р.2. // [Электронный ресурс]. URL: https://pythonprogramming.net/q-learning-reinforcement-learning-python-tutorial/ (дата обращения 07.08.2023 г.).
5. TSPLIB – библиотека бенчмарков Герхарда Рейнельта [Электронный ресурс]. URL: http://comopt.ifi.uni-heidelberg.de/ software/TSPLIB95/tsp/ (дата обращения 26.08.2023).
6. Реализация класса Q agent [Электронный ресурс]. URL: kseniaznvv/tsp (github.com) (дата обращения 20.08.2023 г.).
7. Théo Alves Da Costa Solving the traveling salesman problem with reinforcement learning, November 3, 2021 [Электронный ресурс]. URL: https://ekimetrics.github.io/blog/2021/11/03/tsp/ (дата обращения 07.08.2023 г.).
8. Adam Paszke, Mark Towers Reinforcement learning (dqn) tutorial [Электронный ресурс]. URL: https://pytorch.org/tutorials/ intermediate/reinforcement_q_learning.html (дата обращения 07.08.2023 г.).
9. Mele U.J., Gambardella L.M., Montemanni R. A1-14 Machine Learning Approaches for the Traveling Salesman Problem: A Survey [Электронный ресурс]. URL: A1-14 Machine Learning Approaches for the Traveling Salesman Problem- A Survey.pdf – Google Диск (дата обращения 20.08.2023 г.).
10. Concorde TSP Benchmarks [Электронный ресурс]. URL: https://www.math.uwaterloo.ca/tsp/index.html (дата обращения 20.08.2023 г.).