ANALISA LETAK STRATEGIS KAMPUS UNIVERSITAS DIAN NUSWANTORO KOTA SEMARANG TERHADAP PUSAT PERBELANJAAN DI KOTA SEMARANG, METODE DIJKSTRA (SHORTEST PATH)

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

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:

Gambar 1.  Jalan dan Rute yang dilalui Kendaraan Roda 2 dan Roda 4

Dengan penentuan simpul yang ditetapkan dapat dilihat pada Tabel 1:

Tabel 1. Simpul

SimpulNama TempatJenis
XKampus Universitas Dian NuswantoroKampus
AIndomaret Taman MadukoroMinimarket
BIndomaret Point IndraprastaMinimarket
CAlfamart Indraprasta 1Minimarket
DADA SwalayanSwalayan.dan Grosir
EIndomaret IndraprastaMinimarket
FAlfamart Indraprasta 2Minimarket
GPasar BuluPasar
HIndomaret Imam Bonjol 1Minimarket
IDP Mall SemarangMall
JIndomaret Imam Bonjol 2Minimarket
KSuperindo Imam BonjolSwalayan.dan Grosir
LMall Paragon City SemarangMall
MQueen City Mall Pemuda SemarangMall
NPasar JoharPasar
S1Taman MadukoroBundaran Taman
S2Tugu MudaBundaran Tugu
S3Lampu lalu lintas Imam BonjolLampu lalu lintas
S4Pertigaan Stasiun PoncolLampu lalu lintas
S5Bundaran LAmpu Merah ParagonBundaran lampu lalu lintas
S6Pertigaan Imam Bonjol (depan Kantor Grab)Pertigaan
S7Lampu lalu lintas PemudaLampu lalu lintas
S8Lampu lalu tintas Imam Bonjol (Kota lama - Johar)Lampu lalu lintas
S9Lampu lalu lintas JoharLampu 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.

Gambar 2. Graf berbobot yang dibentuk dari mapping. Bobot Graf menggunakan satuan M sesuai dengan panjang jalan

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 AwalTitik TujuanRute SimpulJarakTotal
XAX - H - S3 - S5 - L - I - S2 - G -D - S1 - A400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 853425
XBX - H - S3 - S5 - L - I - S2 - G -D - S1 - A - B400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 85 + 2503675
XCX - H - S3 - S5 - L - I - S2 - G -D - S1 - A - B - C400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 85 + 250 + 1303805
XDX - H - S3 - S5 - L - I - S2 - G -D400 + 140 + 500 + 150 + 700 + 200 + 250 + 4002740
XEX - H - S3 - S5 - L - I - S2 - G -D - S1 - A - B - C - E4400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 85 + 250 + 130 + 3504155
XFX - H - S3 - S5 - L - I - S2 - G -D - S1 - A - B - C - E - F400 + 140 + 500 + 150 + 700 + 200 + 250 + 400 + 600 + 85 + 250 + 130 + 350 + 1504305
XGX - H - S3 - S5 - L - I - S2 - G400 + 140 + 500 + 150 + 700 + 200 + 2502340
XHX - H400400
XIX - H - S3 - S5 - L - I400 + 140 + 500 + 150 + 7001890
XJX - H - S3 - K - J400 + 140 + 450 + 100990
XKX - H - S3 -400 + 140 + 450890
XLX - H - S3 - S5 - L400 + 140 + 500 + 1501190
XMX - H - S3 - S5 - S7 - M400 + 140 + 500 + 550 + 1501740
XNX - H - S3 - S5 - S7 - M -S9 -N400 + 140 + 500 + 550 + 150 + 300 + 2002240

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.

Tinggalkan komentar