samodro bagus prasetyanto bilqis amaliah,...
Post on 04-Apr-2019
229 Views
Preview:
TRANSCRIPT
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 3atau 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 adalahsegitiga 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 adalahbahasa 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)
P(Ã) = 1
6(a1 + 4a2 + a3)
P(B) = 1
6(b1 + 4b2 + b3)
P(Ã⊕ B) = P(Ã) + P(B) = 1
6(a1 + 4a2 + a3) +
1
6(b1 + 4b2 + b3)
DASAR TEORI (LANJUTAN)
Trapesium Bilangan Fuzzy (Empat bobot pada tiap edge)
P(Ã) = 1
6(a1 + 2a2 + 2a3 + a4)
P(B) = 1
6(b1 + 2b2 + 2b3 + b4)
P(Ã⊕ B) = P(Ã) + P(B) = 1
6(a1 + 2a2 + 2a3 + a4) +
1
6(b1 + 2b2 + 2b3 + b4)
DASAR TEORI (LANJUTAN)
• Node 1 – 3 -> 1
6* (4 + 2 * 5 + 2 * 7 + 8) = 6
• Node 1 – 5 -> 1
6* (12 + 2 * 13 + 2 * 18 + 19) = 15,5
DASAR TEORI (LANJUTAN)
• Node 1 – 4 -> 1
6* (4 + 2 * 5 + 2 * 7 + 8) +
1
6* (1 + 2 * 2 + 2 * 4 + 5) =
1
6* (5 + 2 * 7 + 2 * 11 + 13) = 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 tidakada titik yang terhubung dengan Vs, maka hentikanperulangan
• Langkah 2. Gabungkan titik tersebut dan hapus titik Vu, V :=V – {u}.
• Langkah 3. Perbarui nilai bobot pada tiap sisi W[s,j], pilihyang lebih dekat antara dist(W[s,u], fuzzy) + dist(W[u,j],fuzzy) dan dist(W[s,j], fuzzy). Selanjutnya, pergi ke Langkah1.
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 padastudi kasus antar kota di Pulau Jawa
Pengujian 2
• Pengujian untuk membandingkan penggunaanmemori dan waktu proses antara metode fuzzynode combination dengan algoritma fuzzy Dijkstra(50 kali pengujian, 1 pengujian 1000 graph)
HASIL PENGUJIAN 1
No Rute Jarak (km)
1 Surabaya->Mojokerto->Kediri->Blitar 177,032 Surabaya->Mojokerto->Kediri 131,523 Surabaya->Mojokerto->Jombang->Madiun 174,484 Surabaya->Malang 103,455 Surabaya->Mojokerto 54,386 Surabaya->Mojokerto->Jombang 85,087 Surabaya->Pasuruan 66,308 Surabaya->Pasuruan->Probolinggo 104,909 Surabaya->Surabaya 0,00
10 Surabaya->Pasuruan->Probolinggo->Banyuwangi 302,9011 Surabaya->Tuban 96,50
12 Surabaya->Mojokerto->Jombang->Madiun->Magetan 201,6713 Surabaya->Mojokerto->Jombang->Madiun->Ngawi 208,5714 Surabaya->Mojokerto->Jombang->Madiun->Ponorogo 205,18
HASIL PENGUJIAN 1 (LANJUTAN)
No Rute Jarak (km)
15Surabaya->Mojokerto->Jombang->Madiun-> Ponorogo-> Pacitan 281,58
16 Surabaya->Pasuruan->Probolinggo->Jember 204,90
17Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> Sragen->Surakarta ->Magelang 393,63
18Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> Sragen->Surakarta ->Semarang-> Pekalongan 510,18
19Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> Sragen->Surakarta ->Semarang 414,08
20Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> Sragen->Surakarta 299,42
21Surabaya->Mojokerto->Jombang->Madiun-> Ngawi-> Sragen->Surakarta ->Semarang-> Pekalongan->Tegal 573,88
HASIL PENGUJIAN 1 (LANJUTAN)No Rute Jarak (km)
22Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Yogyakarta 367,55
23Surabaya->Mojokerto->Jombang->Madiun->Ponorogo-> Pacitan->Wonosari 352,68
24 Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen 263,92
25Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen-> Surakarta->Yogyakarta->Purworejo 430,23
26Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Yogyakarta->Purworejo->Purwokerto 547,90
27Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Yogyakarta->Purworejo-> Purwokerto->Cilacap 582,20
28Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Magelang->Temanggung->Wonosobo 457,88
29Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Magelang->Temanggung 417,78
30Surabaya->Mojokerto->Jombang->Madiun->Ngawi->Sragen-> Surakarta->Semarang->Rembang 530,08
HASIL PENGUJIAN 1 (LANJUTAN)No Rute Jarak (km)
31Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Semarang->Pekalongan->Tegal-> Cirebon 649,33
32Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya 696,40
33Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Semarang->Pekalongan->Tegal-> Cirebon->Subang 771,33
34Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya->Bandung 819,90
35Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Semarang->Pekalongan->Tegal-> Cirebon-> Subang->Purwakarta 822,33
36Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya->Bandung->Cianjur 886,50
HASIL PENGUJIAN 1 (LANJUTAN)No Rute Jarak (km)
37Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya->Bandung->Cianjur->Sukabumi 917,00
38Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Yogyakarta->Purworejo-> Purwokerto->Tasikmalaya->Bandung->Cianjur->Bogor 946,10
39Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Semarang->Pekalongan->Tegal-> Cirebon->Subang->Bekasi 898,33
40Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Semarang->Pekalongan->Tegal-> Cirebon->Subang->Bekasi->Jakarta 939,27
41Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Semarang->Pekalongan->Tegal-> Cirebon->Subang->Bekasi->Jakarta->Tangerang 971,92
HASIL PENGUJIAN 1 (LANJUTAN)
No Rute Jarak (km)
42Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta->Semarang->Pekalongan->Tegal-> Cirebon-> Subang->Bekasi->Jakarta->Tangerang->Serang 1038,32
43
Surabaya->Mojokerto->Jombang->Madiun->Ngawi-> Sragen->Surakarta ->Semarang->Pekalongan->Tegal-> Cirebon-> Subang->Bekasi->Jakarta->Tangerang->Serang->Merak 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 nilaialpha maka H0 ditolak sehingga kedua metodetersebut memiliki perbedaan waktu proses yangsignifikan.
HASIL PENGUJIAN 2 (LANJUTAN)
Pengunaan Memori
HASIL PENGUJIAN 2 (LANJUTAN)
Penjelasan Pengunaan Memori
Algoritma fuzzy Dijkstra membutuhkanmemori tambahan untuk penyimpanansementara jarak antar node (d) seperti padaPembaruan jarak bobot edge (W) dilakukan olehmetode fuzzy node combination, sehinggametode ini tidak membutuhkan memoritambahan.
KESIMPULAN
1. Pencarian rute terpendek untuk studi kasusantar kota di Pulau Jawa dapat diselesaikandengan metode fuzzy node combination
2. Metode fuzzy node combination dapatmenambahkan dua jalur terhubung yangdirepresentasikan oleh bilangan fuzzy
3. Metode fuzzy node combination dapatmembandingkan dua rute yangdirepresentasikan oleh bilangan fuzzy
4. Rute terpendek antar kota di Pulau Jawa jugadapat ditampilkan
KESIMPULAN
5. Metode fuzzy node combination memilikiwaktu proses yang hampir sama denganalgoritma fuzzy Dijkstra, namun penggunaanmemori pada metode fuzzy nodecombination 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
top related