## PENERAPAN ALGORITMA A* UNTUK MENCARI JARAK TERDEKAT TEMPAT WISAT KOTA MALANG RAYA
Mukhlis 1 , Mira Orisa 2 , F.X Ariwibisono 3
Program Studi Teknik Informatika S1, Fakultas Teknologi Industri Institut Teknologi Nasional Malang, Jalan Raya Karanglo km 2 Malang, Indonesia
Mkhlis040897@gmail.com

## ABSTRAK
Pariwisata Malang Raya terdiri dari tempat-tempat wisata  yang ada di daerah  Kota Malang, Kabupaten Malang dan Kota Batu. Setiap wilayah  administrative  itu  memiliki ciri khas daerah wisatanya  masing-masing. Kota  Malang  menjadi  kota  terbesar  kedua  di  Jawa  Timur  setelah  Kota  Surabaya.  kini  banyak  dikeluhkan warganya  seperti  kemacetan  dan  kesemrawutan  lalu  lintas  di  karenakan  banyaknya  kendaraan  dari  luar  kota yang  berlibur  ke  tempat  wisata-wisata  di  Kota  Malang. Oleh  sebab  itu  waktu  dan  jarak  tempuh  ke  destinasi wisata pun sangat penting untuk kenyaman perjalanan wisatawan.
Kebutuhan  masyarakat terhadap efisiensi  jarak tempuh ke suatu tempat tujuan wisata berdasarkan  jarak tempuh  terdekat  dapat  diselesaikan  dengan  pembuatan  aplikasi  ini.  Pada  aplikasi  ini  menggunakan  algoritma A*. Penerapan algoritma  A*  bertujuan untuk  mencari  jalur dengan  jarak terdekat.  Pendekatan  yang digunakan adalah  pendekatan  heuristik  untuk  memperkirakan  jalur  terbaik  dari  titik  awal  ke  titik  akhir.  Pendekatan  ini memberikan peringkat ke tiap titik yang dilalui dari titik awal ke titik tujuan. Selain itu Google Maps digunakan untuk menampilkan hasil dari perhitungan jarak.
Hasil  dari  pengujian  fungsional  menyatakan aplikasi  berjalan sesuai dengan rancangan. Hasil pengujian penerapan  metode  A*  pada  aplikasi  ini  sudah  sesuai  dengan  perhitungan  manual  algoritma  A*.  Untuk  hasil kuisioner  pengguna  menyatakan  untuk  tampilan  aplikasi  50%  menyatakan  menarik,  90%  menyatakan kemudahan penggunaan  aplikasi, 70%  menyatakan aplikasi  sesuai  fungsinya  yaitu  mencari  jarak terdekat, dan 90% menyatakan fitur berjalan baik.
Kata kunci : Algoritma A*,Pariwisata,Jarak terdekat, Malang, Kota Batu
.
1. PENDAHULUAN
1.1. Latar Belakang
Pemerintah  Kota  Malang  dan  kota  Batu  selalu berbenah  diri  untuk  menjadi  kota  destinasi  wisata yang bukan hanya sebatas wisata berbasis peninggalan  bersejarah  dan  kuliner  saja  tetapi  juga menghadirkan  lebih  banyak  tempat-tempat  wisata yang  baru  seperti  yang  disampaikan  oleh  Sutiaji selaku  Wali Kota  Malang  di  Merdeka.com. pemerintahan  Kota  Malang  menargetkan  pada  tahun 2019  ini  sebanyak  150.000  kunjungan  wisatawan. Sedangkan  Kabupaten  Malang  yang  memiliki  luasan yang  paling  besar  dan  juga  memiliki  potensi pariwisata  yang  besar.  Kota  Batu  juga  memiliki potensi besar karena keindahaan alamnya.
Kota  Malang  menjadi  kota  terbesar  kedua  di Jawa Timur setelah Kota Surabaya. Dengan demikian banyak  warga  yang  mengeluh  dengan  kemacetan lalulintas  di  Kota  Malang  di  karenakan  banyaknya kendaraan  dari  luar  kota  yang  berlibur  ke  tempat wisata-wisata  di  Kota  Malang.  Sebegitu  besarnya daya  tarik  Kota  Malang  sehingga  mampu  menarik massa  begitu  besar tidak  hanya dari dalam  negri tapi juga  luar  negri.  Oleh  sebab  itu  waktu  dan  jarak tempuh ke destinasi  wisata pun sangat penting untuk kenyaman perjalanan wisatawan.
Pada  website  pemerintahan  Kota  malang  belum tersedia  sistem  informasi  geografis  tentang  destinasi
wisata.  Dan  melihat  banyaknya  jalan  raya  dan  jalan alternative di Malang raya sehingga melatarbelakangi dibangun sistem  informasi geografis untuk pencarian jarak  terdekat  wisatawan  dengan  destinasi  wisata demi  kenyaman  perjalanan  wisata.  Sistem  ini  akan dibangun berbasis website dan menerapkan Algoritma A* sebagai perhitungan untuk menentukan jarak  terdekat.  Karena  Algoritma  A*  menggunakan estimasi  jarak  terdekat  untuk  mencapai  tujuan  (goal) dan  memiliki  nilai  heuristik  yang  digunakan  sebagai dasar pertimbangan.

