E-Jurnal Matematika Vol. 10(3), Agustus 2021, pp. 173-178

DOI: https://doi.org/10.24843/MTK.2021.v10.i03.p339

ISSN: 2303-1751

APLIKASI ALGORITMA DIJKSTRA UNTUK MENENTUKAN

RUTE TERPENDEK DARI KAMPUS A KE B UIN RADEN FATAH

Rendi Saputrama1§, Hartatiana2

1Pendidikan Matematika UIN Raden Fatah [Email: [email protected]] 2Pendidikan Matematika UIN Raden Fatah [Email: [email protected]] §Corresponding Author

ABSTRACT

Finding the shortest direction is one of the options that have been considered while traveling. One of the problems that occur for lecturers, staff, and students of UIN Raden Fatah is determining the shortest direction from Campus A to B. The application of graph theory by using Dijkstra's Algorithm becomes a solution for this problem. This algorithm has the advantage to minimize the expense of the costs by finding the shortest route from starting point to the destination. This study is applied research. The study will discuss the determination of the origin and destination end-point, traverse route, the calculation of the weight distance, analyzes the Dijkstra's iteration to determine the shortest route, and conclusion. As the result, the land route becomes the shortest route option from UIN Raden Fatah Campus A to B. The directed graph of the route represents the location as point, the road as the side, and distance as weight. The result shows that the route distance is 6.94 km using Dijkstra's Algorithm.

Keywords: Dijkstra's Algorithm, Graph, Shortest Route.

  • 1.    PENDAHULUAN

Dalam kehidupan sehari-hari manusia sebagai makluk sosial sering kali melakukan perjalanan dari suatu tempat ke tempat lainnnya. Kebutuhan akan hal ini menuntut adannya efisiensi dalam pemilihan lintasan terpendek dari suatu tempat ke tempat lainnya baik dari sisi efisiensi jarak, waktu, dan biaya yang dikeluarkan untuk mencapai tujuan tersebut. Penentuan rute terpendek dalam suatu perjalanan sudah banyak dibahas mulai dari tahun 1950 (Kusnia & Darmawan, 2017).

Pencarian rute atau lintasan terpendek ini telah diterapkan diberbagai bidang untuk mengoptimalisasi kinerja suatu sistem. Salah satu pencarian rute terpendek yang paling sering dibahas adalah pada permasalahan transportasi. Dalam perjalanan menuju tempat tujuan biasannya memiliki beberapa rute. Permasalahan yang biasa terjadi pada kota-kota besar seperti Jakarta dan Palembang dimana memiliki berbagai jenis transportasi umum yang menggunakan jalan raya, rel kereta api maupun Light Rail Transit (LRT). Tidak hanya dengan transportasi umum, pada kota-kota besar dipadati dengan kendaraan pribadi. Dari efek banyaknnya kendaraan pada area jalur sangat

menyulitkan kita untuk menempuh rute yang efisien. Selain itu, tidak semua orang dapat mengingat dengan baik rute yang harus dilewati dalam sebuah perjalanan dari titik awal keberangakatn menuju titik tujuan (Arifianto, 2012).

Universitas Islam Negeri (UIN) Raden Fatah Palembang berlokasikan di dua tempat yaitu kampus A dan kampus B. Kampus A berlokasi di Jl. Prof. Dr. Zainal Abidin Fikri KM. 3.5, dan Kampus B Berlokasi di kawasan Jakabaring (UIN Raden Fatah Palembang, 2021). Pada kasus pencarian jalur tercepat antar dua lokasi tersebut supaya mendapatkan efisiensi jarak, waktu, dan biaya bagi dosen dan mahasiswa UIN Raden Fatah Palembang, salah satu cara untuk mendapatkan jalur terpendek adalah dengan mengintepretasikan peta ke dalam suatu graf.

Pada bentuk graf, terdapat metode yang dapat digunakan untuk menentukan jarak terpendek. Metode yang digunakan untuk mencari jalur terpendek adalah Algoritma Dijkstra. Algoritma Dijkstra digunakan dalam bentuk graf berarah dimana setiap titik dihubungkan oleh sisi yang memiliki bobot. Dengan menggunakan perhitungan bobot pada

setiap sisi, algoritma ini dapat digunakan untuk menentukan jalur terpendek dari titik awal ke titik akhir (Puspika, dkk., 2012).

Keunggulan dari penggunaan Algoritma Dijkstra yakni meminimalisir biaya yang digunakan dari titik awal menuju titik tujuan dengan cara mencari rute terpendek. Algortma ini lebih intensif dalam komputasi untuk mencari rute optimum dalam suatu jaringan seperti internet dan jalan. Algoritma Dijkstra dapat membuat penggunaan waktu rata-rata eksekusi dengan Algoritma Dijkstra yang efisien, oleh karena itu Algoritma Dijkstra banyak digunakan dalam mencari jalur optimum (Gusmao, dkk., 2013).

