Tourism Route Optimization Based on the Travelling Salesman Problem Using Ant Colony Optimization in the Banyumas and Purbalingga Regions

Abstract

Tourism route planning requires an efficient visiting sequence to reduce travel distance and transportation costs. When multiple tourist destinations must be visited in a single trip, the route-planning problem can be formulated as a Travelling Salesman Problem (TSP). This study implements Ant Colony Optimization (ACO) to determine an efficient route among 12 tourist destinations in Banyumas and Purbalingga. The destinations were represented as nodes in a weighted graph, while the travel distance between each pair of destinations was used as the edge weight. The algorithm constructed candidate routes using probabilistic selection and updated pheromone values based on route quality. Three pheromone evaporation rates, namely ρ=0.3, ρ=0.5, and ρ=0.7, were evaluated. The shortest route obtained in the first iteration was W1–W3–W2–W4–W8–W9–W7–W10–W11–W12–W6–W5–W1, with a total distance of 109.0 km. After pheromone updating, the pheromone levels on the shortest-route edges were 0.016174, 0.014174, and 0.012174 for evaporation rates of 0.3, 0.5, and 0.7, respectively. These results show that the evaporation rate directly affects pheromone retention, with a lower evaporation rate maintaining stronger pheromone information on the selected route. The study demonstrates that ACO can generate an efficient tourism route and provides a computational basis for developing a tourism route decision-support system.