INNOVATIVE: Journal Of Social Science Research Volume 3 Nomor 6 Tahun 2023 Page 7049-7061 E-ISSN 2807-4238 and P-ISSN 2807-4246
Website: https://j-innovative.org/index.php/Innovative

## Implementasi Algoritma A* Pada Sistem Informasi Geografis (GIS) SEKTOR Industri Pariwisata Kota Tomohon
Raffy Avian Sulaeman 1 ✉ , Gladly C. Rorimpandey 2

## Universitas Negeri Manado
Email: raffyas@gmail.com 1 ✉

## Abstrak
Pertumbuhan pesat industri pariwisata di Kota Tomohon menuntut solusi teknologis yang canggih untuk meningkatkan pengalaman pengunjung secara keseluruhan. Sistem Informasi Geografis (GIS) menawarkan  solusi  yang  menjanjikan  untuk  analisis  data  spasial  dan  pengambilan  keputusan  di sektor  pariwisata.  Tujuan  utama  penelitian  ini  adalah  mengimplementasikan  GIS  yang  disesuaikan dengan sektor pariwisata Kota Tomohon. Penelitian ini secara khusus fokus pada integrasi algoritma A* untuk mengoptimalkan perencanaan rute dan navigasi di dalam objek wisata. Implementasi GIS melibatkan  desain  arsitektur  sistem  yang  komprehensif.  Data  geografis,  termasuk  peta  dan  lokasi wisata, menjalani proses pemrosesan yang teliti. Algoritma A* kemudian diintegrasikan ke dalam GIS untuk  memberikan perencanaan rute yang efisien dan optimal bagi pengunjung. Implementasi ini menunjukkan peningkatan navigasi dan optimasi rute di sektor pariwisata Kota Tomohon. Analisis perbandingan dengan metode alternatif menegaskan efektivitas algoritma A* dalam meningkatkan pengalaman  pengguna.  Sebagai  kesimpulan,  integrasi  GIS  dengan  algoritma  A*  terbukti  menjadi aset berharga untuk industri pariwisata di Kota Tomohon.
Kata Kunci : Algoritma A*, Sistem Informasi Geografis, Industri Pariwisata

## Abstract
The rapid growth of Tomohon's tourism industry necessitates advanced technological solutions for an enhanced visitor experience. Geographic Information System (GIS) emerges as a promising tool for spatial data analysis and decision-making in tourism. This study aims to implement a GIS tailored to  Tomohon's  tourism  sector,  specifically  focusing  on  integrating  the  A*  algorithm  for  optimized route planning and navigation within attractions. The GIS implementation involves a comprehensive system architecture design, meticulous processing of geographic data, and the integration of the A* algorithm.  This  results  in  improved  navigation  and  route  optimization  within  Tomohon's  tourism sector.  Comparative  analysis  with  alternative  methods  confirms  the  A*  algorithm's  effectiveness  in enhancing  the  user  experience.  In  conclusion,  the  GIS-A*  algorithm  integration  proves  to  be  a valuable asset, optimizing the tourism industry in Tomohon within a concise framework.
Keyword: A* Algorithm, Geographic Information System, Tourism Industry

