Optimizing historical tourism itineraries in Songkhla Province presents a significant combinatorial challenge, owing to its geographically dispersed attractions and a lack of systematic planning. This research, therefore, proposes the development of a routing model by comparing the efficiency of two heuristic methods: the Nearest Neighbor Heuristic (NNH) and the Clarke and Wright Savings Algorithm (SA). The objective was to create multi-day itineraries covering 20 significant attractions, under the constraint of an 8-hour maximum daily travel duration. The findings indicate that the Savings Algorithm (SA) demonstrates clearly superior performance, yielding a shorter total travel distance (635.4 km compared to 648.9 km) and allocating attractions within each route far more symmetrically. Therefore, the SA is a more suitable tool for stakeholders to implement in actual itinerary planning to reduce costs, enhance the tourist experience, and promote sustainable tourism in Songkhla.
Keywords: heuristic method; tourism route planning; historical tourism