## APLIKASI METODE NEAREST NEIGHBOR PADA PENENTUAN JALUR EVAKUASI TERPENDEK UNTUK DAERAH RAWAN GEMPA DAN TSUNAMI
Oleh : Era Madona, Muhammad Irmansyah
Staf Pengajar Jurusan Teknik Elektro Politeknik Negeri Padang e_madona38@gmail.com, kevin_syah@yahoo.com

## ABSTRACT
Indonesia  located  at  a  ring  of  fire  was  a  country  with  the  threat  level  earthquake  and tsunami that is high. Various activities and socialization has done by government to prepare people to  face  all  possibilities  that  happens  during  and  after  the  earthquake  and  tsunami  hit.  Various facilities such as signs for evacuation instruction, simulation evacuation, and installation of alarm are prepared to assist in minimizing risk caused by tsunami and earthquake.
This paper shows the system to determine shortest track in the tsunami evacuation routes in  Padang  West  Sumatra.  The  selection  of  Padang  is  based  on  the  earthquake  disaster  which tsunami potential ever happened in this town and claimed casualties quite a lot. In this paper, is selected the number of the track that can be follow when the citizens of the city of Padang would do the evacuation line of sector VI. Some of the selected path is shortest routes to secure areas in   by pass road Padang. The shortest distance to the safe sector with the starter point Pasar Raya to road by pass is 9 km using the route - RS. Padang-Aisyiah Jl. Agus Salim-Jl. Sawahan GIS-Haru- Simpang Jl. Andalas-Jl. By pass
Keywords : inverter , PWM, IGBT, induction motors.

## PENDAHULUAN
Indonesia yang terletak pada ring of  fire  merupakan  salah  satu  negara dengan  tingkat  ancaman  gempa  dan tsunami yang cukup tinggi. Gempa Bumi ini  terjadi  karena  adanya  pergeseran lempeng  bumi  dan  bisa  berakibat Tsunami  seperti  yang  terjadi  di  Aceh pada  tahun  2004  dan  di  kota  Padang tanggal 29 September 2009, tetapi tidak mengakibatkan  terjadinya  Tsunami. Walaupun  demikian  di  kota  Padang sendiri termasuk  daerah  yang  rawan akan  terjadinya  Gempa  Bumi  dan Tsunami. Berbagai  usaha  dan  sosialisasi telah  dilakukan  pemerintah  untuk menyiapkan masyarakat guna menghadapi  segala  kemungkinan  yang
terjadi  pada  saat  dan  setelah  terjadi gempa  bumi  dan  tsunami. Berbagai fasilitas  seperti  rambu-rambu  petunjuk jalur  evakuasi,  simulasi  evakuasi,  dan pemasangan sirine telah dilakukan untuk membantu  dalam  meminimalkan  resiko yang  diakibatkan  oleh  bencana  gempa dan tsunami.
Berdasarkan permasalahan di atas maka  pada  penelitian  ini  dibuat  suatu system  yang  dapat  membantu  warga mencari  rute  terpendek  untuk  menuju suatu  daerah  aman  jika  telah  terjadi gempa  dengan  potensi  tsunami.  Untuk penentuan  rute  terpendek  dilakukan dengan  menggunakan  penyelesaian Travelling  Salesman Problem  dengan metode  Nearest  Neighbor  sehingga warga  dapat  dengan  mudah  dan  cepat
menuju  daerah  yang  aman  sehingga jumlah korban jiwa dapat diminimalkan