## PENDAHULUAN
Penelitian  ini  adalah  hasil  perpaduan  antara  pengetahuan  teoritis  yang  diperoleh selama  studi  akademis  dan  pengalaman  praktis  di  dunia  penelitian.  Dalam  proyek penelitian  yang  sedang  berlangsung,  fokus  penelitian  ini  adalah  pada  pengembangan Sistem  Informasi  Geografis  (GIS)  untuk  sektor  industri,  dengan  aplikasi  utama  yang ditujukan  untuk  Dinas  Pariwisata  Kota  Tomohon.  Pengakuan  akan  manfaat  signifikan yang dapat diberikan oleh teknologi GIS bagi industri pariwisata menjadi motivasi utama di balik proyek ini. Motivasi tersebut muncul dari pemahaman bahwa integrasi teknologi GIS  dapat  membuka  peluang  baru  dalam  mengelola  dan  mempromosikan  potensi pariwisata, khususnya dalam sektor industri seperti akomodasi dan restoran.
Perlunya  integrasi  data  geografis  untuk  meningkatkan  efisiensi  dan  efektivitas dalam pengelolaan informasi menjadi sorotan. Karya Nicholas Carr dan Vint Cerf dalam penelitian  mereka  menyoroti  bagaimana  teknologi  dapat  mengubah  cara  kita menyimpan  dan  mengakses  informasi.  Dengan  menerapkan  prinsip-prinsip  tersebut, proyek GIS yang dikembangkan bertujuan untuk menciptakan sistem arsip digital yang menggabungkan  teknologi  GIS  untuk  memajukan  sektor  industri  pariwisata  di  Kota Tomohon.
Tujuan  dari  penelitian  ini  adalah  untuk  menemukan  solusi  inovatif  dan  efisien dalam memenuhi kebutuhan pengelolaan data dan informasi pariwisata. Aplikasi GIS di sektor  industri  ini  diharapkan  dapat  memberikan  manfaat  yang  lebih  luas  dalam
pemetaan, perencanaan, dan pengembangan potensi di wilayah tersebut. Oleh karena itu,  penelitian  ini  diharapkan  dapat  menjadi  langkah  konkret  dalam  menerapkan pengetahuan  teoritis  ke  dalam  solusi  praktis  yang  dapat  memberikan  dampak  positif terhadap industri pariwisata di Kota Tomohon.
Penelitian  ini  juga  mencakup  pengembangan  Sistem  Informasi  Geografis  (GIS) dengan  menerapkan  algoritma  A*  dan  bantuan  Leaflet  untuk  melakukan  sistem pemetaan  lokasi  sektor  industri  pariwisata  Kota  Tomohon.  Algoritma  A*  merupakan salah satu algoritma pencarian jalur yang efisien, sering digunakan dalam sistem navigasi dan  perencanaan  rute.  Dengan  mengintegrasikan  algoritma  A*  ke  dalam  sistem  SIG, proyek  ini  bertujuan  untuk  memberikan  solusi  pintar  dalam  menentukan  rute  optimal bagi  wisatawan,  memaksimalkan  pengalaman  kunjungan,  dan  mengoptimalkan  waktu perjalanan.
Penerapan  algoritma  A*  dalam  GIS  memungkinkan  perhitungan  jalur  terpendek dan  tercepat  antara  lokasi-lokasi  wisata,  dengan  mempertimbangkan  faktor-faktor seperti jarak, waktu tempuh, dan preferensi pengguna. Penggunaan algoritma A* juga dapat  meningkatkan  efisiensi  perencanaan  perjalanan,  membantu  pengunjung  untuk menemukan rute yang paling efisien antara berbagai destinasi wisata di Kota Tomohon.
Harapannya, dengan menggabungkan teknologi GIS dan algoritma A*, proyek ini dapat memberikan solusi yang holistik dan inovatif dalam mendukung pengembangan sektor pariwisata di Kota Tomohon. Dengan mengoptimalkan perencanaan rute wisata, diharapkan  dapat  meningkatkan  daya  tarik  pariwisata  dan  memberikan  pengalaman berwisata yang lebih memuaskan bagi pengunjung.

## METODE PENELITIAN
Untuk memudahkan proses penelitian maka dibuatlah kerangka tahapan penelitian. Tahapan penelitian untuk pengembangan Sistem GIS dengan menggunakan algoritma A* melibatkan beberapa langkah. Berikut adalah tahapan yang diikuti:
Gambar 1. Kerangka Tahapan Penelitian
Pengumpulan Data
Tahap  pengumpulan  data  adalah  proses  mendapatkan  informasi  atau  fakta  yang relevan  dengan  suatu  topik  atau  masalah  yang  sedang  diteliti  atau  dijelaskan.  Ini merupakan langkah kunci dalam riset, penelitian, atau penyusunan laporan karena kualitas data  yang  dikumpulkan  akan  memengaruhi  validitas  dan  kehandalan  analisis  serta kesimpulan yang ditarik.
Pengumpulan  data  untuk  pembuatan  sistem  informasi  geografis  (GIS)  dinas pariwisata  kota  Tomohon  adalah  dengan  melakukan  observasi  dan  wawancara  pada petugas  dan  anggota  dinas  yang  ada,  Selain  itu,  saya  juga  meminta  data  yang  telah tersedia untuk memperoleh informasi yang komprehensif.

