PENCARIAN RUTE TERPENDEK TEMPAT BERSEJARAH DI GORONTALO MENGGUNAKAN ALGORITMA A* Salim Ali1 Agus Lahinta2 Manda Rohandi2
INTISARI Tujuan penelitian ini adalah pencarian rute terpendek tempat bersejarah menggunakan Algoritma A star. Algoritma yang digunakan dalam penelitian ini adalah algoritma A star untuk melakukan pancarian rute terpendek dari posisi user menuju tempat tujuan, A star didapat dari total jarak yang didapat dari node awal ke node sekarang ditambah dengan jarak garis lurus dari node sekarang ke node tujuan, dan untuk menghitung jarak antara node digunakan Spherical Low Of Cosines. Hasil dari penelitian ini adalah aplikasi Mobile GIS yang dapat memberikan informasi mengenai pencarian rute terdekat tempat bersejarah berupa path rute, jarak dan waktu tempuh. Kelemahan dari sistem ini belum mampu menampilkan rute alternatif dan waktu tempuh saat kondisi jalan macet. Kata Kunci : Tempat Bersejarah, Spherical Low Of Cosines, Algoritma A Star , Mobile GIS.
1
Salim Ali, Mahasiswa Teknik Informatika Universitas Negeri Gorontalo
2
Agus Lahinta, ST., M.Kom, Dosen Tenik Informatika Universitas Negeri Gorontalo
2
Manda Rohandi, M.Kom, Dosen Tenik Informatika Universitas Negeri Gorontalo
1
PENDAHULUAN Sebagai salah satu daerah yang sedang berkembang Gorontalo memiliki berbagai aset yang mampu menarik penduduk luar Gorontalo untuk mengunjungi kota ini. Salah satunya adalah tempat bersejarah namun kurangnya promosi dari tempat bersejarah ini kepada masyarakat luas mengakibatkan banyak masyarakat yang belum mengetahui tempat bersejarah tersebut. Pada penelitian sebelumnya oleh Manabung (2013) membangun sebuah aplikasi sistem informasi geografis tempat bersejarah di wilayah gorontalo berbasis web, Hasil akhir dari penelitian ini yaitu sebuah aplikasi yang dapat menampilkan informasi tentang jarak antara satu titik ke titik lainnya dengan menggunakan metode spherical law of cosine (Veness, 2010). d = acos(sin(lat1).sin(lat2)+cos(lat1).cos(lat2).cos(long2−long1)).R .....(1) Keterangan : R = jari-jari bumi sebesar 6371(km) d = jarak (km) dalam penentuan jarak. Sedangkan untuk kekurangan dari penelitian ini adalah tidak adanya pencarian rute terpendek. Pada penelitian Aini (2010) dalam penelitian ini, Algoritma A* digunakan dalam penelitian ini untuk melakukan pencarian rute terpendek dari posisi user menuju tempat bersejarah yang dituju. Dalam notasi matematika rumus A* dituliskan sebagai berikut : f(n) = g(n) + h(n) .....(2) Keterangan : • g(n) adalah total jarak yang didapat dari node awal ke node sekarang (halangan) • h(n) adalah perkiraan jarak dari node sekarang (yang sedang dikunjungi) ke node tujuan. Sebuah fungsi heuristik digunakan untuk membuat perkiraan seberapa jauh lintasan yang akan diambil ke node tujuan. (Suyanto dalam Aini, 2010) Dalam penggunaan aplikasi ini user dapat menginputkan kota asal beserta kota tujuan dengan hasil dari pencarian rute tersebut berupa visual, dan belum bisa secara realtime yaitu tidak adanya pencarian rute dari posisi user menggunakan GPS. 2
Dari beberapa penelitian yang di paparkan sebelumnya, peneliti melakukan pengembangan terhadap penelitan-penelitan tersebut, di mana penelitian ini menggabungkan metode Sphercal Low Of Cosines untuk menghitung jarak antara node , dan Algoritma A star digunakan untuk pencarian jalur terpendek dari posisi user ke tempat bersejarah yang dituju. Hasil dari penelitian ini adalah aplikasi Mobile GIS yang dapat memberikan informasi mengenai pencarian rute terdekat tempat bersejarah berupa path rute, jarak dan waktu tempuh.
METODE PENELITIAN A. Pencarian jarak menggunakan spherical law of cosine. Langkah pertama kita mencari jarak antar node dengan menggunakan rumus spherical law of cosine. d = acos(sin(lat1).sin(lat2)+cos(lat1).cos(lat2).cos(long2−long1)).R R = jari-jari bumi sebesar 6371(km) d = jarak (km).
Maka didapat jarak antar node : 102 ke 113 = 0.205553248597453 km 102 ke 110 = 0.237140032193004 km 102 ke 115 = 0.416379647619946 km 102 ke 99 = 0.285976540236757 km 110 ke 74 = 0.713583275204955 km 110 ke 545 = 0.38378049507761 km 110 ke 533 = 0.0482303082305784 km 533 ke 489 = 0.0501830714927805 km 533 ke 112 = 0.45860353629114 km
3
102
0.194871251349366 km
113
0.397461951204292 km
110
0.0559305085934083 km
115
0.420951065278373 km
99
0.384714117603433 km
74
0.743823657936763 km
545
0.429671652560619 km
533
0.0501830714927805 km
489
0 km
112
0.478860663395206 km
Gambar 1 Jarak garis lurus masing-masing node
B. Pencarian rute terpendek menggunakan algoritma A star Setelah didapat jarak menggunakan spherical law of cosine maka pencarian rute terpendek dilakukan dengan algoritma A Star Langkah 1 Node awal adalah 102 kemudian bangkitkan suksesor dari node 102 yaitu: 113, 110, 99, 115 Fungsi evaluasi: f(113) = g(113) + h(113) = 0.205553248 + 0.397461951 = 0.603015199 f(110) = g(110) + h(110) = 0.293070540 + 0.055930508= 0.293070540 f(99) = g(99) + h(99) = 0.285976540 + 0.384714117 = 0.670690657 f(115) = g(115) + h(115) = 0.416379647+ 0.420951065 = 0.837330712 Selanjutnya 110 terpilih sebagai bestnode, Langkah pertama ini menghasilkan OPEN=[113,99,115] dan CLOSED=[ 102,110]
4
Langkah 2 best node adalah 110 kemudian bangkitkan suksesor dari node 110 yaitu: 533, 545, 74. Fungsi evaluasi: f(533) = g(533) + h(533) = 0.285370340 + 0.050183071 = 0.335553411 f(545) = g(545) + h(545) = 0.620920527 + 0.429671652 = 1.050592179 f(74) = g(74) + h(74) = 0.950723307 + 0.743823657 = 1.694546965 Selanjutnya 533 terpilih sebagai bestnode, Langkah pertama ini menghasilkan OPEN=[113,115,99,545] dan CLOSED=[102,110,533]
Langkah 3 best node adalah 533 kemudian bangkitkan suksesor dari node 533 yaitu: 489, 112. Fungsi evaluasi: f(489) = g(489) + h(489) = 0.335553411+ 0 = 0.335553411 f(112) = g(112) + h(112) = 0.743973876 + 0.478860663 = 1.222834540 Selanjutnya 489 terpilih sebagai bestnode, Langkah pertama ini menghasilkan OPEN=[113,115,99,545,112] dan CLOSED=[102,110,533,489], 489 terpilih sebagai bestnode. Karena bestnode-nya sama dengan goal, berarti solusi telah ditemukan, penelusuran menghasilkan rute 102-110-533-489 = (102 ke 110) + (110 ke 533) + (533 ke 489) = 0.237140032193004 + 0.0482303082305784 + 0.0501830714927805 dengan total jarak dengan 0.335553411 Km, dan lintasan ini merupakan lintasan terpendek dari node 102 ke node 489.
5
HASIL DAN PEMBAHASAN Hasil dari penelitian ini adalah aplikasi Mobile GIS yang dapat memberikan informasi mengenai pencarian rute terdekat tempat bersejarah berupa path rute, jarak dan waktu tempuh, Algoritma A* yang telah diterapkan telah berjalan dengan baik , tetapi terbatasnya titik koordinat yang ada pada perempatan dan pertigaan, serta tidak adanya tittik koordinat pada jalan lurus menyebabkan kurang tepatnya node awal yang dipilih, pada algoritma A star tidak membutuhkan waktu dan memori yang banyak dalam pencarian rute terdekat karena tidak semua node yang menncapai tujuan dilakukan pengujian. A. Penerapan spherical law of cosine ke dalam script : public double CalculationByDistance2(double latAwal, double lonAwal, double latAkhir, double lonAkhir){ // ubah ke radian double radianLatAwal = toRadians(latAwal); double radianLatAkhir = toRadians(latAkhir); double radianLonAwal = toRadians(lonAwal); double radianLonAkhir = toRadians(lonAkhir); double bedaLongitude = radianLonAkhir - radianLonAwal; double radiusBumi = 6371; //jarak dalam km // Spherical Law of Cosines double sinLatAwal = Math.sin(radianLatAwal); double sinLatAkhir = Math.sin(radianLatAkhir); double cosLatAwal = Math.cos(radianLatAwal); double cosLatAkhir = Math.cos(radianLatAkhir); double cosBedaLongitude = Math.cos(bedaLongitude); double double cosBedaLongitude; double double
sinLatLat = sinLatAwal * sinLatAkhir; cosLatLatLon = cosLatAwal * cosLatAkhir * jumSinCos = sinLatLat + cosLatLatLon; acosJumSinCos = Math.acos(jumSinCos);
double distance = acosJumSinCos * radiusBumi; return distance; }
Pada metode spherical law of cosine langkah awal ubah nilai latitude dan longitude ke angka radian kemudian tentukan radius bumi 6371 km setelah angka dirubah keradian, dicari beda longitude awal dan longitude akhir, kemudian kalikan sin latitude awal dan sin latitude akhir, selanjutnya kalikan cos latitude awal, latitude akhir, dan cos beda longitude, selanjutnya sin latitude awal, sin latitude akhir di jumlahkan dengan cos latitude awal, cos latitude akhir,cos beda
6
longitude kemudian jumlanya di acos kan, setelah itu dikalikan dengan radius bumi. B. Penerapan algoritma A Star ke dalam script : public void CariRute(){ latTemp = latAsal; lonTemp = lonAsal; Node node = new Node(); Node nodet = new Node(); Node nskrg = new Node(); Lokasi lokasiasal = new Lokasi(); Lokasi lokasitujuan = new Lokasi(); // masukkan titik asal sebagai close awal node = QueryNode(latTemp, lonTemp); nodet = QueryNode(latTujuan, lonTujuan); lokasitujuan = QueryLokasi(nodet.GetIdasal()); _closed.add(node.GetIdasal()); close.put(node.GetIdasal(), node); nskrg = node; // cari selama asal != tujuan while((nskrg.GetIdasal()!=nodet.GetIdasal()) && (NilaiFnTerkecil(nskrg)!=true )){ // cari node fn pendek Node fnpendek = Bangkitkan(nskrg); lokasiasal = QueryLokasi(nskrg.GetIdasal()); // cek Fn terkecil dari daftar open //Node nodependek = CariFnPendek(); Node nodependek = fnpendek; if(CekNode(nodependek)!=true){ // masukkan daftar close nodependek.SetClosed(true); _closed.add(nodependek.GetIdasal()); close.put(nodependek.GetIdasal(), nodependek); int id = nodependek.GetIdasal(); open.remove(id); _path = new ArrayList(nodependek.path); _path.add(nodependek.GetIdasal()); jaraktempuh = nodependek.GetGn(); nskrg = nodependek; }
Pada Algoritma A* ini langkah awal masukan titik awal sebagai close akan terus mencari selama titik awal tidak sama dengan titik tujuan dan fn sekarang tidak 7
sama dengan fn terkecil, langkah selanjutnya cari fn pendek dari daftar open kemudian masukan fn pendek ke daftar close.
Gambar 2 tampilan pencarian rute Pada tampilan pencarian rute ini user dapat melihat rute terpendek, waktu, dan jarak dari posisi user menuju tempat bersejarah yang dituju.
KESIMPULAN DAN SARAN Kesimpulan dari penelitian ini adalah menggabungkan algoritma A star untuk mencari rute terpendek lokasi tempat bersejarah, dan spherical law of cosine untuk mengukur jarak antar node, dan dibuatkan aplikasi Mobile GIS yang dapat memberikan informasi mengenai pencarian rute terdekat tempat bersejarah berupa path rute, jarak dan waktu tempuh. Adapun saran untuk pengembangan selanjutnya
sistem ini mampu
menampilkan rute alternatif dan waktu tempuh saat kondisi jalan macet.
8
DAFTAR PUSTAKA Aini, Dewi Yusra. Analisis Algoritma A Star (A*) Dan Implementasinya Dalam Pencarian Jalur Terpendek Pada Jalur Lintas Sumatera Di Provinsi Sumatera Utara. [skripsi], Fakultas Matematika Dan Ilmu Pengetahuan Alam
,Universitas
Sumatera
Utara,
(http://repository.usu.ac.id/bitstream/123456789/22616/2/Chapter%20IIIV.pdf, diakses 9 November 2013) Manabung, A. 2013. Sistem Informasi Geografis Tentang Tempat Bersejarah Dan Budaya Yang Terdapat Diwilayah Gorontalo Berbasis Web, Jurusan Teknik Informatika, Universitas Negeri Gorontalo. Veness,
C.,
2010.
Calculate
distance,
Latitude/Longitude
bearing points,
and
more
between (Online)
(http://www.movabletype.co.uk/scripts/latlong.html, diakses 03 april 2014)
9
