1
IMPLEMENTASI ALGORITMA DIJKSTRA UNTUK PENCARIAN RUTE TERPENDEK MENUJU PELABUHAN BELAWAN BERBASIS SISTEM INFORMASI GEOGRAFIS
SKRIPSI
DEFI RAKHMAWATI 091421023
PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2013
2 PERSETUJUAN
Judul
Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas
: IMPLEMENTASI ALGORITMA DIJKSTRA UNTUK PENCARIAN RUTE TERPENDEK MENUJU PELABUHAN BELAWAN BERBASIS SISTEM INFORMASI GEOGRAFIS : SKRIPSI : DEFI RAKHMAWATI : 091421023 : EKSTENSI S1 ILMU KOMPUTER : ILMU KOMPUTER : ILMU KOMPUTER DAN TEKNOLOGI INFORMASI Diluluskan di Medan,
Komisi Pembimbing
2014
:
Pembimbing 2
Pembimbing 1
Drs. Marihat Situmorang, M. Kom 196312141989031001
Drs. Agus Salim Harahap, M.Si NIP. NIP. 195408281981031004
Diketahui/Disetujui oleh Departemen Ilmu Komputer FASILKOM-TI USU Ketua,
Drs. Poltak Sihombing, M. Kom 196203171991031001
3 PERNYATAAN
IMPLEMENTASI ALGORITMA DIJKSTRA UNTUK PENCARIAN RUTE TERPENDEK MENUJU PELABUHAN BELAWAN BERBASIS SISTEM INFORMASI GEOGRAFIS SKRIPSI
Saya mengakui bahwa skripsi ini adalah hasil karya saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing – masing disebutkan sumbernya.
Medan,
Defi Rakhmawati 091421023
2014
4 PENGHARGAAN
Alhamdulillah, puji syukur penulis panjatkan kehadirat Allah SWT, yang telah memberikan rahmat dan ridho-Nya, sehingga saya dapat menyelesaikan penyusunan skripsi ini, sebagai syarat untuk memperoleh gelar Sarjana Komputer, Program Studi Ekstensi S1 Ilmu Komputer Universitas Sumatera Utara. Shalawat dan Salam saya hadiahkan kepada Nabi Besar Muhammad SAW. Ucapan terima kasih saya sampaikan kepada Bapak Drs. Agus Salim Harahap, M.Si sebagai Dosen Pembimbing I dan Bapak Drs. Marihat Situmorang, M. Kom sebagai Dosen Pembimbing II atas bimbingan, saran dan masukkan kepada penulis untuk menyelesaikan dan menyempurnakan skripsi ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Program Studi Ekstensi S1 Ilmu Komputer, Bapak Drs. Poltak Sihombing, M. Kom dan Ibu Maya Silvi Lydia, B.Sc, M.Sc. Dekan dan Pembantu Dekan Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara, semua dosen, pegawai/staf Program Studi Ekstensi S1 Ilmu Komputer USU. Terimakasih yang sebesarnya kepada kedua Orang Tua dan keluarga saya atas dukungannya baik materil maupun spiritual. Terimakasih juga kepada rekan – rekan kerja di PT. Pelabuhan Indonesia I (Persero) serta seluruh teman – teman yang tidak dapat saya sebutkan semuanya. Saya menyadari bahwa skripsi ini masih jauh dari kesempurnaan. Oleh karena itu, saya menerima saran dan kritik yang bersifat membangun demi kesempurnaan skripsi ini. Semoga skripsi ini dapat bermanfaat bagi yang memerlukan.
5
ABSTRAK
Pelabuhan Belawan terletak di kota Medan, Sumatera Utara, Indonesia. Saat ini Pelabuhan Belawan merupakan Pelabuhan tersibuk di Sumatera. Lalu lintas transportasi, logistik maupun aktivitas perdangangan sangat ramai menuju Pelabuhan Belawan sehingga Sistem Informasi Georafis sangat diperlukan. Sistem Informasi Geografis ini dirancang berbasis web dengan layer peta yang direpresentasikan oleh Mapguide Open Source 2.2.0.5703. Digitasi peta menggunakan Quantun GIS 1.8.0-2. Untuk database peta menggunakan PostgreSQL 8.4.16-1 dan Postgis 1.5.5-1. Teknik pencarian rute terpendek menggunakan algoritma Dijkstra, serta diimplementasikan ke halaman web melalui PHP dan Java Script. Adapun penggunaan algoritma Dijkstra karena algoritma ini dipastikan memiliki solusi terbaik dalam menentukan rute terpendek karena algoritma Dijkstra akan membaca seluruh lintasan dan hanya memilih lintasan dengan bobot terkecil sebagai rute terpendeknya. Untuk pengujian dilakukan pencarian rute terpendek dengan melakukan input titik asal dan titik tujuan dimana untuk titik adalah adalah Stasiun Kereta Api Medan dan titik tujuan adalah Terminal Penumpang di Pelabuhan Belawan. Kemudian dari hasil pengujian tersebut menunjukkan bahwa sistem berhasil menampilkan rute terpendek, nama jalan dan jarak yang ditempuh untuk menuju Terminal Penumpang di Pelabuhan Belawan yang divisualisasikan dalam peta kota Medan. Dengan demikian implementasi algoritma Dijkstra pada sistem informasi geografis untuk menentukan rute terpendek menuju Pelabuhan Belawan ini layak digunakan karena berhasil menampilkan rute terpendek menggunakan algoritma Dijkstra.
Kata Kunci : Sistem Informasi Geografis, Algoritma Dijkstra, Rute Terpendek, Pelabuhan Belawan.
6 IMPLEMENTATION OF DIJKSTRA ALGORITHM TO DETERMINE A SHORTEST PATH TO PORT OF BELAWAN BASED ON GEOGRAPHIC INFORMATION SYSTEM
ABSTRACT
Belawan is a port in Medan, North of Sumatra, Indonesia. Belawan is Indonesia's busiest port of Sumatera Island. The traffic of logistics and trade activity in Belawan port is very crowded it means people need Geographic Information System. Geographic Information System created by web basis through map layers which is represented by Mapguide Open Source 2.2.0.5703. Map digitation by Quantun GIS 1.8.0-2. PostgreSQL 8.4.16-1 and Postgis 1.5.5-1 is used for database of map. Dijkstra method is used as the shortest route searching technique. It will be implemented to web page through PHP and Java Script. The author has chosen algorithm Dijkstra because this algorithm has a best solution to find a shortest path because it will find the path with lowest cost as the shortest path. For the testing to find a shortest path add start point and end point which is start point is Stasiun Kereta Api Medan and the end point is Port of Belawan. The result is the shortest path found and represented with routing of shorthest path, name of road and the distance to go to Port of Belawan that visualization in Map of Medan City. Then this System Information Geographic is useful because it can representation the shortest path by using Dijkstra Algorithm.
Keywords : Geographic Information System, Algorithm Dijkstra, Shortest Path, Port of Belawan.
7 DAFTAR ISI
Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Gambar Daftar Tabel Bab I Pendahuluan 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Lokasi dan Waktu Penelitian 1.7 Metode Penelitian 1.4 Sistematika Penulisan Bab II Landasan Teori 2.1 Sistem Informasi Geografis 2.1.1 Sistem 2.1.2 Informasi 2.1.3 Sistem Informasi 2.1.4 Geografi 2.1.5 Sistem Informasi Geografis 2.1.5.1 Subsistem Sistem Informasi Geografis 2.1.5.2 Komponen Sistem Informasi Geografis 2.2 Peta 2.2.1 Proyeksi Peta 2.2.2 Proyeksi Universal Transverse Mercator (UTM) 2.3 Algoritma Dijkstra 2.3.1 Definisi Algoritma Dijkstra 2.3.2 Pseudo Code Algoritma Dijkstra 2.3.3 Penelitian Terdahulu Algoritma Dijkstra Bab III Analisis dan Perancangan Sistem 3.1 Analisis Sistem 3.1.1 Analisis Masalah 3.1.2 Analisis dan Perancangan SIG 3.2 Analisis Kebutuhan 3.2.1 Analisis Kebutuhan Fungsional
ii iii iv v vi vii ix x 1 1 2 3 3 3 4 4 5 6 6 6 6 7 7 7 8 9 11 11 12 14 14 16 16 20 20 20 21 22 22
8 3.2.2 Analisis Kebutuhan Non Fungsional 3.3 Pemodelan Sistem 3.3.1 Model Proses DFD (Data Flow Diagram) 3.3.1.1 DFD (Data Flow Diagram) Level 0 3.3.1.2 DFD (Data Flow Diagram) Level 1 3.3.1.3 DFD (Data Flow Diagram) Level 2 Proses 1 3.3.2 Model Data (Entity Relationship Diagram) 3.4 Flowchart 3.4.1 Flowchart Algoritma Dijkstra Dalam Mencari Rute Terpendek 3.5 Perancangan Database 3.6 Perancangan Antarmuka 3.6.1 Perancangan Antarmuka Situs Pengunjung Bab IV Implementasi Sistem 4.1 Implementasi 4.2 Implementasi Algoritma Dijkstra 4.3 Tampilan Sistem Informasi Geografis 4.3 Pengujian Sistem 4.4 Pengujian Black Box (Black Box Testing) Bab V Kesimpulan dan Saran Daftar Pustaka Lampiran Curriculum Vitae
23 23 23 23 24 25 26 26 26 28 35 35 37 37 37 48 52 53 54 55 57 A-1
9 DAFTAR GAMBAR
Halaman 2.1.5.1 2.1.5.2 2.2.1a 2.2.1b 2.2.2a 2.2.2b 2.3.1 3.1.1 3.1.2 3.3.1.1 3.3.1.2 3.3.1.3 3.3.2 3.4.1 3.6.1 4.2a 4.2b 4.2c 4.2d 4.2e 4.2f 4.2g 4.2h 4.3a 4.3b 4.3c 4.3d 4.3e 4.3f 4.3g
Ilustrasi Subsistem SIG Pelabuhan Belawan Proyeksi Peta Jenis Proyeksi Peta Peta Dunia Berproyeksi UTM Peta Indonesia Berproyeksi UTM Graf Diagram Ishikawa Untuk Analisis Masalah Gambaran Umum Perancangan SIG DFD Level 0 DFD Level 1 DFD Level 2 Proses 1 Entity Relationship Diagram Flowchart Algoritma Dijkstra Perancangan Antarmuka SIG Berbasis Web Representasi Graf Node Terpilih Pada Iterasi ke-1 Node terpilih pada Iterasi ke-2 Node terpilih pada Iterasi ke-3 Node terpilih pada Iterasi ke-4 Node terpilih pada Iterasi ke-5 Node terpilih pada Iterasi ke-6 Node terpilih pada Iterasi ke-7 Tampilan Awal Tampilan Zoom In Tampilan Input Jalan dan Tempat Tampilan Shorthest Path Tampilan Zoom In Shorthest Path Jalur Pendek Tiap - Tiap Jalan Notifikasi Jalur Tidak Ditemukan
8 10 11 11 13 13 15 21 22 24 25 25 26 27 35 38 39 40 41 42 43 44 45 48 49 49 50 51 51 52
10 DAFTAR TABEL
Halaman 2.3.1 3.5a 3.5b 3.5c 3.5d 3.5e 3.5f 3.5g 4.2a 4.2b 4.2c 4.2d 4.2e 4.2f 4.2g 4.5
Perhitungan Dijkstra pada gambar 2.3.1 Bangunan Rincian Tabel Bangunan Jalan Rincian Tabel Jalan Network Database Tabel Bangunan Node Hasil Iterasi Ke-1 Hasil Iterasi Ke-2 Hasil Iterasi Ke-3 Hasil Iterasi Ke-4 Hasil Iterasi Ke-5 Hasil Iterasi Ke-6 Hasil Iterasi Ke-7 Hasil Pengujian Black Box
15 28 28 29 30 32 34 35 39 40 40 41 42 43 44 53