## TINJAUAN PUSTAKA
Untuk  memudahkan  pengawasan  dan pemetaan daerah bahaya tsunami, Badan Nasional  Penanggulangan  Bencana (BNPB)  Kota  Padang  telah  membagi wilayah  kota  Padang  menjadi  6  sektor untuk  memudahkan  penentuan  jalur evakuasi pada masing-masing
wilayah.[8]
Berdasarkan  pemetaan  wilayah  ini, pemerintah Kota Padang telah membuat dan  memasang  rambu  petunjuk  jalur evakuasi  tsunami  seperti  yang  tampak pada gambar 1. Rambu ini menunjukkan arah  menuju  daerah  aman.[7]  Selain rambu juga dipasang peta jalur evakuasi tsunami
Kota Padang. Tujuan pemasangan  rambu  dan  peta  jalur evakuasi  tsunami  ini  bertujuan  untuk membantu  masyarakat  menuju  daerah yang aman jika terjadi gempa bumi dan tsunami.  Akan  tetapi,  seringkali  rambu- rambu ini tidak begitu diperhatikan oleh masyarakat sehingga tidak jarang rambu- rambu  ini  hanya  sebagai  hiasan  jalan dengan  fungsi  yang  tidak  begitu maksimal.
Gambar 1. Contoh rambu petunjuk  jalur evakuasi dan Peta Evakuasi Tsunami
Kota Padang

## Travelling Salesman Problem dengan
Metode Nearest Neighbor Permasalahan tentang Traveling Salesman  Problem dikemukakan  pada tahun 1800 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan Inggris Thomas Penyngton.  Gambar 2  adalah  foto  dari permainan  Icosian  Hamilton  yang membutuhkan
pemain untuk menyelesaikan  perjalanan  dari  20  titik menggunakan hanya jalur -jalur tertentu.
Gambar 2 Foto dari permainan Icosian Hamilton
TSP  dikenal  sebagai  suatu  permasalah optimasi  yang  bersifat  klasik  dan Non- Deterministic Polynomial-time Complete (NPC),  dimana  tidak  ada  penyelesaian yang  paling  optimal  selain  mencoba seluruh kemungkinan penyelesaian yang ada.  Permasalahan  ini  melibatkan seorang traveling  salesman yang  harus melakukan kunjungan sekali pada semua kota  dalam  sebuah  lintasan  sebelum  dia kembali  ke  titik  awal,  sehingga perjalanannya dikatakan sempurna. Pada Metode Nearest Neighbor ini, pemilihan lintasan akan dimulai pada lintasan yang memiliki  nilai  jarak  paling  minimum setiap  melalui  daerah,  kemudian akan memilih  daerah  selanjutnya  yang  belum dikunjungi  dan  memiliki  jarak  yang paling minimum.

## Gambar 3. Wilayah sektor 6
Langkah-langkah  untuk  menyelesaikan Metode Nearest Neighbor : 1. Buat peta aliran
yang menggambarkan  letak-letak  daerah yang terdapat bahaya antar daerah.
2. Proses  pengerjaan  dengan  melihat daerah  dengan  jarak terpendek. Setiap  mencapai  satu  daerah algoritma  ini  akan  memilih  daerah selanjutnya  yang  belum  dikunjungi dan  memiliki  jarak  yang  paling minimum.
3. Perhitungan  nilai  optimal  dengan menjumlah  jarak  dari  awal  sampai akhir perjalanan.

