## SISTEM INFORMASI GEOGRAFIS (SIG) PENENTUAN JALUR TERPENDEK UNTUK MENGHINDARI DAERAH RAWAN BANJIR (STUDI KASUS PROPINSI JAWA TIMUR)
Laylul Musabbichin 1) , Mula’ab 2), Rika Yunitarini 2)
Program Studi Teknik Informatika, Universitas Trunojoyo Madura Jl. Raya Telang, PO BOX 2, Kamal, Bangkalan-691 62
E-mail: *laylulm@gmail.com

## ABSTRAK
Pada  musim  hujan  sering  terjadi  banjir  pada    beberapa  daerah  yang  berada  di  Kota  Surabaya.
Sistem  informasi  geografis  (SIG)  mampu  menyajikan  informasi  fisik  suatu  daerah  yang berpengaruh dalam menentukan daerah rawan banjir serta menentukan jalur terpendek yang terjadi pada wilayah jawa timur. Pengguna juga dapat menentukan jalur terpendek dengan menggunakan metode Breadth  First  Search  (BFS) yang  menggunakan  fungsi  heuristic  guna  mengarahkan pencarian pada peta yang direpresentasikan dalam konsep graph, yang berguna untuk menghindari daerah  mana  yang  seringkali  terjadinya  bencana  banjir  serta  dapat  meminimalkan  kerugian  serta kemacetan  yang  terjadi  propinsi  jawa  timur.  Penelitian  ini  dilakukan  untuk  pencarian  rute terpendek antara perumahan sampai dengan tempat perumahan yang akan menjadi tujuan.
Kata Kunci: Sistem Informasi Geografis, Bredth First Search (BFS) , Banjir

## ABSTRACT
In  rainy  season  frequent  flooding  in  some  areas  in  the  province  of  East  Java.
Geographic  information  systems  (GIS)  can  present  physical  information  of  a  region  that  is influential in determining the flood-prone areas as well as determine the shortest path which occurred  in  East  Java  area.  Users  can  also  determine  the  shortest  path  using Breadth  First Search  (BFS) ,  which  uses  heuristic  function  to  guide  the  search  on  the  map  which  is represented  in  the  concept  graph,  which  is  useful  to  avoid  the  area  where  the  often occurrence of floods and to minimize losses and congestion that occurs provinces east Java. This  study  was  conducted  to  search  the  shortest  route  between  the  place  of  housing  to housing that would be the goal.
Keywords : GIS, Breadth First Search (BFS), flooding

