ABSTRAKSI: LBS adalah sebuah layanan informasi yang dapat diakses dari perangkat bergerak dan memanfaatkan posisi geografis dari perangkat bergerak tersebut. Dalam pengaplikasiannya, LBS dapat mencakup berbagai konteks seperti pekerjaan, kesehatan, kehidupan pribadi, mengidentifikasi seseorang atau benda seperti menemukan ATM terdekat.
Dalam tugas akhir ini, akan dibangun sebuah sistem dengan memanfaatkan GPS untuk diaplikasikan pada LBS yang akan menginformasikan sarana-sarana umum pada pengguna. Sistem ini menggunakan algoritma Dijkstra dan A*. Heuristik yang digunakan pada algoritma A* adalah Manhattan, Distance, Euclidean, dan Custom. Masing-masing algoritma ini akan diuji dengan titik-titik yang berbeda pada pengguna yang berbeda.
Dari hasil pengujian didapatkan A* dengan heuristik custom paling efisien dari sisi vertex yang dikunjungi. Edge pada pejalan kaki lebih banyak dari edge pada pengguna kendaraan itu sebabnya jarak yang ditempuh pada pengguna pengendara relatif sama pada masing-masing algoritma. Untuk heuristik Manhattan, Distance, Euclidean tidak disarankan digunakan untuk studi kasus seperti pada tugas akhir ini. Ini disebabkan nilai heuristiknya terlalu kecil sehingga menyamai hasil yang didapat oleh Dijkstra.Kata Kunci : LBS, GPS, Dijkstra, A*, Manhattan, Distance, Euclidean, heuristikABSTRACT: LBS is an information service that is accessible from mobile devices and take advantage of the geographical position from these mobile devices. In its application, LBS may include a variety of contexts such as employment, health, personal life, identifying a person or an object, e.g. finding the nearest ATM.
In this research, a system using GPS applied on LBS is built, which will result for information of the public facilities for the user. This system uses Dijkstra's algorithm and A* algorithm. Heuristics used in the algorithm A* are Manhattan, Distance, Euclidean, and Custom. Each of these algorithms will be tested with different points on different users.
From the test results obtained, by analyzing the sum of vertices being visited, it is concluded that A* using Custom heuristic is the most efficient. Also, there are more edges resulted for pedestrians than for the vehicle users, therefore the distance traveled for a vehicle user is relatively the same for each algorithms. Meanwhile, Manhattan, Distance, and Euclidean heuristics are not recommended to use for such a case study in this thesis. It is because the heuristic value is too small so that the results obtained is nearly the same as using Dijkstra.Keyword: LBS, GPS, Dijkstra, A*, Manhattan, Distance, Euclidean, heuristik