## Aplikasi Pencarian Rute Terpendek Lokasi Kuliner Khas Palembang Menggunakan Algoritma Euclidean Distance
dan A*(Star)
Dona Marcelina [1]* , Evi Yulianti [2]
Program Studi Manajemen Informatika [1] , Program Studi Sistem Informasi [2]
Universitas Indo Global Mandiri Palembang, Indonesia donamarcelina@uigm.ac.id [1] , eviyulianti@uigm.ac.id [2]
Abstract — Palembang is one of the regions in Indonesia which is known for having culinary which has a distinctive and  delicious  taste.  Besides  having  a  distinctive  taste, Palembang  cuisine  also  has  its  own  story  related  to  the history of Palembang City and the development of people's lives there. The many types of culinary and culinary tourist attractions  in  the  city  of  Palembang  provide  its  own obstacles  for  tourists  and  local  residents  in  choosing  a culinary  meal  and  the  route  to  the  culinary  location.  The solution to the problem proposed is to make the application for the shortest  route search for culinary locations typical of  Palembang  using  the  Euclidean  Distance  and  A  * algorithm.  Euclidean  Distance  algorithm  which  is  a calculation  of  the  distance  from  two  points  as  a  basis  in finding  the  shortest  route  and  gives  the  user  information about the location that is around the user by comparing the distances  and  applying  the  A  *  algorithm  as  a  basis  in finding the shortest route using the smallest estimated cost to achieve the goals to be achieved, and has a heuristic value that is used as a basis for consideration. The final results of the study showed that the algorithm performed had a high degree  of  accuracy  in  determining  the  shortest  culinary route  location  in  Palembang,  namely  the  Mean  Mean percentage error (MAPE) of 4.4%.
Keywords:  Shortest  Route,  Culinary,  Android,  Euclidean Distance, A * (Star )
Abstrak — Palembang  merupakan  salah  satu  daerah  di Indonesia yang dikenal memiliki kuliner yang bercita rasa khas dan enak.  Selain memiliki cita rasa yang khas, kuliner Palembang  juga  memiliki  cerita  tersendiri  berkaitan dengan  sejarah  Kota  Palembang  dan  perkembangan kehidupan  masyarakat  disana.    Banyaknya  jenis  kuliner dan tempat wisata kuliner dikota Palembang memberikan kendala tersendiri bagi para wisatawan pendatang maupun penduduk lokal dalam memilih suatu santapan kuliner dan rute  menuju  lokasi  kuliner  tersebut.  Solusi  permasalahan yang  diusulkan  adalah  membuat  aplikasi  pencarian  rute terpendek  lokasi  kuliner  khas  palembang  menngunakan
algoritma Euclidean Distance dan A*. Algoritma Euclidean Distance yang  merupakan  perhitungan  jarak  dari  2  buah titik sebagai landasan dalam pencarian rute terpendek dan memberikan user informasi lokasi mana yang ada disekitar user dengan  membandingkan  jarak-jarak  lokasi  serta menerapkan  algoritma  A*  sebagai  landasan  dalam . pencarian  rute  terpendek  dengan  menggunakan  estimasi nilai cost terkecil  untuk  mencapai  tujuan  yang  ingin dicapai,  dan  memiliki  nilai  heuristik  yang  digunakan sebagai  dasar  pertimbangan.  Hasil  akhir  penelitian menunjukkan  bahwa  algoritma  yang  dilakukan  memiliki tingkat  akurasi  tinggi  dalam  menentukan  rute  terpendek lokasi  kuliner  palembang  yaitu  Nilai Mean  absolute percentage error (MAPE) sebesar 4,4% .
Kata  Kunci  :  Rute  Terpendek,  Kuliner,  Android,  Euclidean Distance,  A*(Star )

