OPTIMIZATION OF CULTURAL HERITAGE ROUTES USING GRAPH THEORY METHODS: MUSEUM NETWORK AND "LUTSK KLIKUNS"

Abstract

Abstract. This paper addresses the problem of mathematical modeling and algorithmic optimization of tourist routes at macro- (regional) and micro- (urban) levels using graph theory. The research is based on two case studies in the Volyn region: a logistic network of seven key museums and a themed walking route featuring 21 "Lutsk Klikuns" bronze sculptures. The methodology involves representing the spatial distribution of cultural objects as weighted undirected graphs, where edges reflect real logistical costs (time, fuel, or pedestrian distance). The software implementation, performed in Python (Jupyter Notebook, NumPy), integrates distinct algorithmic strategies for different scales. For the regional museum network, Dijkstra’s algorithm, the Nearest Neighbor heuristic, and Kruskal’s algorithm were applied to construct a minimum spanning tree and cost-efficient cycles. For the urban pedestrian route, a combination of the Greedy algorithm and 2-opt local optimization was employed to solve the Traveling Salesman Problem. The results demonstrate the universality of the proposed approach: a logistically sound itinerary minimizing transit costs was created for automobile tourism, while an optimal pedestrian path of approximately 11.5 km (starting from point A1) was calculated for the city tour. The practical significance of the work lies in automating the planning of cultural expeditions and enhancing the tourist experience through scientifically grounded navigation.