## Jalur  Evakuasi  Gempa  Bumi dan Tsunami
Jalur  Evakuasi  ini  di  ambil  dari  data BNPB (Badan Nasional Penanggulangan Bencana)  Propinsi  Sumatera  Barat  yang di bagi menjadi enam sektor yaitu :
1. Sektor I
Pada sektor I ini terdiri dari beberapa wilayah  yaitu  Jl.  Raya  padang  sarai, Jl. Raya Simpang Kalumpang, dan Jl. Raya Pasir Jambak dll.
2. Sektor II Pada sektor II ini terdiri dari beberapa wilayah  yaitu  Jl.  Adi  Negoro,  Jl. Muaro penjalinan, Jl. Dr. Hamka dll.
3. Sektor III Pada  sektor  III  ini  terdiri  dari beberapa wilayah  yaitu Jl. Bhakti, Jl. Parupuk  Raya,  Jl.  Patenggangan, Cendrawasih,  Tunggul  hitam,  Jl. Dadok,  Jl.  Berok  Raya,  UNP,  Basko Grand Mall dll.
4. Sektor IV Pada  sektor  IV  ini  terdiri  dari beberapa wilayah yaitu Jl. S. Parman, Hotel  Pangeran,  Jl.  H.  Juanda,  Jl. Veteran,  Jl.  Khatib  Sulaiman,  Jl. Rasuna Said, Gor Agus Salim, Jl. KH. Ahmad  Dahlan,  Jl.  Gajah  Mada Kurao dll.
5. Sektor V
Pada sektor V ini terdiri dari beberapa wilayah yaitu Purus, Ujung Gurun, Jl.
Damar, Jl. Pemuda, Kantor Gubernur,
RSU Yos Sudarso dll.
6. Sektor VI Pada  Sektor  VI  ini  mana  meliputi daerah  yang  padat  penduduk  dan menjadi  pusat  sentral,  karena  pada sektor  ini  merupakan  tempat  ramai yang  di  kunjungi  oleh  masyarakat terutama  Pasar  Raya  Padang.  Jadi secara tidak langsung Sektor VI ini di pilih  untuk  menentukan  Travelling Salesman  Problem  menggunakan metode nearest Neighbor.

## 2.3 Mikrokontroller ATMega 8535
Untuk
penyimpanan data,
mikrokontroller  AVR  menyediakan  dua jenis  memori  yang  berbeda  yaitu EEPROM ( Electrically Erasable Programmable Read Only Memory ) dan
SRAM ( Static Random Access memory ). EEPROM  umumnya  digunakan  untuk menyimpan  data-data  program  yang bersifat  permanen,  sedangkan  SRAM digunakan  untuk  menyimpan  data variabel  yang  dimungkinkan  berubah setiap saatnya.
Dalam  mikrokontroler  ATMega8535, sudah terdiri dari:
1. Saluran  I/O  sebanyak  32 buah,yaitu  Port  A,  Port  B,  Port C,dan Port D.
2. ADC 10 bit sebanyak 8 saluran. 3. Tiga buah Timer/counter dengan kemampuan pembandingan.
4. CPU  yang  terdiri  atas  32  buah register.
5. Watchdog Timer dengan osilator internal.
6. SRAM sebesar 512 byte.
7. Memori Flash sebesar  8  kb dengan kemampuan Read  While Write .
8. Unit interupsi internal  dan eksternal.
9. Port antarmuka SPI.
10. EEPROM sebesar 512 byte yang dapat diprogram saat operasi.
11. Antarmuka komparator analog.
Port USART untuk komunikasi serial.

## METODOLOGI PENELITIAN Perancangan  dan Penentuan  Rute Terpendek
Tahap  ini  akan  dimulai  dengan pengelompokan  daerah  yang  akan dilakukan  penentuan  rute  terpendek  dan menentukan  kemungkinan  jalur  yang akan  dilalui. Pengolahan  jarak  yang dilakukan  adalah  menggunakan  metode Nearest Neighbor, dengan:
- Daerah  yang  dijadikan  acuan untuk  pemilihan  rute  terpendek adalah  wilayah  sektor  VI  kota Padang
- Titik  awal  perjalanan  adalah Pasar raya Padang.
Pasar raya dipilih karena titik ini merupakan  pusat  perdagangan dikota padang  yang  melibatkan banyak orang.
- Daerah  aman  yang  dituju  untuk penyelamatan  adalah  Jl  by  pass karena  sudah  berada  didaerah aman.
Ada empat jalur yang digunakan pada peta  evakuasi  sektor  VI  ini, diantaranya :
 Jalur pertama Pasar Raya - RS. Aisyiah Padang - Jl.  Agus  Salim - Jl. Sawahan - GIS Simpang Haru - Jl. Andalas - Jl. By pass
 Jalur kedua Pasar  Raya - Hotel  Padang - Jl. Proklamasi - Jl.  Doktor Wahidin

