Stady
Kasus Tentang Jaringan Jalan Untuk Menentukan Rute Terpendek
PENDAHULUAN
Kota Balik papan merupakan salah
satu kota yang berada di Provinsi Kalimantan Timur yang memiliki peningkatan
perkembangan pembangunan yang sangat pesat. Salah satunya adalah pembangunan
pusat kesehatan antara lain rumah sakit dan puskesmas. Peran dari pusat
kesehatan tersebut tidak kalah penting fungsinya seperti bangunan,bangunan
penting lainnya yang ada di Kota Balikpapan. Keberadaan pusat kesehatan sangat
penting karena dapat membantu mengobati
dan merawat orang yang sakit serta
memberikan pelayanan Unit Gawat Darurat (UGD) selama 24 jam bagi masyarakat
yang mengalami kecelakaan atau perawatan yang harus segera ditolong.Bagi warga
Kota Balikpapan, khususnya warga pendatang masih ada yang belum mengetahui
dimana saja letak pusat kesehatan dan harus melewati jalur mana yang lebih
dekat dari tempat mereka berada. Pada saat mereka mengalami keadaan yang sangat
genting, misalnya saja salah satu keluarga mereka mengalami kecelakaan,
sementara mereka baru beberapa hari
berada di Kota Balikpapan, maka
mereka kesulitan dalam menentukan harusdibawa ke mana dan melewati jalur mana
yang lebih dekat dari tempat kejadian, agar orang tersebut segera mendapatkan
pertolongan medis untuk memperkecil resiko yang
tidak diinginkan.Oleh karena itu
diperlukan adanya sistem Penentuan RuteTerpendek menggunakan Metode Dijkstra
berbasis WebGIS. Dimana sistem
informasi berbasis WebGISini,dapat
diakses di semua tempat dan waktu serta bisa dilakukan oleh siapa saja. Dikemas
dalam bentuk sistem informasi yang gratis dan legal, dan dapat digunakan dengan
mudah. Rumusan Masalah Berdasarkan latar belakang tersebut dapat dirumuskan
suatu masalah sebagai berikut,
“Bagaimana Membangun Aplikasi
Penentuan Rute Terpendek menggunakan Metode Dijkstra Berbasis WebGIS ”.Batasan
Masalah Pada penelitian ini pembahasan masalah
dibatasi pada :
1.Daerah yang menjadi objek
penelitian adalah Kota Balikpapan.
2.Data spasial yang digunakan adalah
lokasi Rumah Sakit dan Puskesmas, serta Data Jalan.
3.Input data berupa titik pusat
kesehatan (Rumah Sakit/Puskesmas) sebagai titik nol (awal) dan titik tujuan.
4.Output yang dihasilkan berupa
peta, rute yang dilalui, jarak tempuh dan transportasi yang digunakan antara
tempat pemakai system menuju pusat kesehatan yang terdekat.
Tujuan Penelitian Tujuan yang ingin
dicapai dari penelitian ini adalah sebagai berikut :
1.Dapat mempermudah masyarakat dalam
mencari informasi dan letak bangunan Rumah Sakit dan Puskesmas yang terdapat di
Kota Balikpapan.
2.Terciptanya aplikasi Penentuan
Rute Terpendek menggunakan Metode Dijkstra
untuk membantu memberikan informasi
dalam
bentuk peta yang berbasis web
(WebGIS).
3.Waktu yang digunakan oleh pengguna
sistem (user) untuk mencari pusat kesehatan menjadi lebih singkat dan rute
menjadi lebih dekat.
TINJAUAN PUSTAKA
Algoritma Dijkstra Algoritma
Dijkstra (sesuai dengan nama penemunya, Edsger W. Dijkstra) merupakan sebuah
algoritma yang diterapkan untuk menentukan lintasan terpendek dalam sejumlah
langkah pada graf berarah maupun graf takberarah. Algoritma tersebut
menggunakan prinsip greedy, yakni pada setiap langkah dipilih sisi yang
berbobot minimum dan dimasukkan ke dalam himpunan solusi. Berikut
salah satu versi Algoritma Dijkstra
[10]:
1.
Misalkan sebuah graf berbobot dengan
n buah simpul dinyatakan dengan matriks ketetanggaan
M =
[mij]
yangdalam hal ini,
mij = bobot sisi (i, j)
(pada
graf takberarah mij =
mji)
mii = 0
mij = ∞, jika tidak ada sisi dari simpul
i ke simpul j
2. Selain matriks M, digunakan pula
S =
[si]
yang dalam hal ini,
si = 1, jika simpul i termasuk ke dalam
lintasan terpendek
si = 0, jika simpul i tidak termasuk ke
dalam lintasan terpendek
3. Dan tabel D = [di] yang dalam hal ini,
di = panjang lintasan dari simpul awal
s ke simpul i
Sistem Informasi Geografis
Sistem Informasi Geografis merupakan
suatu sistem informasi yang berbasis komputer, dirancang untuk bekerja dengan
menggunakan data yang memiliki informasi spasial (bereferensi keruangan).
Sistem ini meng-capture, mengecek, mengintegrasikan,memanipulasi, menganalisa,
dan menampilkan data yang secara spasial mereferensikan kepada kondisi bumi.SIG
adalah suatu sistem berbasis komputer yang memiliki kemampuan dalam menangani
data bereferensi geografi yaitu pemasukan data, manajemen data (penyimpanan dan
pemanggilan kembali), manipulasi dan analisis data, serta keluaran sebagai
hasil akhir (output). Hasil akhir
(output) dapat dijadikan acuan dalam
pengambilan keputusan pada masalah yang berhubungan dengan geografi.SIG sebagai
sistem berbasis komputer yang digunakan untuk memasukkan, menyimpan, mengelola,
menganalisis dan mengaktifkan kembali data yang mempunyai referensi keruangan
untuk berbagai tujuan yang berkaitan dengan pemetaan dan perencanaan.MapServer MapServer
adalah program CGI (CGI : Common Gateway Interface) yang terpasang dan
berjalan tapi tidak aktif dalam
server (aktif hanya saat dipanggil). Saat
request/permintaan dikirimkan
kemapserver, maka akan digunakan informasi yang
dikirimkan lewat URL dan mapfile
untuk membuat (generate) peta yang diinginkan. Permintaan ini bisa juga
termasuk permintaan untuk membuat legenda, peta referensi, batang skala, dan
variabel lain yang dikirimkan ke CGI.Program CGI akan dieksekusi di webserver dan
berdasarkan beberapa parameter tertentu (khususnya konfigurasi dalam bentuk
file *.MAP) maka akan menghasilkan data yang kemudian dikirim ke web browser,
baik dalam bentuk gambar peta maupun bentuk lain.
QuantumGIS
QuantumGIS (QGIS) adalah aplikasi
SIG gratis yang mencakup pemetaan, analisis spasial, dan beberapa fitur
DesktopGIS lainnya. Aplikasi ini sama dengan paket aplikasi GIS komersial,
namun aplikasi ini didistribusikan secara gratis dibawah
lisensi GNU. QuantumGIS mendukung
format data vektor, raster, dan database (PostGIS dan Oracle). QuantumGIS juga
dapat diprogram ulang untuk mengerjakan tuga yang lebih spesifik. Aplikasi ini
juga merupakan suatu aplikasi multi-platform yang dapat dijalankanpada sistem
operasi yang berbeda-beda termasuk MacOS X, Linux, Unix dan Windows.HASIL DAN
PEMBAHASAN.
Digitasi Peta Pada QuantumGIS
Peta Kota Balikpapan yang telah
diperoleh sebelumnya akan digunakan untuk proses digitasi.Teknik digitasipeta
pada prinsipnya adalah pembuatan peta melalui proses komputer. Penyimpanan
filedi komputer dari hasil digitasi peta tersebut dikelompokkan berdasarkan
layeryang sesuai dengan tipenya masing-masing. Dalam proses digitasi peta Kota
Balikpapan ini digunakan 3 jenis layer, yaitu tipe
polygon (ruang), tipe point(titik),
dan tipe line (garis). Pada setiap proses digitasi, ditambahkan sejumlah
atribut sesuai kebutuhan masing-masing objek, yang nantinya akan ditampilkan
sebagai suatu informasi pada objek tersebut. Berikut tampilan hasil akhir
proses digitasi peta Kota Balikpapan:
Hasil DigitasiPeta Kota Balikpapan
Menggunakan QuantumGIS Setelah peta
selesai di digitasi, dilanjutkan dengan mengexport peta kedalam bentuk file
*.MAP agar dapat ditampilkan dalam web.
Kemudian membuat database pada
PgAdmin III dengan nama Balikpapan, yang isi tabelnya diperoleh dari hasil
import database pada QuantumGIS.Rancangan Sistem
Berikut adalah rancangan system yang
dibangun menggunakan empat jenis pemodelan UML beserta dengan penjelasannya,
antara lain :
Use Case
Diagram WebGIS Penentuan Rute
Terpendek Menuju Pusat Kesehatan
Sebuah Use Case menggambarkan
interaksi antara aktor dengan sistem dan fungsionalitas dari aplikasi Penentuan
Rute Terpendek Menuju Pusat Kesehatan Menggunakan Metode Dijkstra Berbasis
WebGIS. Diagram tersebut terdiri dari satu aktor dan sembilan Use Case. Dimana
antara Use Case satu dengan lainnya
saling berkaitan jika kondisi
tertentu terpenuhi.
Activity
Diagram WebGIS Penentuan Rute
Terpendek Menuju Pusat Kesehatan Activity Diagrammenggambarkan berbagai alur
aktivitas secara umum dalam sistem yang
sedang dirancang, bagaimana
masing-masing alur berawal, decision yang mungkin terjadi dan bagaimana
berakhir. Pada diagram tersebut alur berawal dari guest yang membuka sistem
Penentuan Rute Terpendek Menuju Pusat Kesehatan Kota Balikpapan, lalu memilih
Menu
Peta Balikpapan dan melakukan
pencarian dengan memilih titik awal dan titik tujuan, kemudian sistem akan
melakukan proses perbandingan kemungkinan
rute yang terpendek. Alur berakhir
dengan pengguna mendapatkan informasi mengenai Rumah Sakit atau Puskesmas yang
dituju, Rute Terpendek, Jarak Tempu
h, Nama Jalan, dan Transportasinya.
Sequence
Diagram
WebGIS Penentuan Rute Terpendek
Menuju Pusat Kesehatan Sequence Diagram
menggambarkan interaksi antar objek
didalam sistem. Dimana pada diagram tersebut menggambarkan langkah-langkah yang
dilakukan dalam sistem yang terdiri dari satu aktor, enam participant dengan
lifelinenya dan 10 message.
Class
Diagram
Penentuan Rute Terpendek Menuju
Pusat Kesehatan Class Diagram menggambarkan hubungan struktur dan deskripsi
class, package beserta objek
antar tabel yang terdapat pada
sistem. Dimana terdapat tujuh tabel yakni tabel peta_balikpapan, jalanutama,
jalanlain,pusatkesehatan, transport, hubungan, dan simpangan yang saling
berhubungan antar satu sama lain.Implementasi Sistem
Implementasi sistem meliputi lingkungan
implementasi serta implementasi program.
Lingkungan Implementasi Merupakan
lingkup dimana tempat penyimpanan file-file
yang digunakan dan saling
berhubungan untuk mendukung pengembangan
aplikasi. Yakni dengan membuat
folder-folder yang digunakan untuk menampung aplikasi yang telah dibuat. Folder
yang dipakai untuk menyimpan aplikasi adalah folder latihan yang berada pada
“File System:\var\www\”. Folderlatihan terdiri dari subfolder data, etc, map,
dan mapscript. Subfolder “data”memiliki subfolder lagi, yakni subfolder shp
berfungsi untuk menyimpan data simbol peta dalam format (*.shp) yang digunakan
dalam sistem. Subfolder “etc” digunakan untuk menyimpan gambar-gambar yang
berfungsi sebagai simbol pada legenda yang melambangkan kelurahan,jalanutama,
jalanlain, pusatkesehatan, dan informasi lainnya yang diperlukan. Subfolder
“map” berisi file PETA_BPP.map yang digunakan untuk menghubungkan antara file
yang berekstensi .shp dan database PostgreSQL dengan mapscript. Dan Subfolder
“mapscript” berisi file-file untuk mengelola WebGIS pencarian rute terpendek
menuju pusat kesehatan Kota Balikpapan.
Tampilan Halaman Peta
Prosedur Algoritma Dijkstra
Seperti dijelaskan pada bab
sebelumnya, algoritma dijkstra adalah algoritma menentukan lintasan terpendek
dalam sejumlah langkah pada
graf berarah maupun graf tak-berarah
yang pada setiap langkah dipilih sisi yang berbobot minimum dan dimasukkan ke
dalam himpunan solusi. Pada sistem ini prosedur algoritma dijkstra yang
dilakukan adalah sebagai berikut :
1.Ditentukan titik awal (startnode)
dan titik tujuan (bestnode) untuk mencari rute terpendek. Kemudian dilakukan
percobaan sebanyak mungkin hingga didapatkan rute terpendek
2.Dilakukan update titik (rute)
terbaru dan sebelumnya hingga kemungkinan maximal percobaan ditemukan.Pada
bagian ini perhitungan dijkstra dilakukan, yakni dengan menambahkan setiap
jarak yang dilalui oleh tiap-tiap titik sehingga didapat kan hasil jarak yang
ditempuh kemudian dibandingkan dengan hasil percobaan sampai ditemukan jarak
yang terpendek.
3.Jika maximal percobaan telah
mendapatkan hasil akhir rute terpendek maka
bestnode (rute terpendek) akan
ditampilkan sebagai hasil pencarian.Pengujian Sistem Pengujian pertama diambil
pencarian secara manual yakni dari titik awal,
Puskesmas Baru Ulu menuju RSU
Kanudjoso, terdapat beberapa jalan
alternatif seperti berikut :
1.5-4-6-7-41-1-42-52-53-55-56-57-58-21-18
dengan jarak 7455m
2.5-4-6-7-41-1-20-19-9-10-11-13-18
dengan jarak 11765m
3.5-4-6-7-41-1-42-43-44-52-53-55-56-57-58-21-18
dengan jarak 9855m
4.5-4-6-7-41-1-42-43-44-45-56-57-58-21-18
dengan jarak 7475m
Maka Jalur terpendeknya adalah
a 5-4-6-7-41-1-42-52-53-55-56-57-58-21-18
dengan jarak7455m
Untuk pencarian menggunakan sistem
adalah
sebagai berikut :
Hasil Pencarian Dari Puskesmas Baru
Ulu Menuju RSU Balikpapan Hasil dari perbandingan pencarian rute terpendek
secara manual dan menggunakan sistem
Dimana rute dari titik awal
Puskesmas Baru Ulu menuju titik tujuanRSU Balikpapan adalah 5-4-6-7-41-1-42-52-53-55-56-57-58-21-18dengan
jarak tempuh 7455 meter. Pada sistem ini juga ditampilkan jalan yang dilalui
dan angkutan umum yang dapat digunakan menuju pusat kesehatan yang telah
dipilih.
KESIMPULAN
Berdasarkan dari hasil pengujian
sistem, dapat disimpulkan bahwa :
1.Sistem dapat mencari jalur
terpendek yang dapat mempermudah masyarakat dalam mencari informasi dan letak
pusat kesehatan yang terdapat di Kota Balikpapan.
2.Dengan adanya WebGIS penentuan
rute terpendek menuju pusat kesehatan Kota Balikpapan menggunakan metode
dijkstra ini, dapat membantu memberikan informasi dalam bentuk peta.
3.Waktu yang digunakan oleh pengguna
sistem untuk mencari pusat kesehatan lebih singkat dan rute menjadi lebih
dekat.
Tidak ada komentar:
Posting Komentar