## 1.2. Rumusan Masalah
Dari  latar  belakang  masalah  diatas,  maka rumusan masalah yang akan dibahas pada penelitian ini antara lain:
1. Bagaimana membangun sistem informasi geografis untuk menentukan jarak terdekat bagi para wisatawan ke lokasi wisata?
2. Bagaimana  menerapkan  Algoritma  A*  dalam melakukan penenetuan jarak terdekat untuk para wisatawan di Malang Raya ?

## 1.3. Batasan Masalah
Adapun  batasan  masalah  pada  penelitian  ini sebagai berikut:
1. Sistem  ini  menggunakan  metode  Algoritma  A* dalam penentuan jarak terdekat.
2. Sistem  ini  memberikan  alternatif  keputusan terbaik berdasarkan parameter berupa jarak dan titik  koordinat  yaitu  hanya  satu  rute  yang  akan menjadi output sistem.
3. Data  yang  diambil  adalah  10  tempat  wisata  di Kota  Malang,  10  tempat  wisata  di  kota  Batu, dan 10 tempat wisata di Kabupaten Malang.
4. Sistem  ini  dirancang  bagi  para  wisatawan  di Malang Raya.

## 1.4. Tujuan
Tujuan  dari  pembuatan  aplikasi  ini  adalah sebagai berikut:
1. Merancang  dan  membangun  sebuah  sistem informasi  yang  membantu  para  wisatawan  di Kota  Malang  untuk  menimati  tempat  wisata yang di inginkan.
2. Mampu  menerapkan  Algoritma  A*  untuk sebuah  sistem  informasi  penentuan  jarak terdekat.

## 2. TINJAUAN PUSTAKA

## 2.1. Sistem Informasi Geografis
Sistem  Informasi  Geografis  (SIG)  merupakan suatu  sistem  yang  dirancang  untuk  menangani pengolahan  dan  pengelolan  data  informasi  geografis berupa peta digital. Sering perkembangan zaman  dan pesatnya  perkembangan  teknologi  pada  saat  ini, menjadikan  SIG  sangat  diminati  oleh  orang  banyak dengan  kecanggihan  teknologi  yang  dimiliki [13] . Teknologi  SIG  mengintergrasikan  operasi  –  operasi seperti  database,  query  dan  analisa  statistik, kemampuan  inilah  yang  menjadikan  SIG  beda  dari sistem informasi lainnya yang menjadikan SIG sangat berguna  untuk  merancang  strategi  dan  memprediksi yang terjadi. [11]

