Transkrip ada setelah tampilan file!
Baihaqi Muhammad 1, Estherina Rahmawati 2, Hafid Nugroho 3, Ragil Sakti4
Fakultas Ilmu Komputer, Universitas Dian Nuswantoro Semarang
Jl. Imam Bonjol No.217 Semarang, telp. (024) 3569196
e-mail: [email protected]1, [email protected]2, [email protected]3, [email protected]4
ABSTRAK
Informasi geografis sangat diperlukan seperti halnya peta yang memudahkan mendapatkan informasi serta akses menuju lokasi yang diinginkan, dan untuk mencari lintasan terpendek dari lokasi yang diinginkan seperti daerah wisata, dibutuhkan implementasi dari algoritma Dijkstra. Secara spesifik penelitian ini menggunakan algoritma Dijkstra dalam proses analisa kemungkinan rute yang ditemukan untuk mengetahui tingkat strategis lingkungan Universitas Dian Nuswantoro. Algoritma Dijkstra bertujuan menemukan jalur terpendek untuk mencapai setiap pusat perbelanjaan. Hasil pengamatan dan pengujian ini dilakukan sebatas analisa terhadap kemungkinan rute yang dapat dijangkau sesuai keadaan lingkungan geografis pada umumnya, tidak mempertimbangkan adanya hambatan seperti perbaikan jalan raya, kemacetan, dan kontruksi jalan.
Kata kunci: algoritma, Dijkstra, implementasi, graf berarah, jalur terpendek
ABSTRACT
Geographic information is very necessary, such as maps that make it easier to get information and access to the desired location, and to find the shortest path from the desired location such as tourist areas, the implementation of the Dijkstra algorithm is needed. Specifically, this study uses the Dijkstra algorithm in the process of analyzing the possible routes found to determine the strategic level of the Dian Nuswantoro University environment. Dijkstra algorithm aims to find the shortest path to reach each shopping center. The results of this observation and test are limited to an analysis of possible routes that can be reached according to the general geographical environment, not considering obstacles such as road repairs, congestion, and road construction.
Keyword: algorithm, Dijkstra, implementation, directed graph, shortest path
Daftar Isi
I. PENDAHULUAN
Di era yang modern saat ini, perkembangan teknologi sangat cepat dan tak terkendali. Dimana penggunaan internet sangat mempermudah kegiatan manusia sehari-hari, seperti pencarian data, komunikasi, serta pencarian suatu lokasi. Pemanfaatan internet dalam pencarian suatu lokasi sangat dibutuhkan masyarakat dengan mobilitas yang tinggi dan kurang paham rute-rute daerah tertentu. [1]
Informasi geografis sangat diperlukan seperti halnya peta yang memudahkan mendapatkan informasi serta akses menuju lokasi yang diinginkan, dan untuk mencari lintasan terpendek dari lokasi yang diinginkan seperti daerah wisata, dibutuhkan implementasi dari algoritma Dijkstra. [1]
Pemanfaatan peta untuk mencari jalan dan rute dengan tujuan tertentu sudah berbentuk aplikasi yang memanfaatkan database untuk menyimpan setiap kemungkinan rute yang ada seperti pada penelitian [1], [2]. Penggunaan algoritma Dijkstra membuat kemungkinan jalan dan rute yang ditempuh menjadi semakin pendek seperti yang dijelaskan pada penelitian [1], [2]. [3]
Penggunaan Google Maps sebagai acuan jalanan dan rute yang ada seperti halnya pada penelitian [3] yang membandingkan kegunaan algoritma Dijkstra [2], [3], [4]. Untuk mengumpulkan kemungkinan rute agar ditemukannya rute yang optimal secara terdistribusi diperlukan metode normalisasi vektor (Vector Normalization Technique) [4]. Dengan membandingkan bagaimana algoritma Dijkstra digunakan pada aplikasi seperti pada penelitian [1], [2], hal ini digunakan untuk mengetahui efektivitas algoritma untuk menemukan rute yang ada pada dunia nyata. [3]
Secara spesifik penelitian ini menggunakan algoritma Dijkstra dalam proses analisa kemungkinan rute yang ditemukan untuk mengetahui tingkat strategis lingkungan Universitas Dian Nuswanoro. Penelitian ini bermanfaat sebagai bahan pertimbangan kepada mahasiswa untuk tinggal di lingkungan sekitar kampus. Paparan latar belakang telah disampaikan pada paragraf-paragraf diatas yang selanjutnya diikuti dengan bahasan metode penelitian dan pembahasan. Kesimpulan terdapat pada bagian akhir laporan penelitian
II. METODE PENELITIAN
A. Studi Literatur
Diawali dengan meninjau penelitian-penelitian terdahulu yang berkaitan dengan algoritma Dijkstra beserta implementasi-nya sebagai referensi yang diambil dari buku, paper, jurnal, makalah, dan beberapa sumber lainnya.
B. Observasi
Dilakukan pengamatan secara daring menggunakan aplikasi Google Maps sebagai penunjang dalam perancangan rute. Rute ditentukan dengan mengamati jalur yang memungkinkan untuk mencapai setiap pusat perbelanjaan di Kota Semarang yang mengitari Universitas Dian Nuswantoro. Bersamaan dengan itu, ditentukan juga jarak dan arah jalur yang melewati setiap titik jalur.
C. Analisa
Dari hasil pengamatan, mencermati kemungkinan adanya permasalahan yang ditemui, kebutuhan yang perlu ditambahkan, dan adanya batasan-batasan yang perlu digarisbawahi.
D. Perancangan Graf
Dari hasil rute yang telah dirancang kemudian ditranslasikan ke dalam bentuk graf berarah. Setiap titik acuan pada jalur yang telah ditandai akan dijadikan sebagai simpul dan jalur menghubungkan setiap titik akan dijadikan sebagai sisi.
E. Implementasi Dijkstra
Dilakukan pengujian terhadap graf berarah untuk mencari rute terpendek untuk setiap titik yang dituju menggunakan algoritma Dijkstra.
F. Evaluasi
Dari hasil pengujian, data dikumpulkan dan dilaporkan secara tertulis. Dari hasil pengujian juga dapat ditentukan adanya manfaat yang diberikan, serta adanya kekurangan yang memungkinkan untuk diperbaiki, baik dari sisi pengamatan maupun pengimplementasiannya.
III. LANDASAN TEORI
A. Algoritma Greedy
Dalam salah satu karya milik Charles Dickens yang juga diadaptasi dalam bentuk film oleh Disney yang berjudul A Christmas Carol, disebutkan terdapat karakter bernama Ebenezer Scrooge yang dikenal sebagai karakter paling serakah. Hasratnya selalu meraup semua emas dengan rakusnya. [8]
Algoritma greedy memiliki cara kerja yang sama dengan Ebenezer Scrooge, dimana algoritma ini mengambil objek secara berurutan dan diambilnya yang dianggap “terbaik” menurut beberapa kriteria tanpa mempedulikan pilihan yang telah diambil dan akan diambil. Algoritma ini memberikan pemecahan masalah dengan mengambil pilihan dengan nilai maksimal. Diharapkan dari setiap pilihannya yang diambil secara lokal dapat dihasilkan solusi yang paling optimal secara global. [8]
Algoritma Greedymengambil semua data dalam masalah tertentu, dan kemudian menetapkan aturan untuk elemen mana yang ditambahkan ke solusi pada setiap langkah algoritma. Dari kumpulan data tersebut diambil data dengan bobot terbesar sesuai aturan yang telah ditetapkan pada setiap bagian dalam permasalahan tertentu. [8]
B. Graf
Graf adalah himpunan simpul (vertices atau node) dan himpunan sisi (edges ataur arcs) yang masing-masing menghubungkan sepasang simpul. [1]
Graf terbagi atas 2 macam, yaitu Graf Tak-Berarah dan Graf Berarah. Perbedaan dari kedua graf tersebut adalah pada graf berarah sisi yang menghubungkan simpul memiliki arah tujuan sedangkan graf tak-berarah tidak. [1]
C. Minimum Spanning Tree
Misal sebuah kantor utama yang ingin menghubungkan jalur komunikasi dengan beberapa kantor cabang menggunakan saluran telepon. Saluran telepon membutuhkan biaya sewa, sambungan saluran telepon yang merentang menghubungkan antar kantor membentuk pohon dan untuk menghemat biaya sewa saluran diperlukan menghapus beberapa sambungan tanpa perlu kehilangan konektivitas. [5]
Minimum Spanning Tree (MST) dari graf berbobot adalah spanning tree yang memiliki jumlah bobotnya tidak lebih besar atau paling minimum dari bobot spanning tree lainnya. [5]
D. Shortest Path
Ketika berkendara di suatu jalanan pasti selalu bertemu dengan persimpangan, begitu juga ketika ingin menuju suatu tempat atau titik pasti akan menemui berbagai persimpangan. Lalu bagaimana cara tercepat menuju titik tersebut? Jika berpikir secara bruteforce maka dengan mengecek setiap rute yang dilalui lalu memilih rute terpendek, namun cara tersebut tidak terlalu efisien karena akan menghasilkan banyak rute.[1], [6]. Cara yang lebih efisien adalah dengan menemukan rute terpendek yang terhubung di setiap titik simpangan dari titik awal hingga titik tujuan. Ini disebut sebagai Shortest Path.[6]
Shortest Path dari suatu simpul menuju simpul lainnya adalah graf berarah dengan sisi dari simpul satu ke simpul lainnya memiliki sifat bahwa tidak ada sisi lain yang memiliki panjang yang lebih pendek.[1], [6]
Shortest Path bertujuan menemukan setiap sisi yang menghubungkan simpul sehingga jumlah panjang sisi dari simpul awal hingga simpul tujuan dapat diminimalkan. Untuk meminimalkannya, sisi dari simpul awal ke setiap simpul yang dituju merupakan sisi terpendek. [2], [3], [6]
E. Algoritma Dijkstra
Algoritma Dijkstra merupakan sebuah algoritma yang dipakai dalam memecahkan permasalahan Shortest Path dalam graf berarah. Algoritma ini dipublikasikan pada tahun 1959 jurnal Numerische Mathematik yang berjudul “A Note on Two Problems in Connexion with Graphs” oleh Edsger Dijkstra. [7]
Algoritma Dijkstra bertujuan menemukan panjang sisi terpendek di antara kedua simpul dalam graf berarah. [7]
Algoritma Dijkstra memiliki cara kerja sebagai berikut.
- Tentukan satu simpul sebagai simpul awal.
- Beri panjang sisi pada setiap simpul yang berdekatan dengan simpul awal.
- Dijkstra akan mengadaptasi pencariannya dari satu simpul ke simpul lain.
- Set jarak simpul awal dengan nilai 0 dan simpul yang belum dilewati dengan nilai tak hingga.
- Tentukan panjang sisi terpendek pada simpul awal dengan simpul-simpul yang berdekatan, lalu set simpul dengan jarak terpendek sebagai simpul yang telah dilewati dan nilai panjang sisinya.
- Lakukan secara berulang pada simpul-simpul berdekatan terhadap simpul terakhir yang telah dilewati hingga mencapai simpul tujuan.
IV. TINJAUAN PUSTAKA
Penelitian ini terinspirasi dari jurnal [1], [2] berisi tentang implementasi algoritma Dijkstra untuk menemukan jalur tercepat dan rute terpendek. Dimana pada [1] mengimplementasikan algoritma djikstra untuk menemukan jalur tercepat dalam mengunjungi setiap lokasi tempat-tempat umum. Sedangkan pada [2] mengimplementasikan algoritma Dijkstra dalam bentuk aplikasi untuk menemukan rute terpendek untuk mencapai lokasi Museum Nasional di Jakarta.
Penelitian ini juga terinspirasi dari [3] yang berisi tentang pengkajian ulang penelitian-penelitian terdahulu terkait pengaplikasian Algortima Dijkstra dalam berbagai masalah. Dalam [3] menyimpulkan bahwa penggunaan Algoritma Dijkstra dalam pemecahan masalah dengan cara, biobjective shortest path (BSP), penentuan jalur multi-objective, graf Dijkstra, evakuasi darurat, permasalahan fuzzy, integrasi dengan fitur location-based service (LBS), dan distribusi rute optimal.
Pada penelitian [4] melakukan komputasi yang berbeda antara parameter biaya dan keuntungan untuk normalisasi data pada pengimplementasian dalam menemukan rute distribusi paling optimal.Hal ini mempengaruhi penelitian yang kami lakukan untuk menemukan rute yang paling optimal.
Penambahan teori diperlukan sebagai penunjang mengenai beberapa istilah dan teori yang digunakan pada penelitian ini. Seperti pada artikel [5-8] yang menjelaskan mengenai graf, MST (Minimum Spanning Tree), dan algoritma Dijkstra.
V. PEMBAHASAN
Paparan berikut ini menjelaskan proses penelitian mengenai letak pusat perbelanjaan pada lingkungan UDINUS dengan radius 3000 m dengan menerapkan algoritma Dijkstra untuk mengetahui rute terpendek. Tahapan mapping hingga menentukan letak strategis kampus dipaparkan mengikuti penelitian model pengerjaan rute terpendek pada setiap tujuan akhirnya.
A. Pemetaan dan Simpul
Sebelum mengerjakan algoritma Dijkstra untuk mengetahui lintasan terpendek, diperlukan bentuk graf yang terdiri dari simpul dan lengan. Paparan rinci mengenai pemetaan pusat perbelanjaan dan jalan dapat dilihat pada Gambar 1:
Dengan penentuan simpul yang ditetapkan dapat dilihat pada Tabel 1:
Tabel 1. Simpul
| Simpul | Nama Tempat | Jenis |
|---|---|---|
| X | Kampus Universitas Dian Nuswantoro | Kampus |
| A | Indomaret Taman Madukoro | Minimarket |
| B | Indomaret Point Indraprasta | Minimarket |
| C | Alfamart Indraprasta 1 | Minimarket |
| D | ADA Swalayan | Swalayan.dan Grosir |
| E | Indomaret Indraprasta | Minimarket |
| F | Alfamart Indraprasta 2 | Minimarket |
| G | Pasar Bulu | Pasar |
| H | Indomaret Imam Bonjol 1 | Minimarket |
| I | DP Mall Semarang | Mall |
| J | Indomaret Imam Bonjol 2 | Minimarket |
| K | Superindo Imam Bonjol | Swalayan.dan Grosir |
| L | Mall Paragon City Semarang | Mall |
| M | Queen City Mall Pemuda Semarang | Mall |
| N | Pasar Johar | Pasar |
| S1 | Taman Madukoro | Bundaran Taman |
| S2 | Tugu Muda | Bundaran Tugu |
| S3 | Lampu lalu lintas Imam Bonjol | Lampu lalu lintas |
| S4 | Pertigaan Stasiun Poncol | Lampu lalu lintas |
| S5 | Bundaran LAmpu Merah Paragon | Bundaran lampu lalu lintas |
| S6 | Pertigaan Imam Bonjol (depan Kantor Grab) | Pertigaan |
| S7 | Lampu lalu lintas Pemuda | Lampu lalu lintas |
| S8 | Lampu lalu tintas Imam Bonjol (Kota lama - Johar) | Lampu lalu lintas |
| S9 | Lampu lalu lintas Johar | Lampu lalu lintas |
B. Pemetaan Simpul ke Dalam Bentuk Graf
Untuk mengetahui rute berdasarkan graf diperlukan lengan simpul (Jalur/Path). Untuk penggunaan jalur antar simpul, sesuai dengan nama jalan yang dilalui oleh simpul. Bentuk graf tidak memerlukan background mengenai lingkungan sekitar dan hanya mengandalkan simpul dan lengannya. Paparan mengenai bentuk graf dan simpul dapat dilihat pada Gambar 2. Setelah mengetahui bentuk graf seperti Gambar 2 dapat ditentukan bobot lengan berdasarkan jarak antar titik menggunakan aplikasi google maps untuk mengetahui jarak sebenarnya. Untuk bobot yang digunakan dipaparkan bersamaan dengan Gambar 2.
C. Penggunaan Algoritma Dijkstra
Untuk menentukan rute terdekat terhadap titik awal X (Universitas Dian Nuswantoro) dengan titik tujuan A, B, C, D, E, F, G, H, I, J, K, L, M, N diperlukan beberapa kali percobaan untuk mengetahui setiap kemungkinan jalur yang dapat dilalui. Ketika ada rute yang lebih dekat daripada rute yang pernah kita temukan, berdasarkan pengertian algoritma greedy maka penentuan rute dimulai dari titik awal dan tidak boleh kembali (backtracking). Hasil penentuan rute berdasarkan simpul dan jarak (bobot graf) terdekat dapat dilihat pada Tabel 2 dibawah ini:
| Titik Awal | Titik Tujuan | Rute Simpul | Jarak | Total |
|---|---|---|---|---|
| X | A | X - H - S3 - S5 - L - I - S2 - G -D - S1 - A | 400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 85 | 3425 |
| X | B | X - H - S3 - S5 - L - I - S2 - G -D - S1 - A - B | 400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 85 + 250 | 3675 |
| X | C | X - H - S3 - S5 - L - I - S2 - G -D - S1 - A - B - C | 400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 85 + 250 + 130 | 3805 |
| X | D | X - H - S3 - S5 - L - I - S2 - G -D | 400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 | 2740 |
| X | E | X - H - S3 - S5 - L - I - S2 - G -D - S1 - A - B - C - E | 4400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 85 + 250 + 130 + 350 | 4155 |
| X | F | X - H - S3 - S5 - L - I - S2 - G -D - S1 - A - B - C - E - F | 400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 85 + 250 + 130 + 350 + 150 | 4305 |
| X | G | X - H - S3 - S5 - L - I - S2 - G | 400 + 140 + 500 + 150 + 700 + 200 + 250 | 2340 |
| X | H | X - H | 400 | 400 |
| X | I | X - H - S3 - S5 - L - I | 400 + 140 + 500 + 150 + 700 | 1890 |
| X | J | X - H - S3 - K - J | 400 + 140 + 450 + 100 | 990 |
| X | K | X - H - S3 - | 400 + 140 + 450 | 890 |
| X | L | X - H - S3 - S5 - L | 400 + 140 + 500 + 150 | 1190 |
| X | M | X - H - S3 - S5 - S7 - M | 400 + 140 + 500 + 550 + 150 | 1740 |
| X | N | X - H - S3 - S5 - S7 - M -S9 -N | 400 + 140 + 500 + 550 + 150 + 300 + 200 | 2240 |
Berdasarkan hasil penerapan algoritma Dijkstra pada rute graf menunjukan bahwa pusat perbelanjaan berada pada jarak <5000m dengan moda transportasi roda 2 dan roda 4, dan penggunaan jalan searah membuat rute jalan menjadi lebih panjang. Dalam data rute Dijkstra diatas menunjukan bahwa di lingkungan kampus universitas dian nuswantoro dalam radius 3000m terdapat 14 pusat perbelanjaan yang dapat ditempuh dengan moda transportasi roda 2 dan roda 4 kurang dari 10 menit dengan ketentuan tidak adanya hambatan. Memungkinkan juga untuk rute yang digunakan terdapat beberapa hambatan seperti adanya perbaikan jalan raya, kemacetan, dan kontruksi jalan.
VI. KESIMPULAN
Berdasarkan hasil dan pembahasan yang telah dijabarkan pada bab sebelumnya dapat disimpulkan bahwa algoritma Dijkstra bisa menjadi solusi yang efisien dalam melakukan pencarian rute terpendek dari UDINUS menuju setiap pusat perbelanjaan dalam radius <3000 m di Kota Semarang. Secara spesifik penelitian ini dilakukan sebatas analisa terhadap kemungkinan rute yang dapat dijangkau sesuai keadaan lingkungan geografis pada umumnya, tidak mempertimbangkan adanya hambatan seperti perbaikan jalan raya, kemacetan, dan kontruksi jalan. Jika kita mengabaikan hal tersebut dapat dikatakan bahwa lingkungan kampus Universitas Dian Nuswantoro dapat dikatakan strategis dengan indikasi ±14 pusat perbelanjaan dalam radius <3000 m dan jarak tempuh rute <5000 m. Penempatan strategis juga dapat membantu untuk membuat keputusan bagi para mahasiswa untuk tinggal di lingkungan sekitar kampus.
REFERENCE
[1] Hasriandi, Rian, dan Lutfi A Muharrom. 2016. Implementasi Algoritma Dijkstra Untuk Pencarian Lintasan Terpendek Lokasi Tempat-Tempat Umum Di Kabupaten Bondowoso Berbasis Web. Undergraduate Thesis. Universitas Muhammadiyah Jember.
[2] Cantona, Aldy, Fauziah, dan Winarsih. 2020. Implementasi Algoritma Dijkstra Pada Pencarian Rute Terpendek ke Museum di Jakarta. Jurnal Teknologi dan Manajemen Informatika. Vol.6 No.1. Halaman 27-34.
[3] Hakim, Rasyid, DKK. 2021. Aplikasi Algoritma Dijkstra dalam Penyelesaian Berbagai Masalah. Jurnal Managemen Sistem Informasi dan Teknologi. Vol.11 No.1. Halaman 42-47.
[4] Rosita, Yesy, Erly Rosyida, Muhammad Rudiyanto. 2019. Implementation of Dijkstra Algorithm and Multi-Criteria Decision-Making for Optimal Route Distribution. Elsevier: Procedia Computer Science.161. pp.37-385.
[5] Sedgewick, Robert, and Kevin Wayne. 2018. “Minimum Spanning Tree”. Princeton University. https://algs4.cs.princeton.edu/43mst/. Diakses pada 8 Januari 2022 pukul 13.57
[6] Sedgewick, Robert, and Kevin Wayne. 2018. “Shortest Path”. Princeton University. https://algs4.cs.princeton.edu/44sp/. Diakses pada 8 Januari 2022 pukul 11.32
[7] Girsang, Abba Suganda. 2017. “Algoritma Dijkstra”. Binus University. https://mti.binus.ac.id/2017/11/28/algoritma-dijkstra/. Diakses pada 8 Januari 2022 pukul 09.57.
[8] Moore, Karleigh, Jimin Kim, and Eli Ross. 2022. “Greedy Algorithms”. Brilliant. https://brilliant.org/wiki/greedy-algorithm/. Diakses pada 8 Januari 2022 pukul 16.45.