## PENDAHULUAN
Bencana  banjir  merupakan  salah  satu fenomena  bencana  yang  sering  terjadi  di musim  penghujan.  Bencana  banjir  tidak terlepas dari beberapa faktor yang sering terjadi  disekitarnya,  contohnya  adalah faktor  alam  yang  disebabkan  karena struktur  bentang  alam  Indonesia  yang sangat  bervariasi,  kemudian  ada  juga faktor yang dapat menyebabkan terjadinya  bencana  banjir  adalah  faktor manusia  dikarenakan  manusia  seringkali melakukan  penggundulan  hutan  atau penebangan hutan secara tidak terkontrol yang menyebankan peningkatan aliran air pemukiman  yang  tinggi  dan  tidak terkendali,  sehingga  menimbulkan  banjir bandang  dan  kerusakan  lingkungan didaerah  satuan  wilayah  sungai  atau perubahan  tata-guna  lahan  yang  tidak memperhatikan daerah resapan air,
kemudian  terdapat  juga  faktor  penyebab banjir  adalah  faktor  iklim  yang  terkait dengan banjir adalah hujan, dimana hujan merupakan  sumber  air  terjadinya  suatu kejadian banjirdan yang terakhir adalahfaktor fisikdari daerah aliran sungai (DAS) yang mempengaruhi
terjadinya  banjir  adalah  faktor  lereng, kemampuan  tanah  dalam  menyerap  air hujan serta jarak dari badan air. Selain itu daerah  aliran  sungai  (DAS)  yang  berada pada  jawa  timur  adalah  aliran  sungai yang  berasal  dari  bengawan  solo  ketika curah  hujan  tinggi  dan  bengawan  solo tidak  dapat  menampung  air  yang  berasal dari  air  hujan,  maka  terjadi  luapan  air yang  menyebabkan  terjadinya  bencana banjir.  Luapan  bengawan  solo  ini menggenangi  daerah  –  daerah  pinggir sungai yang dilalui oleh bengawan solo.
Propinsi Jawa Timurterletak diujung timur  pulau  jawa  dengan  luas  wilayah  ± 47.921.98 km2. Sebelah barat berbatasan dengan  propinsi  jawa  tengah,  disebelah utara  dengan  laut  jawa,  sebelah  timur dengan  selat  bali,  dan  sebelah  selatan berbatasan  dengan  dsamudra  Indonesia. Secara  adminitratif  propinsi  jawa  timur meliputi 29 kabupaten dan 9 kota, dengan
totaljumlah  kecamatan  sebanyak  658 kecamatan dengan 8.457 desa / kelurahan (2.400 kelurahan dan 6.097 desa). Untuk meningkatkan  koordinasi  pelaksanaan pemerintah dan
pembangunan dibentuklah  empat  badan  koordinasi wilayah  pemerintahan  dan  pembangunan jawa timur yaitu kota madiun, kabupaten bojonegoro,  kota  malang,  dan  kebupaten pamekasan.  Dari  sisi  hidrologi  sungai  di propinsi  jawa  timur  dibagi  menjadi  6 wilayah; meliputi wilayah sungai madiun,  sungai  bengawan  solo,  sungai bengawan  solo,  sungai  brantas  tengah, sungai  brantas  hilir,  sungai  pekalen sampean,  dan  sungai  Madura.  Dari  6 wilayah  tersebut,  daerah  aliran  sungai (DAS) bengawan solo dan sungai brantas merupakan  2  DAS  terpenting  di  wilayah jawa timur; dimana kedua sungai tersebut digunakan oleh masyarakat untuk pemenuhan  kebutuhan  sehari  –  hari.
Sungai brantas memliki mata air didaerah malang, tepatnya dilerang gunung anajasmoro.  Sungai  ini  mengalir  kehili melewati  11  kabupaten  dan  4  kota, dengan luas, dengan luas DAS mencapai 12.000 km2. Didaerah mojokerto, sungai brantas  terpecah  membentuk  2  anak sungai  yait  kali  mas  dan  kali  porong. Kedua  anak  sungai  tersebut  kemudian bermuara  di  selat  Madura.  Sementara mata  air  bengawan  solo  berasal  dari wilayah  jawa  tengah, melintasi 5 kabupaten  dan  bermuara  di  gresik. Propinsi  jawa  timur  yang  sering  terjadi dengan bencana banjir. Walaupun pemerintah  setempat  telah  berupaya dengan  semaksimal  mungkin  untuk mengatasi permasalahan penyebab terjadinya  bencana  banjir,  hal  ini  terjadi karena adanya  musim hujan yang berada di  propinsi  jawa  timur,  pengaruh  pasang surut  air  laut  yang  terjadi  pada  daerah pinggiran  sungai,  pengalihan  tata  guna lahan.
Manajemen  didalam  penelitian ini adalah sistem informasi yang berbasis geografis atau biasa dikenal dengan nama Sistem Informasi Geografis (SIG), karena
dala  penelitian  ini  data  yang  digunakan adalah  data  yang  berisikan  tentang  letak geografis.  SIG  merupakan  sistem  untuk penanganan data keruangan. SIG mempunyai fungsi utama dalam pengelolaan  data  spasial,yaitu  suatu  data yang  berorieantasikan  geografis  dan merupakan  suatu  lokasi  yang  memiliki koordinat tertentu. SIG memiliki kemampuan untuk menghubungkan berbagai data pada titik tertentu di bumi, sehingga  diharapkan  bias  menjadi  solusi yang  tepat  untuk  pengelolaan  data geografis.  Selain  itu  SIG  juga  dapat meningkatkan
pemahaman
atau pengertian  terhadap  suatu  informasi lokasi,  ruang  (spasial)  dan unsur  – unsur geografis  yang  terdapat  pada  permukaan bumi.  Sistem  informasi  goegrafis  yang dapat  ditampilkan  adalah  berupa  titik
(line) biasanya digunakan untuk
menentukan  titik  koordinat  tertentu,  ada juga  yang  dapat  ditampilkan  oleh  SIG adalah  garis  (line)  yang  berguna  untuk menampilkan jalan kemudian batas, yang terakhir  yang  dapat  ditampilkan  adalah area  (polygon)  yang  sangat  bermanfaat untuk  penelitian  ini  menampilkan  area mana yang terkena bencana banjir.