## I. PENDAHULUAN
Wisata kuliner merupakan kegiatan makan dan minum yang unik  dilakukan  oleh  setiap  pelancong  yang  berwisata  [1]. Wisata  kuliner  saat  ini  menjadi  sebuah  wisata  yang  banyak dampaknya  bagi  perkembangan  suatu  daerah.  Salah  satu pentingya  adalah  mengembangkan  potensi  makanan  daerah yang sepertinya sudah mulai tergeser oleh produk-produk asing maupun  makanan  asing.  Untuk  itu  perlu  dibuat  usaha  untuk meningkatkan  potensi  ekonomis  ini  dengan  memberikan sentuhan atau dukungan untuk dapat menarik wisatawan lokal maupun  asing  dalam  menikmati  kuliner  asli  daerah  [2]. Makanan  tradisional  atau  kuliner  lokal  adalah  jenis  makanan yang  berkaitan  erat  dengan  suatu  daerah  dan  diwariskan  dari generasi ke generasi sebagai bagian dari tradisi. Makanan lokal khas  daerah-daerah  di  Indonesia  sudah  ada  sejak  lama  dan masih bertahan hingga saat ini sehingga sangat dihargai sebagai warisan budaya [3].
Kota Palembang adalah ibu kota Provinsi Sumatera Selatan. Palembang  merupakan kota terbesar kedua  di pulau Sumatera setelah Medan [4]. Kota Palembang sebagai salah satu destinasi pariwisata  Indonesia  yang  terkenal  dengan  jembatan  Ampera
juga memiliki potensi wisata kuliner [5]. Ibu kota dari Sumatera Selatan ini dikenal memiliki kuliner yang bercita rasa khas dan enak  yang  sangat  sayang  untuk  dilewatkan.  Anda  bisa menemukan sensasi rasa yang gurih, pedas, segar sampai manis dari jajaran kuliner khas Palembang. Selain memiliki cita rasa yang  khas,  kuliner  Palembang  juga  memiliki  cerita  tersendiri berkaitan  dengan  sejarah  kota  Palembang  dan  perkembangan kehidupan  masyarakat  disana.  Banyaknya  jenis  kuliner  dan tempat  wisata  kuliner  dikota  Palembang  memberikan  kendala tersendiri  bagi  para  wisatawan  pendatang  maupun  penduduk lokal  dalam  memilih  suatu  santapan  kuliner  dan  rute  menuju lokasi kuliner tersebut.
Di  era  teknologi  dan  informasi  seperti  sekarang  ini banyak cara yang dapat dilakukan untuk mengakses informasi baik  itu  informasi  objek  wisata  maupun  informasi  geografis menggunakan  perangkat  teknologi.  Salah  satu  perangkat teknologi yang dapat digunakan adalah perangkat ponsel cerdas [6].  Dengan  Memanfaatkan  sistem  operasi  pada smartphone yaitu Android yang merupakan hasil karya Google yang sudah terintregasi  dengan Google  Maps . Google  Maps merupakan sebuah  jasa  peta  globe virtual dan online . Menawarkan  peta yang dapat diseret yang diambil dari satelit. Dengan teknologi LBS yang dimiliki android pencarian informasi geografis suatu wisata  kuliner  dan  rute  terpendek  dapat  dilakukan  kapanpun dan dimanapun. Pencarian rute terpendek tentunya membutuhkan  suatu  algoritma  sehingga  didapat  rute  paling efisien menuju lokasi wisata kuliner tersebut. Terdapat banyak algoritma dalam penyelesaian masalah pencarian rute terpendek seperti algoritma euclidean distance dan algoritma A* (Star) Algoritma  euclidean  distance merupakan  perhitungan jarak dari 2 (dua) buah titik dalam euclidean space . Algoritma ini dapat digunakan untuk menghitung jarak antara lokasi awal dan lokasi tujuan serta membandingkan hasil dari perhitungan dari  beberapa  lokasi,  sehingga  dapat  memberikan  informasi tentang lokasi apa saja yang berada disekitarnya [7]. Sedangan Algoritma  A*( Star) merupakan  suatu  algoritma  yang  dapat memecahkan  masalah  pencarian  jalur  atau  rute  terpendek. Algoritma  A*( Star) ini  menggunakan  estimasi  jarak  terdekat untuk mencapai tujuan  yang  ingin dicapai, dan  memiliki  nilai heuristik  yang  digunakan  sebagai  dasar  pertimbangan. Heuristik  merupakan  kriteria,  metode,  atau  prinsip-prinsip untuk menentukan pilihan sejumlah alternatif untuk  mencapai sasaran  dengan  efektif  [8].  Penelitian  ini  diharapkan  bisa memberikan  informasi  rute  terpendek  lokasi  wisata  kuliner dikota palembang

## II. METODOLOGI PENELITIAN
Metode  yang  digunakan  dalam  penelitian  ini  adalah metode penelitian deskriptif, yaitu suatu metode dalam meneliti status  sekelompok  manusia,  suatu  obyek,  suatu  set  kondisi, suatu  sistem  pemikiran,  ataupun  suatu  kelas  peristiwa  pada masa  sekarang.  Tujuan  dari  penelitian  deskriptif  ini  adalah untuk  membua  tdeskripsi,  gambaran  atau  lukisan  secara sistematis,  factual  dan  akurat  mengenai  fakta-fakta,  sifat-sifat hubungan antar fenomena yang diselidik [9].