## Analisis/Studi Literature
Studi literatur adalah suatu langkah kritis dalam proses penelitian yang melibatkan penyelidikan dan analisis literatur, artikel, dan penelitian sebelumnya yang relevan dengan topik  yang  sedang  diteliti.  Dalam  studi  literatur,  peneliti  secara  kritis  menyelidiki  dan menganalisis  literatur,  artikel,  dan  penelitian  terdahulu  yang  relevan  dengan  topik penelitian.  Fokus  pada  landasan  teori,  penelitian  ini  mengeksplorasi  aspek-aspek  kunci dari Geographic Information System (GIS) dan Algoritma A*.
Sistem  Informasi  Geografis  (GIS)  adalah  sistem  yang  merangkum,  menyimpan, mengelola,  menganalisis,  dan  memvisualisasikan  data  berbasis  lokasi  atau  geografis (Longley et al., 2015). Dalam GIS, informasi tidak hanya dihubungkan dengan data spasial (seperti peta), tetapi juga dengan atribut-atribut non-spatial, memungkinkan pemahaman yang  lebih  baik  tentang  hubungan  spasial  dan  pola  di  dalam  data.  GIS  terdiri  dari beberapa  komponen,  seperti  Data  Geografis  yang  mencakup  peta  dan  citra  satelit,
Database  Geografis  sebagai  tempat  penyimpanan  data  geografis  bersama  dengan atribut-atribut  terkaitnya,  Analisis  Geografis  yang  merupakan  proses  menganalisis  data geografis, dan Visualisasi dan Presentasi menggunakan peta dan visualisasi grafis lainnya untuk menyajikan hasil analisis dengan cara yang mudah dipahami.
Algoritma  A*  (A-star)  adalah  algoritma  pencarian  jalur  yang  menjadi  kunci  dalam domain  kecerdasan  buatan  dan  pemrograman  permainan  untuk  menemukan  jalur terpendek  antara  dua  titik  pada  graf  atau  peta.  Dikembangkan  untuk  mengatasi keterbatasan beberapa algoritma  pencarian sebelumnya, A* memadukan prinsip-prinsip pencarian  terbaik  pertama  (best-first  search)  dan  pencarian  biaya  terkecil  (Dijkstra's algorithm)  dalam  sebuah  pendekatan  yang  inovatif  (Ida  Bagus  Gede  Wahyu  Antara Dalem, 2018).

## Pemodelan Data
1. Use Case Diagram
Dalam proses penelitian sistem GIS (Sistem Informasi Geografis), Use Case Diagram dapat  memberikan  gambaran  singkat  mengenai  interaksi  antara  aktor  (pengguna  atau sistem lain) dengan fungsionalitas utama sistem.

## Gambar 2. Use Case Diagram
2. Activity Diagram
Activity  diagram  adalah  diagram  yang  dapat  memodelkan  proses-proses  yang terjadi  pada  sebuah  sistem.  Pada  diagram  ini  akan  dijelaskan  interaksi  antara  Admin dengan System, dan Admin & User dengan System.
Gambar 3. Activity Diagram 1
Gambar 4. Activity Diagram 2
Untuk  melakukan  uji  coba  pada  Sistem  yang  diimplementasikan  maka ditentukananlah  proses  pengukuran,  pengujian,  dan  evaluasi  hasil  penelitian  dengan memfokuskan  pada  uji  coba  dan  evaluasi  kinerja  algoritma  A*  dalam  menentukan  jalur optimal. Penentuan jalur dilakukan melalui serangkaian langkah yang terstruktur, dimulai dari  menyisipkan  node  awal  ke  dalam  open  list,  menemukan  node  dengan  nilai  f(n) terendah,  hingga  menghentikan  perulangan  setelah  menemukan  jalur  menuju  node tujuan atau open list kosong.

## HASIL DAN PEMBAHASAN
Penentuan Jalur Optimal
Dalam  bagian  ini  akan  dijelaskan  bagaimana  tahap-tahap  dan  proses  yang dilakukan  oleh  algoritma  A*  dalam  menentukan  jalur  terbaik  untuk  mengantarkan seseorang  dari  satu  titik  ke  titik  lainnya.  Algoritma  A*  dapat  digambarkan  secara keseluruhan sebagai berikut:
• Sisipkan node awal ke dalam open list.
• Lakukan perulangan dengan langkah-langkah berikut:
• Temukan node (n) dengan nilai f(n) terendah dalam open list, dan tetapkan node ini sebagai current node.
• Hapus current node dari open list dan tambahkan ke dalam close list. Untuk setiap tetangga current node, lakukan langkah-langkah berikut:
1. Jika tidak dapat dilewati atau sudah terdaftar dalam close list, lewati langkah ini.
2. Jika belum terdaftar dalam open list, tambahkan node tetangga ke dalam open list
dengan current node sebagai parent, dan catat nilai f, g, dan h dari node ini.
3. Jika sudah terdaftar dalam open list, periksa apakah node tetangga memiliki nilai  g yang  lebih  baik  dengan  current  node  sebagai  parent.  Jika  ya,  ubah  parent  dari node ini di dalam open  list menjadi current node, dan perbarui nilai g dan f dari node ini.
Hentikan perulangan jika:
1. Node tujuan telah dimasukkan ke dalam open list, menunjukkan bahwa rute telah ditemukan.
2. Belum  menemukan  node  tujuan  sementara  open  list  kosong,  menandakan  tidak adanya rute yang memungkinkan.
Simpan  rute,  dan  secara  terbalik  urutkan  dari  node  tujuan  ke  node  awal  sambil menyimpan node ke dalam array.
Gambar 5. Titik Lokasi Puskesmas Pembantu dan Gardenia Country Inn
Pembuatan  graf  dalam  konteks  algoritma  A*  diperlukan  karena  algoritma  ini bekerja pada struktur data graf untuk mencari  jalur terpendek dalam ruang pencarian. Graf  digunakan  untuk  merepresentasikan  hubungan  antar  keadaan  atau  titik  dalam lingkungan  yang  dijelajahi.  Dengan  menggunakan  graf,  algoritma  dapat  secara  efisien mengeksplorasi  dan  menilai  jalur  yang  mungkin  dari  titik  awal  ke  tujuan, mempertimbangkan  bobot  tepi  dan  informasi  heuristik  pada  setiap  node.  Dengan demikian, pembuatan graf membantu A* dalam mengorganisir informasi dan memandu pencarian optimal menuju solusi.
Pembuatan  graf  dalam  konteks  algoritma  A*  diperlukan  karena  algoritma  ini
bekerja pada struktur data graf untuk mencari jalur terpendek dalam ruang pencarian. Graf  digunakan  untuk  merepresentasikan  hubungan  antar  keadaan  atau  titik  dalam lingkungan  yang  dijelajahi.  Dengan  menggunakan  graf,  algoritma  dapat  secara  efisien mengeksplorasi  dan  menilai  jalur  yang  mungkin  dari  titik  awal  ke  tujuan, mempertimbangkan  bobot  tepi  dan  informasi  heuristik  pada  setiap  node.  Dengan demikian, pembuatan graf membantu A* dalam mengorganisir informasi dan memandu pencarian optimal menuju solusi.

## Gambar 6. Contoh Graph
Pada  peta  matriks  di  bawah  terdapat  dua  parameter  berbeda,  yaitu,  warna  hijau melambangkan  Node  persimpangan  yang  dilalui,  warna  biru  merupakan  titik  awal (Puskesmas  Pembantu),  dan  titik  berwarna  kuning  merupakan  titik  tujuan  (Gardenia Country  Inn).  Hal  ini  menciptakan  representasi  visual  yang  jelas  dan  memudahkan pemahaman jalur yang ditempuh dari titik awal ke tujuan.
Gambar 7. Matriks
Node  start  dilambangkan  dengan  huruf  A  sementara  node  goals  dilambangkan
dengan huruf M, sedangkan huruf lainnya melambangkan nodes persimpangan. Berikut adalah koordinat yang didapat dari beberapa nodesnya.
Tabel 1. Koordinat Node Node Koordinat A (23, 3) B (20, 3) C (8, 7) D (5, 7) E (2, 7) F (2, 14) G (5, 14) H (8, 15) I (20, 14) J (14, 15) K (17, 21) L (2, 24) M (6, 25)
Setelah menetapkan koordinat titik, masing-masing node dicatat dengan jaraknya, yang kemudian digunakan untuk menemukan rute paling cepat, optimal, atau terbaik di antara  semua opsi  rute yang mungkin dilalui. Dalam proses ini, perhitungan dilakukan dengan mengintegrasikan fungsi heuristik pada setiap node. Jarak antar node terdapat pada tabel berikut.
Tabel 2. Jarak Antar Node Node Jarak A-B 21 Meter B-C 253 Meter C-D 56 Meter D-E 61 Meter E-F 80 Meter G-H 68 Meter B-I 138 Meter I-J 157 Meter
J-K 129 Meter K-M 226 Meter F-L 192 Meter L-M 70 Meter C-H 98 Meter D-G 92 Meter J-H 75 Meter F-G 64 Meter
Lalu pada tahap selanjutnya kita melakukan pemilihan rute yang cocok dan sesuai dengan path/nodenya.
Tabel 3. Pemilihan Path Rute Path 1 A-B-I-J-K-M 2 A-B-C-D-E-F-L-M 3 A-B-C-H-J-K-M 4 A-B-C-D-G-F-L-M 5 A-B-C-D-G-H-J-K-M 6 A-B-C-H-G-F-L-M
Langkah  selanjutnya  melibatkan  perhitungan  pada  fungsi  heuristik.  Dalam penelitian ini, fungsi heuristik yang digunakan adalah nilai Euclidean Distance. Penilaian heuristik  ini  dapat  menghasilkan  rute  pencarian  yang  lebih  baik  atau  mendekati  jarak sesungguhnya.  Setelah  nilai  heuristik  pada  setiap  rute  terbentuk,  langkah  berikutnya adalah  melakukan  perhitungan  menggunakan  rumus  algoritma  A*  untuk  menentukan rute terdekat atau teroptimal dari titik awal ke titik tujuan. Hasil perhitungan keseluruhan dari setiap node adalah sebagai berikut:
• Pada rute dengan node " A-B-I-J-K-M ", menghasilkan nilai total dari f(n) sebesar 671 m.
• Pada  rute  dengan  node  "  A-B-C-D-E-F-L-M  ",  menghasilkan  nilai  total  dari  f(n) sebesar 733 m.
• Pada  rute  dengan  node  "  A-B-C-H-J-K-M  ",  menghasilkan  nilai  total  dari  f(n) sebesar 808 m.
• Pada  rute  dengan  node  "  A-B-C-D-G-F-L-M  ",  menghasilkan  nilai  total  dari  f(n) sebesar 753 m.
• Pada rute dengan node " A-B-C-D-G-H-J-K-M ", menghasilkan nilai total dari f(n) sebesar 920 m.
• Pada  rute  dengan  node  "  A-B-C-H-G-F-L-M  ",  menghasilkan  nilai  total  dari  f(n) sebesar 766 m.
Setelah melakukan proses perhitungan menggunakan rumus algoritma A*, dengan variasi  notasi  rute,  dapat  disimpulkan  bahwa  hasil  perhitungan  menunjukkan  rute terdekat dari titik awal ke titik tujuan dengan nilai optimal pada rute bernotasi " A-B-I-J- K-M  "  dan  bobot  total  f(n)  sebesar  671  m.  Selanjutnya,  dilakukan  perbandingan kesesuaian antara pencarian rute terdekat secara manual dan menggunakan sistem atau aplikasi. Berikut merupakan tampilan hasil pemilihan rute yang dilakukan oleh sistem.

## Gambar 8. Hasil Pencarian Rute Pada Aplikasi
Pada  gambar  di  atas,  aplikasi  menentukan  jarak  yang  setara  dengan  hasil perhitungan jalur secara manual. Dalam percobaan perhitungan manual, diperoleh hasil sebesar 671 m, sementara pada percobaan menggunakan aplikasi, jarak yang dihasilkan adalah  652  m  dari  titik  awal  ke  titik  tujuan  dengan  rute  atau  node  yang  sama, mengakibatkan perbedaan jarak akurasi sekitar 19 meter.
Gambar 9. Implementasi Sistem Pada Halaman WebGIS

## SIMPULAN
Website GIS Sektor Industri Dinas Pariwisata Kota Tomohon sukses menyediakan informasi akurat dan mudah diakses  terkait sektor pariwisata. Fungsionalitasnya teruji, memberikan kontribusi positif dalam memudahkan akses informasi. Integrasi algoritma A*  pada  website  membantu  menentukan  rute  terdekat  dari  titik  awal  ke  titik  tujuan, meningkatkan  efisiensi  pencarian  sarana  akomodasi  dan  restoran.  Dengan  demikian, integrasi  website  GIS  dan  algoritma  A*  menciptakan  solusi  efektif,  menyediakan informasi akurat, dan mempermudah pencarian bagi pengguna

## DAFTAR PUSTAKA
Cao,  Changyong,  and  Nina  Siu-Ngan  Lam.  "Understanding  the  scale  and  resolution effects in remote sensing and GIS." Scale  in  remote sensing  and GIS. Routledge, 2023. 57-72.
Dalem, I.  B. G. W. A. (2018). Penerapan algoritma A*(Star) menggunakan graph untuk menghitung  jarak  terpendek.  Jurnal  RESISTOR  (Rekayasa  Sistem  Komputer),  1(1), 41-47.
Longley,  P.  A.,  Goodchild,  M.  F.,  Maguire,  D.  J.,  &  Rhind,  D.  W.  (2015).  Geographic information science and systems. John Wiley & Sons.
Luthfita, Dinda, and Soeb Aripin. "Implementasi Algoritma A* Dalam Menentukan Tarif Minimum  Berdasarkan  Jarak  Terpendek  Rute  Armada  Taksi  Bandara."  Journal  of Informatics Management and Information Technology 2.1 (2022): 43-47.
Mustaqov,  Muhammad  Ativ,  and  Dyah  Ayu  Megawaty.  "Penerapan  Algoritma  A-Star Pada  Aplikasi  Pencarian  Lokasi  Fotografi  Di  Bandar  Lampung  berbasis  Android." Jurnal Teknoinfo 14.1 (2020): 27-34.
Mustaqov,  Muhammad  Ativ,  and  Dyah  Ayu  Megawaty.  "Penerapan  Algoritma  A-Star Pada  Aplikasi  Pencarian  Lokasi  Fotografi  Di  Bandar  Lampung  berbasis  Android." Jurnal Teknoinfo 14.1 (2020): 27-34.
Nur,  Askar,  and  Fakhira  Yaumil  Utami.  "Proses  dan  Langkah  Penelitian  Antropologi: Sebuah  Literature  Review."  Ad-Dariyah:  Jurnal  Dialektika,  Sosial  dan  Budaya  3.1 (2022): 44-68.
Prasetyo,  B.,  et  al.  (2020).  "Pengaruh  Kualitas  Website  terhadap  Keputusan  Pembelian Online." Jurnal Manajemen Pemasaran, 15(1), 78-89.
Sabilla,  A.  D.,  &  Taufiq,  A.  (2022).  PENERAPAN  ALGORITMA  A*  PADA  WEBGIS PENCARIAN RUTE TERPENDEK. Journal of Information System and Computer, 2(2), 32-35.
Sari,  R.,  et  al.  (2019).  "Pemanfaatan  Pustaka  Leaflet  dalam  Pengembangan  Aplikasi Pemetaan Interaktif." Jurnal Teknik Informatika dan Sistem Informasi, 5(2), 89-98.
Susanto, A., et al. (2018). "Analisis Desain  dan Fungsi Website  Perguruan Tinggi XYZ."
Jurnal Desain Komunikasi Visual, 10(2), 45-56.