В статье рассматривается задача построения туристического маршрута с заранее заданными точками начала и конца маршрута. Объекты делятся на два типа. Первые – обязательные, которые наверняка должны войти в результирующий маршрут. Вторые – дополнительные, посещение которых не является необходимым. Маршрут формируется с учетом приоритетов, заранее заданных для объектов туристом исходя из его интересов и предпочтений, при этом суммарное время посещения объектов не должно превышать заданного крайнего срока прибытия в конечную точку маршрута. Для решения поставленной задачи в статье предлагается подход, основанный на построении известными методами маршрута по основным объектам и дальнейшем его расширением с использованием муравьиных стратегий. С этой целью вводится понятие «сытости» муравья и вероятности возврата к основному маршруту, чтобы была возможность контроля оставшегося времени. В завершении статьи приводятся результаты вычислительного эксперимента, направленного на оценку влияния параметров муравьиного алгоритма на полученный маршрут и разработку рекомендаций по настройке этих параметров в зависимости от размерности задачи. Кроме того, проводится сравнительный анализ маршрутов, полученных предложенным алгоритмом и точным методом ветвей и границ по заданному набору объектов, по результатам которого сделан вывод об эффективности предложенного алгоритма.
The article considers the task of building a tourist route with predetermined points of the beginning and end of the route. The objects are divided into two types. The first ones are mandatory, which should certainly be included in the resulting route. And the second ones are additional ones, which are not necessary to visit. The route is formed taking into account the priorities set for the objects by the tourist, based on his interests and preferences, while the total time of visiting the objects should not exceed the specified deadline for arrival at the end point of the route. To solve this problem, the article proposes an approach based on the construction of a route by known methods along the main objects and its further expansion using ant strategies. To this end, the concept of "satiety" of the ant and the probability of returning to the main route are introduced, so that it is possible to control the time reserve. At the end of the article, we present the results of a computational experiment aimed at assessing the influence of the ant algorithm parameters on the resulting route and developing recommendations for adjusting these parameters depending on the size of the problem. In addition, a comparative analysis of the routes obtained by the proposed algorithm and the exact branch-and-bound method for a given set of objects is carried out, based on the results of which a conclusion is drawn about the effectiveness of the proposed algorithm.
The authors declare that there are no conflicts of interest present.