IMPLEMENTASI DAN ANALISIS ALGORITMA PENCARIAN RUTE TERPENDEK DI KOTA SURABAYA

Pencarian rute terpendek merupakan suatu  masalah yang paling banyak dibahas dan dipelajari  sejak akhir tahun 1950. Pencarian rute terpendek ini  telah diterapkan di berbagai bidang untuk  mengoptimasi kinerja suatu sistem, baik untuk meminimalkan biaya atau mempercepat jalannya suatu proses. Salah satu aplikasi pencarian rute terpendek yang paling menarik untuk dibahas adalah pada masalah transportasi. Dalam pencarian rute terpendek, penghitungan dapat dilakukan dengan beberapa macam algoritma. Secara garis besar algoritma penghitungan rute terpendek dibagi menjadi dua kelas berdasarkan metode pemberian labelnya, yaitu algoritma label setting dan algoritma label correcting[3]. Metode label setting menentukan label jarak sebagai jarak permanen pada setiap iterasinya, sedangkan metode label correcting menentukan label jarak sebagai temporal pada setiap iterasi sampai langkah akhir ketika semua node telah melewati proses pemeriksaan, maka labelnya akan ditentukan sebagai permanen. algoritma dijkstra adalah salah satu algoritma penghitungan rute terpendek kelas label Setting, sedangkan pada kelas label correcting terdapat algoritma floyd dan algoritma two-queues. Ketiga algoritma ini akan dibandingkan performanya, dan juga akan dievaluasi untuk mengetahui faktor-faktor yang mempengaruhi performa dari masing-masing algoritma. Jaringan jalan yang akan digunakan sebagai bahan penghitungan adalah jaringan jalan yang ada di kota Surabaya. Algoritma yang paling cepat dalam melakukan penghitungan akan dipakai dalam aplikasi berbasis teknologi Wireless Application

         Implementasi dan Analisa Algoritma Pencarian Rute Terpendek di Kota Surabaya (Yudhi Purwananto)

Protocol (WAP) untuk mendukung faktor mobilitas dan kemudahan mengakses dari aplikasi. WAP

adalah sebuah fasilitas yang memungkinkan mengakses internet melalui alat-alat komunikasi elektronik tanpa kabel (mobile device). FasilitasWAP biasa terdapat pada handphone atau PDA (Personal Digital Assistance). Diharapkan dengan digunakannya fasilitas WAP, pengguna bisa mendapatkan segala macam dan bentuk informasi yang dibutuhkan dengan mudah dan cepat, termasuk informasi tentang transportasi.

 Teori Dasar Graph dan Pencarian Rute Terpendek

Graph terdiri dari sekumpulan node yang

dihubungkan dengan sekumpulan arc. Notasi untuk

mendeskripsikan suatu graph adalah , dimana

adalah sekumpulan node (vertex) dan adalah

sekumpulan dari arc (edge) dengan nilai-nilai yang

berasosiasi pada setiap node. Nilai-nilai yang

berasosiasi itu adalah jumlah node, jumlah arc, dan

panjang dari arc yang menghubungkan antara node i

dan j yang dinotasikan sebagai d(i,j). Suatu jaringan

dapat direpresentasikan sebagai graph. Beberapa

contoh model jaringan dalam dunia nyata yang dapat

direpresentasikan sebagai graph adalah desain

jaringan pipa minyak, jaringan fisik seperti jalan, rel

kereta api, atau rute pesawat terbang, jaringan kabel

listrik, dan sebagainya. Gambar 1 menunjukkan

sebuah jaringan fisik jalan di kota Surabaya yang

sebagian dimodelkan dengan graph G terdiri dari

delapan node = {A,B,C,D,E,F,G,H}.

Gambar 1. Diagram Data Jalan Kota Surabaya

Proses penghitungan rute terpendek adalah

proses mencari jarak terpendek atau biaya terkecil

suatu rute dari node awal ke node tujuan dalam

sebuah jaringan. Nilai d(i) merupakan nilai jarak

atau bobot total terkecil dari suatu rute.

Pada proses penghitungan rute terpendek

terdapat dua macam proses yaitu proses pemberian

label dan proses pemeriksaan node. Metode

pemberian label adalah metode untuk memberikan

identifikasi pada setiap node dalam jaringan. Pada

sebagian besar algoritma penghitungan rute

terpendek, terdapat 3(tiga) label informasi yang

dikelola untuk setiap node i pada proses pemberian

label yaitu : label jarak d(i), parent node p(I,) dan

status node S(i).

Proses pemberian label berjalan seiring dengan

proses scanning (pemeriksaan). Proses pemeriksaan

node adalah proses membandingkan jarak antara

node awal s dengan node i melalui node j sebagai

node lain dalam suatu jaringan.

Gambar 2. Graph dari Diagram Data Jalan Kota

Surabaya

Pada Gambar 2, node A akan dianggap sebagai

node awal dan node G dianggap sebagai node

tujuan. Node A mempunyai label status r

(permanen), label jarak d(s) = 0, dan label parent

p(s) = 0, oleh karena itu node A dianggap sebagai

node awal. Node B dan node F mempunyai label

