PERANCANGAN SISTEM PENENTUAN RUTE TERPENDEK JALUR EVAKUASI TSUNAMI DENGAN ALGORITMA ANT COLONY (STUDI KASUS: BELAWAN)
SKRIPSI
EKO VERDIANTO 081401034
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
Universitas Sumatera Utara
PERANCANGAN SISTEM PENENTUAN RUTE TERPENDEK JALUR EVAKUASI TSUNAMI DENGAN ALGORITMA ANT COLONY (STUDI KASUS: BELAWAN)
SKRIPSI Diajukan untuk melengkapi tugas akhir dan memenuhi syarat mencapai gelar Sarjana Komputer
EKO VERDIANTO 081401034
PROGRAM STUDI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
Universitas Sumatera Utara
PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: PERANCANGAN SISTEM PENENTUAN RUTE TERPENDEK JALUR EVAKUASI TSUNAMI DENGAN ALGORITMA ANT COLONY (STUDI KASUS: BELAWAN) : SKRIPSI : EKO VERDIANTO : 081401034 : SARJANA (S1) ILMU KOMPUTER : ILMU KOMPUTER : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI (FASILKOM-TI) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, 16 April 2013
Komisi Pembimbing
:
Pembimbing II,
Pembimbing I,
Ade Candra, S.T., M.Kom NIP: 197909042009121002
Dr. Poltak Sihombing, M.Kom NIP: 196203171991021001
Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,
Dr. Poltak Sihombing, M.Kom NIP. 196203171991031001
Universitas Sumatera Utara
PERNYATAAN
PERANCANGAN SISTEM PENENTUAN RUTE TERPENDEK JALUR EVAKUASI TSUNAMI DENGAN ALGORITMA ANT COLONY
(STUDI KASUS: BELAWAN) SKRIPSI
Saya menyatakan bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, 16 April 2013
EKO VERDIANTO 081401034
Universitas Sumatera Utara
PENGHARGAAN
Alhamdulillah. Puji dan syukur penulis ucapkan kepada Allah SWT atas limpahan rahmat dan karunia-Nya sehingga penulis dapat menyelesaikan skripsi ini sebagai syarat untuk memperoleh gelar Sarjana Komputer, Program Studi Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. Kemudian Shalawat dan salam penulis ucapkan kepada Rasulullah Muhammad SAW. Pada pengerjaan skripsi dengan judul Perancangan Sistem Penentuan Rute Terpendek Jalur Evakuasi Tsunami dengan Algoritma Ant Colony, penulis menyadari bahwa banyak campur tangan pihak yang turut membantu dan memotivasi dalam pengerjaannya. Dalam kesempatan ini, penulis mengucapkan terima kasih kepada: 1. Bapak Prof. Dr. dr. Syahril Pasaribu, DTM&H, MSc(CTM). Sp.A(K), selaku Rektor Universitas Sumatera Utara. 2. Bapak Prof. Dr. Muhammad Zarlis, M.Sc., selaku Dekan Fakultas Ilmu Komputer dan Teknologi Informas Universitas Sumatera Utara. 3. Bapak Dr. Poltak Sihombing, M.Kom, selaku Ketua Program Studi Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 4. Ibu Maya Silvi Lydia, B.Sc., M.Sc selaku Sekretaris Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 5. Bapak Dr. Poltak Sihombing, M.Kom dan Bapak Ade Candra S.T., M.Kom selaku dosen pembimbing yang telah memberikan arahan dan motivasi kepada penulis dalam pengerjaan skripsi ini. 6. Bapak Drs. Muhammad Firdaus, M.Si dan Ibu Maya Silvi Lydia, B.Sc., M.Sc. sebagai dosen penguji yang telah memberikan saran dan kritik kepada penulis dalam penyempurnaan skripsi ini. 7. Seluruh dosen Program Studi S1 Ilmu Komputer Fasilkom-TI USU dan semua pegawai Program Studi S1 Ilmu Komputer Fasilkom-TI USU. 8. Ayahanda Bambang Joko Prasetyo dan Ibunda Kasihati yang telah memberikan do’a, dukungan, perhatian serta kasih sayang yang tulus serta pengorbanan yang tidak ternilai harganya. 9. Teman-teman seperjuangan mahasiswa S1-Ilmu Komputer stambuk 2008, Tengku Surya Pramana, Zainuddin Siregar, Ahmad Royhan P.S, Nurul Akhmaliyah, Siska
Universitas Sumatera Utara
Anggraini, Brikson, Mirnawati, Nassan Siregar dan teman-teman lain yang telah memberikan motivasi, arahan dan perhatiannya. 10. Teman-teman Asisten Laboratorium (IKLC), Ramrudin, Arifin, Fauzana, Isman Santoso, Mahadi Z, Basrah Nasution, Mhd. Arisandy Pratama, Azizah Mei Sari Sebayang, Nurhennida, dan asisten laboratorium yang lainnya yang telah memberikan semangat dan dorongan. 11. Adik-adik angkatan 2009 yang telah membakar semangat untuk menyelesaikan penyelesaian skripsi ini. 12. Semua pihak yang terlibat langsung ataupun tidak langsung yang tidak dapat penulis ucapkan satu per satu yang telah membantu penyelesaian skripsi ini. Penulis menyadari bahwa skripsi ini masih jauh dari kesempurnaan, oleh karena itu penulis menerima saran dan kritik yang bersifat membangun demi kesempurnaan skripsi ini. Sehingga dapat bermanfaat bagi kita semuanya.
Medan, 16 April 2013
Eko Verdianto
Universitas Sumatera Utara
ABSTRAK
Tahun 2004, Indonesia dikejutkan oleh tragedi tsunami yang menghancurkan sebagian besar pesisir pantai utara Sumatera, terutama kota Banda Aceh. Tsunami tersebut menyebabkan sekitar lebih dari 230.000 jiwa meninggal. Upaya evakuasi diperlukan untuk mencegah terjadinya korban akibat tsunami, oleh karena itu rute evakuasi yang efektif perlu dibuat. Teknologi informasi yang semakin berkembang memungkinkan pengaplikasian sistem informasi geografis untuk penentuan jalur evakuasi tsunami. Salah satu metode yang dapat digunakan pada sistem informasi geografis untuk mencari rute yang tepat yang dapat dijadikan jalur evakuasi tsunami adalah Algoritma Ant Colony. Algoritma Ant Colony atau disebut juga Ant Colony Optimization (ACO), merupakan metode pencarian metaheuristik yang diinspirasi oleh perilaku semut dalam menyelesaikan permasalahan optimisasi, termasuk dalam permasalahan pencarian rute terpendek. Algoritma Ant Colony dapat digunakan untuk mencari rute terpendek menuju tempat yang aman dari tsunami, sehingga dapat digunakan sebagai jalur evakuasi. Pengujian pada daerah belawan terbukti bahwa sistem dapat menghasilkan rute terpendek yang dapat dijadikan sebagai jalur evakuasi tsunami. Sistem memerlukan waktu sekitar 1 menit 22.4 detik untuk mendapatkan rute terpendek tersebut.
Katakunci : Algoritma Ant Colony, Algoritma Ant Colony System, ArcView GIS 3.3, Sistem Informasi Geografis, Rute Terpendek.
Universitas Sumatera Utara
DESIGN OF SHORTEST PATH DETERMINATION SYSTEM FOR TSUNAMI EVACUATION ROUTE WITH ANT COLONY ALGORITHM (CASE STUDY: BELAWAN)
ABSTRACT
In 2004, Indonesia struck by the tsunami tragedy that destroyed most of the northern coast of Sumatra, especially the city of Banda Aceh. The tsunami left an estimated more than 230,000 people dead or missing persons list. Evacuation effort is needed to prevent the victims of the tsunami, therefore an effective evacuation routes need to be made. With the growing of the information technology, allows us to apply geographic information systems for determining tsunami evacuation routes. One method that can be used in geographic information system to find the exact route that can be used as a tsunami evacuation route is the Ant Colony Algorithm. Ant Colony Algorithm also called Ant Colony Optimization (ACO), a metaheuristic search methods that are inspired by the behavior of ants in solving optimization problems, including the problem for searching the shortest route. Ant Colony Algorithm is used to generate the shortest route to get to the safe haven from the tsunami, so it can be used as an evacuation route. The testing at belawan is shown that system can determine a shortest path which can be used as tsunami evacuation route. The system takes about 1 minute 22.4 seconds to determine the shortest path.
Keywords : Ant Colony Algorithm, Ant Colony System Algorithm, Arc View GIS 3.3, Geographic Information System, Shortest Path.
Universitas Sumatera Utara
DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar Bab 1
Bab 2
ii iii iv vi vii viii x xi
Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Metode Penelitian 1.7 Sistematika Penulisan
1 3 4 4 5 5 6
Tinjauan Pustaka 2.1 Tsunami 2.2 Graph 2.2.1 Macam-macam Graph Menurut Arah dan Bobotnya 2.3 Algoritma Ant Colony 2.3.1 Ant Colony System (ACS) 2.3.1.1 Aturan Transisi Status 2.3.1.2 Aturan Pembaruan Pheromone Lokal 2.3.1.3 Aturan Pembaruan Pheromone Global 2.3.1.4 Penjelasan Alur Kerja Algoritma Ant Colony System 2.4 Sistem Informasi Geografis 2.4.1 Komponen Sistem Informasi Geografis
Bab 3 Analisis Dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis Kebutuhan Sistem 3.1.2.1 Kebutuhan Fungsional Sistem 3.1.2.2 Kebutuhan Non-Fungsional Sistem 3.1.3 Pemodelan 3.1.3.1 Use Case Diagram 3.1.3.2 Activity Diagram 3.1.3.2.1 Activity Diagram Tampil Peta Belawan 3.1.3.2.2 Activity Diagram Pencarian Rute
8 10 10 12 13 14 15 15 16 18 19
21 21 22 22 22 23 23 24 24 26
Universitas Sumatera Utara
Bab 4
Bab 5
3.1.3.3 Sequence Diagram 3.1.3.3.1 Sequence Diagram Tampil Peta Belawan 3.1.3.3.2 Sequence Diagram Pencarian Rute 3.2 Perancangan Sistem 3.2.1 Antarmuka Tampil Peta Belawan 3.2.2 Antarmuka Pencarian Rute
28 28 29 30 30 31
Implementasi Dan Pengujian Sistem 4.1 Implementasi Sistem 4.1.1 Implementasi Algoritma Ant Colony System 4.1.1.1 Proses Pencarian Rute Terpendek Titik t95 4.1.2 Tampilan Peta Belawan 4.1.2 Tampilan Pencarian Rute 4.2 Pengujian Sistem 4.2.1 Pengujian Sistem dengan Radius 4 km 4.2.2 Pengujian Sistem dengan Radius 5 km 4.2.3 Pengujian Sistem dengan Radius 7 km
33 33 36 53 55 59 60 61 63
Kesimpulan Dan Saran 5.1 Kesimpulan 5.2 Saran
66 66
Daftar Pustaka
67
LAMPIRAN A: Listing Program
A-1
Universitas Sumatera Utara
DAFTAR TABEL
Halaman 3.1 3.2 4.1 4.2 4.3 4.4 4.5 4.6
Dokumentasi Naratif Use Case Lihat Peta Daerah Belawan Dokumentasi Naratif Use Case Proses Pencarian Rute Daftar Atribut Jalan pada Daerah Belawan Hasil Siklus 1 Daftar Atribut Jalan yang Telah Diupdate Hasil Pengujian Sistem dengan Nilai Inputan Radius 4 km Hasil Pengujian Sistem dengan Nilai Inputan Radius 5 km Hasil Pengujian Sistem dengan Nilai Inputan Radius 7 km
24 26 35 49 51 60 62 63
Universitas Sumatera Utara
DAFTAR GAMBAR
Halaman 2.1 2.2 2.3 2.4 2.5 2.6 2.7 3.1 3.2
Tsunami saat Menerjang Daratan Graph dengan 4 verteks dan 5 edges Graph berarah dan berbobot Graph tidak berarah dan berbobot Graph berarah dan tidak berbobot Graph tidak berarah dan tidak berbobot Flowchart Ant Colony System Diagram Ishikawa untuk Analisis Permasalah Sistem Use Case Diagram Sistem Penentuan Rute Terpendek Jalur Evakuasi Tsunami 3.3 Activity Diagram Tampil Peta Belawan 3.4 Activity Diagram Pencarian Rute 3.5 Sequence Diagram Tampil Peta Belawan 3.6 Sequence Diagram Pencarian Rute 3.7 Rancangan Antarmuka Tampil Peta Belawan 3.8 Rancangan Antarmuka Pencarian Rute 4.1 Tampilan Titik t95 pada Peta Belawan 4.2 Tampilan Peta Belawan 4.3 Detail Keterangan Legenda 4.4 Keterangan Komponen Legenda pada Peta 4.5 Tampilan Detail Legenda dan Detail Komponen Legenda 4.6 Tampilan Pencarian Rute 4.7 Titik Acuan yang Berada di Radius Tsunami 4.8 Tampilan Message Box Rute Ditemukan 4.9 Rute Terpendek Ditampilkan pada Peta Daerah Belawan 4.10 Message Box Konfirmasi Pencarian Ulang 4.11 Informasi Rute 4.12 Message Box Informasi Kompoen Rute Terpendek 4.13 Informasi Komponen Rute Terpendek Ditampilkan 4.14 Hasil Pencarian Rute Kawasan t95 pada Radius 4 km 4.15 Hasil Pencarian Rute Kawasan t151 pada Radius 5 km 4.16 Hasil Pencarian Rute Kawasan pada Radius 7 km
9 10 11 11 11 12 17 22 24 25 27 28 29 30 32 34 53 54 54 55 55 56 56 57 57 57 58 58 61 62 65
Universitas Sumatera Utara
