BAB II
TINJAUAN PUSTAKA
2.1 Pengertian Sistem Informasi Geografis
Sistem Informasi Geografis atau Geographic Information Sistem (GIS) merupakan sistem komputer yang digunakan untuk memasukkan, menyimpan, memeriksa, mengintegrasikan,
memanipulasi,
menganalisis,
dan
menampilkan
data-data
berhubungan dengan posisi-posisinya di muka bumi. Teknologi SIG mengintegrasikan operasi-operasi umum database, seperti query dan analisis statistik, dengan kemampuan visualisasi dan analisis yang unik yang dimiliki oleh pemetaan. Kemampuan inilah yang membedakan SIG dengan Sistem Informasi lainnya yang membuatnya menjadi berguna berbagai kalangan untuk menjelaskan kejadian, merencanakan strategi, dan memprediksi apa yang terjadi.
Saat ini SIG sudah dimanfaatkan oleh berbagai disiplin ilmu seperti ilmu kesehatan, ilmu ekonomi, ilmu lingkungan, ilmu pertanian dan lain sebagainya. Beberapa aplikasi dari SIG antara lain adalah untuk perencana fasilitas kota, pengelolaan sumber daya alam, jaringan telekomunikasi dan juga untuk manajemen transportasi.
Sebuah peta biasanya terdiri dari kombinasi antara data vector dan data raster. Data vector merepresentasikan setiap fitur ke dalam baris dalam tabel dan bentuk fitur didefinisikan dengan titik x, y dalam ruang. fitur-fitur dapat memiliki lokasi atau titik, garis, dan polygon yang bisa digunakan untuk menampilkan informasi pada peta. Titik bisa digunakan sebagai lokasi sebuah kota atau posisi tower radio. Garis bisa digunakan untuk menunjukkan route suatu perjalanan atau menggambarkan boundary dan polygon bisa digunakan untuk menggambarkan sebuah danau atau sebuah negara pada peta dunia. Sedangkan data raster merupakan kumpulan pixel (picture element) yang membentuk suatu objek. Suatu data raster tersusun dalam baris dan kolom, menyimpan informasi spasial dalam sebuah grid atau matrik. Tiap pixel mempunyai
Universitas Sumatera Utara
nilai, dan nilai ini dapat merepresentasikan sesuatu seperti ketinggian, jenis tanah, penggunaan lahan, dan kemiringan dalam suatu nilai digital.
Gambar 2.1 Peta Raster dan Peta Vektor
2.2 Teori Graph
Graph adalah kumpulan simpul (nodes) yang dihubungkan satu sama lain melalui sisi/busur (edges) [8]. Suatu Graf G terdiri dari dua himpunan yaitu himpunan V dan himpunan E. 1.
Verteks / Node (simpul) : V = Himpunan simpul yang terbatas dan tidak kosong
2.
Edge (sisi/busur) : E =Himpunan busur yang menghubungkan sepasang simpul
Dapat dikatakan graph adalah kumpulan dari simpul-simpul yang dihubungkan oleh sisi-sisi. Menurut arah dan bobotnya, graph dibagi menjadi empat bagian yaitu:
1.
Graph berarah dan berbobot adalah tiap busur mempunyai anak panah dan bobot.
Gambar berikut menunjukkan graf berarah dan berbobot yang terdiri dari tujuh titik yaitu titik A, B, C, D, E, F, G. Titik menunjukkan arah ke titik B dan titik C, titik B
Universitas Sumatera Utara
menunjukkan arah ke titik D dan titik C, dan seterusnya. Bobot antar titik A dan B pun telah diketahui.
Gambar 2.2 Graph Berarah dan Berbobot
2.
Graph tidak berarah dan berbobot adalah tiap busur tidak mempunyai anak panah
tetapi mempunyai bobot. Gambar berikut menunjukkan graph tidak berarah dan berbobot, terdiri dari tujuh titik yaitu titik A, B, C, D, E, F, G. Titik A tidak menunjukkan arah ke titik B atau C, namun bobot antara titik A dan titik B telah diketahui, begitu juga dengan titik yang lain.
Gambar 2.3 Graph tidak berarah dan berbobot
3.
Graph berarah dan tidak berbobot adalah tiap busur tidak mempunyai anak panah
dan tidak berbobot. Gambar berikut menunjukkan graph berarah dan tidak berbobot.
Gambar 2.4 Graph berarah dan tidak berbobot
4.
Graph tidak berarah dan tidak berbobot adalah tiap busur tidak mempunyai anak
panah dan tidak berbobot. Gambar berikut menunjukkan graph tidak berarah dan tidak berbobot.
Universitas Sumatera Utara
Gambar 2.5 Graph tidak berarah dan tidak berbobot.
2.3 Algoritma Dijkstra
Pencarian rute terpendek termasuk kedalam materi teori graf. Algoritma yang sangat terkenal untuk menyelesaikan persoalan ini adalah algoritma Djikstra. Algoritma ini ditemukan oleh seorang ilmuwan komputer berkebangsaan belanda yang bernama Edsger Dijkstra. Algoritma Dijkstra digunakan untuk menetukan jarak terpendek pada sebuah graf berarah. Contoh penerapan algoritma Djikstra adalah lintasan terpendek yang menghubungkan dua lokasi,tempat berlainan tertentu (single-source singledestination shortest path problem). Cara kerja algoritma Djikstra adalah memakai strategi greedy dimana pada setiap langkah dipilih sisi dengan bobot terkecil yang menghubungkan sebuah simpul yang sudah terpilih dengan simpul lain yang belum terpilih. Algoritma Djikstra membutuhkan parameter tempat asal dan tempat tujuan. Hasil akhir algoritma ini adalah jarak terpendek dari tempat asal ke tempat tujuan beserta rutenya. Jika menggunakan algoritma Djikstra untuk menentukan jalur terpendek dari suatu graph, maka akan menemukan jalur yang terbaik karena pada waktu penentuan jalur yang akan dipilih akan dianalisis bobot dari node yang belum terpilih, lalu dipilih node dengan bobot terkecil. Algoritma Djikstra mencari jarak terpendek dari node asal ke node terdekatnya, kemudian ke node kedua, dan seterusnya.
Ada beberapa kasus pencarian lintasan terpendek yang diselesaikan menggunakan algoritma Djikstra, yaitu:
1. Pencarian lintasan terpendek antara dua buah simpul tertentu (a pair shortest path) 2. Pencarian lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single source shortest path)
Universitas Sumatera Utara
3. Pencarian lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path)
Dalam penelitian ini penulis menggunakan model kasus pencarian lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (Intermediate Shortest Path). Jalur terpendek adalah suatu jaringan pengarahan perjalanan dimana seseorang pengarah jalan ingin menentukan jalur terpendek antara dua lokasi berdasarkan beberapa jalur alternatif yang tersedia, dimana titik tujuan hanya satu. Gambar 8.5 menunjukkan suatu graf A, B, C, D, E, F yang berarah dan berbobot. 10
B
20
C 25
20
11
A
5
16
8
F
6 D
17
E
Gambar 2.6Graph A, B, C, D, E, F
Pada gambar diatas, misalkan dari lokasi A ingin menuju ke ke lokasi lain. Dalam kasus ini kita bisa menggunakan rumus yang memudahkan proses pencarian, hanya dengan empat rumus ini kita bisa dengan mudah mencari jarak terpendek dari A ke lokasi lain. Berikut rumus tersebut dan langkah pencarian jalur terpendek dari A ke lokasi lain : 1. Tandai titik asal dengan 0/2. Tandai titik lainnya dengan ∞/3. Hijaukan titik hitam dengan nilai biru terkecil 4. Update seluruh titik yang dituju oleh titik yang tadi dihijaukan jika nilai biru yang terjadi lebih kecil dari sebelumnya. Rumus 1 dan 2 adalah untuk memberikan inisial dari titik-titik yang ada sedangkan rumus 3 dan 4 adalah proses selanjutnya setelah pemberian inisial yang akan diulang beberapa kali untuk mendapatkan hasil yang terbaik. Berikut saya tampilkan langkahlangkah pencarian dari awal sampai mendapatkan hasil yang ditunjukkan pada gambar 2.7.
Universitas Sumatera Utara
10
20 /A
∞ /20
B
C 25
20
0/-
11
A
F
16
5 ∞ /-
8 /A
8
∞ /-
6 D
17
B
20
E
10
20 /A
13 /D C 25
20
0/-
∞ /11
A
25 /D
8 /A
8
F
16
5
6 17
D
E
10
20 /A
13 /D B 0/-
C
20
20
25
A
11
8
16
5
38 /C F
25 /D
8 /A
6 D
17
E
10
20 /A
13 /D B 0/-
C
20
20
25
A
11
8
16
5
30 /B F
25 /D
8 /A
6 D
17
B
20
E
10
20 /A
13 /D
0/-
C
20
25
A
11
8
16
5
30 /B F
25 /D
8 /A
6 D
17
E
10
20 /A
13 /D B 0/-
C
20
20
25
A
11
8
16
5
30 /B F
25 /D
8 /A
6 D
17
E
Gambar 2.7 Contoh Penyelesaian Dijkstra
Universitas Sumatera Utara
Setelah melakukan proses dengan menggunakan rumus tersebut maka didapatlah hasil sebagai berikut : A-B
= 20
A-C
= AD + DC = 13
A-D
=8
A-E
= AD + DE = 25
A-F
= AB + BF = 30
2.4 Tinjauan Penelitian Terdahulu
Dari hasil penelitian Novianty [4] mengenai perancangan prototipe pencarian rute terpendek pada handphone berbasiskan location based services dengan menggunakan algoritma djikstra diperoleh bahwa algoritma Djikstra memiliki waktu yang lebih cepat dalam mencari rute terpendek dibandingkan dengan algoritma Bellman Ford. Algoritma Bellman-Ford menghitung jarak terpendek (dari satu sumber) pada sebuah diagraf berbobot. Maksudnya dari satu sumber ialah bahwa ia menghitung semua jarak terpendek yang berawal dari satu titik node. Algoritma Dijkstra dapat lebih cepat mencari hal yang sama dengan syarat tidak ada sisi (edge) yang berbobot negatif. Maka Algoritma Bellman-Ford hanya digunakan jika ada sisi berbobot negatif. Dari hasil penelitian Faizah [3] mengenai pencarian jalur tercepat untuk transportasi bus transjakarta menggunakan algoritma djikstra diperoleh bahwa Algoritma Djikstra efektif untuk mencari jalur tercepat.
Dari hasil penelitian Syahriza [6] mengenai perbandingan algoritma Greedy dan Djikstra untuk menentukan lintasan terpendek, algoritma Greedy menghasilkan jarak yang lebih besar, sedangkan pada algortitma Djikstra diperoleh hasil yang lebih kecil. Algoritma Greedy tidak beroperasi secara menyeluruh terhadap semua alternatif yang ada, sehingga lintasan terpendek hanya diperoleh dari verteks asal hingga verteks tujuan, sedangkan algoritma Djikstra beroperasi secara menyeluruh terhadap semua alternatif fungsi yang ada, sehingga lintasan terpendek tidak hanya diperoleh dari node
Universitas Sumatera Utara
sumber ke node tujuan saja, akan tetapi lintasan terpendek dapat diperoleh dari semua node.
2.5 Pengenalan Google Maps
Google Maps adalah layanan gratis yang diberikan oleh Google dan sangat popular. Google Maps adalah suatu peta dunia yang dapat kita gunakan untuk melihat suatu daerah. Dengan kata lain, Google Maps merupakan suatu peta yang dapat dilihat dengan menggunakan suatu browser. Kita dapat menambahkan fitur Google Maps dalam web yang telah kita buat atau pada blog kita yang berbayar maupun gratis sekalipun dengan Google Maps API. Google Maps API adalah suatu library yang berbentuk JavaScript.
Gambar 2.8 Alur Proses Google Maps
Pada gambar 2.6 interaksi antara klien dengan server berdasarkan skenario request dan respon. Admin akan melakukan pengolahan map, berdasarkan kebutuhan. Kemudian file map script yang bersangkutan akan dikirim atau ditanam di web server yang kemudian akan menjadi bahan informasi aplilkasi website bagi user yang akan menggunakan aplikasi penentuan rute terpendek menuju sebuah tempat wisata di Kota Banda Aceh.
Universitas Sumatera Utara
2.6 Routing Module
Routing dapat digunakan untuk menyelesaikan masalah pencarian jalur terpendek (Shortest Path) dan juga Travelling Salesman Problem (TSP). Alasan Penggunaan modul routing ini karena pada aplikasi Web GIS ini terdapat sebuiah fungsi untuk menyelesaikan pencarian jalur terpendek menggunakan algoritma Dijkstra.
Gambar 2.9 Alur Proses Routing Map
Pada gambar 2.7 alur proses sebuah routing rute terpendek adalah dengan membuat titik koordinat X dan Y untuk penempatan sebuah titik lokasi
yang
kemudian akan diinputkan kedalam database aplikasi website yang sudah terhubung dengan Google Maps sehinngga akan menjadi sebuah informasi routing untuk penggunaan aplikasi website penentu rute terpendek menuju sebuah tempat wisata di Kota Banda Aceh.
Universitas Sumatera Utara
2.7 Internet Internet adalah sebuah jaringan komputer yang terdiri dari berbagai macam ukuran jaringan komputer diseluruh dunia mulai dari sebuah PC (Personal Computer), jaringan berskala kecil sampai pada jaringan berskala besar (Munawaroh, 2007). Semula Internet hanya sebuah jaringan kecil yang dibuat dalam pemakaian pada Departemen Pertahanan Amerika Serikat. Tetapi kemudian untuk alasan riset maka jaringan itu diperluas dengan dihubungkan dengan jaringan-jaringan perguruan tinggi yang ada lama kelamaan jaringan tersebut terus membesar sehingga sampai sekarang ini. Komponen-komponen Internet adalah sebagai berikut :
a. World Wide Web (WWW) merupakan bagian dari internet yang terdiri dari kumpulan dokumen-dokumen yang disimpan pada komputer-komputer di seluruh dunia. b. Web Page merupakan dokumen elektronik yang terletak pada jaringan Internet dimana web pages disimpan padaWeb server dan membuat web pages tersebut dapat di lihat orang lain. c. Web Site merupakan kumpulan dari web pages yang saling berhubungan dan dapat di akses secara elektronik.
2.8 Aplikasi Web
Pada awalnya aplikasi Web dibangun hanya dengan menggunakan bahasa yang disebut HTML (HyperText Markup Language) dan protocol yang digunakan dinamakan HTTP (HyperText Transfer Protocol). Pada perkembangan berikut, sejumlah skrip dan objek dikembangkan untuk memperluas kemampuan HTML, antara lain yaitu PHP. Aplikasi Web sendiri dapat dibagi menjadi dua bagian, yaitu Web statis dan Web dinamis
Web statis dibentuk dengan menggunakan HTML saja. Kekurangan aplikasi seperti ini terletak pada keharusan untuk memelihara program secara terus-menerus
Universitas Sumatera Utara
untuk mengikuti setiap perubahan yang terjadi. Kelemahan ini diatasi dengan model aplikasi Web dinamis.
Dengan memperluas kemampuan HTML, yakni dengan menggunakan perangkat lunak tambahan, perubahan informasi dalam halaman – halaman Web dapat ditangani melalui perubahan data, bukan melalui perubahan program. Sebagai implementasinya, aplikasi Web dikoneksikan ke basis data. Dengan demikian perubahan informasi dapat dilakukan oleh operator atau yang bertanggung jawab terhadap kemutakhiran data, dan tidak menjadi tanggung jawab pemograman atau webmaster.
Universitas Sumatera Utara