## A. Tahapan Pencarian Rute Terpendek
Adapun  tahapan  pencarian  rute  terpendek  menggunakan Algoritma Euclidean Distance dan Algoritma A*(Star) yaitu: 1. Menghitung  jarak  dua  titik  dengan  Rumus Euclidean Distance Caranya  adalah  kurangkan  setiap  kordinat  titik kedua dengan titik  yang pertama. Kemudian pangkatkan hasil nilai masing-masing,  Kemudian  tambahkan semuanya sehingga memperoleh hasil. Hasil ini kemudian di akar kan.Hasil perhitungan masih dalam satuan decimal degree (sesuai  dengan  format  lat-long  yang  dipakai) sehingga untuk menyesuaikannya perlu dikalikan dengan 111.319 km. (1 derajat bumi = 111.319 km)
2. Menghitung  rute  terpendek  menggunakan  algoritma  A* setelah  nilai  heuristic  dari  masing-masing  titik  didapat maka kita akan mencari 𝑓 ( 𝑛 ).
Berikut  adalah flowchart dari  Algoritma Euclidean Distance dan Algoritma A*(Star):
Gambar 1. flowchart dari Algoritma Euclidean Distance dan Algoritma A*(Star)

## B. Algoritma Euclidean Distance
Euclidean distance adalah perhitungan  jarak dari  2 buah titik  dalam Euclidean  space.  Euclidean  space diperkenalkan oleh  seorang  matematikawan dari  Yunani  sekitar  tahun  300. untuk mempelajari hubungan antara sudut dan jarak. Euclidean ini  biasanya  diterapkan  pada  2  dimensi.  kemudian  juga  bisa sederhana  jika diterapkan pada dimensi  lain  yang  lebih tinggi [7].
C. Perhitungan Algoritma Euclidean Distance Euclidean ini berkaitan dengan Teorema Phytagoras dan biasanya diterapkan pada 1, 2 dan 3 dimensi.