## 2.2. Algoritma A*
Algoritma  A*  merupakan  salah  satu  algoritma penentuan  jarak  terdekat.  Algortima  A*  sangat  baik sebagai  solusi  mencari  jarak  rute  tercepat  yang  akan di  tempuh  dari  titik  awal  sampai  ke  titik  tujuan. Algoritma A* menggunakan nilai heuristik yang akan digunakan sebagai dasar pertimbangan. Fungsi heuristik : Dx = ( node x – goal x ) Dy = ( node y – goal y ) Return D* ( Dx + Dy ) Rumus  diatas  digunakan  karena  aplikasi  ini menggunakan  fungsi heuristic  manhattan  distance. Secara umum dapat dijelaskan sebagai berikut: 1. Masukkan titik awal.
2. Setelah itu masuk ke looping, sebagai berikut:
a. Cari titik dengan nilai jarak yang terkecil
b. Pilih  titik  yang  nilainya  terkecil  (yang  akan dilewati)
c. Bandingkan  setiap  titik  tetangga  dan  pilih  yang bernilai  terkecil  (yang  akan  dilewati),  begitu seterusnya sampai ke titik tujuan
d. Looping berhenti. [7]

## 3. METODE PENELITIAN
3.1 Blok Diagram Sistem
Adapun  blok  diagram  dari  sistem  ini  seperti  pada Gambar 1 berikut:
Gambar 1. Blok diagram sistem Pada blok diagram perancangan sistem penentuan  jarak  terdekat  menggunakan  metode Algoritma  A*  ditunjukkan  pada  Gambar  1.    Dari blok  diagram  pada  Gambar  1  menunjukkan  bahwa ketika  wisatawan  membuka  website  GIS  kemudian memasukkan  data  jarak  antara  titik  awal  dan  titik tujuan.  Data  masukakan  tersebut  akan  dimodelkan dalam sebuah persamaan sehingga dapat dilakukkan proses  perhitungan.  Proses  perhitungan  dilakukan menggunakan Algoritma A* dengan bahasa pemrograman web . Kemudian hasil akan ditampilkan  ke  website  GIS  berupa  Map  yang menunjukkan  Jarak  terdekat  yang  dapat  dilewati para  wisatawan  menuju  tempat  wisata  di  Malang Raya.
3.2 Data Flow Diagram Level 0
Gambar 2. DFD level 0
DFD  Level  0  menjelaskan  bahwa  ada  1  pelaku yang  terdapat  di  dalam  aplikasi  yaitu  admin.  Admin yang  bertugas  untuk  mengelola  data  yang  ada  di aplikasi tersebut.
Data Flow Diagram Level 1
Gambar 3. DFD level 1 DFD  level  1  pada  Gambar  3  menyatakan  bahwa penentuan jarak terdekat menggunakan Algoritma A* ini  terdapat  3  proses  yaitu  proses  1 login ,  proses  2 lokasi pariwisata, proses 3 perhitungan jarak terdekat. Setiap  proses  di  jelaskan  dengan  DFD  level  1  secara detail . 3.3 Flowchart Sistem
Gambar 4. Flowchart sistem Sistem  ini  dimulai  dengan  menginputkan  data lokasi,  kemudian  diberikan  input  lokasi  tujuan. Setelah  itu  sistem  akan  melakukan  perhitungan  jarak menggunakan metode Algoritma A*. Proses perhitungan itu sendiri menghasilkan jalur yang akan dilewati sebagai jarak terdekat bagi para wisatawan di kota Malang dan sekitarnya.
3.4 Flowchart Metode Algoritma A*
Gambar 5. Flowchart metode Algoritma A* Metode
Algortima A*dimulai dari menginisialisasikan  antara  titik  awal  ke  titik  tujuan dan  tiap-tiap  titik.  Setelah  itu  menentukan  jarak dengan  cara  menghitung  dan  membandingkan  tiap- tiap  node  sehingga  ditemukan  jarak  terdekat,  setelah ditemukan  maka  diberikan  marker  permanen  pada titik  tersebut.  Setelah  diberikan  marker  maka  akan dibandingkan  lagi  untuk  mencari  jarak  terdekat menuju titik tujuan, maka akan ditemukan  jalur  yang dilewati.

