Efficient Route Planning in Northeast Thailand Using a Random Shuffle Enhanced 2-opt Algorithm

Abstract

This research presents a detailed comparative analysis of algorithms designed to solve the Traveling Salesman Problem (TSP) within the Northeast region of Thailand, encompassing 20 provinces. The study evaluates the performance of several heuristic algorithms, including Nearest Neighbor, Farthest Insertion, traditional 2-opt, and a novel variant termed 2-optRS, which integrates a random shuffle mechanism. The primary aim is to minimize the total travel distance while considering the computational trade-offs of these algorithms. Authentic distance data between provinces were sourced from Google Maps to ensure accuracy and relevance to real-world applications. The study addresses the dual challenge of computational efficiency and solution quality, emphasizing the practical implications of algorithmic enhancements in route optimization. Among the tested algorithms, 2-optRS exhibited superior performance, achieving a notable reduction of approximately 158.6 km in travel distance compared to the traditional 2-opt algorithm. However, this improvement came at the expense of significantly increased processing time, highlighting the inherent trade-offs between computational demands and optimization benefits. By focusing on the Northeast region, which is poised for significant development through frameworks like the Greater Mekong Subregion (GMS) and Lancang-Mekong Cooperation (LMC), this research provides valuable insights for optimizing logistical networks in this rapidly growing area. The findings underscore the potential of advanced heuristic methods to enhance decision-making in regional transportation planning, contributing to the broader advancement of TSP optimization methodologies.