JNATIA Volume 2, Nomor 1, November 2023

Jurnal Nasional Teknologi Informasi dan Aplikasinya

p-ISSN: 2986-3929

Optimasi Pencarian Rute Terpendek pada Provinsi Bali Menggunakan Algoritma Genetika

Muhammad Caesar Gilang Indrawana1, I Made Widiarthaa2

aProgram Studi Informatika, Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Udayana, Bali

Jln. Raya Kampus UNUD, Bukit Jimbaran, Kuta Selatan, Badung, 08261, Bali, Indonesia 1[email protected] 2[email protected]

Abstract

Bali is one of the most popular tourist destinations in Indonesia. Therefore, many local and international tourists visit Bali for holidays. Searching for the shortest route is needed for tourists who want to take a walk around the island of Bali. By getting the shortest route between the initial location and the destination location, the efficiency level of time needed to travel between the two locations will be better. Searching for the shortest route can be done by applying a genetic algorithm. Genetic algorithm is a method or technique of optimization and search based on the mechanism of natural genetic principles and natural selection.

Keywords: Optimation, Shortest Path, Genetic Algorithm

  • 1.    Pendahuluan

Seiring dengan perkembangan zaman, teknologi dan ilmu pengetahuan juga turut berkembang dengan pesat. Salah satu perkembangan teknologi yaitu teknologi dalam hal pencarian rute terpendek. Pencarian rute terpendek ini dapat membantu kegiatan manusia dalam menjalankan aktivitasnya yang digunakan untuk mengoptimalkan kinerja. Pencarian rute terpendek sangat bermanfaat untuk diimplementasikan pada kegiatan seperti pengiriman barang, pencarian lokasi, dan lain sebagainya. Ada perjalanan yang memerlukan waktu yang sebentar dengan jarak tempuh yang pendek, sedangkan ada pula perjalanan yang memerlukan waktu yang cukup lama untuk sampai ke tujuan dengan jarak tempuh yang panjang.

Dengan mendapatkan rute terpendek antara lokasi awal dan lokasi yang dituju maka, tingkat efisiensi waktu yang dibutuhkan untuk melakukan perjalanan antara dua lokasi tersebut akan semakin baik. Dalam pengaplikasian rute terpendek ini dapat dibuat untuk penentuan rute terpendek antar kabupaten yang terdapat di Bali yang biasanya teknologi ini dimanfaatkan oleh kurir yang mengirim barang dari satu kabupaten ke kabupaten lain, masyarakat yang ingin mengeksplor Bali, dan wisatawan-wisatawan yang ingin melakukan touring untuk mengelilingi provinsi Bali.

Untuk mendapatkan rute terpendek, maka diperlukan suatu algoritma. Algoritma yang digunakan untuk pencarian rute terpendek adalah algoritma genetika. Algoritma Genetika adalah teknik pencarian yang di dalam ilmu komputer untuk menemukan penyelesaian perkiraan untuk optimisasi dan masalah pencarian.[1] Algoritma genetika adalah kelas khusus dari algoritma evolusioner dengan menggunakan teknik yang terinspirasi oleh biologi evolusioner seperti warisan, mutasi, seleksi alam dan rekombinasi (atau crossover). Algoritma genetika dapat mewakili solusi untuk masalah seperti kromosom.[2] Algoritma genetika merupakan bagian dari komputasi mengoptimalkan evolusioner yang terinspirasi dari survival of the fittest dari Darwin. Algoritma genetika dimulai dengan pembentukan sejumlah alternatif pemecahan yang disebut populasi.[3]

  • 2.    Metode Penelitian

    2.1  Data dan Metode Pengumpulan Data

Pengumpulan dan analisis data dilakukan seperti fungsi dari algoritma Genetika yang dapat menentukan jalur terpendek dari satu tempat ke tempat lain. Data yang dikumpulkan yaitu berupa koordinat dari daftar kota/kabupaten yang terdapat di provinsi Bali. Koordinat didapat secara manual dengan mengambilnya pada google maps setelah masing-masing kabupaten dilock (ditandai). Adapun data untuk daftar kabupaten yang digunakan terbatas yaitu hanya 9 kabupaten diantaranya, Klungkung, Denpasar, Bangli, Tabanan, Gianyar, Karangasem, Badung, Jembrana, dan Buleleng.

  • 2.2    Tahap Penentuan Rute Terpendek

Berikut ini merupakan alur dari pencarian rute terpendek dari titik awal ke titik tujuan:

Gambar 1. Alur pencarian rute terpendek

Pada alur penelitian ini terdapat 7 tahap diantaranya

  • 1. Proses Inisialisasi Populasi Secara Acak

  • 2. Proses Membuat Fungsi Fitness

  • 3. Proses Seleksi

  • 4. Proses Crossover

  • 5. Proses Mutasi

  • 6. Proses Elitism (steady state replacement)

  • 7.    Prosedur GA

Hasil akhir atau output dari input yang berupa titik awal kabupaten dan titik akhir kabupaten adalah berupa rute terbaik dan seharusnya yang dilewati dari titik awal kabupaten untuk mencapai titik akhir kabupaten yang dipilih.

  • 3.    Hasil dan Pembahasan

Berikut ini adalah hasil interface dari sistem pencarian rute terpendek di provinsi Bali. Pada awal, pengguna akan diminta untuk memilih titik awal dan titik akhirnya.

Gambar 2. Tampilan awal sistem

Gambar 3. Pemilihan titik awal

Gambar 4. Pemilihan titik tujuan

Setelah memilih titik awal dan titik tujuan, maka akan muncul rute terpendek dari titik awal dan titik tujuan tersebut.

Gambar 5. Hasil pencarian rute terpendek

  • 4.    Kesimpulan

Kesimpulan yang didapat adalah pada penelitian pencarian rute terpendek antar kabupaten yang terdapat di provinsi Bali ini data yang digunakan yaitu koordinat dari kota/kabupaten yang terdapat di provinsi Bali yang terdiri dari 9 kabupaten diantaranya yaitu Klungkung, Denpasar, Bangli, Tabanan, Gianyar, Karangasem, Badung, Jembrana, dan Buleleng dengan menggunakan fungsi dari algoritma Genetika. Adapun alur atau tahapan dalam penelitian ini terdiri dari beberapa proses yaitu proses inisialisasi populasi secara acak, proses membuat fungsi

fitness, proses seleksi, proses crossover, proses Mutasi, proses elitism (steady state replacement), dan prosedur GA. Dengan hasil akhir yang didapatkan dari input yaitu berupa titik awal kabupaten dan titik akhir kabupaten yang merupakan rute terbaik yang terdapat dalam populasi.

Daftar Pustaka

  • [1]    M. Di and U. D. Mebel, “Penerapan Algoritma Genetika Dalam Efisiensi Persediaan Bahan

Baku,” vol. 2, pp. 155–165.

  • [2]    S. F. Pane, R. Maulana Awangga, E. V. Rahcmadani, and S. Permana, “Implementasi

Algoritma Genetika Untuk Optimalisasi Pelayanan Kependudukan,” J. Tekno Insentif, vol. 13, no. 2, pp. 36–43, 2019, doi: 10.36787/jti.v13i2.130.

  • [3]    Anies Hannawati, Thiang, and Eleazar, “Pencarian Rute Optimum Menggunakan

Algoritma Genetika,” J. Tek. Elektro, vol. 2, no. 2, pp. 78–83, 2002, [Online]. Available: http://puslit2.petra.ac.id/ejournal/index.php/elk/article/view/15857.

Halaman ini sengaja dibiarkan kosong

130