## - Jl.  Singamangaraja - Simpang
Haru - Jl. By pass
 Jalur ketiga Pasar Raya - Bank Indonesia (Jl. Jendral Sudirman) - Jati 3 - M. Jamil - Dipo Lokomotif Padang - Jl. By pass  Jalur keempat Pasar Raya - Jl. Ganting - Jl. Parak Pisang - Jl. Parak Gadang - Jl. Sutomo - Jl. By pass
Penentuan  rute  terpendek  untuk  jalur dari  pasar  raya  menuju  jl by  pass  ada beberapa  alternatif  dengan  perhitungan sebagai berikut:
1. Jalur  Pertama  dari  Pasar  Raya – By Pass, jaraknya dalam satuan (km).
Tabel 1 Data Hasil Pengukuran Jalur Pertama M 1 T 2 3 4 5 6 7 JT 0,30 0,96 1,42 1,93 2,64 4,52 M 2 T 3 4 5 6 7 JT 0,66 1,12 1,63 2,34 4,22 M 3 T 4 5 6 7 JT 0,46 0,97 1,68 3,56 M 4
T 5 6 7
JT 0,51 1,22 3,10 M 5
T 6 7 JT 0,71 2,59 M 6
T 7 JT 1,88 M 7
T 1 JT 4,52 Keterangan :
M  =  Mulai  perjalanan JT  =  Jarak tempuh antara masing – masing daerah T  = Tujuan
Pasar Raya
1. RS. Aisyiah
2. JL. H Agus Salim
3. Jl. Sawahan
4. GIS Simpang Haru 5. Jl. Andalas
6. Jl. By Pass
Dari  hasil  perhitungan  diatas  didapat lintasan terpendeknya adalah 1 – 2 – 3 – 4 – 5 – 6 – 7 – 1  dengan  total  jarak tempuh sebesar 9,04 km.
2. Jalur Kedua dari Pasar Raya – By Pass, jaraknya dalam satuan (km).
Tabel 2 Data  Hasil  Pengukuran  Jalur Kedua
Keterangan : M = Mulai perjalanan T  = Tujuan JT  =  Jarak  tempuh  antara  masing – masing daerah
1. Pasar Raya
2. Hotel Padang
3. JL. Proklamasi
4. Jl. Doktor Wahidin
5. Jl. Singamangaraja 6. Simpang Haru 7. Jl. By Pass M 1
T 2 3 4 5 6 7 JT 0,32 0,78 1,41 1,54 1,79 4,67 M 2 T 3 4 5 6 7 JT 0,46 0,89 1,20 1,48 4,27 M 3 T 4 5 6 7 JT 0,53 0,82 1,10 3,94 M 4 T 5 6 7
JT 0,34 0,60 3,42 M 5
T 6 7 JT 0,33 3,12 M 6 T 7 JT 2,85
Dari  hasil  perhitungan  diatas  didapat lintasan terpendeknya adalah 1 – 2 – 3 – 4 – 5 – 6 – 7 – 1 dengan  total  jarak tempuh sebesar 9,5 km.
3. Jalur Ketiga dari Pasar Raya – By Pass, jaraknya dalam satuan (km).
Tabel 3 Data  Hasil  Pengukuran  Jalur Ketiga.
T 2 3 4 5 6 JT 0,56 0,68 0,83 1,58 4,79 M 2 T 3 4 5 6 JT 0,20 0,51 1,26 4,22 M 3 T 4 5 6 JT 0,32 0,97 4,0
M 4
T 5 6 JT 0,76 0,82 M 5
T 6 JT 2,97 M 6
T 1 JT 4,79