## 4. HASIL DAN PEMBAHASAN
4.1 Halaman Login
Gambar 6. Halaman login
Halaman login admin merupakan  halaman yang ada pertama kali  saat admin  membuka aplikasi. Pada  halaman  login  mengharuskan  admin  harus menginputkan  username  dan  password  agar  bisa melanjutkan  ke  halaman  utama  ( home )  dan  admin mempunyai hak penuh untuk aplikasi ini.

## 4.2 Halaman Home
Gambar 7. Halaman Home
Pada  gambar  7  merupakan  halaman  utama dari aplikasi pencarian jarak terdekat wisata di Kota Malang  Raya.  halaman  utama  ( home )  terdapat  peta lokasi  pariwisata  di  Kota  Malang  Raya    yang  di gunakan untuk mencari jarak terdekat yang dapat di tempuh  para  wisatawan    dari  lokasi  awal  menuju lokasi  tujuan  wisata  berikutnya.  Lokasi  awal menggunakan  tombol  agar  mempermudah  untuk melacak lokasi yang terkini dan tujuan dapat di pilih pada combobox yang telah di sediakan.

## 4.3 Halaman Data Lokasi
Gambar 8. Halaman Data Lokasi
Pada  gambar  8  merupakan  halaman  data lokasi  wisata  yang  ada  di  Kota  Malang  Raya.  Data lokasi  tersebut  digunakan  untuk  mempermudah menentukan destinasi wisata yang ingin dikunjungi di Kota  Malang  Raya.  Admin  juga  bisa  mengubah  dan menghapus data lokasi wisata di kota malang raya.

## 4.4 Halaman Tambah Lokasi
Gambar 9. Halaman Tambah Lokasi
Pada gambar 9 merupakan halaman tambah lokasi yang  digunakan  untuk  menambahkan  lokasi  wisata yang  belum  terdapat  di  peta  di  halaman  utama ( home ),  agar  mempermudahkan  pengguna  ( user ) mencari  jarak  terdekat  yang  di  tempuh  ke  lokasi wisata yang di pilih.
4.5 Halaman Hasil Penentuan Jarak Terdekat
Gambar 10. Halaman hasil
Pada  Gambar  10  merupakan  hasil  penentuan jarak  terdekat  dari  lokasi  awal  si  pengguna  ( user )  ke tempat  wisata  yang  di  tuju.  Hasil  penentuan  jarak terdekat  menampilkan  rute  yang  tercepat  untuk  di tempuh oleh si pengguna ( user ).

