Dimensions
Dimensions
Yulianti, Silviyatus, Jauhari, Mohammad Nafie and Nashichuddin, Ach. 
ORCID: https://orcid.org/0009-0006-8273-8878
(2025)
Optimasi algoritma cheapest insertion heuristic dengan algoritma tabu search dalam pencarian rute terpendek.
Jurnal Riset Mahasiswa Matematika, 4 (6).
pp. 367-375.
ISSN 2808-4926
|
Text
25944.pdf - Published Version Available under License Creative Commons Attribution Share Alike. Download (591kB) | Preview |
Abstract
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.
| Item Type: | Journal Article |
|---|---|
| Keywords: | Cheapest Insertion Heuristic Algorithm; Route Optimization; Tabu Search Algorithm; Traveling Salesman Problem |
| Subjects: | 01 MATHEMATICAL SCIENCES > 0101 Pure Mathematics > 010104 Combinatorics and Discrete Mathematics (excl. Physical Combinatorics) |
| Divisions: | Faculty of Mathematics and Sciences > Department of Mathematics |
| Depositing User: | Mohammad Nafie Jauhari |
| Date Deposited: | 12 Dec 2025 08:16 |
Downloads
Downloads per month over past year
Origin of downloads
Actions (login required)
 |
View Item |