Jurnal Teknik Vol. 02 No.01 Oktober 2022 Page : 56-63

## ANALISIS JALUR TERPENDEK DALAM EVAKUASI BENCANA TSUNAMI DI DESA TOWARA DENGAN MENGUNAKAN ALOGARITMA A-STAR (A*)
Anuwar Kadir Abdul Gafur 1* , Farkun Boke 2
1 * Program Studi Matematika Universitas Pasifik Morotai, anuwarkadir657@gmail.com 2 Alumni Program Studi Matematika Universitas Pasifik Morotai

## ABSTRAK
Kabupaten Pulau Morotai yang terletak di Maluku Utara merupakan salah satu daerah rawan bencana gempa bumi dan tsunami di Indonesia, sehingga sangat penting untuk mengetahui jalur evakuasi tsunami di wilayah yang berpotensi tsunami di Kabupaten Pulau Morotai, Salah satunya adalah Kecamatan Morotai Jaya. Mengacu pada beberapa sumber penelitian sebelumnya, jalur evakuasi bencana dimodelkan dengan menggunakan Teori Graf,  khususnya  hubungan  atau  konektivitas  antar  objek  pada  graf  berbobot.  Persimpangan  jalan direpresentasikan  sebagai  titik  dan  jalur  evakuasi  tsunami  direpresentasikan  sebagai  sisi.  Pencarian  jalur evakuasi  tsunami  dicari  menggunakan  algoritma  A-Star  (A*),  disimpulkan  bahwa  penentuan  jalur  terpendek untuk evakuasi bencana tsunami, dari titik asal
dan ke titik tujuan ( terminal vertekx ) yaitu dan . memiliki  jarak  tempuh  yang  berbeda,  oleh  sebab  itu,  apa  bila  saya  berada  pada  titik dan  memililih  jalur terpendek  dari  titik ke  titik  tujuan dan maka  saya  akan  memilih  dari  titik menuju  ke  titik  tujuan  L karena dari titik A ke L lebih dekat dibandingkan dari titik ke . Begitu pun sebaliknya apabila saya berada pada titik dan maka jalur terpendek yang saya pilih adalah jalur yang menuju ke titik tujuan M, karena dari titik atau ke titik lebih dekat dibandingkan dari titik atau ke titik .
Kata kunci : jalur evakuasi tsunami, jalur terpendek, pemodelan graf, algoritma A-Star
@2021 Penerbit : Fakultas Teknik Universitas Pasifik Morotai

## 1 PENDAHULUAN

## 1.1 Latar Belakang
Kepala  Bidang  Mitigasi  Gempa  bumi  dan  Tsunami  (BMKG),  Daryono,  merilis  perkembangan  gempa  yang merusak di  Morotai, Maluku Utara. Menurutnya, gempa berkekuatan M 6,8 dengan kedalaman 111  km  yang terjadi pada Kamis tanggal 4 bulan juni tahun 2020 lalu, pukul 15.49 WIB berdampak menimbulkan kerusakan pada ratusan  bangunan  di Kabupaten  Pulau  Morotai.  Perkembangan  hasil  monitoring  BMKG  hingga  Minggu pagi 7 Juni 2020 menunjukkan aktivitas gempa susulan yang terjadi hanya 5 kali. Daryono mengatakan, gempa susulan  bermagnitudo  terbesar  mencapai  M  4,8  dan  terkecil  M  2,9.  Selain  itu,  gempa  susulan  terakhir  pada pukul 10.58 WIB tercatat berkekuatan M 3,9.
Hasil  analisis  Daryono  dan  BMKG,  minimnya  aktivitas  gempa  susulan  di  Morotai  di  sebabkan  karakteristik batuan  pada  Lempeng  Laut  Filipina  sangat  homogen  dan  elastis  (ductile).  Sifat  elastis  pada  batuan  ini  yang
menjadikan  batuan  tidak  rapuh,  sehingga  gempa  susulan  yang  terjadi  di  Morotai  sangat  sedikit.  Daryono melanjutkan, hasil monitoring BMKG selama bulan Mei 2020 sudah menunjukkan adanya peningkatan aktivitas seismisitas  khususnya  untuk  aktivitas  gempa  menengah  di  kedalaman  sekitar  100  km  di  wilayah  Morotai.
Sehingga, jika di zona aktif gempa yang terjadi sebulan sebelumnya, kini terjadi gempa kuat.
Faktanya,  perkembangan  hasil  monitoring  BMKG  hingga  Minggu  pagi  7  Juni  2020  menunjukkan  aktivitas gempa susulan yang terjadi hanya 5 kali. Guncangan tersebut membuat masyarakat berhamburan keluar rumah.
Kabupaten  pulau  morotai merupakan  salah  satu  daerah  yang  rawan  bencana  gempa  bumi  dan  tsunami,  maka sangat penting untuk mengetahui jalur evakuasi tsunami di daerah yang berpotensi terjadi tsunami di Kabupaten Pulau  Morotai,  salah  satunya  Desa  Towara  Kecamatan  morotai  Jaya.  Hal  inilah  yang  menarik  bagi  peneliti untuk menjadikan teori Graf sebagai tema penelitian adalah Analisis Jalur Terpendek Dalam Evakuasi Bencana Tsunami Di Desa Towara Dengan Menggunakan Algoritma A-Star (A*).