## METODE
Algoritma Breadth First Search(BFS)
Breadth  First  Search    (BFS) adalah algoritma  pathfindingyang  menggunakan menggunakan  fungsi  heuristic  untuk menuntun  pencarian  solusi,  dengan menghitung  berapa  jauh  goaldari  node sekarang  [5].  Dari  sekian  pilihan  jalan, dipilih  jalan  yang  paling  dekat  ke tujuan.BFS  tidak  menjamin  menemukan rute yang paling pendek, namun algoritma  ini  bekerja  dengan  sangat cepat. Pada setiap langkah proses pencarian terbaik pertama, memilih node –  node  dengan  menerapkan  fungsi heuristik yang memadai pada setiap node / simpul yang diplih dengan menggunakan  aturan  –  aturan  tertentu untuk
menghasilkan penggantinya.
Fungsi heuristik merupakan suatu strategi untuk  melakukan  proses pencarian ruang keadaan  suatu  problema  secara  selektif, yang  memandu  proses  pencarian  yang dilakukan  sepanjang  jalur  yang  memiliki kemungkinan sukses paling besar.
Keuntungan Breadth  First  Search (BFS) :
1. Tidak menemui jalan buntu.
2. Jika ada solusi lebih dari satu solusi, maka  solusi  minimum  yang  akan ditemukan
Gambar  1 Breadth  First  Search (BFS)
Cara Kerja Algoritma Breadth First Search(BFS)
Ada  beberapa  istilah  yang  sering digunakan  pada  metode  best  first  search yaitu : 1. Start node adalah sebuah terminology  untuk  posisi  awal sebuah pencarian. 2. Curret  node  adalah  simpul  yang sedang  dijalankan  dalam  algoritma pencarian jalan terpendek.
3. Suksesor  adalah  simpul  –  simpul yang  akan  diperiksa  setelah  current node.
4. Simpul (node) merupakan representai dari area pencarian.
5. Open  list adalah tempat  menyimpan data  simpul  yang  mungkin  diakses dari  starting  node  maupun  simpul yang sedang dijalankan.
6. Closed list adalah tempat menyimpan  data  simpul  yang  juga merupakan bagian dari jalur terpendek yang telah berasil didapatkan.
7. Goal node yaitu simpul tujuan.
8. Parent  adalah  current  node  dari suksesor.
Untuk  mengimplementasikan  algoritma diperlukan dua senarai yaitu OPEN yang berguna  untuk  mengolah  node  –  node yang  pernah  dibangkitkan  dan  belum dievaluasi  dan  CLOSE  untuk  mengolah node  –  node  yang  pernah  dibangkitkan dan sudah pernah dievaluasi. Algoritmanya sebagai berkut : 1. OPEN  berisi  inisial  state  dan
CLOSE masih kosong.
2. Ulangi  sampai  goal  ditemukan  atau sampai tidak ada dalam OPEN.
a. Ambil  simpul  terbaik  yangada di OPEN
b. Jika  simpul  tersebut  sama dengan goal maka sukses
c. Jika  tidak,  masukan  simpul tersebut ke dalam CLOSED
d. Bangkitkan  aksesor dari simpul tersebut e. Untuk setiap suksesor kerjakan Jika suksesor tersebut belum pernah dibangkitkan, evaluasi suksesor  tersebut,  tambah ke OPEN dan catat perent Jika suksesor tersebut sudah pernah dibangkitkan,  ubah  parentnya  jika jalur  melalui  parent  ini  lebih  baik dari  pada  jalur  melalui  parent sebelumnya.
Rancangan Sistem
a. Flowchart sistem
Gambar  2  . Flowchart Sistem  Pencarian Jalur Terpendek
Flowchart pada  sistem  pencarian jarak  terpendek  yang  akan  dibangun secara  umum  dapat  dijelaskan  pada Gambar 1 sebagai berikut :
1. Mulai
2. Inisialisasi peta
3. Membaca  data  seluruh node dan bobot  sisi  pada database  node dan jarak.
4. Input node-node tujuan.
5. Melakukan  proses  perhitungan lintasan  terpendek  menggunakan Algoritma Breadth First search(BFS) berdasarkan input dari langkah sebelumnya.c
6. Menampilkan  lintasan  terpendek pada peta.
7. Selesai.

