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.
Sumber :
Tidak ada komentar:
Posting Komentar