## 1) Penerapan 1 dimensi
Semisal  ingin  menghitung  jarak  Euclidean  1  dimensi. Titip  pertama  adalah  4,  titik  kedua  adalah  -10.  Caranya adalah kurankan -10 dengan 4. sehingga menghasilkan -14. Cari nilai absolut dari nilai -14 dengan cara mempangkatkannya sehingga mendapat nilai 196. Kemudian  diakarkan  sehingga  mendapatkan  nilai  14. Sehingga  jarak  euclidean  dari  2  titik  tersebut  adalah  14. Euclidean Distance didefinisikan dalam 1 dimensi [7]
Ed = √ (Y – X)2 (2.1) …………………………(1) Dimana :
X = Jarak titik pertama
Y = Jarak titik kedua
2) Penerapan 2 dimensi
Berbeda  dengan  penerapan euclidean  distance 1 dimensi,  2  dimensi  sesuai  dengan  bentuk  pencarian menggunakan  2  titik  koordinat  pada  wilayah  permukaan bumi,  yang  membandingkan  antara  titik  koordinat Euclidean Distance didefinisikan dalam 2 dimensi [7]
Ed = √ (X2 – X1)2+ (Y2 – Y1)2 .............................. (2 )
Pada  rumus  tersebut  dapat  kita  dapat  implementasi kedalam bentuk koordinat menjadi
Ed  =  √  ((Latitude  2  –  Latitude  1)2+  (Longitude  2  – Longitude 1)2 ......................................................... (3)
Dimana :
Latitude = garis  lintang  mengarah dari khatulistiwa (0) ke  kutub  selatan,  atau  khatulistiwa  ke  kutub utara (sudut 0-90 dan 0 -90).
Longitude   = garis bujur adalah garis horizontal seperti dari khatulistiwa.  Sudut  0  (Greenwich)  ke  arah Hawai adalah 0-180, sedangkan kebalikannya dari 0 ke -180.

## D. Algoritma A* (A-Star )
Algoritma ini pertama kali diperkenalkan pada 1968 oleh Peter  Hart,  Nils  Nilsson,dan  Bertram  Raphael.  Algoritma  A* merupakan  salah  satu  dari heuristic  search, adalah  algoritma untuk mencari estimasi jalur dengan cost terkecil dari node awal ke  node  berikutnya  sampai  mencapai  node  tujuan  [4].    A* memiliki  suatu  fungsi  yang  di  notasikan  dengan f(x) untuk menetapkan estimasi cost yang terkecil dari  jalur yang dilalui node x dengan rumus
f(x) = h(x) + g(x) ........................................................... (4)
Fungsi h(x) adalah hyphotesis cost atau heuristic cost atau estimasi cost terkecil dari node x ke tujuan, yang disebut juga sebagai future path cost. Fungsi g(x) adalah geographical cost atau cost sebenarnya dari node x ke node tujuan, yang disebut juga sebagai past path-cost.
Dengan  metode atau algoritma  A*, cost  untuk mencapai node  berikutnya  didapat  dari  fungsi  f(x),  sehingga  pada pemilihan  jalur  terpendek  dapat  langsung  diketahui  node berikutnya dengan cost terkecil sampai  mencapai  node tujuan tanpa kembali ke node yang sudah dikunjungi[8]. .
E. Menghitung Fungsi Heuristik
Fungsi Heuristik yang  digunakan  adalah  “ Euclidean Distance ”  alasan  penulis  menggunakan  fungsi heuristik ini karena fungsi ini memberikan hasil yang lebih baik (mendekati jarak  sebenarnya)  dibandingkan  dengan  fungsi  heuristik  yang lain[8]
Setelah  nilai  heuristik  dari  masing-masing  node  didapat maka  kita  akan  mencari f(n) menggunakan  algoritma  A* dengan rumus
f(n) = g(n) + h(n).......................................... (5)
dimana, g(n) = Jarak real dari titik awal ke titik sekarang h(n ) = Jarak perkiraan dari titik sekarang ke tujuan.

## F.     Pengukuran Hasil Prediksi
Pada  kenyataannya  tidak  ada  prediksi  yang  memiliki tingkat akurasi 100%, karena setiap prediksi pasti mengandung kesalahan. Oleh karena itu, untuk  mengetahui metode prediksi dengan  tingkat  akurasi  yang  tinggi,  maka  dibutuhkan menghitung  tingkat  kesalahan  dalam  suatu  prediksi.  Semakin kecil  tingkat  kesalahan  yang  dihasilkan,  maka  semakin  baik prediksi  tersebut.    Menghitung  kesalahan  prediksi  disebut sebagai  menghitung  akurasi  pengukuran.  Standar  umum pengukuran  kesalahan  prediksi  yang  digunakan  adalah mean absolute  percentage  error (MAPE)  untuk  persentase akurasi[8]. ditunjukkan oleh persamaan
𝑀𝐴 P𝐸 = 1 𝑛 ∑ |𝐴𝑡−𝐹𝑡| 𝐴𝑡 𝑛 𝑖=1
...................... (6) dimana:
At = nilai aktual pada waktu ke t Ft = nilai prediksi pada waktu ke t n = banyak data
Nilai  MAPE  digunakan  untuk  menganalisis  kinerja  proses prediksi seperti yang tertera pada Tabel 1
Tabel 1. Nilai MAPE untuk Evaluasi Prediksi Nilai MAPE Akurasi Prediksi MAPE ≤ 10% Tinggi 10% < MAPE ≤ 20% Baik 20% < MAPE ≤ 50% Reasonable MAPE > 50% Rendah

## G. P ENELITIAN T ERDAHULU
Penelitian yang berkaitan dengan pencarian rute terdekat sudah  banyak  dilakukan  oleh  peneliti  sebelumnya.  Berbagai metode yang diterapkan dalam membangun aplikasi pencarian
rute  terpendek    yang  bertujuan  untuk  memudahan  dalam pencarian lokasi berdasarkan rute terdekatnya.
Penelitian  yang dilakukan oleh Fernando, Mutsaqov dan Megawaty,  “  Penerapan  Algoritma A*(Star) Pada  Aplikasi Pencarian  Lokasi  Fotografi  di  Bandar  Lampung  Berbasis Android”[10] Pencarian   rute lokasi   atau   spot   foto   di   Kota Bandar    Lampung    menggunakan    metode  A-Star  berhasil dilakukan.      Hasil    yang    didapatkan    adalah  menunjukkan bahwa  fungsi-fungsi    pada    aplikasi    pencarian    spot    foto berbasis  android    dapat    berjalan    dengan    baik    dengan persentase perhitungan  sebesar  97,36%, Proses     pencarian rute dilakukan   dengan   menentukan   terlebih   dahulu node- node dan   memberikan graph pada   node, setelah  dilakukan perhitungan    Algoritma  A-Star  dapat    dihitung    dengan menggunakan  data graph yang   membawa   nilai Latitude dan Longitude.
Menurut  penelitian  yang  dilakukan  oleh  Pugas, “Pencarian Rute Terpendek Menggunakan Algoritma Dijkstra dan  A  star  (A*)  pada  SIG  Berbasis  Web  untuk  Pemetaan Pariwisata Kota  Sawahlunto”[11]  membahas  tentang menggunakan  algoritma  Dijkstra  dan  A  star  untuk  pencarian rute tependek  Pariwisata  Kota  Sawahlunto.  Kedua    algoritma tersebut   menghasilkan rute  yang  sama pada  5  kali  sample pengujian.    Namun    terdapat    perbedaan  waktu      proses pencarian   rute   terpendek   antara   algoritma Dijkstra  dan   A star.   Algoritma   A  star   memperoleh  rute terpendek  dengan waktu  pencarian  yang  relatif  lebih  cepat daripada algoritma Dijkstra.
Penelitian  yang dilakukan oleh Purnama, Megawaty dan Fernando,  “ Penerapan  Algoritma A*(Star) Untuk Penentuan Jarak  Terdekat  Wisata  Kuliner  Di  Kota  Bandarlampung”[12] membahas  tentang  menggunakan  algoritma  A*star  untuk pencarian  rute  tependek  menuju  lokasi  kuliner.    Berdasarkan hasil  pengujian    black    box  menghasilkan  kriteria        baik dengan        persentase  sebesar    100  %,  sedangkan    untuk pengujian  black  box  berdasarkan  hasil yang  didapat,  dapat disimpulkan  dari  pengujian  yang dilakukan  pada  algoritma secara    manual  dan  aplikasi  mendapatkan    hasil    yang  valid dengan  jarak  yg  sama yaitu dengan jarak 1.5KM
Penelitian  yang  dilakukan  oleh  Syukriah,  Falahah  and Solihin, “ Penerapan Algoritma A*(Star) Untuk Mencari Rute Tercepat  Dengan  Hambatan”[8]  Berdasarkan  hasil  pengujian metode A* dapat menentukan rute (jalur) terbaik dari titik awal (start)  menuju  titik  akhir  (finish)  dengan  hambatan-hambatan yang  diberikan  disetiap  rute,  rute  yang  ditemukan  merupakan rute  yang  terbaik  dengan  nilai  f(n)  terkecil  dibandingkan dengan rute-rute (jalur-jalur) lainnya
Penelitian yang dilakukan “Perancangan Aplikasi   Wisata Kabupaten Lebak Menggunakan  Algoritma  A*(Star)  Berbasis Android”[13]  membahas  tentang  penggunaan  algoritma A*(Star) untuk mengetahui rute terpendek menuju lokasi wisata kabupaten  lebak.  Fitur  yang  dimiliki  oleh  aplikasi  adalah penentuan posisi user dalam memilih tujuan objek wisata untuk mendapatkan rute terdekat yang ditampilkan pada peta  secara online.  Algoritma A* bisa memanfaatkan library Google Maps yang menyimpan simpul simpul berupa rute jalan

## III. HASIL DAN PEMBAHASAN

## A. Penerapan metode Euclidean Distance dan A*(Star)
Pada  penelitian  ini  peneliti  menerapkan  algoritma Euclidean Distance yang  merupakan perhitungan  jarak dari 2 buah titik sebagai landasan dalam pencarian rute terpendek dan memberikan user informasi lokasi mana yang ada disekitar user dengan  membandingkan  jarak-jarak  lokasi  serta  menerapkan algoritma  A* (Star) sebagai  landasan  dalam  pencarian  rute terpendek  lokasi  kuliner  dengan  menggunakan  estimasi  nilai cost  terkecil  untuk  mencapai  tujuan  yang  ingin  dicapai,  dan memiliki nilai heuristik yang digunakan sebagai dasar.
Contoh  :  Menghitung  Rute  Terpendek  dari  UIGM– Pempek  Talang  Ratu Menggunakan  Algoritma Euclidean Distance dan algoritma A* (Star) . Agar didapat hasil pengukuran yang lebih akurat, digunakan software pendukung Google  Earth untuk  mengetahui  jalur-jalur  yang  akan  dilalui. Tujuh  node  dihasilkan  dari  proyeksi Google  Earth, dimana pengambilan node nya berdasarkan persimpangan jalan dan dua kemungkinan rute yang akan di lalui (Gambar 2).
Gambar 2. Peta Uigm-Pempek Talang Ratu
• A (0,0) = UIGM
• B(−2,957860,  104,736390)  =  Jl.Jendral  Sudirman  – Jl.Lintas Sumatera
• C  (−2,953474,  104,734656)=  Jl.Lintas  Sumatera  – Jl.Lintas Sumatera
• D (−2,957037, 104,730991) = Jl. Letnan Kasnariansyah
• E (−2,954662, 104,731241) = Lrg.Asmi
• F (−2,954392, 104,732300) = Jl.Garuda Putra 1
• G  (−2,954016,  104,732146)  =  Pempek  Talang  Ratu  – Jl.Letnan Murod
1) Tahap 1
Menghitung  jarak  dua  titik  dengan  Rumus Euclidean Distance. Caranya  adalah  kurangkan  setiap  kordinat  titik kedua dengan titik yang pertama. Kemudian pangkatkan hasil nilai  masing-masing  ,Kemudian  tambahkan  semuanya sehingga  memperoleh  hasil.  Hasil  ini  kemudian  di  akar  kan. Hasil perhitungan masih dalam satuan decimal degree (sesuai dengan  format  lat-long  yang  dipakai)  sehingga  untuk menyesuaikannya  perlu  dikalikan  dengan  111.319  km  (1 derajat bumi = 111.319 km).
Tabel 2. Hasil Perhitungan rute terpendek menggunakan algoritma Euclidean Distance
No Node Koordinat Node (1) (x,y) Koordinat Node (2) (x,y) 𝐸𝑑= (√(𝑥 2 − 𝑥 1 ) 2 +   (𝑦 2 − 𝑦 1 ) 2 )
∗  111.319 (1 derajat bumi) 1 A - B 0,0 −2,957860, 104,736390 116,631 km 2 B - C −2,957860, 104,736390 −2,953474, 104,734656
0,522086 𝑘𝑚
3 C - G −2,953474,
104,734656 −2,954016, 104,732146
0,285755 𝑘𝑚
4 B - D
−2,957860,
104,736390 −2,957037, 104,730991 0,606354 𝑘𝑚
5 D _ E −2,957037, 104,730991 −2,954662, 104,731241 0,278074 𝑘𝑚
6 E - F −2,954662, 104,731241 −2,954392, 104,732300
0,121337 𝑘𝑚
7 F - G −2,954392,
104,732300 −2,954016, 104,732146 6,674932 𝑘𝑚
Berikut diperoleh nilai heuristic h( 𝑛 ) dari masing-masing titik(116,6371 𝑘𝑚 , 0,522086 𝑘𝑚 , 0,285755 𝑘𝑚 , 0,606354 𝑘𝑚 , 0,278074 𝑘𝑚 ,  0,121337 𝑘𝑚 ,  6,674932 𝑘𝑚 )  yang  akan digunakan  untuk  menghitung  rute  terpendek  menggunakan algoritma A*