## 2 TINJAUAN PUSTAKA

## 2.1 Teori Graf
Sungai  Pregolya  melawati  sebuah  kota  yang  dikenal  sebagai  kota  Königsberg.  Pada  tahun  1700-an,  di  kota Königsberg terdapat tujuh jembatan yang terletak menyebrangi sungai ini seperti yang terlihat pada Gambar 1.
Penduduk  kota  melewati  jembatan-jembatan  ini,  tetapi,  sesulit  apapun  mereka  mencoba,  tidak  ada  penduduk yang  dapat  melewati  masing-masing  jembatan  ini  tepat  satu  kali.  Seorang  Matematikawan  Swiss  bernama Leonhard  Euler  mempelajari  fenomena  ini,  dan  pada  tahun  1736  ia  menulis  sebuah  artikel  yang  berjudul “ Solutio  problematis  ad  geometriam  situs  pertinentis” tentang  fenomena  ini  yaitu  Masalah  Jembatan Königsberg di anggap banyak orang sebagai awal dari Teori Graf.

## Gambar 1. Jembatan Königsberg
Sebuah graf terdiri atas , sebuah himpunan titik-titik ( vertices ) yang tidak kosong dan , sebuah himpunan garis-garis ( edges ). Setiap garis memiliki antara satu atau dua titik-titik yang terhubung dengannya, yang  di  sebut  titik-titik  ujungnya  ( endpoints )  (Rosen,  K.H.  2012).  Lintasan adalah    suatu    graf  dengan
himpunan    titik dimana untuk dan   himpunan    sisi .  Titik dan adalah    titik  ujung    dari ,  sedangkan
adalah  titik  dalam  dari . Untuk   sebarang   graf ,  titik dikatakan  terhubung   dengan jika  terdapat suatu lintasan   dari ke di  dalam  graf .   Graf disebut   sebagai  graf  terhubung  jika  untuk setiap dua  titik,  terdapat  suatu  lintasan    yang  menghubungkan  kedua  titik  tersebut.  Dalam  hal dan
terhubung,  jarak   dari ke dinotasikan   dengan
yang didefinisikan   sebagai   panjang   lintasan terpendek   dari ke di

