94
IMPLEMENTASI DAN ANALISIS ALGORITMA PENCARIAN RUTE TERPENDEK DI KOTA SURABAYA Yudhi Purwananto1, Diana Purwitasari2, Agung Wahyu Wibowo Jurusan Teknik Informatika, Institut Teknologi Sepuluh Nopember (ITS) 1
[email protected],
[email protected] Abstrak Pencarian rute terpendek merupakan satu masalah yang paling banyak dibahas dengan transportasi sebagai salah satu contoh menarik. Pada beberapa masalah transportasi, penghitungan rute terpendek memegang peranan penting karena harus dilakukan dalam waktu yang sangat singkat dan pada saat itu juga. Tiga algoritma penghitungan rute terpendek, yaitu algoritma dijkstra, algoritma floyd, dan algoritma two queues, akan diujicoba dan dievaluasi untuk mengetahui algoritma yang paling cepat eksekusinya dengan memperhitungkan faktor-faktor tertentu. Ujicoba dilakukan dengan menggunakan data jaringan jalan kota Surabaya yang disimpan dalam basis data MySQL. Algoritma penghitungan diimplementasikan dalam bentuk aplikasi berbasis WEB dan WAP, yang akan memudahkan pengguna untuk mendapatkan informasi rute terpendek. Berdasarkan uji coba yang telah dilakukan, lama waktu eksekusi algoritma penghitungan rute terpendek dipengaruhi oleh jumlah node dalam suatu jaringan dan jumlah node yang diperiksa. Untuk kasus yang jumlah node-nya kurang dari 1000, algoritma dijkstra mampu menghasilkan waktu eksekusi lebih cepat, yaitu kurang dari 1 detik, sedangkan untuk kasus yang jumlah node-nya lebih dari 1000, lebih tepat menggunakan algoritma two queues. Kata kunci : algoritma pencarian rute terpendek, algoritma dijkstra, algoritma floyd, algoritma two queues, WAP. Abstract Shortest path problem is a frequent illustration in optimazion with transportation domain as one of exciting model. For some transportation cases, finding a shortest path takes important role because the process is a real time problem. The used algorithms to solve shortest path problem are dijkstra algorithm, floyd algorithm and two queues algorithm. Those three algorithms will be evaluated for finding the fastest in execution time considered with some issues. The street network of Surabaya is used as data in MySQL database for evaluating algorithms. Calculation process for finding shortest path is implemented into web based and WAP based application to make user get the solution easily. Execution time of shortest path algorithm is influenced by the amount of nodes being existed in street network and nodes being checked. For some cases, the amount of nodes under 1000 have dijkstra algorithm as the fastest algorithm with execution time no more than one second. While other cases two queues algorithm is proved better. Keywords : shortest path algorithm, dijkstra algorithm, floyd algorithm, two queues algorithm, WAP. 1.
Pendahuluan
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
Jurnal Penelitian dan Pengembangan TELEKOMUNIKASI, Desember 2005, Vol. 10, No. 2
95
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). Fasilitas WAP 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. 2.
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.
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 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. 3.
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
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 masingmasing 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
Implementasi dan Analisa Algoritma Pencarian Rute Terpendek di Kota Surabaya (Yudhi Purwananto)
96
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 adalah (|E|).
dalam suatu jaringan, kemudian rute-rute ini akan dibandingkan, dan rute dengan jarak yang paling pendek akan dipilih sebagai rute terpendek. Proses ini akan terus berlangsung secara iterasi dan akan berhenti ketika mencapai node tujuan. Pada algoritma dijkstra, node-node dibagi menjadi dua set. Set pertama berisi node yang telah diperiksa, sedangkan set kedua berisi node yang belum diperiksa. Untuk menyimpan node-node itu dapat digunakan struktur data array dan priority queue dengan elemen yang mempunyai urutan tertentu, yaitu ascending atau descending. Dengan priority queue, pemilihan node yang akan diperiksa dilakukan dengan menghapus bobot paling kecil sampai node tujuan tercapai. Ukuran dari priority queue dapat mencapai |E|. Terdapat sejumlah |E| proses memasukkan node serta menghapus node, maka waktu eksekusinya menjadi (|E|log|E|), dimana |E| | |2, sehingga akan mempengaruhi waktu eksekusi menjadi log|E| 2log| |. 4.
Gambar 3. Representasi Graph dengan Matriks
Gambar 4. Representasi Graph dengan Adjacent List Algoritma dijkstra di sini menggunakan adjacent list untuk merepresentasikan sebuah jaringan. Secara garis besar algortima dijkstra membagi semua node menjadi dua, kemudian dimasukkan ke dalam tabel yang berbeda, yaitu tabel permanen dan tabel temporal. Tabel permanen berisi node awal dan node-node yang telah melalui proses pemeriksaan dan labelnya telah diubah dari temporal menjadi permanen. Tabel temporal berisi node-node yang berhubungan dengan node pada tabel permanen. Pemilihan rute algoritma dijkstra dilakukan dengan Best First Search (BFS), dimana sebuah rute akan dihitung jaraknya dari node awal ke node lain
Algoritma Floyd
Algoritma floyd adalah algoritma penghitungan rute terpendek yang dapat mencari semua jarak node (all pairs shortest path) pada suatu jaringan. Algoritma floyd menggunakan matriks dua dimensi sebagai representasi dari sebuah jaringan. Jika suatu jaringan terdiri dari n buah arc maka matriks yang akan dibentuk oleh algoritma floyd untuk proses penghitungan adalah sebesar n x n. Matriks ini merepresentasikan bobot w dari keseluruhan arc yang ada pada graph ( , ,) dengan w(i,j) dimana i adalah node awal dan j adalah node tujuan. Bobot dari node i ke node j atau w(i,j) mempunyai tiga kemungkinan nilai yaitu : w(i,j) = 0 jika i = j (dari node i ke node i itu sendiri) w(i,j) = bobot arc jika i ≠ j dan node i terhubung dengan node j w(i,j) = jika i ≠ j dan node i tidak terhubung dengan node j. Algoritma floyd mampu menghitung bobot terkecil dari jaringan dengan bobot negatif. Pada kasus tertentu seperti proses penghitungan biaya dengan kemungkinan mengandung bobot negatif, algoritma floyd mempunyai kelebihan dalam memecahkan proses penghitungannya. Algoritma floyd akan memeriksa setiap arc dan membandingkan setiap “jalur tengah” untuk mendapatkan rute terpendek. Jalur tengah adalah rute yang dilalui dari node c ke node g dengan melewati node perantara h. Jalur tengah pada Gambar 5 akan dipilih sebagai rute terpendek dari node c ke node g jika jarak dari node c ke node h ditambah jarak dari node h ke node g lebih kecil dari jarak dari node c ke node g , d(c, h)+d(h, g)
Jurnal Penelitian dan Pengembangan TELEKOMUNIKASI, Desember 2005, Vol. 10, No. 2
97
dari node i dengan semua jalur tengahnya berada pada set {1,2,3,…k}. Ketika k = 0 maka rute terpendek dari node i ke node j tidak terdapat jalur tengah, sehingga definisi rekursif dari
Gambar 5. Jalur tengah dari node c ke node g melalui node h
dij0 min dijk 1 , dikk 1 d kjk 1 jika k ≥ 1 Hasil akhir yang diperoleh adalah d(i,j) yang merupakan bobot terkecil untuk semua rute dari node i ke node j, dimana i,j . Berdasarkan definisi rekursif , sebuah prosedur bottom-up (mencari dari nilai yang terkecil) dapat digunakan untuk mencari nilai dijk seiring dengan bertambahnya nilai k. Input yang dipakai adalah matriks bobot w, berukuran n x n yang didefinisikan pada Gambar 6. 0
W (i, j )
15 0
0 ij
nil jika i = j atau w(i,j) =
0 ij
i jika i ≠ j dan w(i,j) <
(2)
Untuk k ≥ 1, jika rute yang terpilih adalah i k j dimana k ≠ j maka predecessor j yang terpilih sama dengan predecessor j rute terpendek dari node k dengan semua jalur tengahnya berada pada set {1,2,3,…k-1}. Berikut adalah definisi rekursif untuk k ≥ 1:
Penghitungan yang dipakai algoritma floyd untuk mencari rute terpendek adalah dengan menggunakan metode rekursif. Bobot sebuah rute dari node i ke node j adalah dijk dengan k bernilai {1,2,3…k}. Jika k = 0 maka nilai dij0 w(i, j ) karena dari node i ke node j tidak terdapat jalur tengah yang dapat dibandingkan dengan bobot rute dari node i ke node j secara langsung, dengan w(i,j) adalah nilai bobot awal pada matriks yang pertama kali dibuat. Definisi rekursif yang terdapat pada algoritma floyd adalah sebagai berikut: (1) dij0 w(i, j ) jika k = 0
k ij adalah:
5.
k ij
k 1 ij
k ij
k 1 kj jika
jika
d ijk
1
d ikk 1
d kjk 1
d ijk
1
d ikk 1
d kjk 1
(3)
Algoritma Two Queues
Algoritma Graph growth implemented with two queues (TQQ) dikembangkan Pallotino pada tahun 1984. Algoritma TQQ menggunakan 2 set label untuk mengatur node-node yang diperiksa, Q1 dan Q2. Q1 merupakan set label prioritas yang berisi node yang telah melalui proses pemeriksaan setidaknya satu kali, dan Q2 merupakan set label non prioritas yang berisi node-node sisanya. Algoritma TQQ menggunakan dua buah queue sebagai struktur datanya dan pemilihan rutenya menggunakan FIFO. Kompleksitas dari algoritma ini adalah O(n²m) dengan n adalah jumlah node dan m adalah jumlah arc. Dengan menggunakan Gambar 2, dapat diberikan contoh penghitungan rute terpendek dari node A ke node G menggunakan algoritma two queues . Algoritma ini akan memeriksa satu persatu jarak dan successsor dari semua node, mulai node pertama (node ke-1) sampai node terakhir (node ken) secara iteratif.
8 1 0
5 3 0 5
5 4 0 2
0
12 0
Gambar 6. Representasi Floyd Menggunakan Matriks dengan Bobot Negatif Prosedur algoritma floyd akan menghasilkan matriks D yang merupakan matriks dengan nilai bobot antar node terkecil, kemudian membuat predecessor matriks dari matriks D. Bentuk dari matriks adalah berupa matriks 0, 1, 2, …, n dimana = n dan kij didefinisikan sebagai predecessor dari arc atau node j dan rute terpendek
Gambar 7. Hasil Penghitungan Rute Terpendek dengan Algoritma Two-Queues
Implementasi dan Analisa Algoritma Pencarian Rute Terpendek di Kota Surabaya (Yudhi Purwananto)
98
Node A akan diperiksa pertama kali sebagai node ke-1 maka jarak node A, d(A) = 0 dan node B serta F sebagai successor. Node B dan node F akan dimasukkan ke Q2 untuk diperiksa selanjutnya. Pada saat pemeriksaan, algoritma two queues juga melakukan pemberian label terhadap node-node yang nilai jaraknya berubah. Jika node yang nilai jaraknya berubah pernah diperiksa sebelumnya setidaknya satu kali maka node ini akan dimasukkan ke Q2 dan diberi label temporal, jika belum pernah diperiksa akan dimasukkan ke Q1 dan diberi label unreached. Proses ini akan terus berlangsung sampai Q1 dan Q2 kosong sehingga hasil akhir yang diperoleh merupakan rute terpendek dari node awal A ke node tujuan G, seperti ditunjukkan pada Gambar 7. 6.
Sumber Data
Data input yang diperlukan berupa data jaringan jalan yang direpresentasikan sebagai graph. Suatu pemodelan jalan memerlukan aturan-aturan tertentu agar sesuai dengan kondisi jalan yang direpresentasikannya. Ketika suatu segmen garis bertemu dengan segmen garis yang lain dan saling berinterseksi, maka terdapat tiga kemungkinan dari interseksi tersebut : a. Segmen-segmen garis tersebut benar-benar saling berinterseksi dan diperbolehkan untuk melakukan sembarang belokan dari segmensegmen garis yang berinterseksi tersebut. b. Segmen-segmen garis tersebut benar-benar saling berinterseksi, namun tidak diperbolehkan antar segmen garis tersebut untuk saling berhubungan, misalnya, melakukan belokan dari segmen garis yang saling berinterseksi. Hal ini dapat terjadi karena adanya aturan-aturan lalu lintas yang harus dipatuhi. c. Segmen-segmen garis tersebut tidak benar-benar saling berinterseksi. Hal ini karena suatu segmen garis dalam kondisi riil berada di atas segmen garis yang saling berinterseksi tersebut (misalnya, dalam memodelkan jalan tol yang berada di atas jalan yang lain).
Gambar 8 adalah contoh interseksi model kedua. Jalan Blauran berinterseksi dengan Jalan Bubutan, Jalan Kranggan, Jalan Baliwerti, dan Jalan Praban. Tetapi dari arah jalan Blauran hanya boleh mengarah ke jalan Praban atau jalan Bubutan, hal ini dikarenakan ada peraturan jalan yang melarang dari arah jalan Blauran belok ke arah jalan Kranggan. 7.
Uji Coba dan Evaluasi
Penggunaan perangkat pendukung yang membentuk purwarupa sistem layanan informasi pencarian rute terpendek untuk kota Surabaya dilakukan pada komputer dengan prosesor AMD Athlon 850MHz, memori 320 MB, hard disk 20 GB dan memori video 64 MB. Sedangkan lingkungan perangkat lunaknya adalah sistem operasi Microsoft XP Professional, Linux Mandrake 9.1, web server Apache, DBMS server MySQL Server Ver 11.15 Distrib 3.23.42-nt, dengan bahasa web scripting PHP v4.2.1, kompiler GCC dan web browser Internet Explorer 6.0. serta WAP browser M3Gate. Pada pengujian digunakan jaringan jalan kota Surabaya yang diperoleh dari Instansi Pemerintah Surabaya pada tahun 2000. Data jaringan jalan tersebut akan dibagi menjadi 6(enam) bagian yang berbeda jumlah total node dalam jaringan, jumlah arc, dan panjang arc, ditunjukkan pada Tabel 1. Uji coba dilakukan untuk mengetahui kecepatan eksekusi dari masing-masing algoritma penghitungan rute terpendek. Pada uji coba ini akan dipilih variabel-variabel yang mempunyai korelasi dengan algoritma penghitungan rute terpendek sehingga dapat diketahui variabel yang bisa mempengaruhi kecepatan eksekusi dari algoritma. Variabel-variabel ini antara lain : panjang jarak antar node, jumlah node yang diperiksa, dan jumlah node total dalam jaringan. Pada algoritma dijkstra akan diujicobakan menggunakan struktur data yang berbeda yaitu array dan priority queue. Hal ini bertujuan untuk mengetahui struktur data yang paling tepat untuk digunakan pada algoritma dijkstra. Pada algoritma floyd dan two queues struktur data yang digunakan adalah array karena input dan output dari perhitungan algoritma floyd dan two queues berbentuk array. a.
Percobaan 1: Uji Coba Berdasarkan Jumlah Node Tabel 1. Data Jaringan Jalan Kota Kota
Gambar 8. Pemodelan Belokan pada Salah Satu Ruas Jalan di Kota Surabaya
Jumlah Node
Jumlah Rasio Arc Arcs / Node
Panjang Panjang Arc Arc Maximum Minimum
SBY 1
285
336
1.18
2203 m
6m
SBY 2
457
571
1.24
2248 m
6m
SBY 3
589
857
1.45
3432 m
2m
SBY 4
697
1143
1.63
7640 m
2m
SBY 5
792
1429
1.80
7640 m
2m
SBY 6
863
1713
1.98
7640 m
2m
Jurnal Penelitian dan Pengembangan TELEKOMUNIKASI, Desember 2005, Vol. 10, No. 2
99
Uji coba dilakukan untuk mengetahui, apakah faktor jumlah node yang diperiksa dapat mempengaruhi waktu eksekusi program dengan membuat skenario jumlah node sama dalam jaringannya. Data yang digunakan hanya data Surabaya 4 – Surabaya 6. Data Surabaya 1 – Surabaya 3 tidak dapat digunakan karena sebagian besar node tidak terhubung antara satu dengan yang lainnya. Waktu eksekusi yang dicatat merupakan waktu eksekusi rata-rata dari 10 kali percobaan. Tabel 2 menampilkan hasil uji coba dengan data Surabaya 5, algoritma dijkstra memerlukan waktu eksekusi yang lebih lama ketika jumlah nodenya banyak Tabel 2. Hasil Uji Coba Berdasarkan waktu eksekusi SBY 4 (detik)
SBY 5 (detik)
SBY 6 (detik)
Lontar ke Indragiri
Node yang Dilewati 13
DJIKS + arr
0,09931
0,11666
0,13537
DJIKS + PQ
0,06108
0,07566
0,08293
FLOYD
4,31942
4,35703
4,40016
2-QUEUE
0,34336
0,61585
1,30520
Blauran ke Gajahmada
29
DJIKS + arr
0,10946
0,13056
0,13999
DJIKS + PQ
0,06119
0,07628
0,08334
FLOYD
4,31898
4,35515
4,39555
2-QUEUE
0,34071
0,59309
1,31564
Hangtuah ke Kandangan Jaya DJIKS + arr
0,12835
0,16135
0,16377
DJIKS + PQ
0,06815
0,07864
0,08733
FLOYD
4,32769
4,35708
4,41861
2-QUEUE
0,34733
0,64217
1,32175
55
Algoritma dijkstra dengan priority queue lebih cepat waktu eksekusinya dibandingkan dengan array. Waktu eksekusi algoritma floyd dan two queues tidak terpengaruh oleh penambahan jumlah node. Selisih waktu tercepat dan terlama pada algoritma floyd dan two queues adalah 0,03 detik, sedangkan pada algoritma dijkstra selisihnya adalah 0,07 detik. Pada data hasil uji coba Surabaya 6, peningkatan waktu eksekusi algoritma dijkstra dan floyd tidak terlalu signifikan dibandingkan dengan data Surabaya 5. Waktu eksekusi yang diperlukan algoritma two queues pada Surabaya 6 adalah dua kali waktu eksekusi pada Surabaya 5. Selisih waktu eksekusi tercepat dan terlama untuk algoritma dijkstra =0,05 detik, two queues= 0,1 detik ,dan untuk floyd = 0,01 detik. Hasil uji coba menggunakan Surabaya 5 dan Surabaya 6 pada algoritma dijkstra menunjukkan kecenderungan naik. Hal ini menggambarkan bahwa perbedaan jumlah node yang diperiksa berpengaruh terhadap waktu eksekusi. Pada algoritma floyd hasilnya cenderung stabil yang menggambarkan bahwa perbedaan jumlah node yang diperiksa tidak terlalu berpengaruh terhadap waktu eksekusi.
Sedangkan untuk algoritma two queues pada beberapa kasus mungkin terjadi peningkatan cukup tajam, seperti saat menghitung node 29 dengan data Surabaya 5, tapi hanya terjadi sesekali. Peningkatan waktu eksekusi dari node yang sedikit ke node yang banyak relatif kecil sehingga terlihat stabil. b.
Percobaan 2: Uji Coba Berdasarkan Jarak Antar Node yang Berbeda
Skenario ini hanya mengubah jarak antar node yang diperiksa, sedangkan jumlah node yang diperiksa dan jumlah node dalam jaringan yang diperiksa adalah sama. Uji coba dilakukan untuk mengetahui apakah faktor jarak yang dihitung dapat mempengaruhi waktu eksekusi program. Pada data Surabaya 2 akan melewati jumlah node yang sama sedangkan jarak yang diperiksa akan semakin panjang dibanding Surabaya 1. Untuk algoritma dijkstra dengan priority queue dan algoritma two queues waktu eksekusinya kurang dari 1 detik. Selisih waktu tercepat dengan terlamanya adalah 0,01 detik untuk algoritma dijkstra array ; 0,003 detik untuk algoritma dijkstra priority queue; dan 0,004 detik untuk algoritma two queues , sedangkan untuk algoritma floyd waktu eksekusinya berkisar 4 detik dengan selisih waktu 0,01 detik. Tabel 3. Hasil Uji Coba Berdasarkan Jarak SBY 1 (detik)
SBY 2 (detik)
SBY 3 (detik)
SBY 4 (detik)
SBY 5 (detik)
Tandes Utara ke Raya Tandes
SBY 6 (detik) 130 m
DJIKS + arr
0,08254
0,08602
0,09068
0,09092
0,10201
0,11447
DJIKS + PQ
0,04116
0,04743
0,05216
0,06102
0,07300
0,08246
FLOYD
4,20292
4,21615
4,29923
4,32750
4,35703
4,39690
2-QUEUE
0,03954
0,08442
0,16910
0,28363
0,70662
Praban ke Kranggan
1,31700 342 m
DJIKS + arr
0,08263
0,09436
0,09261
0,09960
0,10167
0,12041
DJIKS + PQ
0,03870
0,05112
0,05278
0,06139
0,07373
0,08226
FLOYD
4,20434
4,22942
4,29424
4,32264
4,35515
4,40105
2-QUEUE
0,03561
0,08511
0,16801
0,32173
0,59188
Ketintang Selatan ke Ketintang Madya
1,30071 779 m
DJIKS + arr
0,08122
0,09671
0,08863
0,09899
0,09893
0,11220
DJIKS + PQ
0,03766
0,04840
0,05130
0,06101
0,07309
0,08226
FLOYD
4,15336
4,21766
4,29112
4,32836
4,36208
4,40874
2-QUEUE
0,04344
0,08754
0,16393
0,32121
0,62777
Semolowaru Tengah ke Klampis Harapan
1,31900 1325 m
DJIKS + arr
0,07625
0,08442
0,09628
0,09109
0,09547
0,11354
DJIKS + PQ
0,03836
0,04819
0,05251
0,05872
0,07334
0,08273
FLOYD
4,20021
4,22633
4,28872
4,32617
4,35232
4,40495
2-QUEUE
0,03411
0,08371
0,16445
0,34290
0,68356
Lidah Kulon ke Raya Menganti
1,36430 2203 m
DJIKS + arr
0,07917
0,08558
0,09144
0,09301
0,10100
0,11270
DJIKS + PQ
0,04241
0,04752
0,05121
0,05954
0,07327
0,08169
FLOYD
4,20533
4,22142
4,29262
4,33026
4,36538
4,39595
2-QUEUE
0,03614
0,08517
0,16713
0,34733
0,63216
1,38570
Uji coba menggunakan data Surabaya 3, waktu eksekusi algoritma dijkstra dan two queues tetap kurang dari 1 detik dengan selisih waktu 0,01 detik untuk algoritma dijkstra array; 0,0018 untuk
Implementasi dan Analisa Algoritma Pencarian Rute Terpendek di Kota Surabaya (Yudhi Purwananto)
100
algoritma dijkstra priority queue; dan 0,004 detik untuk algoritma two queues . Jika dibandingkan waktu eksekusi algoritma two queues menggunakan data Surabaya 2 dengan data Surabaya 3 terdapat peningkatan yang cukup signifikan, sekitar 2 kali lipat untuk penambahan jumlah node dalam jaringan. Waktu eksekusi yang diperlukan floyd tetap sekitar 4 detik, dengan selisih waktu terlama dan tercepatnya 0,01 detik. Waktu eksekusi yang diperlukan algoritma two queues pada Surabaya 5 adalah 2 kali waktu eksekusi pada Surabaya 4. Pada data Surabaya 6 waktu eksekusi algoritma dijkstra masih berkisar kurang dari satu detik, yaitu 0,12 detik, dengan selisih waktu tercepat dan terlamanya adalah 0,01 detik. Waktu eksekusi dari algoritma two queues sekitar 2 kali lipat dari Surabaya 5, yaitu berkisar pada 1,3 detik dengan selisih antara waktu tercepat dan waktu terlamanya adalah 0,08 detik. Pada algoritma floyd waktu eksekusinya sekitar 4,4 detik dengan selisih antara waktu tercepat dan waktu terlamanya adalah 0,03 detik. Hasil uji coba pada Tabel 3 menunjukkan kecenderungan bergerak stabil. Sehingga faktor jarak antar node yang dihitung dapat diabaikan karena tidak berpengaruh signifikan terhadap waktu eksekusi. c.
Percobaan 3: Uji Coba Kebenaran Hasil Tabel 4. Hasil Uji Coba Kebenaran SBY 4 (meter) SBY 5 (meter) SBY 6 (meter) Blauran ke Mayjen Sungkono DJIKS + arr
18.682
5.096
DJIKS + PQ
18.682
5.096
3.692
FLOYD
18.682
11.124
9.086
18.682
5.096
3.692
2-QUEUE
3.692
Blauran ke Gajahmada 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
Pabean ke Kedung Mangu DJIKS + arr
14.229
13.393
DJIKS + PQ
14.229
13.393
5.096
FLOYD
14.229
13.393
8.729
14.229
13.393
5.096
2-QUEUE
5.096
Blauran ke Rungkut Madya 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
Berikutnya akan diamati hasil rute terpendek yang diperoleh dari masing-masing algoritma penghitungan dengan data jaringan jalan Surabaya 4 – Surabaya 6, sehingga dapat diketahui algoritma yang dapat menghasilkan rute terpendek dibanding algoritma lain. Pada Tabel 4 panjang rute yang dihasilkan tidak sama antara algoritma yang satu dengan yang lain. Jarak yang dihasilkan masing-masing algoritma penghitungan rute terpendek menggunakan data Surabaya 4 adalah sama, sedangkan dengan data Surabaya 5, kemampuan setiap algoritma menemukan rute terpendek berbeda-beda. Pada semua kasus menggunakan data Surabaya 5, dijkstra menemukan rute paling pendek. Dijkstra dan two queues memberikan jarak rute terpendek yang sama pada semua kasus uji coba menggunakan data Surabaya 6. Hasil penghitungan menggunakan algoritma dijkstra array tidak berbeda dengan algoritma dijkstra priority queue. d.
Uji coba kemampuan bertujuan untuk mengetahui batasan kemampuan dari masing-masing algoritma untuk melakukan penghitungan rute terpendek. Dari hasil uji coba yang telah dilakukan terhadap masing-masing algoritma penghitungan rute terpendek menggunakan data jaringan jalan utama Indonesia dengan jumlah node mencapai 4200 dan jumlah arc lebih dari 6000, algoritma floyd sama sekali tidak mampu melakukan penghitungan rute terpendek. Algoritma dijkstra hanya mampu melakukan penghitungan rute terpendek pada sebagian kecil kasus yang diujicobakan, sedangkan algoritma two queues mampu menyelesaikan semua kasus yang diujicobakan dengan waktu eksekusi program rata-rata berkisar pada 15 detik. Uji coba kemampuan juga dilakukan dengan melihat penggunaan memori dari masing-masing algoritma penghitungan rute terpendek dengan data Surabaya 1 – Surabaya 6, dicatat menggunakan fungsi khusus yang dibuat dalam bahasa pemrograman C. Fungsi tersebut akan mencatat ID eksekusi untuk mendapatkan log penggunaan memorinya. Hasil uji coba penggunaan memori dicatat pada Tabel 5. Tabel 5. Penggunaan Memori pada Uji Coba
Hangtuah ke Wonokromo DJIKS + arr
29.542
15.288
7.129
DJIKS + PQ
29.542
15.288
7.129
FLOYD
29.542
18.227
7.129
29.543
15.288
7.129
2-QUEUE
Percobaan 4: Uji Coba Kemampuan
Iskandar Muda ke Kebonsari 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
Hangtuah ke Kandangan Jaya
8.
DJIKS + arr
30.707
16.748
DJIKS + PQ
30.707
16.748
9.956
FLOYD
30.707
16.748
15.892
2-QUEUE
30.707
16.748
9.956
Kesimpulan
9.956
Jurnal Penelitian dan Pengembangan TELEKOMUNIKASI, Desember 2005, Vol. 10, No. 2
101
8.
Kesimpulan
Untuk studi kasus kota Surabaya, waktu eksekusi pada algoritma dijkstra, algoritma floyd, dan algoritma two queues, tidak terpengaruh oleh variabel jarak yang diperiksa. Dari hasil rute terpendek yang diperiksa, kinerja algoritma dijkstra lebih baik daripada dua algoritma penghitungan rute terpendek yang lainnya. Hal ini terlihat dari waktu eksekusi yang diperlukan oleh algoritma dijkstra dan algoritma two queues berbanding quadratic dengan jumlah node yang diperiksa, sedangkan untuk algoritma floyd waktu eksekusinya berbanding cubic dengan pertambahan jumlah node dalam jaringan. Untuk suatu kasus data yang memerlukan penghitungan kurang dari 1000 node, algoritma dijkstra mempunyai kecepatan eksekusi lebih baik, yaitu kurang dari 1 detik. Untuk suatu kasus data yang memerlukan penghitungan lebih dari 1000 node, algoritma two queues lebih tepat untuk digunakan. Waktu eksekusi dari algoritma label correcting lebih stabil, tidak terpengaruh oleh jumlah node yang diperiksa, tetapi lebih ditentukan oleh jumlah node dalam jaringan. Penggunaan struktur data priority queue pada algoritma dijkstra pemakaian space memorinya lebih kecil dibanding dengan pemakaian struktur data array. 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.
Implementasi dan Analisa Algoritma Pencarian Rute Terpendek di Kota Surabaya (Yudhi Purwananto)
