Minimum Spanning Tree Solutions for Smart and Enhanced Tour Planning - Aristawati, Carolina Nathaniela; Pradana, Bayu Ilham (Fakultas Ekonomi dan Bisnis Universitas Brawijaya, 2025)
Purpose – This study aims to design optimal tourism routes for travel agencies in Batu City by applying the Minimum Spanning Tree (MST) method using Prim’s algorithm and comparing manual calculations with results generated by QM for Windows software. Design/Methodology/Approach – This study employs a descriptive quantitative approach with a replication research model. Data were collected from primary and secondary sources. Primary data were obtained through structured interviews with a key informant, namely a travel coordinator at Tour and Travel Agency X, while secondary data regarding inter-location distances were obtained from Google Maps and internal documents. The analysis was conducted by constructing weighted graphs and calculating MST using both manual methods and QM for Windows software on four predefined tour packages. Findings – The results indicate that QM for Windows consistently generates shorter tourism routes compared with manual calculations. The application of MST through Prim’s algorithm can support more efficient route planning by reducing travel distances and improving operational effectiveness. However, practical implementation requires consideration of real-world factors, including road conditions, accessibility, and travel agency policies, to ensure the feasibility of the proposed routes. Originality/Value: This research provides value by integrating Prim’s algorithm with QM for Windows to compare computational efficiencies in real tourism route planning, an approach seldom applied in local travel operations. The study offers original practical insights that bridge algorithmic optimization with real-world travel management, supporting more accurate and customer-oriented decision-making for tourism agencies.