Seiring perkembangan zaman, smartphone android saat ini sudah memiliki fitur Global Positioning Sistem (GPS) untuk mencari posisi dengan koordinat dengan bantuan satelit. Untuk smartphone yang telah didukung oleh GPS, penggunanya dapat mengetahui posisinya saat itu juga dengan memanfaatkan fungsi GPS yaitu Location-Based Services (LBS). Algoritma Simple Hill Climbing merupakan metode menentukan node-node yang telah diberi jarak antar node, dengan membandingkan node yang telah ada berdasarkan pemilihan jarak terdekat dari posisi sekarang. Pada aplikasi Pencarian lokasi objek wisata di Sumatera Barat ini diterapkan metode Simple Hill Climbing untuk mendapatkan hasil pencarian jarak terdekat dari lokasi pengguna. Selain itu aplikasi pencarian lokasi objek wisata ini juga akan menampilkan lokasi objek wisata yang dilewati oleh pengguna dalam perjalanan ke lokasi objek wisata tujuan. Diharapkan dengan adanya aplikasi ini dapat memudahkan pencarian lokasi objek wisata di Sumatera Barat. Berdasarkan pengujian black box diketahui bahwa aplikasi sudah berjalan dengan benar dan sesuai dengan fungsi yang
diharapkan, kemudian pengujian cyclomatic complexity, algoritma Simple Hill Climbing dikategorikan dalam kode yang ditulis dengan baik dan terstruktur serta hight testability karena tidak terdapat v(G) diatas 10, sementara berdasarkan hasil pengujian kesesuaian sistem, didapatkan 94.6% responden setuju bahwa aplikasi bermanfaat, kemudian didapatkan 92.6% responden setuju bahwa aplikasi mudah untuk digunakan dan 90% responden setuju bahwa aplikasi sesuai dengan kebutuhan dalam mencari wisata di Sumatera Barat.

Kata kunci : Android, Global Positioning System, Jarak Terdekat, Location Based Service, Simple Hill Climbing