## Keterangan :
M = Mulai perjalanan T = Tujuan JT  =  Jarak  tempuh  antara  masing – masing daerah
1. Pasar Raya
2. Bank Indonesia
3. Jati 3
4. M. Jamil 5. Dipo Lokomotif 6. Jl. By Pass Dari  hasil  perhitungan  diatas  didapat lintasan terpendeknya adalah 1 – 2 – 3 – 4 – 5 – 6 – 1 dengan total jarak tempuh sebesar 9,6 km.
4. Jalu r Ked ua dari Pasa r Ray a – By Pass , jara kny a dala m satuan (km).
Tabel 4 Data  Hasil  Pengukuran  Jalur Keempat
Keterangan : M = Mulai perjalanan T = Tujuan JT = Jarak tempuh antara masing – masing daerah
Dari  hasil  perhitungan  diatas  didapat lintasan terpendeknya adalah 1 – 2 – 3 – 4 – 5 – 6 – 7 – 1  dengan  total  jarak  tempuh sebesar 10,17 km.
Data  hasil  pengukuran  di  atas  dapat disimpulkan  bahwa  berdasarkan keempat jalur evakuasi yang telah di buat, memiliki perbedaan jarak tempuh yaitu :
Tabel 6 Data Hasil Pengukuran tiap – tiap Jalur
Maka  dari  keempat  jalur  tersebut  yang memiliki  jarak  tempuh  yang  terpendek
M 1 T 2 3 4 5 6 JT 1,13 1,43 1,79 2,00 5,01 M 2 T 3 4 5 6 JT 0,51 0,81 1,30 3,88 M 3 T 4 5 6 JT 0,35 0,74 3,37 M 4 T 5 6 JT 0,56 3,31 M 5 T 6 JT 2,61 M 6
T 1 JT 5, 01
Nama Jalur
Jarak Tempuh Jalur pertama 9,04 km Jalur kedua 9,5 km Jalur ketiga 9,6 km
Jalur keempat 10,17 km
adalah  jalur  pertama  dengan  jarak  tempuh 9,04 km.
Kesimpulan 1. Travelling Salesman Problem menggunakan metode nearest neighbor  untuk  menentukan  rute terpendek pada peta evakuasi sektor VI,  dimana  jarak  tempuh  yang terpendeknya adalah 9,04 km.
2. Aplikasi  hasil  rute  terpendek  pada peta sektor VI membantu penunjukan  arah  yang  dituju  dari pasar raya ke Jl by pass.

## DAFTAR PUSTAKA
[1]  Winoto,  Ardi.  2010. Mikrokontroler AVR  ATmega8/32/16/8535 dan  Programannya  Dengan Bahasa  C  Pada  WinAVR . Bandung : Informatika. [2]  Wiyono, Didik, ST. 2007. Panduan Praktis Mikrokontroler Keluarga AVR Menggunakan DT-COMBO AVR-51 Starter Kit dan DT-COMBO AVR Exercise Kit . Surabaya : Innovative Elektronics [3]  GTZ-GITEWS  Editorial.  2008.
Peningkatan kapasitas masyarakat  lokal  kerjasama Indonesia-jerman  untuk  system peringatan
dini tsunami.
Potsdam-germany.
[4] Rifwan, Fitra. 2012. Studi evaluasi efektifitas penggunaan Jalur evakuasi pada zona berpotensial Terkena bencana tsunami di kota padang. Program Pascasarjana Universitas Andalas : Padang [5] Amin, Rahma Aulia. Dkk, 2006. Traveling Salesman Problem, Bandung: Institut Teknologi Bandung
[6] Tailor III, Bernard W,2005.
Introduction to management science, Pearson Prentice Hall.
[7] Vidiarina,Henny D. Rambu evakuasi – Standar nasional dan ISO, Jakarta:GTZ-GITEWS
[8]  BNPB  Kota  Padang,  Peta  sektor daerah  bahaya  tsunami  kota  padang, Padang.