Perbandingan Algoritma Genetika dan A* dalam Pencarian Rute Terpendek Antara Bengkel Resmi Sepeda Motor di Kota Medan Berbasis Android

Abstract

Berkembanganya industri kendaraan bermotor khususnya roda 2 untuk menunjang tingginya mobilitas masyarakat, menjadikan para produsen sepeda motor menghadirkan bengkel resmi sebagai sarana untuk perawatan dan perbaikan yang terjamin sehingga dibutuhkan informasi tentang lokasi terdekat dari satu bengkel resmi sepeda motor. Seiring perkembangan teknologi, penggunaan algoritma Genetika dan A* dapat menjadi solusi atas kebutuhan tersebut, yaitu untuk menemukan rute terpendek antara bengkel resmi sepeda motor melalui aplikasi smartphone berbasis Android, dengan parameter yang digunakan adalah running time dan kompleksitas algoritma big θ. Penelitian ini dilakukan terhadap 20 sampel bengkel resmi sepeda motor yang ada dikota Medan. Hasil setelah 5 kali proses pengujian running time, didapatkan bahwa algoritma A* lebih cepat dibandingkan algoritma Genetika. Sementara pada penghitungan kompleksitas algoritma, didapatkan bahwa algoritma A* memiliki kompleksitas sebesar θ(n2), dan algoritma Genetika memiliki kompleksitas sebesar θ(n4), sehingga hasil perhitungan menunjukkan algoritma Genetika memiliki kompleksitas lebih besar dibandingkan algoritma A*. Kesimpulan akhir, algoritma A* lebih cepat dibanding Genetika karena memiliki kompleksitas yang lebih kecil.

The growth of development of the motor vehicle industry especially the 2 wheels to support the high mobility of the community, making motorcycle manufacturers present an official workshop as a means for guaranteed maintenance and repairs, so information is needed about the nearest location of an official motorcycle workshop. As technology develops, the use of Genetic Algorithms and A * can be a solution to these needs, namely to find the shortest route between official motorcycle workshops through Android-based smartphone applications, with the parameters used are running time and the complexity of the big algoritma algorithm. This research was conducted on 20 samples of official motorcycle workshops in the city of Medan. The results after 5 times the running time testing process, it was found that the A * algorithm is faster than the Genetic algorithm. While in calculating the complexity of the algorithm, it was found that the A * algorithm has a complexity of θ (n2), and the Genetic algorithm has a complexity of θ (n4), so the calculation results show that the Genetic algorithm has a greater complexity than the A * algorithm. Final conclusion, the A * algorithm is faster than Genetics because it has less complexity.