BAB 2 LANDASAN TEORI
2.1. Geographical Information System (GIS) Geographical Information System (GIS) yang dalam bahasa Indonesia dikenal sebagai Sistem Informasi Geografis (SIG) didefenisikan sebagai sebuah sistem informasi yang digunakan untuk memasukkan, menyimpan, mengambil, memanipulasi, menganalisa, dan menghasilkan data geospasial atau data yang mengacu secara geografis. GIS digunakan dalam rangka mendukung pengambilan keputusan untuk perencanaan dan pengelolaan dari penggunaan lahan, sumber daya alam, lingkungan, transportasi, fasilitas perkotaan, dan rekam administrasi lainnya (Murai, 1999). Komponen utama dari GIS adalah sistem komputer, pengguna, dan data geospasial, seperti ditunjukkan pada Gambar 2.1.
Gambar 2.1. Komponen Utama GIS
Universitas Sumatera Utara
8
Sistem komputer untuk GIS terdiri dari hardware, software dan prosedur yang didesain untuk mendukung pengambilan data, pemrosesan, penganalisaan, pemodelan dan tampilan dari data geospasial. Sumber dari data geospasial adalah peta digital, fotografi udara, gambar satelit, tabel statistikal, dan dokumen terkait lainnya. Data geospasial diklasifikasikan ke dalam data grafik (atau disebut data geometrik) dan atribut (atau disebut data thematik). Data grafik memiliki 3 elemen, yaitu titik (atau disebut node), garis (atau disebut arc) dan area (atau disebut polygon) di salah satu bentuk raster atau vector yang melambangkan geometri dari topologi, ukuran, bentuk, posisi, dan orientasi. Peranan dari user atau pengguna adalah untuk memilih informasi yang berhubungan, menentukan standar penting, mendesain skema penetapan harga efisien, menganalisa keluaran GIS untuk tujuan yang berkaitan, dan merencanakan penerapan. Peralatan penerima GIS berbasis mobile adalah komputer berukuran kecil atau terminal yang bisa menampilkan peta dan informasi lokasi ke pengguna akhir. Komponen hardware termasuk CPU, memori, peralatan penyimpanan, koneksi masukan/keluaran, dan fungsi tampilan atau screen (Tsou, 2004). PC saku, smart phone, tablet PC atau PDA adalah komponen penerima GIS mobile yang terkenal. Komputer notebook juga bisa menjadi penerima GIS mobile apabila dikoneksikan ke GPS dan komponen GIS lainnya. Namun, kebanyakan penerima GIS mobile meminta peralatan hardware berukuran kecil untuk mencapai tujuan portable atau bisa dibawa kemana-mana. Keuntungan lain dari solusi GIS berbasis mobile adalah bahwa kerangka kerja GIS bisa diintegrasikan dengan peralatan GPS yang bisa menyediakan pengukuran geodesi komprehensif dan fungsi navigasi. Dengan keunggulan dan penggabungan dari GPS, internet, dan teknologi komunikasi wireless, GIS berbasis mobile memiliki potensial yang hebat untuk memainkan peran penting dalam bidang akuisisi dan validasi data dan layanan jalur transportasi. Komponen penyedia GIS menyediakan fungsi geospasial untuk banyak location-based system (LBS) termasuk informasi peta, visualisasi peta dan layanaan folder. Google Maps dengan API bisa dikategorikan sebagai provider GIS (Kushwaha & Kushwaha, 2011).
Universitas Sumatera Utara
9
2.2. Algoritma A Star atau A* Algoritma A Star atau A* adalah salah satu algoritma pencarian yang menganalisa input, mengevaluasi sejumlah jalur yang mungkin dilewati dan menghasilkan solusi. Algoritma A* adalah algoritma komputer yang digunakan secara luas dalam graph traversal dan penemuan jalur serta proses perencanaan jalur yang bisa dilewati secara efisien di sekitar titik-titik yang disebut node (Reddy, 2013). Algoritma A* menggabungkan fitur dari pencarian cost dan pencarian heuristik untuk menghitung solusi optimal secara efisien. Karena keakuratan dan kinerjanya, A* digunakan secara luas. Peter Hart, Nils Nilsson, dan Bertram Raphael menemukan algoritma ini pada tahun 1968. Algoritma ini adalah penyempurnaan dari algoritma Edsger Dijkstra. Algoritma A* memperoleh kinerja lebih baik (dalam hal waktu) dengan menggunakan heuristik.
2.2.1. A Star-Pendekatan Heuristik Karakteristik yang menjelaskan algoritma A* adalah pengembangan dari “daftar tertutup” untuk merekam area yang dievaluasi. Daftar tertutup ini adalah sebuah daftar untuk merekam area berdekatan yang sudah dievaluasi, kemudian melakukan perhitungan jarak yang dikunjungi dari “titik awal” dengan jarak diperkirakan ke “titik tujuan” (Reddy, 2013). Daftar terbuka yang sering disebut “open list” adalah dafar semua lokasi secara langsung berdekatan dengan area yang sudah dieksplor dan dievaluasi (daftar tertutup). Daftar tertutup adalah rekaman seluruh lokasi yang sudah dieksplor dan dievaluasi dengan algoritma A*.
Universitas Sumatera Utara
10
2.2.2. Cara Kerja Algoritma A* Contoh dari implementasi algoritma A* adalah Disneyland Paris di bawah ini (Reddy, 2013) seperti pada Gambar 2.2.
Gambar 2.2. Disneyland Paris Keterangan dari gambar di atas adalah: -
Pintu gerbang adalah node inisial atau asal.
-
Magic Kingdom adalah tujuan akhir.
-
Ada 2 jalur yang bisa diambil dan ditandai dengan node.
-
Setiap node akan memiliki fungsi f(x), g(x), dan h(x).
-
Akan ditunjukkan pada setiap node dan diindikasikan node selanjutnya yang akan dikunjungi berdasarkan cost jalur terendah. Contohnya, apabila seseorang sedang berada di pintu gerbang Disneyland
Paris dan dia hendak menuju Magic Kingdom. Ada dua jalur berbeda yang tumpang tindih di tengah. Dua pilihan ini adalah: -
Yang berwarna ungu dengan yang tertinggi f(x).
-
Yang berwarna hijau dengan nilai lebih rendah f(x). Seperti yang disebutkan sebelumnya, A* akan memilih jalur dengan f(x)
terendah. Ketika node tujuan dimunculkan di daftar prioritas, lalu pencarian selesai.
Universitas Sumatera Utara
11
Algoritma A* menggunakan path paling rendah ke node yang membuatnya sebagai algoritma pencarian nilai pertama yang terbaik atau best first search. Menggunakan rumus f(x) = g(x) + h(x), dimana: -
g(x) adalah jarak total dari posisi asal ke lokasi sekarang.
-
h(x) adalah fungsi heuristik yang digunakan untuk memperkirakan jarak dari lokasi sekarang ke lokasi tujuan. Fungsi ini jelas berbeda karena ini adalah perkiraan semata dibandingkan dengan nilai aslinya. Semakin tinggi keakuratan heuristik, semakin cepat dan bagus lokasi tujuan ditemukan dan dengan tingkat keakuratan yang lebih bagus. Fungi f(x) = g(x) + h(x) ini adalah perkiraan saat ini dari jarak terdekat ke tujuan.
2.2.3. Pseudo Code dari Algoritma A* Berikut ini adalah pseudo code dari algoritma A* (Reddy, 2013): function A*(start,goal) 1
closed = empty set
2
q = makequeue(path(start))
3
while q is not empty do
4
p = removefirst(q)
5
x = lastnode(p)
6
if x in closed then
7
end if
8
if x = goal then
9
return p
10
end if
11
add x to closed
12
for y successor(x) do
13
enqueue(q, p, y)
14
end for
15
return Failure
16
end while
17 end function Gambar 2.3. Algoritma A* (Reddy, 2013)
Universitas Sumatera Utara
12
2.3. Global Positioning System (GPS ) Android GPS
adalah alat yang bisa menyediakan informasi koordinat berbasis geografis
(ketinggian X, Y, dan Z) dan mengirimnya ke penerima GIS mobile. GPS menggunakan sinyal satelit untuk menghitung posisi dari unit GPS. Aplikasi GIS membutuhkan GPS dalam area perkotaan untuk memperoleh hasil yang memuaskan (Tsou, 2004). Data geospasial, yaitu latitude (garis lintang) dan longitude (garis bujur) diatur oleh lapisan GIS pada aplikasi GIS mobile (Tsou, 2004). Layanan pengumpulan lokasi dalam rangka mendapatkan latitude dan longitude untuk pengguna dibutuhkan. Komponen ini bisa diakses secara langsung seperti melalui penerima GPS di smart phone. Module data mengontrol akses data dalam smart phone Andoid. Ini memungkinkan pengaksesan data dan juga untuk mengambil informasi lokasi menggunakan GPS (Kushwaha & Kushwaha, 2011).
2.4. Graph Graph didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertices atau nodes) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul (Munir, 2005). Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf maka graf digolongkan menjadi dua jenis: 1. Graf sederhana (simple graph) Graf yang tidak mengandung gelang maupun sisi ganda dinamakan graf sederhana. 2. Graf tak sederhana (unsimple graph) Graf yang mengandung sisi ganda atau gelang dinamakan graf tak sederhana (unsimple
graph).
Contoh
dari
graf
tak
sederhana
adalah
graf
ganda (multigraph). Graf ganda adalah graf yang mengandung sisi ganda.
Universitas Sumatera Utara
13
Contoh dari tiga buah graph (Fitria, 2005), yaitu G1, G2, dan G3 dideskripsikan pada Gambar 2.4.
Gambar 2.4. (G1) Graph Sederhana, (G2) Multigraph, dan (G3) Multigraph
Keterangan dari gambar di atas adalah sebagai berikut: -
G1 adalah graph dengan himpunan simpul V dan himpunan sisi E adalah: V = {1, 2, 3, 4} E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)}
-
G2 adalah graph dengan himpunan simpul V dan himpunan sisi E adalah: V = {1, 2, 3, 4} E = {(1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4)} = {e1, e2, e3, e4, e5, e6, e7}
-
G3 adalah graph dengan himpunan simpul V dan himpunan sisi E adalah: V = {1, 2, 3, 4} E = {(1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3)} = {e1, e2, e3, e4, e5, e6, e7, e8}
2.4.1. Lintasaan Terpendek Masalah lintasan terpendek atau shortest path untuk menemukan nilai travel minimum satu atau lebih titik asal ke satu atau lebih tujuan melalui jaringan terhubung. Ini adalah masalah penting karena cakupan yang luas untuk pengaplikasiannya di bidang transportasi. (Lim & Kim, 2005).
Universitas Sumatera Utara
14
Jaringan transportasi bisa dirancang dalam bentuk graph yang terdiri dari titiktitik dan sisi yang menghubungkan titik-titik. Algoritma berbeda-beda telah diajukan untuk menemukan jalur terpendek antara 2 simpul di graph. Semua algoritma yang diajukan berdasarkan graph berbobot (Gutenschwager et al., 2012). Contoh graph untuk jarak terpendek adalah jaringan yang terdiri dari sekumpulan N dari n simpul dan sekumpulan E dari e sisi (arcs). Setiap menghubungkan dua simpul (i,j), nilai dari sebuah sisi ditandai sebagai d(i,j) untuk koneksi langsung yang diberikan, sedangkan untuk semua koneksi lain (melalui simpul lain) d(i,j) menandai jarak terdekat. Contoh digraph bernilai, untuk menentukan jalur terpendek berararah dari s menuju t (Princeton, 2013). Nilai dari jalur = total nilai sisi dalam jalur dicontohkan seperti pada Gambar 2.5.
Gambar 2.5. Digraph untuk Lintasan Terpendek
2.5. Penelitian Terdahulu Penelitian tentang pencarian shortest path (jalur terpendek) telah banyak dilakukan dengan beberapa metode. Pergerakan objek berdasarkan lokasi (location-based object movement) juga sudah banyak dilakukan dengan metode yang berbeda-beda pula. Pada dasarnya, gabungan shortest path dan pergerakan objek berdasarkan lokasi ini digunakan untuk kepentingan transportasi. Pada tahun 2004, Tsou, M. melakukan penelitian untuk melacak keberadaan objek berdasarkan lokasi dengan cara sederhana. Penulis tersebut menggunakan Mobile GIS Software. Namun, pada penelitian ini tidak disertakan penelitian tentang shortest path.
Universitas Sumatera Utara
15
Selanjutnya pada tahun 2010, Siboro, R. melakukan penelitan untuk menentukan jalur terpendek dengan metode algoritma Genetika. Penulis dalam hal ini tidak mengikutsertakan penelitian mengenai pergerakan objek berdasarkan lokasi (location-based object movement). Selanjutnya, pada tahun 2010, Kurniawan, I. juga melakukan penelitian untuk menentukan jalur terpendek dengan metode algoritma Dijkstra. Seperti yang lain, penulis hanya membatasi penelitian sampai pada penentuan jalur terpendek, tanpa meneliti tentang pergerakan objek berdasarkan lokasi (location-based object movement). Pada tahun 2011, Kushwaha A. & Kushwaha V. melakukan penelitian untuk pergerakan objek berdasarkan lokasi dengan metode LBS pada Android Mobile. Metode ini juga membatasi penelitian sampai pada pelacakan objek saja. Dalam penelitian ini, tidak ditemukan penentuan shortest path. Pada tahun 2014, Hutabarat, J. menggunakan metode Dijkstra untuk menentukan rute terpendek berbasis mobile GIS dengan studi kasus Universitas Sumatera Utara (USU). Penulis merancang aplikasi ini untuk sistem operasi Android berbasis mobile. Pada metode yang diterapkan oleh penulis tersebut, tidak disertai pembahasan mengenai pergerakan objek berdasarkan lokasi (location-based object movement). Rangkuman dari penelitian terdahulu dapat dilihat pada Tabel 2.1.
Tabel 2.1. Penelitian Terdahulu Metode yang Digunakan No.
Peneliti
Tahun
Shortest Path
Object Movement
1
Tsou, M.
2004
-
Mobile GIS Software
2
Siboro, R.
2010
Genetika
-
3
Kurniawan, I.
2010
Dijkstra
-
4
Kushwaha A. & 2011
-
Location
Based
Services
(LBS)
Kushwaha V.
Android Mobile 5
Hutabarat, J.
2014
Dijkstra
-
Universitas Sumatera Utara