## 2) Tahap II
Menghitung  rute  terpendek  menggunakan  algoritma  A*. Setelah  nilai  heuristic  dari  masing-masing  titik  didapat  maka kita  akan  mencari 𝑓 ( 𝑛 ).  Dari  hasil  perhitungan  menggunakan algoritma A*(Star), Titik B memiliki 2 cabangan yaitu titik C dan  titik  D,  maka f(n) yang  harus  dipilih  adalah f(n) yang menghasilkan biaya paling  kecil, yaitu titik C. Titik C memiliki 1 cabang  menuju titik G  maka titik C  memilih  cost pada titik G,sehingga titik G sebagai titik terakhir. Maka 𝑓 ( 𝑛 ) total yang
di  dapat  adalah  13,349231 𝑘𝑚 ,  rute  terpendek  adalah 𝐴 − 𝐵 − 𝐶 − 𝐺 yaitu  UIGM,  Jl.Jendral  Sudirman-  Jl.Lintas Sumatera , Jl.Lintas Sumatera – Jl.Kolonel H.Barlian, Pempek Talang Ratu (Jl.Letnan Murod).
Tabel 3. Hasil Perhitungan rute terpendek menggunakan algoritma A*
Rute Node �(�) = ℎ(𝑛) +  𝑔(𝑛) 1 A -  B 11,7377 𝑘𝑚 2 B – C 1,047726 𝑘𝑚 B - D 1,210705 𝑘𝑚 3 C - G 0,563805 𝑘𝑚
Selanjutnya penulis   membandingkan   kesesuaian   antara pencarian      rute      terdekat      secara      manual      dan      dengan menggunakan   sistem   atau   aplikasi. Berikut   adalah tampilan hasil  pemilihan  rute  yang  dilakukan  oleh  sistem  yang  dapat dilihat pada gambar 3
Gambar 3. Hasil Pencarian Rute Pada Aplikasi