## 2.2 Algoritma A-Star (A*)
Algoritma  A-Strar  atau  disinggat  dengan  A*  pertama  kali  di  perkenalkan  pada  1968  oleh  Peter  Hart,  Nils Nilsson,  dan  Bertram  Raphael,  yang  di  namakan  algoritma  A*.  Penggunaan  fungsi  heuristik  yang  tepat  pada algoritma A* sehingga dapat memberikan hasil yang optimal mengakibatkan algoritma ini berkembang menjadi algoritma A* (Pijls, W. and A. Kolen, 1992).  algoritma A* merupakan gabungan algoritma Dijkstra dan Best First untuk  mengkompensasikan  kelemahan-kelemahan  dari  masing-masing  algoritma.  Algoritma  A*  adalah algoritma pencarian terbaik dalam mencari jalur terpendek dengan perhitungan terkecil pada jalur dengan titik awal menuju titik akhir. Perhitungan pada Algoritma A* dapat di tentukan sebagai berikut:
a) ( ) adalah nilai pada pergerakan titik awal menuju titik berikutnya.
b) ( ) adalah perkiraan nilai pergerakan titik awal menuju tujuan akhir titik.
c) ( )  adalah jumlah  nilai  dari fungsi ( )  dan ( ) dengan  nilai  terkecil ( ) adalah jalur  terpendek menuju tujuan akhir
Secara singkat algoritma A* dapat ditulis
. Algoritma A* dinilai optimal jika ( ) adalah admissible heuristic , yaitu jarak dengan menarik garis lurus karena jarak terdekat dari dua titik adalah dengan menarik garis lurus (Wardhani F. P., A. Johar, dan Y. Fauzi, 2014).

## 3 METODE PENELITIAN

## 3.1 Tempat dan Waktu Penelitian
Penelitian ini akan dilaksanakan dimulai dari pengambilan data serta pengolahan data. Pengambilan data dari Badan Nasional Penanggulangan Bencana, Pekerjan Umum (PU) dan di Desa Towara Kecamatan Morotai Jaya selama bulan febuari-april 2022.

## 3.2 Analisis Data
Sumber pengumpulan data yang di gunakan dalam penelitian ini adalah data sekunder. Adapun data sekunder yang  diperoleh  berupa  informasi  yang  di  peroleh  dari  Badan  Nasional  Penanggulangan  Bencana  (BNPB),
Pekerjaan  Umum  dan  tempat  penelitian.  Metode  yang  di  gunakan  dalam  karya  tulis  ini  adalah  analisa  studi literatur. Sumber yang di gunakan berasal dari buku, jurnal ilmiah, dan artikel di internet.
Langkah-langkah:
1) Pengambilan data
2) Membuat graf berdasarkan peta Kabupaten Pulau Morotai khususnya Desa Towara Kecamatan Mortai Jaya, dimana persimpangan jalan akan di representasikan sebagai titik atau simpul dan jalur evakuasi tsunami akan di representasikan sebagai garis atau sisi.
3) Menentukan solusi optimal menggunakan Algoritma A- Star (A*).
4) Mendapatkan hasil optimal jalur evakuasi bencana tsunami terpendek.
Tabel 1. Daerah yang Beresiko Tsunami di Kabupaten Pulau Morotai Kode Kecamatan Nama Kecamatan Luas Risiko (Ha) Jiwa Terpapar (orang) 82.07.01 Morotai Selatan 1,809 18,304 82.07.02 Morotai Selatan Barat 1,499 11,556 82.07.03 Morotai Jaya 1,962 8,115 82.07.04 Morotai Utara 956 7,372 82.07.05 Morotai Timur 814 9,264 sumber: http//inarisk.bnpb.go.id
Gambar 2. Desa Towara

## 4 HASIL DAN PEMBAHASAN