## b. Flowchart Metode Breadth First search(BFS)
Pencarian Rute dengan Menggunakan BFS Inisialisasi List OPEN = Nil Closed = closed Masukan Mode Awal Ke List OPEN Set Current_Node = Best_Node (OPEN) Current_Node GOAL Keluarkan Current_ Node dari OPEN, Masukan ke CLOSED Bukan For I = to jumlah nighbor Current_Node do Nilai h Node (i) < h Node Dalam OPEN Node (i) Dapat Dapat dilalui Ada Dalam Closed ? Ya Ada Dalam OPEN ? Tidak Ya Masukan Node (I) dalam OPEN Set Parent Node (i) = current_Node, Hitung Dan Simpan Nilai F dan H Set Parerent node (i) = current Node Kalkulasi Ulang Nilai f dan h Ya Backtrack untuk menampilkan jalur i OPEN = Nil ? Rute Tidak Ada Retrun Ya Tidak Tidak Ya Tidak Ya Tidak
Gambar  3. Flowchart Breadth  First search(BFS)
Keterangan
Memasukan  posisi  awal  keberadaan pengguna  setelah  itu  menentukan  posisi tujuan  maka  sistem  akan  mencari  rute mana  saja  yang  akan  dilalui  oleh pengguna, setelah pencarian rute ditemukan  maka  sistem  akan  mengolah rute  mana  yang  jarak  tempuhnya  paling cepat  dengan  cara  membandingkan  rute yang  satu  dengan  rute  yang  lain,  apabila rute yang pertama jarak tempuhnya lebih sedikit  dibandingkan  dengan  rute  yang lainya  maka,  sistem  akan  menampilkan rute  mana  yang  paling  cepat  dilalui  oleh pengguna.

## c. Usecase Diagram
Gambar 4. Usecase Diagram
Keterangan : Dari usecase diatas dapat dilihat terdapat dua  user  yaitu  admin  dan  user  biasa. Admin  dapat  melakukan  login,  manage data master jalan dan data jalur terpendek juga  dapat  melihat  visualisasi  jalur terpendek  untuk  menghindari  daerah rawan  banjir  serta  mencetak  hasil visualisasi tersebut. Sedangkan user biasa hanya dapat menentukan posisi awal user dan  juga  posisi  tujuan  user  dengan melihat visualisasi pemetaan jalur terpendek pada sistem dan mencetaknya
d. Activity Diagram
Activity  diagram adalah  sebagai penjabar dari usecase diagram
sebelumnya,  jika  pada usecase  diagram hanya  dijelaskan  hak  akses  dari  setiap user maka pada activity diagram dijelaskan hak akses tersebut beserta alur proses  kerjanya. Activity  diagram juga menggambarkan berbagai aliran aktivitas dalam  sistem  yang  sedang  dirancang, bagaimana  alur  berawal,  keputusan  yang mungkin  terjadi,  hingga  bagaimana mereka  berakhir. Activity  diagram untuk sistem ini diperlihatkan pada gambar 5.
Gambar 5. Activity Diagram