## B. Pengujian Tingkat Akurasi
Pengujian  akurasi  rute  terpendek  dari  pengguna  menuju tempat lokasi yang ditujuh dengan pengukuran Google Earth, menggunakan  10  tempat  lokasi  kuliner  di  kota  palembang menggunakan algoritma euclidean distance dan A*(star). Tabel hasil pengujian tingkat akurasi MAPE dapat dilihat pada tabel 4.
Tabel 4. Hasil Pengujian MAPE(Lokasi Awal UIGM)
No  Lokasi Tujuan
Jarak Pengukuran (Km)
| 𝐴 − 𝑋1 𝐴 | Via Google Earth A Via Aplikasi X I 1 Pondok  Kelapa Restoran 0.55 0.58 0.05 2 Pindang  Prabu Indah Restoran 1.80 1.78 0.011
No  Lokasi Tujuan Jarak Pengukuran (Km)
| 𝐴 − 𝑋1
𝐴 | Via Google Earth A Via Aplikasi X I 3 Sri Melayu Restoran 1.68 1.65 0.017 4 Pempek Pak Raden 0.34 0.28 0.17 5 Pempek Candy 0.53 0.55 0.014 6 Pempek Beringin 0.71 0.7 0.06 7 Pempek  Nony 168 0.28 0.3 0.07 8 Brasserie Restoran 1.65 1.67 0.012 9 Dunkin Donuts 1.86 1.90 0.021 10 Pempek Saga 3.80 3.77 0.007 ∑ 13.2 13.18 0.437 MAPE 1.32 1.38 0.0437 MAPE 0.0437 * 100 = 4.4 %
Berdasarkan  hasil  akurasi  yang  dicapai  pada  pengujian menunjukkan bahwa dilihat dari Tabel 2.1 Nilai MAPE untuk Evaluasi  Prediksi  akurasinya  yaitu  4,4%  .  Pengujian  yang dilakukan  menghasilkan  kesimpulan  bahwa  algoritma  yang dilakukan  memiliki tingkat akurasi tinggi pada pencarian rute terpendek lokasi kuliner di kota palembang.

