Optimasi Algoritma Cheapest Insertion Heuristic dengan Algoritma Tabu Search dalam Pencarian Rute Terpendek

The shortest route finding problem is a significant topic in graph theory and combinatorial optimization, with wide applications in logistics, transportation, and scheduling. This research aims to improve the quality of the solution and time efficiency in solving the Traveling Salesman Problem (TSP) by optimizing the Cheapest Insertion Heuristic (CIH) algorithm using the application of the Tabu Search algorithm. The CIH algorithm constructs an initial solution by inserting points based on minimum weight. At the same time, the Tabu Search algorithm is applied to enhance the solution by avoiding local optima using a tabu list mechanism. The research data, consisting of the distances between parking retribution collection points by the Malang City Transportation Agency in Sukun Sub-district, were obtained from Google Maps. The algorithm performance evaluation is done by comparing the total mileage before and after optimization, and statistically analyzed using the Wilcoxon signed-rank test because the data does not follow a normal distribution. The results showed that optimizing the CIH algorithm using the Tabu Search algorithm significantly resulted in routes with shorter travel distances than using the CIH algorithm alone. This finding proves that optimizing the CIH algorithm with Tabu Search increases the effectiveness of finding the shortest route.The shortest route finding problem is a significant topic in graph theory and combinato-rial optimization, with wide applications in logistics, transportation, and scheduling. Thisresearch aims to improve the quality of the solution and time efficiency in solving the Trav-eling Salesman Problem (TSP) by optimizing the Cheapest Insertion Heuristic (CIH) algo-rithm using the application of the Tabu Search algorithm. The CIH algorithm constructs aninitial solution by inserting points based on minimum weight. At the same time, the TabuSearch algorithm is applied to enhance the solution by avoiding local optima using a tabulist mechanism. The research data, consisting of the distances between parking retributioncollection points by the Malang City Transportation Agency in Sukun Sub-district, were ob-tained from Google Maps. The algorithm performance evaluation is done by comparing thetotal mileage before and after optimization, and statistically analyzed using the Wilcoxonsigned-rank test because the data does not follow a normal distribution. The results showedthat optimizing the CIH algorithm using the Tabu Search algorithm significantly resulted inroutes with shorter travel distances than using the CIH algorithm alone. This finding provesthat optimizing the CIH algorithm with Tabu Search increases the effectiveness of findingthe shortest route.