Study Kasus Tentang Jaringan Jalan Untuk Menentukan Rute Terpendek

          Study Kasus Tentang Jaringan Jalan Untuk Menentukan Rute Terpendek

      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: https://jurnalinforman.files.wordpress.com/2013/03/penentuan-rute-terpendek-menuju-pusat-kesehatan-menggunakan-metode-dijkstra-berbasis-webgis-studi-kasus-kota-balikpapan.pdf