## HASIL DAN UJI COBA
Pada  penelitian  ini  perlu  dilakukan skenario  uji  coba  pengiriman  data  posisi awal yang dapat ditunjukan melalui nama perumahan  beserta  alamat  lengkapnya serta posisi tujuan juga dengan menunjukan nama dan alamat perumahan yang  akan  dituju  .  Untuk  uji  coba skenario  akan  dilakukan  pencarian  jalur terpendek antar perumahan dengan menggunakan  sistem  informasi  yang kemudian akan dihitung dengan menggunakan metode. Pengiriman dilakukan secara berskala dari titik posisi awal  sampai  akhir(target).  Berikut  ini adalah  contoh skenario uji coba aplikasi menentukan jalur terpendek antara perumahan Perumahan,  yang  beralamat di  Jl.  Kalilom  Lor  Indah  menuju
Admin user Managemen data master jalan Managemen data banjir Managemen data jalur terpendek Managemen data bobot Pemetaan posisi user Perhitungan jalur terpendek menggunakan BFS Hasil jalur terpendek
Perumahan  Permata  Tanjung  Sari,  yang ber alamat di  Jl. Tanjungsari No.44
1. Membuka  halaman  pencarian  jalur terpendek  yang  ada  di  sistem  dan harus  dikoneksikan  dengan  internet supaya  peta  dasar  surabaya  dapat terlihat. 2. Menentukan posisi awal yaitu perumahan  yang  ber  alamat  di  Jl. Kalilom  lor  indah.  Yang  akan ditunjukan pada Gambar 6 :

## Gambar 6 Perumahan Start
3. Menentukan  posisi  tujuan  yaitu berupa  perumahan  permata  tanjung sari  yang  beralamat  di  Jl.  Tanjung sari  No.  44.  Yang  akan  ditunjukan pada Gambar 7 :
Gambar 7 perumahan Finish 4. Maka langsung diperoleh perumahan  apa  saja  yang  akan dilalui  yang  akan  ditunjukan  pada Gambar 8 : Gambar 8 Hasil Rute 5. Dan juga akan menampilkan jalan – jalan  mana  saja  yang  akan  dilalui beserta  total  jarak  tempuh  untuk mencapai  perumahan  yang  akan dituju.  Yang  akan  ditunjukan  pada gambar 9 :
Gambar 9 Nama jalan yang dilalui 6. Garis  berwarna  merah  adalah  hasil akhir  dari  pencarian  jalur  terpndek yang  akan  ditunjukan  pada  Gambar
10:

## Gambar 10 Hasil Pencarian

