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

Silviyatus Yulianti, Mohammad Nafie Jauhari, Achmad Nashichuddin

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.

Keywords


Cheapest Insertion Heuristic Algorithm; Route Optimization; Tabu Search Algorithm; Traveling Salesman Problem

Full Text:

PDF

References


[1] I. Kholidasari, A. P. Zein, and S. Sundari, “Penerapan Metode Shortest Route Problem Untuk Menentukan Rute Distribusi Produk Gas Lpg 3 Kg Dengan Kriteria Minimasi Biaya Transportasi Di Pt.Www,” Industrika : Jurnal Ilmiah Teknik Industri, vol. 1, no. 1, pp. 1–10, 2022.

[2] F. Suryani, R. K. Natadipura, and H. Tunafiah, “Optimalisasi Rute Perjalanan Sarana Angkutan Umum Terpadu Bogor-Jakarta,” Ikra-ITH Teknologi, vol. 3, no. 2, pp. 63–75, 2019.

[3] D. T. Wiyanti, “Algoritma Optimasi untuk Penyelesaian Travelling Salesman Problem,” Jurnal Transformatika, vol. 11, no. 1, pp. 1–6, 2013.

[4] G. Aristi, “Perbandingan Algoritma Greedy, Algoritma Cheapest Insertion Heuristics Dan Dynamic Programming Dalam Penyelesaian Travelling Salesman Problem,” Paradigma, vol. XVI, no. 2, pp. 52–58, 2014.

[5] Y. V. Via, M. S. Munir, and A. Muhammad, “Optimasi Penjadwalan Pegawai Rumah Sakit Menggunakan Algoritma Genetika,” Scan : Jurnal Teknologi Informasi dan Komunikasi, vol. 12, no. 1, pp. 81–88, 2017.

[6] G. Chartrand, L. Lesniak, and P. Zhang, Graphs and Digraphs. New York: CRC Press Taylor Francis Group, sixth ed., 2015.

[7] E. Yulianto and A. Setiawan, “Optimasi Rute Sales Coverage Menggunakan Algoritma Cheapest Insertion Heuristic Dan Layanan Google Maps Api,” INTERNAL (Information System Journal), vol. 1, no. 1, pp. 39–54, 2018.

[8] R. G. Utomo, D. S. Maylawati, and C. N. Alam, “Implementasi Algoritma Cheapest Insertion Heuristic (CIH) dalam Penyelesaian Travelling Salesman Problem (TSP),” Jurnal Online Informatika, vol. 3, no. 1, p. 61, 2018.

[9] K. Saleh, Helmi, and B. Prihandono, “Penentuan Rute Terpendek Dengan Menggunakan Algoritma Cheapest Insertion Heuristic (Studi Kasus: PT. Wicaksana Overseas International Tbk. Cabang Pontianak),” Buletin Ilmiah Math. Stat. dan Terapannya (Bimaster), vol. 04, no. 3, pp. 295–304, 2015.

[10] K. Kusrini and J. E. Istiyanto, “Penyelesaian Travelling Salesman Problem dengan Algoritma Cheapest Insertion Heuristic dan Basis Data,” Jurnal Informatika, vol. 8, no. 2, pp. 109–114, 2007.

[11] V. Dayanti, “Efektivitas Parameter Algoritma Cheapest Insertion Heuristic ( CIH ) dalam Menentukan Rute Terpendek Bus Sekolah Gratis Kota Malang,” Jurnal Riset Mahasiswa Matematika, vol. 4, no. 1, pp. 1–9, 2024.

[12] Y. Wang, Q. Wu, and F. Glover, “Effective Metaheuristic Algorithms for The Minimum Differential Dispersion Problem,” European Journal of Operational Research, vol. 258, no. 3, pp. 829–843, 2017.

[13] H. M. Sitorus, C. P. Juwono, and P. Ciputra, “Penerapan Algoritma Tabu Search pada Permasalahan Lintasan Keseimbangan Bentuk U Tipe I dengan Waktu Proses Stokastik,” Inasea, vol. 15, no. 1, pp. 15–27, 2014.

[14] S. E. Ramadhania and S. Rani, “Implementasi Kombinasi Algoritma Genetika dan Tabu Search untuk Penyelesaian Travelling Salesman Problem,” Automata, vol. 2, no. 1, pp. 99–106, 2021.

[15] A. C. Sembiring, I. S. Lumbanntoruan, and H. B. Jufri, “Optimalisasi Rute Distribusi Menggunakan Algoritma Tabu Search Dan Nearest Neighbor,” Junal Ilmiah Teknik Industri Prima), vol. 6, no. 2, pp. 50–56, 2023.




DOI: https://doi.org/10.18860/jrmm.v4i6.33343

Refbacks

  • There are currently no refbacks.