Penentuan rute terpendek dipilih menggunakan Algoritma Dijkstra juga di dukung oleh penelitian yang telah di lakukan oleh peneliti dari luar negeri maupun dalam dalam negeri. Penelitian yang telah dilakukan oleh Jin-dong Zhang, dkk (2016) penelitian ini membahas tentang perencanaan dalam menentukan rute kendaraan pada area perkotaan agar dapat meminimalkan beberapa kebutuhan mencakup jarak, kecepatan, waktu mengemudi, arus perjalanan, dan konsumsi oli. Dengan menggunakan teknik penentuan titik awal dan titik akhir sebagai destinasi tujuan, algoritma Dijkstra membantu untuk mencarikan rute optimal yang layak dilalui pada peta secara otomatis. Kusnia & Darmawan (2017) penelitian ini membahas penggunaan Algoritma Dijktra untuk menentukan rute terpendek dari graf berbobot yang bobotnnya bernilai lebih besar dari nol, dari tirik awal dari semua titik yang dikehendaki, sehingga nantinya dapat ditemukan rute terpendek dari titik asal menuju titik akhir.

Berdasarkan pemaparan di atas, maka peneliti tertarik melakukan penelitian terkait rute jalur terpendek menggunakan algoritma Dijstra yang ditetapkan pada rute darat dari Kampus A ke Kampus B Universitas Islam Negeri (UIN) Raden Fatah Palembang, sehingga peneliti mengambil judul “Penerapan Algoritma Dijkstra Untuk Menentukan Rute Terpendek Jalur Lintas Darat Dari Kampus A Menuju Kampus B UIN Raden Fatah Palembang”.

  • 2.    METODE PENELITIAN

Jenis penelitian yang digunakan pada penelitian ini adalah Applied Reasearch (Penelitian Terapan). Penelitian terapan adalah penelitin yang mengkaji kenyataan praktis

dalam berbagai bidang. Selain itu, penelitian terapan memiliki posisi sebagai penelitian tentang penerapan ilmu yang dihasilkan dari penelitian dasar. Dalam penelitian ini dapat dilakukan pengujian tentang manfaat, mengetahui hubungan empiris antara teori dengan pelaksanaan di dunia praktis. Penelitian terapan berfungsi untuk mencari solusi tentang masalah-masalah tertentu. Tujuan utama penelitian terapan adalah pemecahan masalah sehingga hasil penelitian dapat dimanfaatkan untuk kepentingan manusia. Oleh karena itu, penelitian terapan tidak diarahkan menemukan teori baru, tetapi diarahkan pada pengembangan aplikasi baru dan penelitian yang ada. (Kusnia & Darmawan, 2017).

Algoritma Dijkstra bekerja dengan membuat jalan ke satu simpul maksimal pada tiap langkah.Jadi pada langkah ke- n, paling tidak terdapat nnodeyang telah kita ketahui jalan terpendek. Berikut ini urautan logika dari Algoritma Dijktra (Nurrizky, dkk., 2020).

  • 1.    Dari titik awal ke tiap titik yang lain diberikan nilai bobot (jarak), dengan metode menset nilai 0 pada node dini serta nilai tidak sampai terhadap node lain yang belum mempunyai bobot nilai.

  • 2.    Set node awal sebagai node keberangkatan setelah itu ukur jarak dari node awal ke tiap node yang ada.

  • 3.    Dari node keberangkatan, pertimbangkan node lain yang belum terhitung jaraknya dari titik keberangkatan. Misalnya, dengan nilai keberangkatan O ke A mempunyai nilai bobot jarak 3 serta dari A ke node D berjarak 2, hingga jarak ke D melewati A jadi 3+2=5.

  • 4.    Jarak dari setiap node ke node dihitung nilai bobotnya. Nilai jarak yang sudah tersimpan ialah nilai jarak terpendek terakhir sehingga tidak butuh mengulang informasi ke belakang.

  • 5.    Set node belum terjamah dengan jarak terkecil (dari node keberangkatan) sebagai node keberangkatan berikutnya serta lanjutkan dengan kembali ke step 3.

  • 3.    HASIL DAN PEMBAHASAN

Kegiatan yang pertama dilakukan peneliti adalah menentukan titik awal dan tujuan. Titik awal adalah tempat dimulainya perjalanan sedangkan titik tujuan adalah suatu tempat yang akan dituju. Pada penelitian ini titik origin titik awal yang diambil adalah Kampus A UIN Raden Fatah Palembang berlokasi di Jl. Prof. Dr. Zainal Abidin Fikri KM. 3.5, Pahlawan, Kecamatan