## 4.7.Pengujian Algoritma A Star (A*)
Penjelasan  analisis  perhitungan  dari  algoritma  A Star  (A*)  untuk  scenario  1  misalkan  menentukan tujuan  tempat  wisata  Hawai  jika  user  berada  di  ITN kampus  2.  Hal  pertama  yang  akan  dilakukan  user menentukan  tempat  asal.  Dari  tabel  tempat  diambil nilai  Longitude  (x)  dan  Latitude  (y).  Misalkan ditentukan  tempat  asal  adalah  ITN  kampus  2  dengan nilai Longitude (x) = 112.6320693 dan Latitude (y) = -7.9165401  Kemudian  menentukan  tempat  tujuan Hawai Longitude (x) = 112.6570293 dan Latitude (y) -7.923639. Selain itu diketahui bahwa terdapat 2 rute yang bisa dilalui user untuk sampai ke tempat tujuan. Kemudian  dilakukan  perhitungan  heuristic  untuk menentukan  rute  mana  yang  paling  dekat.  Rumus Heuristic ecludian distance:
d (x,y) = √ ( x1 – y1)² + (x2– y2)² Hasil dari perhitungan adalah : Tabel 1 Heuristic Ecludian Distance
Rute Heuristic ecludian distance Rute 1 25.8 – 16.2 – 10 – 3.4 – 8 – 10 – 4 – 8 Rute 2 25.8 – 16.2 – 12 – 16 – 8
Maka  menurut  hasil  perhitungan  algoritma  A* didapatlah rute 1 untuk di tempuh oleh user menuju ke tempat  tujuan.  Rute  1  memiliki  nilai  antar  node  yang lebih  pendek  dibandingkan  rute  2.  Pada  saat persimpangan  Algoritma  A*  memilih  node  yang memiliki  nilai  paling  kecil  untuk  rute  yang  akan dilewati  selanjutnya  maka  pada  2  persimpangan  yang ditemui  saat  user  akan  menuju  hawai  yaitu persimpangan  1  memiliki  nilai  nodenya  10  dan persimpangan  2  memiliki  nilai  node  12,  sehingga dipilihlah  rute  yang  akan  ditempuh  selanjutnya  yaitu
persimpangan  yang  memiliki  nilai  node  terkecil  yaitu 10. Hal tersebut dapat terlihat pada Gambar 11
Gambar 11. Rute Jalur 1
Gambar 12. Graph Rute Jalur 1
Gambar 13. Rute Jalur 2
Gambar 14. Graph Rute Jalur 2

## 4.6    Pengujian Fungsional Aplikasi
Pengujian  fungsional  merupakan  cara  untuk mengetahui  apakah  fitur-fitur  dari  aplikasi  yang tersedia  dapat  berjalan  tanpa  ada  kendala  yang
membuat  sistem  tidak  berfungsi  dengan  baik.  Dalam tahapan  pengujian  fungsional  ini  di  mulai  dari halaman registrasi hingga selesai.
Hasil  pengujian  fungsional  fitur-fitur  aplikasi dapat  dilihat  pada  tabel  diatas.  Setelah  dilakukan pengujian terhadap 2 browser tersebut, semua fungsi dari sistem berjalan sesuai dengan yang diinginkan.
Tabel . 2 .Pengujian Fungsional

## 5. KESIMPULAN DAN SARAN

## 5.1 Kesimpulan
Setelah  melakukan  pengujian  pada  aplikasi penentuan  jarak  terdekat  dengan  menggunakan Algoritma  A*,  maka  dapat  di  Tarik  kesimpulan sebagai berikut:
1. Pada  pengujian  fungsional  yang  dilakukan  dapat di  simpulkan  bahwa  aplikasi  penentuan  jarak terdekat  tempat  wisata  di  Kota  Malang  Raya dengan  menggunakan  Algortima  A*  dapat berjalan  sesuai  dengan  yang  di  inginkan  pada beberapa browser seperti Mozzila dan Chrome . 2. Untuk  hasil  kuisioner  pengguna  menyatakan untuk tampilan aplikasi 50% menyatakan menarik, 90% menyatakan kemudahan penggunaan  aplikasi,  70%  menyatakan  aplikasi sesuai fungsinya yaitu mencari jarak terdekat, dan 90% menyatakan fitur berjalan baik.
3. Dari  10  kasus  yang  diuji  pada  aplikasi menyatakan bahwa aplikasi telah berhasil berjalan
sesuai  dengan  perhitungan  manual  dari  algoritma A*.

## 5.1 Saran
Pada  rancang  bangun  aplikasi  penentuan  jarak terdekat dengan menggunakan Algoritma A* terdapat kelebihan  dan  kekurangan,  oleh  karena  itu  saran untuk memperbaiki sistem ini.
Berikut  ini  adalah  saran  dari  penelitian  yang telah dilakukan:
1. Memperbaiki  program  agar  bisa  memberikan lebih  dari  1  jalur  yang  di  rekomendasikan  ke pengguna ( user ).
2. Dikembangkan  pada  perangkat mobile seperti  di
Android dan iOS agar lebih mempermudah untuk di gunakan.