## C. Implementasi Antarmuka Aplikasi
1) Halaman Akses Splash Screen
Halaman Splash Screen merupakan  halaman  yang akan tampil  pertama  kali  sebagai  tanda  pengenal  Aplikasi  Lokasi Kuliner  Khas  Palembang  telah  dieksekusi.  Tampilan  hasil eksekusi  pada  halaman Splash  Screen dapat  dilihat  pada Gambar 4,
Gambar  4. Tampilan Halaman Akses Splash Screen

## 2) Halaman Menu Utama
Pada menu ini, user dan admin dapat memilih menu yang akan di tampilkan. Terdapat 3 menu pilihan, diantaranya adalah menu  Daftar  Kuliner,  menu  Informasi  Kuliner,  dan  menu Bantuan. Dapat dilihat pada gambar 5 berikut:

## Gambar 5. Tampilan Halaman Utama

## 3) Halaman Daftar Kuliner
Pada  halaman  menu  Daftar  kuliner,  pengguna  akan langsung  melihat  pilihan  dari  daftar  yang  terdiri  dari  alamat kuliner  dan  jarak  yang  ditempuh.  Daftar  kuliner  ditampilakn secara  terurut  berdasarkan  lokasi  terdekat.  Untuk  halaman menu lokasi kuliner bisa dilihat pada Gambar 6.
Gambar 6. Daftar Lokasi Kuliner
Selanjutnya jika diklik pada salah satu lokasi kuliner  akan tampil halaman peta dan rute, pengguna akan melihat peta dan rute lokasi kuliner  yang di pilih. Untuk halaman peta dan rute terpendek  di  titik  awal  uigm  ke  lokasi  kuliner  Pempek  Pak Raden Palembang bisa dilihat pada Gambar 7 dibawah ini :

## Gambar 7. Rute Lokasi Kuliner Terpendek

## 4) Halaman Infomasi Kuliner
Menu  ini  terdiri  dari  detail  informasi  dari  kuliner  yang dipilih  oleh  pengguna.  Sehingga  pengguna  dapat  mengetahui informasi  lengkap  dari  kuliner  khas  palembang  yang  akan dituju  dari  bahan  kuliner,  resep  cara  memasak  serta  sejarah kuliner  yang  dituju  tersebut.  Dihalaman  informasi  kuliner  ini juga  pengguna  sekaligus  bisa  melihat  lokasi  kuliner  terebut. Berikut adalah antarmuka menu informasi kuliner pada gambar 8.

## 5) Halaman Menu Login Admin
Pada  menu ini  admin  dapat  melakukan  login menggunakan  username  dan  password  yang  telah  terdaftar. Admin yang telah melakukan login akan diarahkan pada menu panel admin. Dapat dilihat pada gambar 8 berikut:
Gambar 9. Tampilan Halaman Login Admin

## 6) Halaman Menu Panel Admin
Admin  dapat  melakukan  penambahan  data  baru  dengan memilih  button  tambah  daftar  kuliner  baru  maka  admin  akan diarahkan pada menu tambah data baru. Jika admin ingin keluar admin dapat menekan tombol logout. Untuk mengedit data dan menghapus  data  dapat  menekan  tombol  lihat  daftar  kuliner. Dapat dilihat pada gambar 10 berikut:
Gambar 10. Tampilan Halaman Utama Admin

