BAB 2 LANDASAN TEORI
2.1 Definisi Ambulans Pada Kamus Besar Bahasa Indonesia (KBBI) online versi 1.4 (2015) am·bu·lans n adalah kendaraan (mobil dan sebagainya) yang dilengkapi peralatan medis untuk mengangkut orang sakit atau korban kecelakaan. Pada Peraturan Pemerintah Republik Indonesia nomor 43 tahun 1993 tentang prasarana dan lalu lintas pasal 65 ayat 1 b dan c, tertulis bahwa (1) Pemakai jalan wajib mendahulukan sesuai urutan prioritas sebagai berikut : b. Ambulans mengangkut orang sakit; c. Kendaraan untuk memberi pertolongan pada kecelakaan lalu lintas.
2.2 Permasalahan Lintasan Terpendek (Shortest Path) Salah satu persoalan optimasi adalah persoalan lintasan terpendek di dalam graf. Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot (weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Asumsi yang digunakan adalah setiap bobot bernilai positif. Kata “terpendek” tidak selalu diartikan secara fisik sebagai panjang minimum, karena kata “terpendek” berbeda-beda maknanya bergantung pada tipikal persoalan yang akan diselesaikan. Namun, secara umum “terpendek ” berarti meminimalisasi bobot pada suatu lintasan di dalam graf (Munir, 2010). Ada beberapa macam persoalan lintasan terpendek, antara lain : a. Lintasan terpendek antara dua simpul tertentu.. b. Lintasan terpendek antara semua pasangan simpul. c. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain. d. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.
Universitas Sumatera Utara
8
2.3. Pengertian Algoritma A Star (A*) Algoritma A* adalah sebuah algoritma yang telah diperkaya dengan menerapkan suatu heuristik, algoritma ini membuang langkah-langkah yang tidak perlu dengan pertimbangan bahwa langkah-langkah yang dibuang sudah pasti merupakan langkah yang tidak akan mencapai solusi yang diinginkan dengan menerapkan suatu heuristik. Heuristik adalah nilai yang memberi nilai pada tiap simpul yang memandu A* mendapatkan solusi yang diinginkan. Dengan heuristik, maka A* pasti akan mendapatkan solusi (jika memang ada solusinya). Dengan kata lain, heuristik adalah fungsi optimasi yang menjadikan algoritma A* lebih baik dari pada algoritma lainnya (Kusumadewi et al. 2005). Menurut Russel & Norvig (2003) algoritma A* memiliki lima komponen utama, yaitu: node awal, node goal, open list, closed list dan cost. Node awal merupakan titik awal dari posisi saat ini, sedangkan node goal merupakan titik akhir atau dapat juga disebut titik tempat tujuan. Cost merupakan nilai dari jarak yang telah ditempuh untuk sampai ke tempat tujuan. Open list ini berupa sebuah priority queen, dimana setiap node yang masuk pertama akan dikeluarkan pertama dengan syarat tertentu. Closed list ini berupa sebuah stack (tumpukan), dimana node yang terakhir dimasukkan akan dikeluarkan pertama kali. Selain sebagai penampung node yang telah dilewati, closed list ini juga digunakan untuk mendapatkan rute terdekat saat node goal sudah dicapai. Algoritma A* menggunakan dua antrian, yaitu Open dan Close. Dimulai dengan titik awal dijadikan antrian prioritas titik untuk dilalui, dikenal sebagai Open set. Semakin rendah cost untuk suatu simpul x, semakin tinggi prioritas. Pada setiap langkah dari algoritma A* simpul dengan cost tertinggi maka akan dihapus dari antrian, f dan h nilai-nilai tetangganya diperbarui sesuai dengan relasi pada graf dan tetangga ini ditambahkan ke antrian . Algoritma A* akan terus mencari sampai titik tujuan yang memiliki nilai f lebih rendah dengan menggunakan nilai heuristik untuk mempersempit ruang pencarian yaitu dengan membatasi vertex yang akan diuji pada setiap percabangan. Jika sudah sampai ke titik tujuan maka A* akan menjumlahkan panjang path yang sebenarnya (Coppin, 2004). Algoritma memeriksa node dengan menggabungkan g(n) yaitu cost yang dibutuhkan untuk mencapai sebuah node dan h(n), yaitu cost yang di dapat dari node ke tujuan. Sehingga didapatkan rumus dasar dari algoritma A* adalah:
Universitas Sumatera Utara
9
f(n)= g(n) + h(n) ….......(1) dimana: h(n) = Nilai heuristik antar koordinat g(n) = Jarak koordinat ke titik tujuan Dalam notasi standar yang dipakai untuk algoritma A* pada rumus persamaan (1), digunakan g(n) untuk mewakili cost rute dari node awal ke node n. Lalu h(n) mewakili perkiraan cost dari node n ke node goal, yang dihitung dengan fungsi heuristik. A* „menyeimbangkan‟ kedua nilai ini dalam mencari jalan dari node awal ke node goal (Ilham et al. 2011).
Berikut terminologi dasar yang terdapat pada algoritma A* : 1. Starting point sebagai posisi awal sebuah benda. 2. Current adalah simpul yang sedang dijalankan pada algoritma pencarian jarak terpendek. 3. Simpul adalah petak kecil atau pixel sebagai representasi dari arah path finding. Bentuknya dapat berupa persegi, lingkaran, maupun segitiga. 4. Open list adalah tempat menyimpan data simpul yang mungkin diakses dari starting point maupun simpul yang sedang dijalankan. 5. Closed list adalah tempat penyimpanan data simpul sebelum Current yang juga merupakan bagian dari jalur terpendek yang telah berhasil diciptakan. 6. “f” adalah nilai yang diperoleh dari penjumlahan. ”g” merupakan jumlah nilai tiap simpul dalam jalur terpendek dari titik awal ke Current dan “h” merupakan jumlah nilai perkiraan dari sebuah simpul ke simpul tujuan. Sehingga dapat diformulasikan dengan f(x) = g(x) + h(x). 7. Simpul tujuan adalah simpul yang dituju. 8. Halangan adalah sebuah atribut yang menyatakan bahwa sebuah simpul tidak dapat dilalui oleh Current. A* dapat juga dapat diimplementasikan, jika kebutuhan akan pencarian yang membutuhkan perulangan. Prinsip algoritma A* yaitu, akan melintasi semua graf yang berhubungan dengan starting point, mengurutkan cost terkecil dengan memperhatikan cost (f) kedalam antrian graf yang dilalui (Pratama & Putra, 2011). Jika pada titik tertentu segmen jalan yang dilalui memiliki biaya yang lebih tinggi dari segmen jalan
Universitas Sumatera Utara
10
yang lain yang sedang dihadapi, maka A* akan meninggalkan jalan dengan cost yang lebih tinggi. Gambar 2.1 merupakan contoh sederhana pengaplikasian algoritma A*.
Gambar 2.1 Contoh Pengaplikasian algoritma A * (Hayati et al, 2010) 2.4 Google Maps API (Application Programming Interface) Google Maps adalah layanan pemetaan berbasis web service yang disediakan oleh Google dan bersifat gratis, yang memiliki kemampuan terhadap banyak layanan pemetaan berbasis web. Google Maps juga memiliki sifat server side, yaitu peta yang tersimpan pada server Google dapat dimanfaatkan oleh pengguna. Google Maps API adalah suatu library yang berbentuk javascript yang berguna untuk memodifikasi peta yang ada di Google Maps sesuai kebutuhan. Untuk membangun aplikasi yang memanfaatkan Google Maps di desktop dan mobile device maka akan digunakan Google Maps Javascript API v3 yang memiliki keunggulan lebih cepat dari versi sebelumnya (Google Developers, 2012). Google Maps API menyediakan layanan web (Web Services) sebagai interface untuk meminta data Maps API dari layanan eksternal untuk digunakan dalam aplikasi Maps. Google Maps Web Services adalah kumpulan dari interface HTTP ke layanan Google yang menyediakan data geografis untuk aplikasi Maps. Menurut Shodiq (2009) menulis program Google Map API dilakukan dengan urutan sebagai berikut : 1. Memasukkan Maps API JavaScript ke dalam HTML. 2. Membuat element div dengan nama map_canvas untuk menampilkan peta (Maps). 3. Membuat beberapa objek literal untuk menyimpan property-properti pada peta. 4. Menuliskan fungsi JavaScript untuk membuat objek peta. 5. Meng-inisiasi peta dalam tag body HTML dengan event onload.
Universitas Sumatera Utara
11
Parameter mapTypeId menentukan jenis peta yang akan ditampilkan. Pilihannya ada empat yaitu : 1. ROADMAP, untuk menampilkan peta biasa 2 dimensi. 2. SATELLITE, untuk menampilkan foto satelit. 3. TERRAIN, untuk menunjukkan relief fisik permukaan bumi dan menunjukkan seberapa tingginya suatu lokasi, contohnya menunjukkan gunung dan sungai. 4. HYBRID, menunjukkan foto satelit yang diatasnya tergambar pula apa yang tampil pada ROADMAP (jalan dan nama kota). 2.5 GIS (Geographic Information System) GIS (Geographic Information System) adalah sistem yang bekerja dengan data yang tereferensi secara spasial atau koordinat-koordinat geografi (Ilham et al.
2011).
Sistem ini mampu untuk mengolah data dan melakukan operasi tertentu dengan menampilkan dan menganalisa data. Aplikasi GIS ini menjadi beragam jenis aplikasinya.
Selain
jumlah
aplikasinya
yang
juga
bertambah,
kedepannya
pengembangan aplikasi ini merambah ke aplikasi berbasis jaringan yang dikenal dengan web GIS. Ini dikarenakan lingkungan jaringan merupakan tempat subur berkembangnya geoinformasi. Contohnya adalah peta sebuah kota secara online yang tidak mengenal batas geografi penggunaannya. Tujuan
pokok
dari
pemanfaatan
GIS
adalah
untuk
mempermudah
mendapatkan informasi yang telah diolah dan tersimpan sebagai atribut suatu lokasi atau objek. Ciri utama data yang bisa dimanfaatkan dalam GIS adalah data yang telah terikat dengan lokasi dan merupakan data dasar yang belum dispesifikasi (Dulbahri, 1993). Data-data yang diolah dalam GIS pada dasarnya terdiri dari data spasial dan data atribut dalam bentuk digital, dengan demikian analisis yang dapat digunakan adalah analisis spasial dan analisis atribut. Data spasial merupakan data yang berkaitan dengan lokasi keruangan yang umumnya berbentuk peta. Sedangkan data atribut merupakan data tabel yang berfungsi menjelaskan keberadaan berbagai objek sebagai data spasial. Penyajian data spasial mempunyai tiga cara dasar yaitu dalam bentuk titik, bentuk garis dan bentuk area (polygon). Titik merupakan tampilan tunggal dari sepasang koordinat x,y yang menunjukkan lokasi suatu obyek berupa ketinggian,
Universitas Sumatera Utara
12
lokasi kota, lokasi pengambilan sampel dan lain-lain. Garis merupakan sekumpulan titik-titik yang membentuk suatu tampilan memanjang seperti sungai, jalan, kontus dan lain-lain. Sedangkan area adalah kenampakan yang dibatasi oleh suatu garis yang membentuk suatu ruang homogen, misalnya: batas daerah, batas penggunaan lahan, pulau dan lain sebagainya. Struktur data spasial dibagi dua yaitu model data raster dan model data vektor. Data raster adalah data yang disimpan dalam bentuk kotak segi empat (grid/sel) sehingga terbentuk suatu ruang yang teratur. Data vektor adalah data yang direkam dalam bentuk koordinat titik yang menampilkan, menempatkan dan menyimpan data spasial dengan menggunakan titik, garis atau area (polygon) (Barus & Wiradisastra 2000). Bentuk produk suatu GIS dapat bervariasi baik dalam hal kualitas, keakuratan dan kemudahan pemakainnya. Hasil ini dapat dibuat dalam bentuk peta-peta, tabel angka-angka: teks di atas kertas atau media lain (hard copy), atau dalam cetak lunak (seperti file elektronik). Barus dan Wiradisastra (2000) juga mengungkapkan bahwa GIS adalah alat yang handal untuk menangani data spasial, dimana dalam GIS data dipelihara dalam bentuk digital sehingga data ini lebih padat dibanding dalam bentuk peta cetak, tabel atau dalam bentuk konvensional lainnya yang akhirnya akan mempercepat pekerjaan dan meringankan biaya yang diperlukan.
2.6 Peneliti Terdahulu Algoritma A* telah banyak digunakan dalam pencarian jarak terpendek pada sebuah aplikasi. Harianja (2013) membangun sebuah sistem optimalisasi pencarian solusi dynamic water jug dengan menerapkan algoritma A*. Permasalahan optimalisasi dynamic water jug adalah bagaimana mengoptimalkan penyelesaian sebuah permasalahan water jug atau mencari sebuah solusi paling optimal dalam menyelesaikan sebuah kasus wadah air. Putra et al. (2012) menggunakan algoritma A* untuk pencarian rute terpendek pada labirin. Labirin adalah sebuah jaringan dari jalur-jalur yang saling berhubungan untuk dilalui dari awal hingga akhir yang dimaksudkan untuk sebuah tantangan, manusia mungkin masih dapat menyelesaikan masalah pencarian ruang terdekat yang sederhana, tetapi jika jumlah rute yang ada sudah sedemikian banyaknya, maka akan mengalami kesulitan dan memakan waktu yang lama untuk menyelesaikannya.
Universitas Sumatera Utara
13
Pugas et al. (2011) menggunakan algoritma djikstra dan A* dalam SIG (Sisyem Informasi Geografis) pada aplikasi pencarian rute terpendek untuk pemetaan kota Sawahlunto. Teknologi Sistem Informasi Geografis (SIG) telah berkembang pesat. SIG dibuat dengan menggunakan informasi yang berasal dari pengolahan sejumlah data, yaitu data geografis atau data yang berkaitan dengan posisi objek di permukaan bumi. Teknologi SIG mengintegrasikan operasi pengolahan data berbasis database yang biasa digunakan saat ini, seperti pengambilan data berdasarkan kebutuhan, analisis statistik dengan menggunakan visualisasi yang khas serta berbagai keuntungan yang mampu ditawarkan analisis geografis melalui gambar-gambar petanya. SIG juga dapat memberikan penjelasan tentang suatu peristiwa, membuat peramalan kejadian, dan perencanaan strategis lainnya serta dapat membantu menganalisis permasalahan umum seperti masalah ekonomi, penduduk, sosial pemerintahan, pertahanan serta bidang pariwisata. Ichsan et al. (2012) menerapkan algoritma Hybrid Fuzzy-Dijkstra dalam pembangunan aplikasi pencarian jalur tercepat. Dalam perpaduan kedua algoritma tersebut dikatakan bahwa nilai yang dimiliki oleh jalan selalu dinamis, sehingga proses yang dilalui akan bisa berubah setiap saat, dan rute yang dipilih bisa berubah setiap saat. Florens et al. (2009) juga membangun sebuah aplikasi pencarian jalur tercepat untuk transportasi bus Trans Jakarta menggunaka algoritma Djikstra. Hasil yang dicapai adalah aplikasi berupa kios informasi yang dapat melakukan pencarian jalur tercepat dalam Trans Jakarta. Varita et al. (2013) membangun sebuah aplikasi pencarian jalur tercepat rute perjalanan wisata dengan algoritma Tabu Search. Pencarian jalur tercepat dengan parameter panjang, volume dan kepadatan jalan dapat diaplikasikan dengan algoritma Tabu Search dengan hasil jumlah iterasi dalam algoritma Tabu Search mempengaruhi jumlah cost. Semakin besar iterasi akan mendapatkan cost yang lebih rendah sehingga didapatkan jalur tercepat dengan cost terendah, yaitu iterasi I dibatasi 300, atau jika hasil cost jalur terbaik sudah pernah sama sebanyak 15 kali. Penambahan fungsi antrian yang diimplementasikan dalam neighbourhood berperan dalam mengurangi kompleksitas iterasi. Karena setiap parameter dalam Tabu Search mempengaruhi satu
Universitas Sumatera Utara
14
sama lain. Parameter dalam penelitian ini adalah iterasi , threshold, dan data yang digunakan. Tabel 2.1 Peneliti Terdahulu No 2
Nama Peneliti Rufina
Judul Penelitian
Florens, Analisis
Jenny
dan
Tahun 2009
Tirta Perancangan
Keterangan Hasil
dicapai
adalah aplikasi berupa
Kusuma & Rimbun Sistem Pencarian
kios
Mataram
dapat
Jalur
yang
Tercepat
informasi
yang
melakukan
Untuk
pencarian jalur tercepat
Transportasi Bus
dalam Trans Jakarta.
Trans
Algoritma
Jakarta
Dijkstra
Menggunaka
mampu mencari jalur
Algoritma
tercepat sesuai dengan
Djikstra
keinginan
pengguna
tranportasi
Trans
Jakarta. 3
Diana Okta Pugas, Aplikasi Maman &
Somantri pencarian
Kodrat
Satoto
2011 rute
Iman terpendek
Pencarian
rute
terpendek menggunakan
menggunakan
algoritma Dijkstra dan
algoritma Djikstra
A Star menghasilkan
dan A Star (A*)
rute jalan yang sama.
pada SIG berbasis web
untuk
pemetaan pariwisata Sawahlunto
Pencarian
terpendek A Star lebih cepat
kota
rute
dengan
dibandingkan algoritma
Djikstra.
Universitas Sumatera Utara
15
Tabel 2.1. Penelitian Terdahulu (Lanjutan) No 4
Nama Peneliti Moch.
Judul Penelitian
Hannats Optimal
Hanafi Ichsan, Erni Pencarian
Tahun 2012
Keterangan Nilai yang dimiliki oleh
Jalur
jalan selalu dinamis,
Yudaningtyas & M. Tercepat dengan
sehingga proses yang
Aziz Muslim
Algoritma Hybrid
dilalui
Fuzzy-Dijkstra
setiap saat dan rute yang
bisa
berubah
dipilih
bisa
berubah setiap saat. 5
Ivana Varita, Onny Pencarian
Jalur 2013
Setyawati & Didik Tercepat
Rute
Rahadi
Pencarian jalur tercepat dengan
parameter
Perjalanan Wisata
panjang, volume dan
Dengan
kepadatan jalan dapat
Algoritma
Tabu
diaplikasikan
Search
dengan
algoritma Tabu Search. Hasil
jumlah
iterasi
dalam algoritma Tabu Search mempengaruhi jumlah cost. 6
Firman Harianja
Penerapan
2013
algoritma
A*
Optimalisasi dynamic water
jug
adalah
pada
mengoptimalkan
permasalahan
penyelesaian
sebuah
optimalisasi
permasalahan
water
pencarian
solusi
jug atau mencari solusi
dynamic
water
paling optimal dalam
jug.
meyelesaikan
sebuah
kasus wadah air
Universitas Sumatera Utara
16
Tabel 2.1 Penelitian Terdahulu (Lanjutan) No 1
Nama Peneliti
Judul Penelitian
Rengga Dionata Pencarian Putra,
rute
Ir. terdekat pada labirin
Muhammad
menggunakan
Tahun
Keterangan
2012
Algoritma A * tidak menjamin mendapat
selalu jalur
yang
Aswin, MT. & metode A*
terbaik (bobot terkecil),
Waru Djuriatno,
dari semua rute yang
ST., MT.
ada.
Universitas Sumatera Utara
