Модифицированный муравьиный алгоритм для построения туристического маршрута с ограничением по времени

В статье рассматривается задача построения туристического маршрута с заранее заданными точками начала и конца маршрута. Объекты делятся на два типа. Первые – обязательные, которые наверняка должны войти в результирующий маршрут. Вторые – дополнительные, посещение которых не является необходимым. Маршрут формируется с учетом приоритетов, заранее заданных для объектов туристом исходя из его интересов и предпочтений, при этом суммарное время посещения объектов не должно превышать заданного крайнего срока прибытия в конечную точку маршрута. Для решения поставленной задачи в статье предлагается подход, основанный на построении известными методами маршрута по основным объектам и дальнейшем его расширением с использованием муравьиных стратегий. С этой целью вводится понятие «сытости» муравья и вероятности возврата к основному маршруту, чтобы была возможность контроля оставшегося времени. В завершении статьи приводятся результаты вычислительного эксперимента, направленного на оценку влияния параметров муравьиного алгоритма на полученный маршрут и разработку рекомендаций по настройке этих параметров в зависимости от размерности задачи. Кроме того, проводится сравнительный анализ маршрутов, полученных предложенным алгоритмом и точным методом ветвей и границ по заданному набору объектов, по результатам которого сделан вывод об эффективности предложенного алгоритма.

1. Geunes J. Operations Planning: Mixed Integer Optimization Models (Operations Research Series). Boca Raton: CRC Press; 2014. 218 p. https://doi.org/10.1201/b17414

2. Ntakolia C., Iakovidis D.K. A swarm intelligence graph-based pathfinding algorithm (SIGPA) for multi-objective route planning. Computers & Operations Research. 2021;133. https://doi.org/10.1016/j.cor.2021.105358

3. Сучкова Т.М., Волкова Л.Л. О разработке рекомендательной системы для составления туристических маршрутов на основе тематических предпочтений пользователя. В сборнике: Искусственный интеллект в автоматизированных системах управления и обработки данных: Сборник статей II Всероссийской научной конференции: в 5 томах: Том 1, 27-28 апреля 2023 года, Москва, Россия. Москва: Издательский дом «КДУ»; 2023. С. 145–150.

4. Полетайкин А.Н. Компьютерная система составления туристических маршрутов методом генетических алгоритмов. В сборнике: Техническая эксплуатация водного транспорта: проблемы и пути развития: Материалы Второй международной научно-технической конференции, 23-25 октября 2019 года, Петропавловск-Камчатский, Россия. Петропавловск-Камчатский: Камчатский государственный технический университет; 2020. С. 158–162.

5. Pasandi L., Hooshmand M., Rahbar M. Modified A* Algorithm integrated with ant colony optimization for multi-objective route-finding; case study: Yazd. Applied Soft Computing. 2021;113. https://doi.org/10.1016/j.asoc.2021.107877

6. Zheng W., Liao Zh., Qin J. Using a four-step heuristic algorithm to design personalized day tour route within a tourist attraction. Tourism Management. 2017;62:335–349. https://doi.org/10.1016/j.tourman.2017.05.006

7. Ruiz-Meza J., Brito J., Montoya-Torres J.R. A GRASP-VND algorithm to solve the multi-objective fuzzy and sustainable Tourist Trip Design Problem for groups. Applied Soft Computing. 2022;131. https://doi.org/10.1016/j.asoc.2022.109716

8. Корбут А.А., Финкельштейн Ю.Ю. Дискретное программирование. Москва: Наука; 1969. 368 с.

9. Żak A. Growth order for the size of smallest hamiltonian chain saturated uniform hypergraphs. European Journal of Combinatorics. 2013;34(4):724–735. https://doi.org/10.1016/j.ejc.2012.10.009

10. Родзин С.И., Родзина О.Н., Эль-Хатиб С.А. Гибридный муравьиный алгоритм сегментации медицинских изображений. Вестник Чувашского университета. 2017;(3):262–272.

11. Medvedev S.N., Medvedeva O.A. Modified ant colony optimization algorithm for solving the vehicle routing problem with a given load capacity. Journal of Physics: Conference Series. 2021;1902. https://doi.org/10.1088/1742-6596/1902/1/012123