Text
Pencarian Rute Terpendek Menggunakan Algoritma Dijkstra dan Algoritma Branch and Bound Dengan Menentukan Lokasi Awal dan Akhir Suatu Rumah Sakit Tertentu di Kota Semarang
ABSTRAK
Pada era globalisasi, teknologi komputer menjadi kebutuhan pokok dalam membantu kinerja
manusia. Peranan komputer sangat luas, seperti alat bantu hitung dan menjadi alat bantu
penyelesaian masalah yang dihadapi manusia. Metode komputasi dan teknologi informasi
semakin berkembang untuk membantu dalam menyelesaikan masalah routing, seperti penentuan
rute terpendek dan Travel Salesman Problem (TSP). Kota Semarang mempunyai banyak lokasi
rumah sakit. Letak rumah sakit di Kota Semarang berbeda-beda sehingga banyak pilihan rute
yang harus dipilih sesuai kebutuhan pengguna. Algoritma merupakan prosedur komputasi yang
mengubah dari sejumlah masukkan menjadi sejumlah keluaran. Algoritma Dijkstra merupakan
salah satu algoritma greedy yang dipakai dalam memecahkan permasalahan jarak terpendek
untuk sebuah graf berarah dengan bobot sisi yang bernilai positif. Algoritma Branch and Bound
merupakan sebuah teknik algoritma yang secara khusus mempelajari bagaimana cara
memperkecil search tree menjadi sekecil mungkin. Hasil akhir dari sistem ini berupa
perbandingan rute terpendek menggunakan algoritma Dijkstra dan algoritma Branch and Bound.
Hasil tersebut dipaparkan dalam bentuk visualisasi pada peta dan waktu eksekusi yang dilakukan
oleh kedua algoritma. Pengujian dilakukan menggunakan data lokasi rumah sakit yang didapat
dari Dinas Kesehatan Kota Semarang. Pada pengujian sistem dilakukan pengujian dengan
memasukkan titik awal dan titik akhir data asli menghasilkan rute yang sama pendek tetapi untuk
waktu eksekusi, algoritma Dijkstra lebih cepat dibanding algoritma Branch and Bound.
Kata Kunci : Algoritma Dijkstra, Algoritma Branch and Bound, Rute Terpendek
ABSTRACT
In globalization era, computer technology becomes a compulsory requirement on helping
human's works. The role of computer is very vast, from calculation tools to problem solving
tools for human. Computation method and information technology was growing to help for
solving routing problem, such as shortest route decision and the Travel Salesman Problem (TSP)
of Semarang has a lot of hospital location. The locations of hospital in Semarang are different, so
that there are so many routes choices that have to be decided as the human's needs. Algorithm is
a computation procedure which transforms inputs to outputs. Djikstra Algorithm is one of the
greedy algorithm that is used to solve the shortest route problem for a directed graph with the
positive value of side weights. Branch and Bound Algorithm is the algorithm technique which
specifically learns how to minimize search tree as little as possible. The final result of this
system was a comparison of the shortest route using Djikstra Algorithm and Branch-and-Bound
Algorithm. The result was visualized on map visualization and execution time of both algorithm.
The system test was done using the location data of the hospital from The Health Service of
Semarang. The system test was done by entering initial and final point from the original data
which resulted the route with the same length but different execution time, where Djikstra
algorithm was faster than Branch-and-Bound Algorithm.
Keyword : Djikstra Algorithm, Branch and Bound Algorithm, Shortest Route
418F16IV | 005.1 UTO p | Perpustakaan FSM Undip (Referensi) | Tersedia |
Tidak tersedia versi lain