## DAFTAR PUSTAKA
1. Syahputra,  Siswan.  (2017).  Penentuan  Rute Terpendek Pendistribusian Naskah Ujian Nasional Menggunakan Algoritma Dijkstra
(Dinas  Pendidikan  Dan  Pengajaran  Kota  Binjai). Rute Terpendek, Algoritma Djikstra.
2. Sulistiani,  Heni  dan  Danang  Ari  Wibowo. (2018).  Perbandingan  Algoritma  A*  Dan Dijsktra  Dalam  Pencarian  Kecamatan  Dan Kelurahan  Di  Bandar  Lampung. Perbandingan Algoritma A* dan Algoritma Dijsktra.
3. Pratiarso,  Aries  dkk.  (2010).  Perbandingan Metode  Ant  Colony  Optimization  Dan  Dijkstra Untuk Pengembangan Sistem Pengiriman Barang Di  Kantor  Pos  Area  Surabaya  Timur  Berbasis J2ME. Perbandingan  Metode  Ant  Colony Optimization dan Algoritma Dijkstra.
4. Joni,  Luh  Erawati  Dewi.  (2010).  Pencarian  Rute Terpendek  Tempat  wisata  Di  Bali  Dengan Menggunakan Algoritma Djikstra Rute Terpendek, Algoritma Djikstra.
5. Saputra, Ragil. (2011). Sistem Informasi Geografis  Pencarian  Rute  Optimum  Obyek Wisata  Kota  Yogyakarta  Dengan  Algoritma Floyd-Warshall. Sistem  Informasi  Geografis Pencarian Rute, Algoritma Floyd-Warshall.
6. Musabbichin,  Laylul.  Mula’ab.,  dan  Rika Yunitarini.  (2015).  Sistem  Informasi  Geografis Penentuan  Jalur  Terpendek  Untuk  Menghindari Daerah  Rawan  Banjir    (Studi  Kasus  Propinsi Jawa  Timur). Sistem  Informasi  Geografis,  Jalur Terpendek.
7. Syukriyah,  Yenie.  Falahah,  dan  Hermi  Solihin. (2016).  Penerapan  Algoritma  A*  (Star)  Untuk Mencari  Rute  Tercepat  Dengan  Hambatan. Algoritma A*, Rute Tercepat.
8. Juniawan, Panca Fransiskus. Dwi Yuny Sylfania.,  dan  Eza  Budi  Perkasa.  (2017). Pemanfaatan Algoritme A* Menggunakan Aispace  Dalam Pencarian Rute Terpendek. Rute Terpendek, Algoritme A*.
9. Fatkhurrozi, Bagus dan Ika Setyowati. Pencarian Rute  Terpendek  Objek  Wisata  Di  Magelang
Menggunakan  Ant  Colony  Optimization  (Aco). Pencarian  Rute  Terpendek,  Metode  Ant  Colony Optimization.
10. Andriani,  Anik. (2014). Rancang Bangun Sistem Informasi  Rute  Wisata  Terpendek  Berbasis Algoritma  Floyd-Warshall. Rancang  Bangun Sistem  Informasi  Rute  Wisata  Terpendek, Algoritma Floyd- Warshall.
11. Aini,  Anisah  (2007).  Artikel  Mengenai  Sistem Informasi Geografis Pengertian Dan Aplikasinya
12. Putri, W.R., 2012. Artikel Mengenai Pemrograman Web. Diambil dari:http://ilmukomputer.org/wpcontent/uploads/ 2012/10/windapemrograman-web.  pdf  .  Diakses pada 7 Agustus 2018.
13. Rokhman, Moh Miftakhur. 2017. Sistem Informasi Geografi Pemetaan Sebaran Lokasi Fasilias Kesehatan Masyarakat Di Wilayah Kota
Malang Berbasis Web. Pemetaan, SIG, Kesehatan.