Pencarian Jalur Terpendek dari Kota Surabaya ke Wilayah Jawa Timur dengan Algoritma Genetika
Keywords:
Travelling Salesman Problem, Algoritma Genetika, Jalur Terpendek, Navigasi, HeuristikAbstract
Penelitian ini mengevaluasi efektivitas Algoritma Genetika dalam menyelesaikan masalah Travelling Salesman Problem (TSP) antara Kota Surabaya dan wilayah-wilayah di Jawa Timur. TSP merupakan masalah optimasi di mana penjual harus mengunjungi sejumlah kota dengan jarak total minimum dan kembali ke kota asal. Algoritma Genetika digunakan karena kemampuannya yang kuat dalam menangani ruang pencarian yang luas dan menghindari terjebak dalam solusi optimal lokal, dengan melibatkan proses seleksi, crossover, dan mutasi untuk menghasilkan solusi yang lebih baik dari generasi ke generasi. Data jarak antara Kota Surabaya dan berbagai kota di Jawa Timur dikumpulkan sebagai input, dengan jarak mulai dari 28.5 km ke Kabupaten Gresik hingga 303.0 km ke Kabupaten Banyuwangi. Hasil penelitian menunjukkan bahwa Algoritma Genetika berhasil menemukan rute yang lebih efisien dibandingkan metode pencarian rute biasa. Rute optimal pada penelitian ini mendapatkan hasil total jarak 2335.30 km. Penelitian ini menunjukkan bahwa Algoritma Genetika dapat mengoptimalkan rute perjalanan, menghemat waktu dan biaya, serta meningkatkan efisiensi transportasi. Namun, kelemahan seperti kebutuhan waktu komputasi tinggi dan ketergantungan pada ukuran populasi serta probabilitas crossover dan mutasi diidentifikasi. Meskipun demikian, hasilnya konsisten dan signifikan, membuktikan potensi besar Algoritma Genetika dalam aplikasi praktis untuk masalah optimasi rute. Penelitian ini membuka peluang untuk pengembangan lebih lanjut dengan mempertimbangkan faktor tambahan seperti kondisi lalu lintas, waktu tempuh aktual, dan cuaca. Implementasi Algoritma Genetika dalam sistem navigasi yang lebih canggih dapat memberikan manfaat besar bagi sistem transportasi di Jawa Timur dan daerah lainnya.
References
Badan Pemeriksa Keuangan Republik Indonesia. Kota Surabaya. Diakses pada 3 Juni 2024, dari https://jatim.bpk.go.id/kota-surabaya/.
Utomo, R. G., Maylawati, D. S., Alam, C. N., (2018). Implementasi Algoritma Cheapest Insertion Heuristic (CIH) dalam Penyelesaian Travelling Salesman Problem (TSP). JOIN (Jurnal Online Informatika), 3 (1), 61-67.
Syamsudin, Aries., (2004). Pengenalan Algoritma Genetik. (IlmuKomputer.com)
Simanjuntak, O.S., Seminar Nasional Informatika 2012 (semnasIF 2012). In : UPN “Veteran”, Pengembangan Shortest Path Algorithm (SPA) Dalam Rangka Pencarian Lintasan Terpendek Pada Graf Bersambung Berarah Terurai, Yogyakarta, 30 Juni 2012. UPN “Veteran”: Yogyakarta.
"History of the TSP." Diakses pada Juni 2024, dari http://www.math.uwaterloo.ca/tsp/history/.
Amri, Faisal., Nababan, Erna Budhiarti., dan Syahputra, Mohammad Fadly.2012. Artificial Bee Colony Algorithm untuk Menyelesaikan Travelling Salesman Problem. Jurnal Dunia Teknologi Informasi,Vol. 1, No. 1, pp. 8-13
Manggolo, Inu., Marzuki, Marza Ihsan., dan Alaydrus, Mudrik. 2011. Optimalisasi Perencanaan Jaringan Akses Serat Optik Fiber To The Home Menggunakan Algoritma Genetika. InComTech, Jurnal Telekomunikasi dan Komputer, Vol. 2, No. 2, pp. 21-36.
Salaki, D. T., (2011). Penentuan Lintasan Terpendek Dari FMIPA ke Rektorat dan Fakultas di UNSRAT manado Menggunakan Algoritma Djikstra. Jurnal Ilmiah Sains. 11(1), 73-78
Salaki, D. T., (2011). Penentuan Lintasan Terpendek Dari FMIPA ke Rektorat dan Fakultas di UNSRAT manado Menggunakan Algoritma Djikstra. Jurnal Ilmiah Sains. 11(1), 73-78
W. F. Mahmudy, "Algoritma evolusi," Program Teknologi Informasi dan Ilmu Komputer, Universitas Brawijaya, Malang, pp. 1-101, 2013.
A. Tohari and Y. P. Astuti, "Penerapan algoritma genetika dalam menentukan rute terpendek PT. Pos Cabang Lamongan," MATHunesa: Jurnal Ilmiah Matematika, vol. 11, no. 03, pp. 458-467, 2023.
H. Ardiansyah and M. B. S. Junianto, "Penerapan Algoritma Genetika untuk Penjadwalan Mata Pelajaran," Jurnal Media Informatika Budidarma, vol. 6, no. 1, pp. 329-336, 2022.
D. Gunawan, D. Riana, D. Ardiansyah, F. Akbar, and S. Alfarizi, "Komparasi Algoritma Support Vector Machine dan Naïve Bayes dengan Algoritma Genetika pada Analisis Sentimen Calon Gubernur Jabar 2018-2023," 2020.
R. Hartono and A. Zein, "Penerapan Algoritma Genetika dan Jaringan Syaraf Tiruan dalam Penjadwalan Mata Kuliah," Jurnal Ilmu Komputer JIK, vol. VI, no., 2023.
I. W. Supriana, M. A. Raharja, I. M. S. Bimantara, and D. Bramantya, "Implementasi dua model crossover pada algoritma genetika untuk optimasi penggunaan ruang perkuliahan," Jurnal RESISTOR (Rekayasa Sistem Komputer), vol. 4, no. 2, pp. 167-177, 2021.
