Pencarian jalur terpendek menggunakan Algoritma Dijkstra pada lingkungan yang bersifat fuzzy

Abstract

Saat ini kegiatan transportasi sudah merupakan hal yang biasa dilakukan orang-orang banyak. Biasanya dalam melakukan kegiatan transportasi, orang-orang memilih rute yang menghasilkan jarak tempuh yang minimal karena masalah waktu. Namun seringkali pada praktiknya, dalam perjalanan sering ditemukan hambatan. Beberapa faktor yang menghambat sebuah perjalanan biasanya karena ruas jalan yang padat, bencana alam, kerusakan jalan dan lainnya. Karena faktor-faktor inilah setiap perjalanan tidak pasti menghasilkan waktu tempuh minimum meskipun dipilih jalur dengan total jarak minimum. Maka dibutuhkan teknik untuk memilih jalur yang menghasilkan total waktu minimum. Salah satu algoritma yang populer digunakan untuk menyelesaikan masalah pencarian jalur terpendek adalah Algoritma Dijkstra. Algoritma Dijkstra bekerja dengan menghitung penjumlahan antar jalur lalu dipilih jalur dengan total penjumlahan antar jalur yang paling minimum. Algoritma Dijkstra biasa digunakan pada weighted graph berarah maupun weighted graph tidak berarah. Syarat utama agar sebuah graph dapat dilakukan penelusuran menggunakan Algoritma Dijkstra adalah weight untuk setiap edge harus bernilai positif. Fuzzy merupakan sebuah logika yang memiliki kemampuan untuk merepresentasikan sebuah masalah yang bersifat samar. Dalam merepresentasikan kondisi yang samar, fuzzy menggunakan membership value pada rentang 0 sampai 1 ([0 1]). Apabila sebuah pernyataan bernilai 0 maka pernyataan itu sangat salah, sebaliknya apabila bernilai 1 maka pernyataan tersebut sangat benar. Apabila membership value untuk sebuah pernyataan memiliki nilai pada rentang [0 1], maka nilai kebenaran dari pernyataan tersebut memiliki kebenaran sebesar nilai membership value yang didapat. Pada masalah transportasi diatas, didapatkan variabel yang samar adalah "waktu". Waktu tempuh sebuah rute akan direpresentasikan menggunakan fuzzy number dengan metode Triangular Fuzzy Number. Pada skripsi ini akan dibuat perangkat lunak yang memiliki keemampuan untuk menyelesaikan masalah pencarian jalur terpendek menggunakan Algoritma Dijkstra pada lingkungan yang bersifat fuzzy. Untuk jalur terpendek pada skripsi ini didefinisikan rute yang menghasilkan total waktu paling minimum. Agar triangular fuzzy number dapat diimplementasikan pada perangkat lunak, dibutuhkan proses deffuzzification untuk mengubah triangular fuzzy number menjadi bilangan riil(R). Berdasarkan hasil pengujian yang dilakukan, perangkat lunak yang sudah dibangun dapat menjalankan Algoritma Dijkstra untuk kasus yang bersifat Fuzzy.