## IV.      PENUTUP
Berdasarkan hasil yang didapat dalam penelitian ini maka disimpulkan  bahwa  Algoritma Euclidean  Distance dan  A* (Star)  dapat  digunakan  untuk  melakukan  pencarian  rute terpendek  lokasi  kuliner  yang  ada  di  kota  palembang. Berdasarkan  hasil  akurasi  yang  dicapai  pada  pengujian
menunjukkan  bahwa Nilai MAPE  ( mean absolute percentage error) untuk evaluasi prediksi akurasinya yaitu 4,4%. Pengujian yang dilakukan menghasilkan kesimpulan bahwa metode yang dilakukan memiliki tingkat akurasi tinggi. Peneliti menyarankan untuk penelitian selanjutnya dapat mengembangkan aplikasi ini seperti dengan menambahan fitur seperti  suara  untuk  mengarahkan  ke tempat  lokasi  tujuan  dan juga menghitung kemacetan lalu lintas jalan.

## REFERENSI
[1] Besra, Eri. 2012. Potensi Wisata Kuliner Dalam Mendukung Pariwisata Di Kota Padang. Jurnal Riset Akuntansi Dan Bisnis, No. 12, Vol. 1.
[2] Yermias, L. J. I., Joko S., & Eduard R. (2013). Pengembangan E-Kuliner Kota Kupang. Prosiding Seminar Nasional Sains dan Teknologi Fakiltas Teknik, 1(1).
[3] Tyas,  Agnes.  S.P.  2017.  identifikasi  Kuliner  Lokal  Indonesia  dalam Pembelajaran Bahasa Inggris. Jurnal Pariwisata Terapan, No. 1, Vol. 1.
[4] Falanda,  F.,  Gustriansyah,  R.  and  Hartini  (2016)  ‘Penentuan  Objek
Wisata,  Objek  Kuliner  Serta  Akomodasi  Disekitar  Pengguna  Dikota Palembang  Dengan  Menggunakan  Algoritma Euclidean  Distance ’, Jurnal Ilmiah Informatika Global , 7(1), pp. 17–24.
[5] Hidayah,  N.  Dan  Suherlan,  H.  2015.  Sikap  Wisatawan  Nusantara Terhadap  Produk  Wisata  Kuliner  Di  Kota  Palembang.  Jurnal  Ilmiah
Pariwisata- STP Trisakti. Vol.20(No.2)
[6] Kamil,  Muhammad  Insan.  Hengky  Anra,  dan  Helen  Sastypratiwi.
(2015).  Rancang  Bangun  Aplikasi  Pencarian  Rute  Terpendek  Lokasi Wisata Kuliner Kota Pontianak Berbasis Mobile. Program Studi Teknik Informatika Universitas Tanjungpura, pp. 1-6.
[7] Febrylian  Samopa  dan  Yulianawati.  (2013).  ‘Penerapan  algoritma Euclidean  Distance Pada  Pencocokan  Pola  Untuk  Konversi  Citra  ke Teks’.
[8] Syukriah, Y., Falahah and Solihin, H. (2016) ‘Penerapan algoritma a* (star) untuk mencari rute tercepat dengan hambatan’, Seminar Nasional Telekomunikasi dan Informatika (SELISIK), (Selisik), pp. 219–224. doi:
ISSN : 2503-2844.
[9] Safaat, N. (2015) Pemograman Aplikasi Mobile Smartphone dan Tablet
PC Berbasis Android . Bandung.
[10]  Fernando,  Y.,  Purnama,  S.,  dan  Megawaty,  D.  A.  (2020).    Penerapan Algoritma A-Star Pada Aplikasi Pencarian Lokasi Fotografi Di Bandar Lampung berbasis Android. Jurnal TEKNOINFO. Vol.14(No.1), 27–34
[11]  Pugas, D. O. (2014) ‘Judul’, Pencarian Rute  Terpendek Menggunakan
Algoritma  Dijkstra  dan  A*(Star)  pada  SIG  Berbasis  Web  untuk Pemetaan Pariwisata Kota Sawahlunto, 1, pp. 27–32.
[12]  Purnama,  S.,  Megawaty,  D.  A.,  &  Fernando,  Y.  (2018).    Penerapan
Algoritma A*(Star) Untuk Penentuan Jarak Terdekat Wisata Kuliner Di Kota Bandarlampung. Jurnal TEKNOINFO. Vol.12(No.1), 28–32 [13]  Anwar,  U.,  Sari,  A.  P.,  &  Nasution,  R.  (2017). Perancangan   Aplikasi Wisata   Kabupaten   Lebak Menggunakan  Algoritma  A  *  (  A-Star  ) Berbasis  Android.  Simposium    Nasional    Ilmu    Pengetahuan  Dan Teknologi (SIMNASIPTEK)