Kemuning, Kota Palembang dengan titik tujuan Kampus B UIN Raden Fatah Palembang berlokasi di Jl. Pangeran Ratu, 5 Ulu, Kec. Seberang Ulu 1, Jakabaring, Kota Palembang.

Gambar 1. Titik Origin (Titik Awal) Kampus A UIN Raden Fatah Palembang (diakses di http://maps.google.com)

Gambar 2. Titik Destinasi (Titik Akhir) Kampus B UIN Raden Fatah Palembang

(diakses di http://maps.google.com)

Kegiatan kedua peneliti menentukan titik-titik jalur yanga akan dilalui. Pada langkah ini peneliti menggunakan dari google maps untuk menentukan titik-titik jalur yang akan dilalui dari titik awal menuju titik tujuan.

Gambar 3. Jalur Pertama Melewati Jembatan

Ampera

(diakses di http://maps.google.com)

Gambar 4. Jalur Kedua Melewati Jembatan Musi VI (diakses di http://maps.google.com)

Gambar 5. Jalur Ketiga Melewati Jembatan Musi IV (diakses di http://maps.google.com)

Titik-titik jalur yang akan dilalui dibuat dengan pemetaan node untuk setiap lokasi beserta keterangan untuk mempermudah dalam memperesentasikannnya dalam berntuk graf berarah. Hal ini dapat dilihat pada tabel berikut:

Tabel 1. Titik Awal, Titik Tujuan, dan Jalur

Node

Tempat

Keterangan

O

Kampus A UIN Raden Fatah Palembang

Titik Awal

A

Pengadilan Tinggi Agama Islam Sumatera Selatan

Jalur

B

RSU YK Madira

Jalur

C

Restoran Pagi Sore (Depan RS Caritas)

Jalur

D

Apotik Mitra

Jalur

E

Dinas Sosial Sumatera Selatan

Jalur

F

Sudirman City Center – Ultima Horison

Jalur

G

Zeni Daerah Militer (Ziden) II Sriwijaya

Jalur

H

Bundaran Air Mancur Palembang

Jalur

I

Jembatan Gledek

Jalur

J

Universitas Syakhyakirti Palembang

Jalur

K

Jembatan Ampera

Jalur

L

Jembatan Musi 6

Jalur

M

Flyover Jakabaring

Jalur

N

Jembatan Musi 4

Jalur

O

Kampus Muhammadiyah

Jalur

P

RS Muhammadiyah Pelaju

Jalur

Q

Polresta Palembang

Jalur

R

Stasiun LRT Polresta

Jalur

S

Kampus B UIN Raden Fatah Palembang

Titik Tujuan

Kegiatan ketiga peneliti menentuka bobot dari setiap jarak yang ditemputh. Berdasarkan seluruh data yang didapat dari google maps selanjutnya data akan direpresentasikan menggunakan graf beraraf sebagai berikut:

Gambar 6. Pemetaan Jalur Origin (Titik Awal) Menuju Destinasi (Titik Tujuan)

Kemudian jarak tempuh atau bobot di representasikan dalam bentuk tabel dalam satuan kilometer (Km). Berikut ini ringkasan jalur tempuh atau bobot yang dilewati.

Tabel 2. Ringkasan Jalur Tempuh yang dilewati

Jalur/Rute

Jarak (Km)

O-A

0,30

A-B

0,93

B-C

0,52

B-E

0,44

E-G

2,30

C-D

0,88

C-F

0,39

D-H

0,58

G-J

1,59

I-N

1,07

H-K

0,38

J-L

0,69

N-O

2,12

K-M

1,23

L-M

3,06

O-P

0,43

P-M

0,60

M-Q

0,31

Q-R

0,36

R-S

1,45

Kegiatan keempat peneliti melakukan iterasi pembobotan jalur terpendek untuk sampai ke titik tujuan. Pada langkah ini peneliti melakukan iterasi perhitungan metode Algoritma Dijkstra secapa looping dari titik awal keberangkatan sampai dengan lokasi tujuan. Iterasi Algoritma Dijktra dilakukan dengan memperhatikan jalur atau rute terpendek perjalanan dari kamus A ke Kampus B UIN Rade Fatah Palembang.

Tabel 3. Iterasi Algoritma Dijktra

Iterasi

Jalur/Rute

Jarak (Km)

Total Jarak (Km)

1

O-A

0,30

6,94

A-B

0,93

B-C

0,52

C-D

0,88

D-H

0,58

H-K

0,38

K-M

1,23

M-Q

0,31

Q-R

0,36

R-S

1,45

2

O-A

0,30

11,43

A-B

0,93

B-E

0,44

E-G

2,30

G-J

1,59

J-L

0,69

L-M

3,06

M-Q

0,31

Q-R

0,36

R-S

1,45

3

O-A

0,30

9,87

A-B

0,93

B-C

0,52

C-F

0,39

F-I

1,39

I-N

1,07

N-O

2,12

O-P

0,43

P-M

0,60

M-Q

0,31

Q-R

0,36

R-S

1,45

Kegiatan kelima peneliti memilih jarur yang paling optimal (rute paling pendek). Dari perhitungan iterasi menunjukkan jalur O-A-B-C-D-H-K-M-Q-R-S merupakan jalur terpendek yang dapat ditempuh oleh pengendara yang mengunakan jalan raya dari titik awal (kampus A) untuk sampai ke titik akhir (Kampus B). Maka deskripsi jalur yang di tempuh pengendara sebagai berikut:

  • 1.    Kampus A UIN Raden Fatah Palembang

  • 2.    Pengadilan Tinggi Agama Islam Sumatera Selatan

  • 3.    RSU YK Madira

  • 4.    Restoran Pagi Sore (Depan RS Caritas)

  • 5.    Apotik Mitra

  • 6.    Bundaran Air Mancur Palembang

  • 7.    Jembatan Ampera

  • 8.  Flyover Jakabaring

  • 9.  Polresta Palembang

  • 10.    Stasiun LRT Polresta

  • 11.    Kampus B UIN Raden Fatah Palembang

Kegiatan keenam peneliti menarik kesimpulan. Setelah melakukan penelitian Peneliti menarik kesimpulan dalam penentuan rute terpendek perjalanan dari titik awal (Kampus A) menuju titik tujuan (Kampus B) yaitu dengan rute Kampus A UIN Raden Fatah Palembang → Pengadilan Tinggi Agama Islam Sumatera Selatan → RSU YK Madira → Restoran Pagi Sore ( Depan RS Caritas) → Apotik Mitra → Bundaran Air Mancur Palembang → Jembatan Ampera → Flyover Jakabaring → Polresta Palembang → Stasiun LRT Polresta → Kampus B UIN Raden Fatah Palembang. Jalur tersebut menunjukkan perjalanan dari titik awal menuju titik tujuan dengan jatak total 6,94 KM. Jalur terpendek yang didapat dapat memberikan keuntungan bagi pengendara dari sisi waktu menjadi lebih cepat, dari segi biaya dan jarak menjadi lebih optimal.

  • 4.    KESIMPULAN DAN SARAN

Jarak rute terpendek dari Kampus A menuju Kampus B UIN Raden Fatah Palembang adalah 6,94 KM. Penantuan ini dapat dilakukan dengan menentukan titik pada setiap jalur yang akan ditempuh. Titik yang sudah dibuat digunakan untuk menyelesaikan penentuan rute terpendek dengan menggunakan Algoritma Dijkstra.

Pada penelitian ini peneliti hanya meninjau untuk mendapatkan hasil keadaan realnya. Saran untuk penelitian ini agar dapat ditinjau dari berbagai aspek seperti faktor kemacetan, jenis kendaraan, muatan kendaraan, serta deskripsi ongkos biaya kendaraan.

DAFTAR PUSTAKA

Arifianto, S. (2012). Sistem Aplikasi Penentuan Rute Terpendek Pada Jaringan Multi Moda Transportasi Umum Menggunakan Algoritma Dijkstra. In Tesisi. Pasca Sarjana Universitas Diponogoro.

Gusmao, A., Pramono, S. H., & Sunaryo. (2013). Sistem  Informasi   Geografis

Pariwisata Berbasis Web Dan Pencarian Jalur  Terpendek Dengan  Algoritma

Dijkstra. 7(2), 125–130.

J.-d. Zhang, Y.-j. Feng, F.-f. Shi, G. Wang, B. Ma, R.-s. Li, and X.-y. Jia, “Vehicle routing in urban areas based on the oil consumption weight-dijkstra algorithm,” IET Intelligent Transport Systems, 10(7), 495–502.

Kusnia, N., & Darmawan, R. N. (2017).

Penerapan Algoritma Dijkstra Untuk Menentukan Rute Terpendek Jalur Lintas Darat Dari Alun-Alun Kota Banyuwangi Menuju Alun-Alun Kota Jember. Jurnal Pendidikan Matematika, 1(2), 22–30.

Nurrizky, M. F., Dwiagnes, S., & Anggraeni, N. F. (2020). Pencarian Rute Terpendek Pada Distribusi Raw Material Metode Djikstra Di PT. SHP. Jurnal Teknik:   Media

Pengembangan Ilmu Dan Aplikasi Teknik, 19(1), 34–39.

Puspika, B. N., Racmat, A., & Kurniawan, E. (2012). Implementasi Algoritma Dijkstra Daram penentuan Jalur. 8(2), 141–149.

UIN Raden Fatah Palembang. (2021, April 6). UIN Raden Fatah Palembang. Retrieved from UIN Raden Fatah Palalembang: https://radenfatah. ac. id/

Website Google Maps. http://maps.google.com

178