## 4.1 Hasil Penelitian
Berdasarkan hasil obeservasi dan pengamatan di desa towara Kecamatan Morotai Jaya pada Gambar 2 terdapat pemungkiman warga dengan total jiwa yang berada di dekat persisir pantai yaitu 580 jiwa yang terdiri dari total pria 296 jiwa dan wanita 284.
Gambar 3. Penempatan titik dan sisi serta jarak pada sisi
Berdasrkan gambar 3, peneliti mendefinisikan atau memberi keterangan tabel untuk bobot dari titik i ke titik j :
1. Jika = (dari titik ke itu sendiri)
: 2. Jika ≠ dan titik terhubung dengan titik : 3. Jika ≠ dan titik tidak terhubung dengan titik :
Oleh karena itu, diperoleh hasil pada tabel 2  dan tabel 3sebagai berikut
Tabel  2. Bobot pertama (jarak) A B C D E F G H I J K L M A 0 74 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ B 74 0 50 ∞ ∞ ∞ 81 ∞ ∞ ∞ ∞ ∞ ∞ C ∞ 50 0 84 ∞ ∞ ∞ ∞ 85 ∞ ∞ ∞ ∞ D ∞ ∞ 84 0 42 ∞ ∞ ∞ ∞ 76 ∞ ∞ ∞ E ∞ ∞ ∞ 42 0 90 ∞ ∞ ∞ ∞ 76 ∞ ∞ F ∞ ∞ ∞ ∞ 90 0 ∞ ∞ ∞ ∞ ∞ ∞ 122 G ∞ 81 ∞ ∞ ∞ ∞ 0 212 62 ∞ ∞ ∞ ∞ H ∞ ∞ ∞ ∞ ∞ ∞ 212 0 ∞ ∞ ∞ 74 ∞ I ∞ ∞ 85 ∞ ∞ ∞ 62 ∞ 0 80 ∞ 110 ∞ J ∞ ∞ ∞ 76 ∞ ∞ ∞ ∞ 80 0 34 ∞ ∞ K ∞ ∞ ∞ ∞ 76 ∞ ∞ ∞ ∞ 34 0 ∞ 42 L ∞ ∞ ∞ ∞ ∞ ∞ ∞ 74 110 ∞ ∞ 0 150 M ∞ ∞ ∞ ∞ ∞ 122 ∞ ∞ ∞ ∞ 42 150 0 Tabel  3. Bobot Kedua ( Akses Jalan) A B C D E F G H I J K L M A 0 1 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ B 1 0 1 ∞ ∞ ∞ 1 ∞ ∞ ∞ ∞ ∞ ∞ C ∞ 1 0 1 ∞ ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ D ∞ ∞ 1 0 1 ∞ ∞ ∞ ∞ 2 ∞ ∞ ∞ E ∞ ∞ ∞ 1 0 1 ∞ ∞ ∞ ∞ 1 ∞ ∞ F ∞ ∞ ∞ ∞ 1 0 ∞ ∞ ∞ ∞ ∞ ∞ 1 G ∞ 1 ∞ ∞ ∞ ∞ 0 1 1 ∞ ∞ ∞ ∞ H ∞ ∞ ∞ ∞ ∞ ∞ 1 0 ∞ ∞ ∞ 1 ∞ I ∞ ∞ 2 ∞ ∞ ∞ 1 ∞ 0 1 ∞ 2 ∞ J ∞ ∞ ∞ 2 ∞ ∞ ∞ ∞ 1 0 1 ∞ ∞ K ∞ ∞ ∞ ∞ 1 ∞ ∞ ∞ ∞ 1 0 ∞ 2 L ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 2 ∞ ∞ 0 1 M ∞ ∞ ∞ ∞ ∞ 1 ∞ ∞ ∞ ∞ 2 1 0
Berdasarkan kedua table diatas, kami menganalisa jalur evakuasi masyarakat terhadap bencana tsunami. Pada bobot kedua yaitu akses jalan, terdapat 2 kategori bobot. Kategori pertama bernilai 1 yang berarti jalan dengan akses paling  mudah (jalan lebar dan terdapat beberapa rumah penduduk), dan kategori kedua bernilai 2 yang berarti jalan dengan akses sedang (jalan titak terlalu lebar dan terdapat beberapa rumah penduduk). Karena, jika ada banyak orang yang berjalan secara bersamaan pada jalan yang jaraknya sama tetapi tingkat kesulitan akses jalannya berbeda, akan lebih mudah berjalan di jalan yang aksesnya mudah dibandingkan yang aksesnya sulit.
Akses  jalan  ini  ditentukan  berdasarkan  lebar  jalan  dan  adanya  rumah  penduduk.  Pemilihan  bobot  tidak  bisa terlalu jauh karena akan mempengaruhi perbandingan jarak yang sebenarnya.
Berikut ini pada tabel 4 merupakan bobot graf yang merepresentasi dari table 2 dan tabel 3, sebagai berikut.
Tabel 4. Bobot Graf A B C D E F G H I J K L M A 0 74 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ B  74 0 50 ∞ ∞ ∞ 81 ∞ ∞ ∞ ∞ ∞ ∞ C ∞ 50 0 84 ∞ ∞ ∞ ∞ 17 ∞ ∞ ∞ ∞ D ∞ ∞ 84 0 42 ∞ ∞ ∞ ∞ 15 ∞ ∞ ∞ E ∞ ∞ ∞ 42 0 90 ∞ ∞ ∞ ∞ 7 ∞ ∞
F ∞ ∞ ∞ ∞ 90 0 ∞ ∞ ∞ ∞ ∞ ∞ 12 G ∞ 81 ∞ ∞ ∞ ∞ 0 21 62 ∞ ∞ ∞ ∞ H ∞ ∞ ∞ ∞ ∞ ∞ 21 0 ∞ ∞ ∞ 74 ∞ I ∞ ∞ 17 ∞ ∞ ∞ 62 ∞ 0 80 ∞ 22 ∞
J ∞ ∞ ∞ 15 ∞ ∞ ∞ ∞ 80 0 3 ∞ ∞
K ∞ ∞ ∞ ∞ 76 ∞ ∞ ∞ ∞ 34 0 ∞ 84 L ∞ ∞ ∞ ∞ ∞ ∞ ∞ 74 22 ∞ ∞ 0 15 M  ∞ ∞ ∞ ∞ ∞ 12 ∞ ∞ ∞ ∞ 8 15 0
berikut  ini  peneliti  memberikan  warna  untuk  mempermudah  menganalisa  jarak  terpendek  dari    lokasi  atau tempat rawan bencana  menuju titik kumpul atau titik aman dari bencana tsunami. Dapat dilihat pada gambar 4 dan  gambar  5  dimana  warna  merah  memiliki  arti  titik  asal  (rawan  bencana)  dan  warna  biru  menjelakan  titik tujuan (titik kumpul).
Gambar 4. Graf Jalur Evakuasi untuk Titik L
Gambar 5. Graf Jalur Evakuasi untuk Titik M
Pada gambar 4 dan gambar 5 menjelaskan bahwa memilih jalur alternative yang terbaik atau jalur terpendek dari titik , , , , dan menuju titik tujuan yaitu titik atau titik . Berikut ini dengan menngunakan algoritma
A* tabel berikut ini:
Tabel 5. Jalur Terpendek dngan Menggunakan Algoritma A-Star (A*)

