Fuzzy Node Combination untuk Menyelesaikan Masalah Pencarian Rute Terpendek. Studi Kasus : Antar Kota di Pulau Jawa
Samodro Bagus Prasetyanto Bilqis Amaliah, S.Kom., M.Kom. Dr. Chastine Fatichah, S.Kom., M.Kom.
LATAR BELAKANG
Shortesh Path Problem (SPP)
Umumnya Dijkstra
Tidak dapat mencari rute terpendek pada lingkungan yang tidak pasti
Bobot pada tiap edge berjumlah 3 atau 4 bobot
Fuzzy Node Combination
RUMUSAN MASALAH Bagaimana menambahkan dua jalur terhubung yang direpresentasikan oleh bilangan fuzzy? Bagaimana membandingkan dua rute yang direpresentasikan oleh bilangan fuzzy? Bagaimana mengkombinasikan metode node combination dengan teori himpunan fuzzy untuk mencari rute terpendek antar kota di Pulau Jawa?
Bagaimana menampilkan rute terpendek antar kota di Pulau Jawa?
LINGKUP MASALAH Teori himpunan fuzzy yang digunakan adalah segitiga bilangan fuzzy dan trapesium bilangan fuzzy Jumlah bilangan fuzzy di tiap rute pada satu graph memiliki jumlah yang sama Jumlah node pada satu graph tidak melebihi 200 node
LINGKUP MASALAH (LANJUTAN) Bahasa pemrograman yang digunakan adalah bahasa C/C++ Angka pada bobot edge harus naik dan positif Studi kasus yang digunakan adalah antar kota di Pulau Jawa
DASAR TEORI Segitiga Bilangan Fuzzy (Tiga bobot pada tiap edge)
1 6
P(Ã) = (a1 + 4a2 + a3)
1 6
P(B) = (b1 + 4b2 + b3)
1 6
P(Ã ⊕ B) = P(Ã) + P(B) = (a1 + 4a2 + a3) +
1 6
(b1 + 4b2 + b3)
DASAR TEORI (LANJUTAN) Trapesium Bilangan Fuzzy (Empat bobot pada tiap edge)
1 6
P(Ã) = (a1 + 2a2 + 2a3 + a4)
1 6
P(B) = (b1 + 2b2 + 2b3 + b4)
1 6
1 6
P(Ã ⊕ B) = P(Ã) + P(B) = (a1 + 2a2 + 2a3 + a4) + (b1 + 2b2 + 2b3 + b4)
DASAR TEORI (LANJUTAN)
1 6 1 6
• Node 1 – 3 -> * (4 + 2 * 5 + 2 * 7 + 8) = 6 • Node 1 – 5 -> * (12 + 2 * 13 + 2 * 18 + 19) = 15,5
DASAR TEORI (LANJUTAN)
• Node 1 – 4
1 -> * (4 + 2 * 5 + 2 * 7 + 8) + 6 1 * (1 + 2 * 2 + 2 * 4 + 5) = 6 1 * (5 + 2 * 7 + 2 * 11 + 13) 6
=9
FUZZY NODE COMBINATION • Langkah 0. Inisialisasi. W[s,u] := 0, vu := vs, V := V – {s}, fuzzy := 3 atau 4 • Langkah 1. Memilih titik yang terdekat dengan Vs. Jika tidak ada titik yang terhubung dengan Vs, maka hentikan perulangan • Langkah 2. Gabungkan titik tersebut dan hapus titik Vu, V := V – {u}. • Langkah 3. Perbarui nilai bobot pada tiap sisi W[s,j], pilih yang lebih dekat antara dist(W[s,u], fuzzy) + dist(W[u,j], fuzzy) dan dist(W[s,j], fuzzy). Selanjutnya, pergi ke Langkah 1.
DATA SET Antar Kota di Pulau Jawa Google Maps November 2013 Tiga bobot pada tiap edge/rute 43 kota dan 64 rute antar kota
PENGUJIAN Pengujian 1 • Pengujian metode fuzzy node combination pada studi kasus antar kota di Pulau Jawa
Pengujian 2 • Pengujian untuk membandingkan penggunaan memori dan waktu proses antara metode fuzzy node combination dengan algoritma fuzzy Dijkstra (50 kali pengujian, 1 pengujian 1000 graph)
HASIL PENGUJIAN 1 No 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Rute Surabaya->Mojokerto->Kediri->Blitar Surabaya->Mojokerto->Kediri Surabaya->Mojokerto->Jombang->Madiun Surabaya->Malang Surabaya->Mojokerto Surabaya->Mojokerto->Jombang Surabaya->Pasuruan Surabaya->Pasuruan->Probolinggo Surabaya->Surabaya Surabaya->Pasuruan->Probolinggo->Banyuwangi Surabaya->Tuban Surabaya->Mojokerto->Jombang->Madiun->Magetan Surabaya->Mojokerto->Jombang->Madiun->Ngawi Surabaya->Mojokerto->Jombang->Madiun->Ponorogo
Jarak (km) 177,03 131,52 174,48 103,45 54,38 85,08 66,30 104,90 0,00 302,90 96,50 201,67 208,57 205,18
HASIL PENGUJIAN 1 (LANJUTAN) No
Rute Surabaya->Mojokerto->Jombang->Madiun-> Ponorogo-> 15 Pacitan 16 Surabaya->Pasuruan->Probolinggo->Jember Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> 17 Sragen->Surakarta ->Magelang Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> 18 Sragen->Surakarta ->Semarang-> Pekalongan Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> 19 Sragen->Surakarta ->Semarang Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> 20 Sragen->Surakarta Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> 21 Sragen->Surakarta ->Semarang-> Pekalongan->Tegal
Jarak (km) 281,58 204,90 393,63 510,18
414,08 299,42 573,88
HASIL PENGUJIAN 1 (LANJUTAN) No 22 23 24 25 26 27 28 29 30
Rute Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Yogyakarta Surabaya->Mojokerto->Jombang->Madiun->Ponorogo-> Pacitan->Wonosari Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen-> Surakarta->Yogyakarta->Purworejo Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Yogyakarta->Purworejo->Purwokerto Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Yogyakarta->Purworejo-> Purwokerto->Cilacap Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Magelang->Temanggung->Wonosobo Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Magelang->Temanggung Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Semarang->Rembang
Jarak (km) 367,55 352,68 263,92 430,23 547,90 582,20 457,88 417,78 530,08
HASIL PENGUJIAN 1 (LANJUTAN) No 31
32
33
34
35
36
Rute Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Semarang->Pekalongan->Tegal-> Cirebon Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Semarang->Pekalongan->Tegal-> Cirebon->Subang Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya->Bandung Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Semarang->Pekalongan->Tegal-> Cirebon-> Subang->Purwakarta Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya->Bandung->Cianjur
Jarak (km)
649,33
696,40
771,33
819,90
822,33
886,50
HASIL PENGUJIAN 1 (LANJUTAN) No 37
38
39
40
41
Rute Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya->Bandung->Cianjur->Sukabumi Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya->Bandung->Cianjur->Bogor Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Semarang->Pekalongan->Tegal-> Cirebon->Subang->Bekasi Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Semarang->Pekalongan->Tegal-> Cirebon->Subang->Bekasi->Jakarta Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Semarang->Pekalongan->Tegal-> Cirebon->Subang->Bekasi->Jakarta->Tangerang
Jarak (km)
917,00
946,10
898,33
939,27
971,92
HASIL PENGUJIAN 1 (LANJUTAN) No
Rute Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> 42 Sragen->Surakarta->Semarang->Pekalongan->Tegal-> Cirebon-> Subang->Bekasi->Jakarta->Tangerang->Serang Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Semarang->Pekalongan->Tegal-> 43 Cirebon-> Subang->Bekasi->Jakarta->Tangerang-> Serang->Merak
Jarak (km)
1038,32
1072,32
HASIL PENGUJIAN 2 Algoritma Fuzzy Dijsktra
HASIL PENGUJIAN 2 (LANJUTAN) Metode Fuzzy Node Combination
HASIL PENGUJIAN 2 (LANJUTAN) Hasil Uji T
HASIL PENGUJIAN 2 (LANJUTAN) Penjelasan Hasil Uji T
Nilai p-value hasil uji T kurang dari nilai alpha maka H0 ditolak sehingga kedua metode tersebut memiliki perbedaan waktu proses yang signifikan.
HASIL PENGUJIAN 2 (LANJUTAN) Pengunaan Memori
HASIL PENGUJIAN 2 (LANJUTAN) Penjelasan Pengunaan Memori
Algoritma fuzzy Dijkstra membutuhkan memori tambahan untuk penyimpanan sementara jarak antar node (d) seperti pada Pembaruan jarak bobot edge (W) dilakukan oleh metode fuzzy node combination, sehingga metode ini tidak membutuhkan memori tambahan.
KESIMPULAN 1. Pencarian rute terpendek untuk studi kasus antar kota di Pulau Jawa dapat diselesaikan dengan metode fuzzy node combination 2. Metode fuzzy node combination dapat menambahkan dua jalur terhubung yang direpresentasikan oleh bilangan fuzzy 3. Metode fuzzy node combination dapat membandingkan dua rute yang direpresentasikan oleh bilangan fuzzy 4. Rute terpendek antar kota di Pulau Jawa juga dapat ditampilkan
KESIMPULAN 5. Metode fuzzy node combination memiliki waktu proses yang hampir sama dengan algoritma fuzzy Dijkstra, namun penggunaan memori pada metode fuzzy node combination lebih kecil
PENGEMBANGAN
Perlu adanya pengembangan
Tidak hanya terbatas pada variabel jarak secara geometri
Variabel lain: Cuaca, Penggunaan Bahan Bakar, Kondisi jalan dan lain-lain
TERIMA KASIH