## SIMPULAN DAN SARAN
Setelah  dilakukan  perancangan dan  pembuatan  Sistem  Informasi Geografis  penentuan  jalur  terpendek untuk  menghindari  daerah  rawan banjir  padaTugas  Akhir  ini,  dapat ditarik kesimpulan bahwa :
1. Pada  penelitian  ini  pencarian  jalur terpendek  anatar  perumahan    lebih mudah  diamati  karena  dengan memanfaatkan  sistem  informasi geografis serta dengan menggunakan  algoritma Breadh first search (BFS) sebagai pencarian jarak terpendek. 2. Pencarian  jalur  terpendek  pada
TugasAkhir  ini  diberikan  contoh
yang  dilakukan  dari  posisi  awal yang  ditunjukan  nama  perumahan dan  alamat  perumahan    menuju perumahan yang akan di inginkan.
3. Untuk  aplikasi  pencarian rute optimum    pada  peta,  algoritma
Breadh  first  search  (BFS) lebih baik karena menggunakan algoritma heuristic yang  lain karena  dari  segi  jarak  hasil rute yang  ditemukandan  total path  cost
/ biaya  tempuh rute ,  algoritma Breadh first search (BFS)
memberikan hasil yang lebih baik.
4. Penggunaan pembagian node-node peta  berdasarkan  kotak grid peta memiliki keuntungan mempermudah  dan  mempercepat proses pemberian bobot node serta mempermudah interface pencarian rute  dengan  pengguna  aplikasi, dimana  pengguna  dapat  memilih lokasi  dimana  saja  pada  peta.
Namun kerugian  metode  ini, jumlah node yang tercipta banyak, apalagi  untuk  peta  dengan  ukuran besar, yang berakibat pada lamanya  proses  pencarian rute dengan  algoritma Breadh  first search (BFS) dan besarnya ukuran file project yang disimpanpadakomputer. 5. Software QuantumGIS yang digunakan  dalam  proses  digitasi peta sangat mudah untuk digunakan, serta peran penyimpanan data .shp di PostgreSQL yang  otomatis  akan
membantu  perhitungan  algoritma Breadh  first  search  (BFS) dengan asumsi bahwa PostGIS .

## Saran
Semoga    penelitian  pada  Tugas
Akhir  ini  dapat  bermanfaat  dan dikembangkan untuk penelitian
selanjutnya, seperti :
1. Pada  peniltian  selanjutnya  supaya mempertimbangkan arah jalur baik satu arah maupun dua arah.
2. Agar membandingkan secara langsung  antara  metode Breadh first  search  (BFS) dengan  metode depth first search (DFS) dikarenakan kedua metode tersebut saling berhubungan.

## DAFTAR PUSTAKA
[ 1 ]. Jumadi dan Widiadi. 2009.
Implementasi Aplikasi Sistem Informasi  Geografis  (Sig)  Untuk Manajemen Pemanfaatan Air Tanah.Forum  Geografi.Vol  23  (2) Desember 2009. [ 2 ]. Alhasanah, F. 2006. Pemetaan  Dan  Analisis  Daerah Rawan Banjir Tanah Longsor Serta Upaya  Mitigasinya    Menggunakan Sistem Informasi Geografis. Thesis Program Pasca Sarjana.IPB. [ 3 ]. Prahasta, Eddy. 2009.
Sistem  Informasi  Geografis  : Konsep-konsep  Dasar  (Perspektif Geodesi  &  Geomatika) .  Penerbit Informatika, Bandung. [ 4 ]. Aronoff, S. 1993. Geographic  Information  Systems  : A  Management  Perspective .  WDL Publication.Otawa. Canada.
[ 5 ]. Dechter,
Rina; Judea Pearl. Generalized best-first search strategies and the optimality of A*. Journal of the ACM32 (3): pp. 505 – 536. 1985. [ 6 ]. Ruhimat, Imat, 2010. Sistem Informasi Geografis. http://ilmutanah.unpad.ac.id/peneli tian-publikasi-artikel/arikel/sistem- informasi-geografis.html?start=1 . [ 7 ]. Ichtiara, Cici dan Kallamullah, Ramli. 2008. Implementasi aplikasi sistem informasi geografis (SIG) Universitas Indonesia (UI)
berbasis Webdengan menggunakan    Google  Maps  API . Universitas  Indonesia.  Fakultas
Teknik. R.03.08.149 Ich i.
[ 8 ] Anugrah,  Nurah,  2010.
PHP. http://www.nurahratu.com/tut orial/web-design/1-lastest-
news/203-php-adalah.html .
[ 9 ]. Fathansyah. 1999. Basis data, Informatika. Bandung