## 3.2  Pembahasan
Berdasarkan  data  daerah  yang  beresiko  tsunami  di  kecamatan  morotai  jaya  kususnya  desa  Towara  yang  di peroleh  sehingga  dapat  dibentuk  graf  yang  titik-titiknya  ( vertices) merupakan  persimpangan-persimpangan  di desa towara sedangkan garisnya (edge) merupakan jalur evakuasi, dan bobotnya (tabel 4) merupakan perkalian dari  bobot  jarak  antara  titik  (tabel  2)  dan  bobot  akses  jalan  (tabel  3)  setiap  persimpangan  di  desa  towara direprestasikan sebagai  satu titik sehingga terbentuk 13 titik.
Untuk mencari jalur terpendek dengan Algoritma A-Star (A*),  bisa kita lihat pada   Gambar 4. dan Gambar 5 yang dimana setiap sisi dari jalur terpendek dalam evakuasi tsusnami di tandai dengan warna hijau. Pewarnaan sisi dari titik asal ke titik tujuan ( terminal vertekx ), yaitu L. Sedangkan, pada Gambar 5 adalah pewarnaan sisi dari titik asal ke titik tujuuan ( terminal vertekx ), yaitu M. Ketika dikontruksi dalam graf yang terbentuk, terdapat 13  titik.  Dari  13  titik  yang  ada,  dipilih  5 titik  sebagai  titik  asal,  yaitu  lokasi  yang  berada  di  pinggiran  pantai merupakan wilayah yang beresiko tsunami di desa Towara Kecamatan Morotai  Jaya. Dari 8 titik yang tersisa, di pilih 2 titik sebagai titik tujuan, yaitu lokasi yang berada di dataran tinggi dan merupakan daerah yang aman dari bencana tsunami. Karna terdapat 5 titik asal dan 2 titik tujuan, maka terdapat 10 jalur evakuasi. Dengan menggunakan algoritma A* untuk memilih  jalur terpendek maka terdapat 5 buah lintasan terpendek dari titik asal , dan menuju titik tujuan atau masing-masing, sebanyak 3 buah lintasan terpendek dari dari titik asal dan menuju titik tujuan yaitu
, , dan
serta sebanyak 2 buah lintasan terpendek dari titik asal dan menuju titik yaitu dan
.  Hal  ini  didebabkan  oleh  titik lebih  dekat  dengan  titik dibandingkan  menuju  ke  titik .
Begitu pun sebaliknya apabila saya berada pada titik dan maka jalur terpendek yang saya pilih adalah jalur yang menuju ke titik tujuan , karena dari titik atau ke titik lebih dekat dibandingkan dari titik atau ke titik .
Berdasarkan  hasil  analisis  dari  Algoritma  A-Star  (A*)  dapat  disimpulkan  bahwa  dalam  penentuan  jalur terpendek untuk evakuasi bencana tsunami, dari titik asal
dan ke titik tujuan ( terminal vertekx ) yaitu dan . memiliki jarak tempuh yang berbeda, oleh sebab itu, apa bila saya berada pada titik dan memililih jalur terpendek dari titik ke titik tujuan dan maka saya akan memilih dari titik menuju ke titik tujuan L karena dari titik A ke L lebih dekat dibandingkan dari titik ke . Begitu pun sebaliknya apabila saya berada pada titik dan maka jalur terpendek yang saya pilih adalah jalur yang menuju ke titik tujuan M, karena dari titik atau ke  titik lebih  dekat  dibandingkan  dari  titik atau ke  titik .  Oleh  karena  itu,  peneliti memberikan saran berdasarkan kesimpulan diatas untuk pengembangan penelitian lebih lanjut mengenai jalur evakuasi  tsunami  di  Desa  atau  Kecamatan  lainnya  dan  fator-faktor  lain  yang  memenngaruhi  saat  evakuasi tsunami berlangsung selain jarak dan ukuran jalan. Penelitian ini diharapkan dapat pemerintah dalam pembuatan jalur optimal untuk evakuasi tsunami kususnya di desa towara kecamatan morotai jaya.

## DAFTAR PUSTAKA
[1]  BMKG.  2012.  Buku  Pedoman  Pelayanan  Peringatan  Dini  Tsunami  InaTEWS.  Badan Meteorologi Klimatologi dan Geofisika (BMKG) dan GTZ-IS GITEWS, Jakarta.
[2]  Profinsi Maluku Utara dalam ankga, Badan Pusat statistik, Ternate, 2018
[3]  Badan Penanggulangan Bencana daerah Pulau Morotai, 2012.
[4]   Rosen, K.H. 2012. Discrete Mathematics and Its Applications. 7th Edition. McGraw-Hill, New York.
[5]  Pijls, W. and A. Kolen (1992). A General Framework for Shortest Path Algorithms. Technical Report 92-08, Erasmus University Rotterdam.
[6]  Wardhani  F.  P.,  A.  Johar,  dan  Y.  Fauzi.  Manajemen  Basis  Data  Sarana  Kampus  Universitas Bengkulu Menggunakan Algoritma A* Berbasis Spasial. Jurnal Rekursif. 2(2): 121-128, 2014.