status t (temporal) yang berarti node tersebut telah

melalui proses pemberian label tetapi belum melalui

proses pemeriksaan. Node C, D, E dan G

mempunyai label status u (unreached), label

jaraknya d(i) = ~, dan label parent p(i) = null, karena

node-node tersebut belum melalui proses pemberian

label dan proses pemeriksaan. Pada proses

pemeriksaan node B dan node F, akan dipilih node

dengan nilai bobot yang terkecil yaitu node F, oleh

karena itu, maka label status node F, s(b), akan

berubah menjadi r, label parent, p(b), menjadi A,

dan label jaraknya, d(b) menjadi 8. Proses ini akan

terus berlangsung sampai node tujuan tercapai.

Algoritma Dijkstra

Algoritma dijkstra pertama kali dikembangkan

oleh E.W. Dijkstra. Pada perkembangannya,

algoritma ini menggunakan struktur data yang

berbeda-beda.

Pada umumnya, graph setidaknya mempunyai

satu arc penghubung dari satu node ke node yang

lain, sehingga konsekuensinya |E|=| |2. Jika masing-

masing node terhubung dengan semua node lainnya

pada suatu jaringan, maka |E|= (| |2). Graph dengan

(| |2) disebut dengan dense graph. Pada dunia

nyata nilai =(| |) karena tidak semua node

terhubung dengan masing-masing node lainnya.

Keadaan ini disebut dengan sparse graph.

Untuk merepresentasikan suatu graph dapat

digunakan matriks dua dimensi. Untuk tiap node

(i,j), nilai bobotnya dapat dimasukkan ke dalam aij.

Untuk node yang tidak saling terhubung, nilai

bobotnya dapat diisi dengan tak terhingga. Proses ini

96

Jurnal Penelitian dan Pengembangan TELEKOMUNIKASI, Desember 2005, Vol. 10, No. 2

memerlukan waktu (| |2) dengan jumlah memori

yang dibutuhkan sebanyak (| |2). Penggunaan

matriks ini cocok untuk merepresentasikan dense

graph (lihat Gambar 3), sedangkan untuk sparse

graph representasi yang cocok adalah menggunakan

adjacent list (lihat Gambar 4), dimana suatu graph

akan direpresentasikan secara linier, sehingga

memori yang dibutuhkan untuk merepresentasikan

sparse graph menggunakan adjacent list

Kesimpulan

SBY 4 (meter) SBY 5 (meter) SBY 6 (meter)

DJIKS + arr 18.682 5.096 3.692

DJIKS + PQ 18.682 5.096 3.692

FLOYD 18.682 11.124 9.086

2-QUEUE 18.682 5.096 3.692

DJIKS + arr 22.339 8.085 4.650

DJIKS + PQ 22.339 8.085 4.650

FLOYD 22.339 11.024 4.650

2-QUEUE 22.339 8.085 4.650

DJIKS + arr 14.229 13.393 5.096

DJIKS + PQ 14.229 13.393 5.096

FLOYD 14.229 13.393 8.729

2-QUEUE 14.229 13.393 5.096

DJIKS + arr 25.040 13.137 7.921

DJIKS + PQ 25.040 13.137 7.921

FLOYD 25.040 13.330 7.921

2-QUEUE 25.040 13.137 7.921

DJIKS + arr 29.542 15.288 7.129

DJIKS + PQ 29.542 15.288 7.129

FLOYD 29.542 18.227 7.129

2-QUEUE 29.543 15.288 7.129

DJIKS + arr 29.989 17.998 8.729

DJIKS + PQ 29.989 17.998 8.729

FLOYD 29.989 17.998 8.729

2-QUEUE 29.989 18.314 8.729

DJIKS + arr 30.707 16.748 9.956

DJIKS + PQ 30.707 16.748 9.956

FLOYD 30.707 16.748 15.892

2-QUEUE 30.707 16.748 9.956

Hangtuah ke Wonokromo

Iskandar Muda ke Kebonsari

Hangtuah ke Kandangan Jaya

Blauran ke Mayjen Sungkono

Blauran ke Gajahmada

Pabean ke Kedung Mangu

Blauran ke Rungkut Madya

101

           

Daftar Pustaka

[1] Benjamin Zhan, F., 2000, Three Fastest

Shortest Path Algorithms on Real Road

Networks: Data Structures and Procedures,

Journal of Geographic Information and

Decision Analysis, vol.1, no.1, pp. 69-82

[2] Purba, Jan Waren, 2003, Sistem Informasi

Geografis Berbasis Web Dengan Menggunakan

Teknologi Scalable Vector Graphic (SVG) Studi

Kasus Pencarian Lokasi Pelayanan Kesehatan

Terdekat, Tugas Akhir : Jurusan Teknik

Informatika Fakultas Teknologi Informasi

Institut Teknologi Sepuluh Nopember, Surabaya

[3] Zhan, F.B., Noon, C.E, 2000, A Comparison

Between Label-Setting and Label Correcting

Algorithms for Computing One-to-One Shortest

Path, Journal of Geographic Information and

Decision Analysis, Vol. 4 No. 2.