## Penerapan Algoritma Dijkstra dan Algoritma Semut pada Pendistribusian Barang

## Try Azisah Nurman
Universitas Islam Negeri Alauddin Makassar, try.azisah@uin-alauddin.ac.id

## Risnawati Ibnas
Universitas Islam Negeri Alauddin Makassar, risnawati.ibnas@uin-alauddin.ac.id

## Alfian Nurul Hidayat
Universitas Islam Negeri Alauddin Makassar, 60600117019@uin-alauddin.ac.id
ABSTRAK ,  Penelitian  ini  membahas  tentang  penentuan rute terpendek dalam penentuan pendistribusian barang pada pasar  Kalukuan,  Panciro  dan  Minasamaupa  dengan membandingkan Algoritma Dikstra dan Algoritma Semut . Tujuan penelitian ini adalah mengetahui hasil perbandingan antara Algoritma Dikstra dan Algoritma Semut. Berdasarkan hasil penelitian yang telah kami teliti bahwasanya algoritma yang  unggul  dalam  penentuan  pendistribusian  barang  dari sumber ketujuan adalah algoritma Dijkstra karena algoritma Dijkstra  memberikan  rute  tanpa  berulang  dan  menghemat banyak waktu untuk pedagang sampai ketujuan.
KataKunci : Algoritma, Dijkstra, algoritma Semut

## 1. PENDAHULUAN
Dengan  persaingan  yang  semakin  ketat  di dunia  perdagangan,  maka  diperlukan  strategi untuk mengoptimalkan dan menentukan efisiensi, penyederhanaan saluran distribusi barang dangan menghasilkan  pasar  yang  lebih  kompetitif  dan harga  komoditas,  ketika  produk  diproduksi  dan dikemas, maka kuncinya adalah mendistribusikan produk  ke  konsumen.  Penerimaan  konsumen terhadap suatu produk akan  sangat mengganggu proses lainnya.Jika produk tidak laku di pasaran, produksi akan dilarang atau bahkan dihentikan.
Seiring dengan berkembangnya ilmu, proses pendistribusian  barang  yang  terjadi  di  pasar Minasamaupa, Panciro dan Kalukuan didistribusikan  kebeberapa  tempat,  diatanranya Makassar  (pasar  Terong),  Maros  (Tramo), Barru(pasar Mattirowalle) dan Bone (pasar Sentral Watanpone)  dengan  alasan  memilih  tempat tersebut  karena  sayur-  sayuran  (sawi,  bayam, kangkung dan cemangi) tidak memiliki ketahanan dalam waktu yang lama.
Proses  distribusi  yang  dilakukan  para penjual  dan  pembeli  (pedagang) menggunakan sistem yang tidak jelas, sehingga dipandang perlu diterapkan metode pendistribusian dengan tujuan untuk  menghemat  waktu  dan  biaya  dalam
perjalanan yang dilewati oleh para pedagang. Ada beberapa metode yang dapat menyelesaikan kasus tersebut, diantaranya merupakan metode Konvensional dan metode Heuristik.
Metode konvensional merupakan algoritma yang  menggunakan  perhitungan  matematika normal,  salah  satu  algoritma  yang  digunakan adalah  algoritma  Dijkstra  sedangkan  metode heuristik merupakan algoritma kecerdasan buatan untuk  mencari  dan  menentukan  rute  terpendek, salah  satu  algoritma  yang  digunakan  adalah algoritma Semut.
Penelitian sebelumnya  yang dilakukan oleh (Surachmad  Pratama)  hasil  penelitian  yang diperoleh  dengan  membandingkan  algoritma Dijkstra dan Floyd Warshall menunjukkan bahwa algoritma  Dijkstra  lebih  optimal  karena  terbukti lebih  sedikit  menggunakan  memori  dan  waktu yang digunakan dalam proses pencarian rute lebih cepat.
2. TINJAUAN PUSTAKA
a. Definisi Grab
Grap  merupakan  diagram  yang  membahas informasi  tertentu  bila  diinterpretasikan  secara tepat.  Dalam    kehidupan      sehari-hari,  grap digunakan  untuk  menggambarkan  berbagai macam    struktur  yang  ada.  Tujuannya  adalah sebagai  visualisasi  objek-objek  agar  lebih dimengerti  [1].  Sebuah  grap  g  terdiri  dari  dua bagian:
a. Sebuah himpunan 𝑉 = 𝑉(𝐺) memiliki elemen- elemen yang dinamakan vertex , titik mode b. Sebuah  kumpulan 𝐸 = 𝐸(𝐺) merupakan pasangan  terurut  dari  verteks-verteks  yang berbeda dinamakan edge
Grap  dapat  ditentukan  dalam  bentuk 𝐺(𝑉, 𝐸) bila ingin menyatakan dua bagian dari 𝐺 [2]. Berdasarkan arah dan bobotnya, grap terbagi kedalam empat bagian,yaitu:
a. Grap  berarah  dan  berbobot:  tiap  busur
mempunyai anak panah dan bobot. Gambar 2.1 menunjukkan grap berarah dan berbobot yang terdiri
dari tujuh titik,yaitu titik A,B,C,D,E,F,G.  Titik  menunjukkan  arah  ke tititk B dan C,titik B menunjukan arah ke titik D dan titik C, dan seterusnya. Bobot antar titik A dan titik B yang telah diketahui.
Gambar 2.1 Grap berarah dan berbobot b. Grap  tidak  berarah  dan  berbobot  :  tiap  busur tidak mempunyai anak panah tetapi mempunyai  bobot.  Gambar  2.2  menunjukkan grap tidak berarah dan berbobot . Grap terdiri dari  tujuh  titik,  yaitu  titik 𝐴, 𝐵, 𝐶, 𝐷, 𝐸, 𝐹, 𝐺. Titik 𝐴 tidak menunjukkan arah ke titik 𝐵 dan 𝐶 , namun bobot antara titk 𝐴 dan titik 𝐵 telah diketahui. Begitu juga dengan titik yang lain
Gambar 2.2 Grap tidak berarah dan  berbobot c. Grap  berarah  dan  tidak  berbobot:  tiap  busur mempunyai  anak  panaha  yang  tidak  bebobot. Gambar  2.3  menunjukkan  grap  berarah  dan tidak berbobot.
Gambar 2.3 Grap berarah dan tidak  berbobot d. Grap  tidak  berarah  dan  tidak  berbobot:  tiap busur  tidak  mempunyai  anak  panah  dan  tidak berbobot
Gambar 2.4 Grap tidak berarah dan tidak  berbobot

## c. Permasalahan  optimasi
Pada  umumnya,  penyelesaian  masalah pencarian jaluir terpendek dapat dilakukan dengan menggunakan dua metode, yaitu metode konvensional  dan  metode  heuristik.  Metode konvensional  diterapkan  dengan  perhitungfan matematis  biasa,  sedangkan  metode  heuristik diterapkan dengan perhitungan kecerdasan buatan[3]
1. Metode Konvensional Metode konvensional merupakan metode yang menggunakan perhitungan matematis biasa. Metode konvensional yang biasa digunakan untuk melakukan pencarian rute terpendek ialah: algoritma Djikstra, algoritma Floyd- Warshall , dan algoritma Bellman-Ford[4]. 2. Metode haeuristik Metode  Heuristik  merupakan  sub  bagian  dari kecerdasan  buatan    yang  digunakan  untuk melakukan  pencarian  dan  optimasi.  Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam permasalahan optimasi diantaranya ialah: algoritma genetika, algoritma  Semut,  logika fuzzy jaringan  saraf tiruan,  pencarian  tabu, simulated  annealing , dan sebagainya[5].
Permasalahan  Rute  Terpendek  (Shortest  Path

## Problem)
Rute  terpendek  merupakan  suatu  jaringan pengarahan perjalanan dimana sesorang pengarah jalan ingin menentukan rute terpendek antara dua kota,berdasarkan  beberapa  rute  alternatif  yang tersedia, dimana titik  tujuan hanya satu[6].

## d. Algoritma Semut
Algoritma  Semut  diperoleh    dari  perilaku koloni  Semut  yang  dikenal            sebagai  sistem Semut.  Secara  alamiah  koloni  Semut  mampu menemukan rute terpendek dalam perjalanan dari sarang ke tempat-tempat sumber makanan. Koloni Semut  dapat  menemukan  rute  terpendek  antara sarang  dan  sumber  makanan  berdasarkan  jejak kaki  pada  lintasan  yang  telah  dilalui.  Semakin
banyak Semut yang melalui suatu lintasan, maka akan semakin jelas bekas jejak kakinya[7]. Hal ini akan  menyebabkan  lintasan  yang  dilalui  Semut dalam jumlah sedikit, semakin lama akan semakin berkurang  kepadatan  Semut  yang  melewatinya, atau  bahkan  akan  tidak  dilewati  sama  sekali. Sebaliknya  lintasan  yang  dilalui  Semut  dalam jumlah  banyak,  semakin  lama  akan  semakin bertambah  kepadatan  Semut  yang  melewatinya, atau  bahkan  semua  akan  melalui  lintasan tersebut[8].

## Algoritma Djisktra
Algoritma  Dijkstra merupakan  salah  satu varian  dari  algoritma greedy, yaitu  salah  satu bentuk  algoritma  populer  dalam  pemecahan persoalan  yang  terkait  dengan  masalah  optimasi. Sesuai dengan artinya yang secara harafiah berarti tamak  atau  rakus,  algoritma  greedy  ini  hanya memikirkan solusi terbaik yang akan diambil pada setiap langkah tanpa memikirkan konsekuensi ke depan[9].
Algoritma  Dijkstra  meggunakan  prinsip greedy dalam mencari solusi optimum pada setiap langkah yang dilalui. Algoritma ini membandingkan setiap nilai dari simpul pada satu level dan akan dibandingkan lagi untuk rute yang baru[10].

## 3. METODOLOGI
Jika  ditinjau  dari  segi  tempat  penelitian berlangsung, maka penelitian ini termasuk dalam kategori  peneliatian  lapangan,  karena  penelitian ini  dilakukan  di  pasar,  Sedangkan  jika  ditinjau dari  segi  hasil penelitian,  maka  peneltian  ini dikategorikan penelitian terapan.

## Objek Penelitian
Penelitian ini dilakukan di pasar Minasamaupa,  Panciro  dan  Kalukuan  yang  ada dikabupaten Gowa.

## Pengumpulan Data
Jenis  data  yang  digunakan  adalah  data kuantitatif,  yaitu  data  yang  berupa  jarak  yang diambil  dari  google  maps  dengan  penempatan pengambilan jarak berada dia pasar Minasamaupa, Panciro dan Kalukuan
Prosedur Penelitian Adapun prosedur penelitian dalam penelitian ini adalah :
1. Menentukan  sumber  dan  tujuan  dalam pendistribusian barang
2. Menggambarkan setiap
titik lokasi pendistribuan barang  kedalam bentuk grap. 3. Menentukan  jarak  tempu  masing  masing dengan  menggunakan  bantuan  pencarian  arah Google Maps.
4. Menentukan rute terpendek dengan menggunakan algoritma Dijktra. 5. Menentukan rute terpendek dengan menggunakan   algoritma   Semut.
6. Membandingkan    langkah 4 dan 5 untuk mendapatkan rute terpendek dalam
endistribusian barang (sayur) yang efektif. 7. Memperoleh  hasil  rute  terpendek  dalam pendistribusian barang
berdasarkan perbandingan  algoritma  Dijktra  dan  algoritma Semut.

## 4. HASIL dan PEMBAHASAN Penentuan Sumber dan Tujuan Barang Dalam Pendistribusian
Pada  umumnya  pencarian  rute  terpendek dilakukan  di  beberapa  rute  pendistribusian  dari ketiga pasar distribusi, yaitu pasar Kalukuan, pasar Panciro    dan  pasar  minasamaupa  dengan  tujuan untuk menghemat waktu dalam perjalanan menuju ketujuan dan mencagah terjadinya rute yang dapat membuat  para  pedagang  berputar-putar  diketiga pasar  tersebut.  Adapun  rute  pendistribusian  yang dimaksud adalah :
1. Pasar Terong (Makassar)
2. Pasar  Tramo (Maros)
3. Pasar Mattirowalle (Barru)
4. Pasar Palakka (Bone)
dimana  keterangan  setiap  pasar  ketika  dikaitkan dengan grap, yaitu sebagai berikut:
V1 = Pasar Kalukuan V2 = Pasar Panciro V3 = Pasar Minasamaupa V4 = Pasar Terong(Makassar) V5 = Pasar Tramo (Maros) V6 = Pasar Mattirowale (Baru) V7 = Pasar Palakka (Bone)

## Penggambaran  Titik  lokasi  Pendistribusian Barang kedalam Grap
Adapun penggambaran setiap titik lokasi dan tujuan  pendistribusian  barang  dapat  dilihat  pada Gambar 4.1.
Berdasarkan  gambar  4.1  diperoleh  bahwa untuk V1,V2,V3 adalah sumber dari pendistribusian barang yang akan di didistribusikan  kebeberapa  titik  tujuan,  yaitu
V4,V5,V6 dan V7.

## Gambar 4.1
Menentukan Jarak Tempuh
dengan

## Menggunakan Google Maps
Dari gambar diatas tersebut diperoleh data jarak  antar  daerah  pendistribusian  berdasarkan perhitungan  google  maps.  Berikut  disajikan  data jarak  antara  daerah  sumber  pendistribusian pertama dan  beberapa tujuan perdistribusian.
Tabel 4.1 Jarak Pasar Kalukuan dengan Tujuan Distribusi
Tabel 4.2 Jarak Pasar Minasamaupa dengan Tujuan Distribusi
Tabel 4.3 Jarak pasar Panciro dengan Tujuan Dsitribusi
Berdasarkan  tabel  4.1,  4.2  dan  4.3 didapatkan  konversi  berdasarkan  jarak  yang disimbolkan dengan V(verteks) di tabel 4.4, yaitu:
𝜏𝑖𝑗 =  𝜏0  = 𝑘 𝑔𝑟𝑒𝑒𝑑𝑦 (4.1)
Tabel 4.4 Konversi Verteks
Berdasarkan data jarak dari tabel 4.4 verteks ke verteks, maka didapatkan nilai visibilitas pada tabel dibawah ini, dengan menggunakan persamaan;
𝜂𝑖𝑗  = 1 𝑑𝑖𝑗 (4.2)

## a. Perhitungan Algoritma Semut
Algoritma Semut merupakan algoritma yang dihasilkan  dari  koloni  Semut  dan  merupakan algoritma yang digunakan untuk menentukan rute terpendek. Berikut penyelesaian masalah algoritma  Semut  berdasarkan  data  jarak  tempuu yang telah ditetapkan:
Diberikan nilai ketetapan: 𝛼   = 1 ; 𝛼 > 0 𝛽   = 1 ; 𝛽 > 0 𝜌   = 1; 𝜌  > 0 𝜏 𝑖𝑗 = 0,01 ; 𝜏 𝑖𝑗 > 0 𝑢𝑛𝑡𝑢𝑘 𝑚𝑒𝑛𝑐𝑒𝑔𝑎ℎ 𝑝ℎ𝑒𝑟𝑜𝑚𝑜𝑛 𝑦𝑎𝑛𝑔 𝑡𝑒𝑟𝑙𝑎𝑙𝑢 𝑏𝑒𝑠𝑎𝑟 Sehingga :
∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 V4 → V1 = (0,01) 1 . (0,058) 1 = 0,00058 V4 → V2 = (0,01) 1 . (0,06) 1 = 0,0006 V4 → V3 = (0,01) 1 . (0,083) 1 = 0,00083 ∑[𝜏 𝑖𝑗 ] 𝛼 .[ 𝜂 𝑖𝑗 ] 𝛽 = 0,00058  + 0,0006 + 0,00083 = 0,00201 𝑃 𝑖𝑗 𝑘 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V4 → V1 = 0,00058 0,00201 = 0,288 No Jarak Pasar Kalukuan Daerah Pasar 1.   17 km Pasar Terong (Makasar) 2. 40 km Pasar Tramo (Maros) 3.    113 km Pasar Mattirowalle (Barru) 4. 138 km Pasar Palakka (Bone) No Jarak Pasar Minasamaupa Daerah Pasar 1.   12 km Pasar Terong (Makasar) 2. 35 km Pasar Tramo (Maros) 3.   108 km Pasar Mattirowalle (Barru) 4. 132 km Pasar Palakka (Bone) No Jarak Pasar
Panciro Daerah Pasar 1. 15 km Pasar Terong (Makasar) 2. 38 km Pasar Tramo (Maros) 3. 111 km Pasar Mattirowalle (Barru) 4. 136 km Pasar Palakka (Bone)
Jarak
Verteks Ke Verteks I II III V1  V2 V3 V4 I 0 2.5 9.6 17 40 113 138 II 2.5 0 4.1 15 38 111 136 III 9.6 4.1 0 12 35 108 132 V1 17 15 12 0 0 0 0 V2 40 38 35 0 0 0 0 V3 113  111  108 0 0 0 0 V4 138  136  132 0 0 0 0
V4 → V2 = 0,0006 0,00201 = 0,298
V4 → V3 = 0,00083 0,00201 = 0,412
Berdasarkan  perhitungan  nilai  probabilitas, didapatkan  nilai  yang  paling  mendekati  1,  yaitu jarak  dari  V4 → V3 = 0,412 ,  Sehingga  terpilih jarak tersebut pada siklus pertama,yaitu: V4 → V3 → V2 → V1 = 12  + 4.1  + 2.5  = 18,6 Untuk memperoleh siklus kedua,maka digunakan langkah sebagai berikut V4 → V1 = (0,01) 1 . (0,058) 1 = 0,00058
V4 → V2 = (0,01) 1 . (0,06) 1 = 0,0006 V4 → V3 = (0,01) 1 . (0,083) 1 = 0,00083 ∑[𝜏 𝑖𝑗 ] 𝛼 .[ 𝜂 𝑖𝑗 ] 𝛽 = 0,00058  + 0,0006 + 0,00083 = 0,00201 𝑃 𝑖𝑗 𝑘 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V4 → V1 = 0,00058 0,00201 = 0,288 V4 → V2 = 0,0006 0,00201 = 0,298 V4 → V3 = 0,00083
0,00201 = 0,412 V3 → V2 = ∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 V3 → V2 = (0,01) . (0,24) =  0,0 024 dimana untuk memperoleh probabilitas dari V3 → V2 , maka diselesaikan dengan persamaan sebagai berikut:
V3 → V2 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V3 → V2 = 0,0024 0,0024 =  1
Untuk  jarak  antara  V2 → V1,  dapat ditentukan  dengan  menggunakan  persamaan sebagai berikut:
V2 → V1 = ∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 V2 → V1 = (0,01) . (0,4) =  0,0 04 V2 → V1 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V2 → V1 = 0,004 0,004 =  1
Untuk  siklus  2  didapatkan  sebuah  jarak V4 → V3 → V2,  dimana  nilai  teersebut  diperoleh sebagai berikut:
V4 → V3 → V2 = 12 + 4,1 = 16,1 Untuk mendapatkan nilai dari siklus ketiga, maka diambil jarak dari V4 → V3, dimana bobot jarak tersebut sebagai berikut:
V4 → V3 = 12
Berdasarkan  nilai  jarak  dari  ketiga  siklus tersebut,maka  diperoleh  jarak  yang  paling terpendek, yaitu:
V4 → V3 = 12
V5 = Pasar Maros
V5 → V1 = (0,01) 1 . (0,025) 1 = 0,00025 V5 → V2 = (0,01) 1 . (0,02) 1 = 0,0002 V5 → V3 = (0,01) 1 . (0,028) 1 = 0,00028 ∑[𝜏 𝑖𝑗 ] 𝛼 .[ 𝜂 𝑖𝑗 ] 𝛽 = 0,00025  +  0,0002 +  0,00028 = 0,00073
𝑃 𝑖𝑗 𝑘 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V5 → V1 = 0,00025 0,00073 = 0,333 V5 → V2 = 0,0002 0,00073 = 0,273 V5 → V3 = 0,00028 0,00073 = 0,383
Berdasarkan  perhitungan  nilai  probabilitas, didapatkan  nilai  yang  paling  mendekati  1,  yaitu jarak  dari  V5 → V3 = 0,383 ,  Sehingga  terpilih jarak tersebut pada siklus pertama, yaitu:
V5 → V3 → V2 → V1 = 35  + 4,1  + 2,5  = 41,6 Kemudian untuk siklus kedua dapat dicari dengan cara sebagai berikut:
Untuk  meperoleh  siklus  kedua,maka  digunakan langkah sebagai berikut
V5 → V1 = (0,01) 1 . (0,025) 1 = 0,00025 V5 → V2 = (0,01) 1 . (0,02) 1 = 0,0002 V5 → V3 = (0,01) 1 . (0,028) 1 = 0,00028
∑[𝜏 𝑖𝑗 ] 𝛼 .[ 𝜂 𝑖𝑗 ] 𝛽 = 0,00025  +  0,0002 +  0,00028
= 0,00073 𝑃 𝑖𝑗 𝑘 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V5 → V1 = 0,00025 0,00073 = 0,333 V5 → V2 = 0,0002 0,00073 = 0,273
V5 → V3 = 0,00028 0,00073 = 0,383 V3 → V2 = ∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 V3 → V2 = (0,01) . (0,24) =  0,0 024 Dimana untuk memperoleh probabilitas dari V3 → V2 , maka  diselesaikan  dengan  persamaan sebagai berikut:
V3 → V2 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V3 → V2 = 0,0024 0,0024 =  1
Untuk  jarak  antara  V2 → V1,  dapat ditentukan  dengan  menggunakan  analisi  sebagai berikut:
V2 → V1 persama
Penerapan Algoritma Dijkstra dan Algoritma Semut pada Pendistribusian Barang
= ∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽
V2 → V1 = (0,01) . (0,4) =  0,0 04 V2 → V1 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V2 → V1 = 0,004 0,004 =  1
Untuk siklus 2 didapatkan sebuah jarak V5 → V3 → V2,  dimana  nilai  teersebut  diperoleh sebagai berikut:
V5 → V3 → V2 = 35 + 4,1 = 39,1
Untuk mendapatkan nilai dari siklus ketiga, maka diambil jarak dari V5 → V3, dimana bobot jarak tersebut sebagai berikut: V5 → V3 = 35
Berdasarkan  nilai  jarak  dari  ketiga  siklus tersebut,maka  diperoleh  jarak  yang  paling terpendek, yaitu:
V5 → V3 = 35
V6 = Pasar Mattirowalle (Barru)
V6 → V1 = (0,01) 1 . (0,008) 1 = 0,00008
V6 → V2 = (0,01) 1 . (0,00925) 1 = 0,000925 V6 → V3 = (0,01) 1 . (0,009) 1 = 0,00009
∑[𝜏 𝑖𝑗 ] 𝛼 .[ 𝜂 𝑖𝑗 ] 𝛽 = 0,00008  +  0,000925 +  0,00009
= 0,001095 𝑃 𝑖𝑗 𝑘 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V6 → V1 = 0,00008 0,001095 = 0,073 V6 → V2 = 0,0000925 0,001095 = 0,082
V6 → V3 = 0,00009
0,001095 = 0,844
Berdasarkan
perhitungan
nilai
probabilitas,  didapatkan  nilai  yang  paling mendekati 1, yaitu jarak dari V6 → V3 = 0,844 , Sehingga  terpilih  jarak  tersebut  pada  siklus pertama,yaitu:
V6 → V3 → V2 → V1 = 108  + 4.1  + 2.5 = 114.6
Kemudian untuk siklus kedua dapat dicari dengan cara sebagai berikut:
V6 → V1 = (0,01) 1 . (0,008) 1 = 0,00008 V6 → V2 = (0,01) 1 . (0,00925) 1 = 0,000925 V6 → V3 = (0,01) 1 (0,009) 1 = 0,00009 ∑[𝜏 𝑖𝑗 ] 𝛼 .[ 𝜂 𝑖𝑗 ] 𝛽 = 0,00008  +  0,000925 +  0,00009 = 0,001095 𝑃 𝑖𝑗 𝑘 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V6 → V1 = 0,00008 0,001095 = 0,073
V6 → V2 = 0,0000925 0,001095 = 0,082
V6 → V3 = 0,00009 0,001095 = 0,844 V3 → V2 = ∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 V3 → V2 = (0,01) . (0,24) =  0,0 024 Dimana untuk memperoleh probabilitas dari V3 → V2 , maka  diselesaikan  dengan  persamaan sebagai berikut:
V3 → V2 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V3 → V2 = 0,0024 0,0024 =  1
Untuk  jarak  antara  V2 → V1,  dapat ditentukan  dengan  menggunakan  persamaan sebagai berikut:
V2 → V1 = ∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 V2 → V1 = (0,01) . (0,4) =  0,0 04 V2 → V1 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V2 → V1 = 0,004 0,004 =  1
Untuk siklus 2 didapatkan sebuah jarak V6 → V3 → V2,  dimana  nilai  teersebut  diperoleh sebagai berikut:
V6 → V3 → V2 = 108 + 4.1 = 112.1 Untuk mendapatkan nilai dari siklus ketiga, maka diambil jarak dari V6 → V3, dimana bobot jarak tersebut sebagai berikut:
V6 → V3 = 108
Berdasarkan  nilai  jarak  dari  ketiga  siklus tersebut,maka  diperoleh  jarak  yang  paling terpendek, yaitu:
V6 → V3 = 108 V7 = Palakka (Bone) V7 → V1 = (0,01) 1 . (0,00724) 1 = 0,0000724 V7 → V2 = (0,01) 1 . (0,00735) 1 = 0,0000735
V7 → V3 = (0,01) 1 . (0,0075) 1 = 0,000075
∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 = 0,0000724  + 0,0 000735 + 0,0 00075 =  0,0002209 𝑃 𝑖𝑗 𝑘 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V7 → V1 = 0,0000724 0,0002209 = 0,327
V7 → V2 = 0,0000735 0,0002209 = 0,332 V7 → V3 = 0,000075 0,0002209 = 0,339 Berdasarkan perhitungan nilai
probabilitas,  didapatkan  nilai  yang  paling mendekati 1, yaitu jarak dari V7 → V3 = 0,339 , Sehingga  terpilih  jarak  tersebut  pada  siklus pertama,yaitu:
V7 → V3 → V2 → V1 = 132  + 4.1  + 2.5  = 138.6
Kemudian untuk siklus kedua dapat dicari dengan cara sebagai berikut:
V7 → V1 = (0,01) 1 . (0,00724) 1 = 0,0000724 V7 → V2 = (0,01) 1 . (0,00735) 1 = 0,0000735
V7 → V3 = (0,01) 1 . (0,0075) 1 = 0,000075 ∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 = 0,0000724  + 0,0 000735 + 0,0 00075 =  0,0002209
𝑃 𝑖𝑗 𝑘 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V7 → V1 = 0,0000724 0,0002209 = 0,327 V7 → V2 = 0,0000735
0,0002209 = 0,332
V7 → V3 = 0,000075 0,0002209 = 0,339
V3 → V2 = ∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 V3 → V2 = (0,01) . (0,24) =  0,0 024 Dimana  untuk  memperoleh  probabilitas dari  V3 → V2 , maka  diselesaikan  dengan persamaan sebagai berikut:
V3 → V2 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V3 → V2 = 0,0024 0,0024 =  1
Untuk  jarak  antara  V2 → V1,  dapat ditentukan  dengan  menggunakan  persamaan sebagai berikut:
V2 → V1 = ∑[𝜏 𝑖𝑗 ] 𝛼 . [ 𝜂 𝑖𝑗 ] 𝛽 V2 → V1 = (0,01) . (0,4) =  0,0 04 V2 → V1 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽 V2 → V1 = 0,004 0,004 =  1
Untuk siklus 2 didapatkan sebuah jarak V7 → V3 → V2,  dimana  nilai  teersebut  diperoleh sebagai berikut:
V7 → V3 → V2 = 132 + 4.1 = 136.1 Untuk mendapatkan nilai dari siklus ketiga, maka diambil jarak dari V7 → V3, dimana bobot jarak tersebut sebagai berikut:
V7 → V3 = 132
Berdasarkan  nilai  jarak  dari  ketiga  siklus tersebut,maka  diperoleh  jarak  yang  paling
terpendek, yaitu: V7 → V3 = 132
b. Perhitungan Rute Terpendek

## DenganAlgoritma Dijkstra
Algoritma  Dijkstra  merupakan  algoritma yang digunakan untuk mencari lintasan terpendek pada    grap  berarah.  Berikut  penyelesaian algoritma  Dijkstra  berdasarkan  data  yang  telah diberikan:
Diberikan  verteks  V1,V2,V3  dan  V4,  dimana jaraknya masing, yaitu sebagai berikut:
V1 → V2 = 2.5
V2 → V3 = 4.1
V3 → V4 = 12 V4 → V2 = 15 V4 → V1 = 17 V5 → V1 = 39 V5 → V2 = 37 V5 → V3 = 35 V6 → V1 = 113 V6 → V2 = 111 V6 → V3 = 108 V7 → V1 = 138 V7 → V2 = 136 V7 → V3 = 132
Berikut  adalah  langkah-langkah  dalam  mencari rute  terpendek  dengan  menggunakan  algoritma Dijkstra sebagai berikut:
1. Pasar Terong (Makassar)
Berikut  ditampilkan  gambar  rute  perjalanan pedagang  dari  pasar  terong  menuju  pasar pendistribusian.berdasarkan  data  jarak  yang diberikan  maka  dapat  diselesaikan  denngan beberapa langkah sebagai berikut:
a. Tarik jarak untuk setiap titik pasar Minasamaupa,  Panciro  dan  Kalukuan  ke  titik pasar Terong (pasar Makassar), lalu set  nilai 0 pada  node  awal  dan  nilai  tak  hingga  terhadap node lain (yang belum terisi).
𝐿 = {0};  𝑉𝑖 =  ∞
b. Set  semua  node  “belum  terjamaah”  dan  set node  awal  sebagai  node  keberangkatan  dari pasar.
𝐷(𝑣4) − 𝑊(1, 𝑣3) = 12  − 0  = 12 𝐷(𝑣4) − 𝑊(1, 𝑣2) = 15  − 0  = 15 𝐷(𝑣4) − 𝑊(1, 𝑣1) =  17  − 0  = 17 𝐷(𝑣3) − 𝑊(1, 𝑣2) =  4.1  − 0  = 4.1 𝐷(𝑣2) − 𝑊(1, 𝑣1) =  2.5  − 0  = 2.5
c. Pertimbangkan    setiap  jarak  terhadap  node tetangga,  tandai  node  yang  telah  terjemaah
sebagai  node  terjemaah,  node  terjemaah  tidak akan  pernah  dicek  kembali.  Jarak  yang disimpang  adalah  jarak  terakhir  dan  yang paling minimal bobotnya.
Setelahdipertimbangkan didapatkan hasil dari: 𝐷(𝑣4) − 𝑊(1, 𝑣3) = 12  − 0   = 12 𝐷(𝑣4) − 𝑊(1, 𝑣2) = 15  − 0   = 15 𝐷(𝑣4) − 𝑊(1, 𝑣1) =  17  − 0  = 17 𝐷(𝑣3) − 𝑊(1, 𝑣2) =  4.1  − 0  = 4.1 𝐷(𝑣2) − 𝑊(1, 𝑣1) =  2.5  − 0  = 2.5
Setelah  dipertimbangkan  maka  didapatkan jarak  terpendek,yaitu  {12,  4.1,  2.5}dimana ketiga  jarak  tersebut  mengarah  kepada  titik {V4, V3, V2 dan V1}
d. Atur node yang belum terjamaah dengan jarak terkecil  (dari  node  keberangkatan)  sebagai node keberangkatan, berikut adalah jarak hasil terkecil  yang  akan  terpilih  sebagai  rute perjalanan,yaitu {12, 4.1, 2,5} dan tepat berada dititik {V4, V3, V2 dan V1}.
2. Pasar Tramo(Maros)
a. Beri  nilai  (jarak)  untuk  setiap  titik  pasar Minasamaupa,  Panciro  dan  Kalukuan  ke  titik pasar  Terong  (pasar  Makassar),  lalu  set    nilai  0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi).
𝐿 = {0};  𝑉𝑖 =  ∞
b. Atur semua node “belum terjamaah” dan set node awal sebagai node keberangkatan dari pasar. 𝐷(𝑣5) − 𝑊(1, 𝑣3) = 35  − 0    = 35 𝐷(𝑣5) − 𝑊(1, 𝑣2) = 37  − 0    = 37 𝐷(𝑣5) − 𝑊(1, 𝑣1) =  39 − 0     = 39 𝐷(𝑣3) − 𝑊(1, 𝑣2) =  4.1  − 0   = 4.1 𝐷(𝑣2) − 𝑊(1, 𝑣1) =  2.5  − 0  = 2.5
c. pertimbangkan    setiap  jarak  terhadap  node tetangga, tandai node yang telah terjemaah sebagai node terjemaah, node terjemaah tidak akan pernah dicek kembali. Jarak yang disimpang adalah jarak terakhir dan yang paling minimal bobotnya. 𝐷(𝑣5) − 𝑊(1, 𝑣3) = 35  − 0     = 35 𝐷(𝑣5) − 𝑊(1, 𝑣2) = 37  − 0     = 37 𝐷(𝑣5) − 𝑊(1, 𝑣1) =  39 − 0     = 39 𝐷(𝑣3) − 𝑊(1, 𝑣2) =  4.1  − 0    = 4.1 𝐷(𝑣2) − 𝑊(1, 𝑣1) =  2.5  − 0   = 2.5 Setelah  dipertimbangkan  maka  didapatkan  jarak terpendek,yaitu {35, 4.1, 2.5}dimana ketiga jarak tersebut mengarah kepada titik {V5, V3, V2  dan V1}
d. Set  node  yang  belum  terjamaah  dengan  jarak terkecil  (dari  node  keberangkatan)  sebagai  node keberangkatan, berikut adalah jarak hasil terkecil
yang  akan  terpilih  sebagai  rute  perjalanan,yaitu {35, 4.1, 2,5} dan tepat berada dititik {V5, V3, V2 dan V1}.
3. Pasar Mattirowalle(Barru)
a. Beri  nilai  (jarak)  untuk  setiap  titik  pasar Minasamaupa,  Panciro  dan  Kalukuan  ke  titik pasar Terong (pasar Makassar), lalu set  nilai 0 pada  node  awal  dan  nilai  tak  hingga  terhadap node lain (yang belum terisi).
𝐿 = {0};  𝑉𝑖 =  ∞
b. Set  semua  node  “belum  terjamaah”  dan  set node  awal  sebagai  node  keberangkatan  dari pasar.
𝐷(𝑣5) − 𝑊(1, 𝑣3) = 108  − 0    = 108 𝐷(𝑣5) − 𝑊(1, 𝑣2) = 111  − 0    = 111 𝐷(𝑣5) − 𝑊(1, 𝑣1) =  113 − 0    = 113 𝐷(𝑣3) − 𝑊(1, 𝑣2) =  4.1  − 0     = 4.1 𝐷(𝑣2) − 𝑊(1, 𝑣1) =  2.5  − 0     = 2.5 c. pertimbangkan    setiap  jarak  terhadap  node tetangga,  tandai  node  yang  telah  terjemaah sebagai  node  terjemaah,  node  terjemaah  tidak akan  pernah  dicek  kembali.  Jarak  yang disimpang  adalah  jarak  terakhir  dan  yang paling minimal bobotnya.
𝐷(𝑣6) − 𝑊(1, 𝑣3) = 108  − 0    = 108 𝐷(𝑣6) − 𝑊(1, 𝑣2) = 111  − 0    = 111 𝐷(𝑣6) − 𝑊(1, 𝑣1) =  113 − 0    = 113 𝐷(𝑣3) − 𝑊(1, 𝑣2) =  4.1  − 0     = 4.1 𝐷(𝑣2) − 𝑊(1, 𝑣1) =  2.5  − 0      = 2.5 Setelah  dipertimbangkan  maka  didapatkan jarak  terpendek,yaitu  {108,  4.1,  2.5}dimana ketiga  jarak  tersebut  mengarah  kepada  titik {V6, V3, V2  dan V1}
d. Set  node  yang  belum  terjamaah  dengan  jarak terkecil  (dari  node  keberangkatan)  sebagai node keberangkatan, berikut adalah jarak hasil terkecil  yang  akan  terpilih  sebagai  rute perjalanan,yaitu  {108,  4.1,  2,5}  dan  tepat berada dititik {V6, V3, V2 dan V1}.
4. Pasar Palakka(Bone)
a. Beri  nilai  (jarak)  untuk  setiap  titik  pasar Minasamaupa,  Panciro  dan  Kalukuan  ke  titik pasar Terong (pasar Makassar), lalu set  nilai 0 pada  node  awal  dan  nilai  tak  hingga  terhadap node lain (yang belum terisi).
𝐿 = {0};  𝑉𝑖 =  ∞
b. Set  semua  node  “belum  terjamaah”  dan  set node  awal  sebagai  node  keberangkatan  dari pasar.
𝐷(𝑣7) − 𝑊(1, 𝑣3) = 35  − 0    = 35
𝐷(𝑣7) − 𝑊(1, 𝑣2) = 37  − 0    = 37 𝐷(𝑣7) − 𝑊(1, 𝑣1) =  39 − 0    = 39 𝐷(𝑣3) − 𝑊(1, 𝑣2) =  4.1  − 0  = 4.1 𝐷(𝑣2) − 𝑊(1, 𝑣1) =  2.5  − 0  = 2.5
c. Pertimbangkan    setiap  jarak  terhadap  node tetangga,  tandai  node  yang  telah  terjemaah sebagai  node  terjemaah,  node  terjemaah  tidak akan  pernah  dicek  kembali.  Jarak  yang disimpang  adalah  jarak  terakhir  dan  yang paling minimal bobotnya.
𝐷(𝑣6) − 𝑊(1, 𝑣3) = 132  − 0    = 132 𝐷(𝑣6) − 𝑊(1, 𝑣2) = 136  − 0    = 136 𝐷(𝑣6) − 𝑊(1, 𝑣1) =  138 − 0    = 138 𝐷(𝑣3) − 𝑊(1, 𝑣2) =  4.1  − 0  = 4.1 𝐷(𝑣2) − 𝑊(1, 𝑣1) =  2.5  − 0  = 2.5 Setelah  dipertimbangkan  maka  didapatkan jarak  terpendek,yaitu  {132,  4.1,  2.5}dimana ketiga  jarak  tersebut  mengarah  kepada  titik {V7, V3, V2  dan V1}
d. Set  node  yang  belum  terjamaah  dengan  jarak terkecil  (dari  node  keberangkatan)  sebagai node keberangkatan, berikut adalah jarak hasil terkecil  yang  akan  terpilih  sebagai  rute perjalanan,yaitu  {132,  4.1,  2,5}  dan  tepat berada dititik {V7, V3, V2 dan V1}

## Pembahasan
Dalam  menganalisis  data  yang  diperoleh dari  pengukuran  melalui  google  maps  dengan menggunakan  algoritma  Dikjtra  dan  algoritma Semut,  maka  hal  pertama  yang  dilakukan  adalah menghiung  setiap  jarak  pendek  pada  masing- masing  algoritma.  Algoritma  Dikjtra  merupakan algoritma  yang  dapat  melakukan  pencarian  rute terpendek dengan menggunakan beberapa langkah-langkah  dengan  mencari  rute  terpendek dengan meperhatikan rute yang dilewati menggunakan  rumus ∑[𝜏 𝑖𝑗 ] 𝛼 .  [ 𝜂 𝑖𝑗 ] 𝛽 sebagai rumus pertama, untuk menentukan rute yang akan ditempuh menggunakan rumus
𝑃 𝑖𝑗 𝑘 = [𝜏 𝑖𝑗 ] 𝛼 .[𝜂 𝑖𝑗 ] 𝛽 ∑[𝜏𝑖𝑗] 𝛼 .  [𝜂𝑖𝑗] 𝛽
Output  dari  hasil  penelitian  ini  antara algoritma  Dijkstra  dan  algoritma  Semut,  dimana algoritma  Dijkstra  menyatakan  bahwa  rute  yang dilewati  pedagang  tidak  melakukan  pengulangan dalam dalam perjalanannya menuju pasar tujuan, sedangkan Algoritma Semut memberikan gambaran bahwa rute yang diperoleh berdasarkan analisis yaitu rute yang berulang. Sehingga hal ini dapat dinyatakan bahwa untuk mendapatkan rute
efektif  bagi  para  pedagang,  maka    digunakan algoritma  Dijkstra  dalam  mengefektifkan  rute pendistribusian.
5. KESIMPULAN
Adapun  kesimpulan  pada  penelitian  ini adalah  menyatakan  bahwa  untuk  mendapatkan rute  pendistribusian  barang  yang  terpendek berdasarkan  rute  pasar  Kalukuan,  Panciro  dan Minasamaupa ke pasar Makassar (Terong), Maros (Tramo), Barru (Mattirowalle) dan Bone (Palakka)  setelah  dilakukannya  penelitian  dan proses analisis dengan membandingkan algoritma Dijktra  dan  algoritma  Semut,  maka  dipilih algoritma Dijktra, hal ini di karenakan  algoritma Dijktra  memberikan  rute  yang  efektif  dan  lebih cepat,  baik  dari  segi  analisis  maupun  hasil  yang diperoleh.
.

## 6. DAFTAR PUSTAKA
[1] Ayu,  Andira.  “Algoritma  Greedy  untuk menentukan  lintasan  terpendek  dalam  area kotaMakassar ”. Skripsi (Makassar: Fakultas Sains dan Teknologi UIN Makassar, 2013).
[2] Fandi  Ahmad,  Hafidz  Fadel  Muharram. 2018. “ Penentuan Jalur Distribusi Dengan
Metode  Saving  Matriks  “ Jakarta:  Vol.  13
No.1.
[3] Hardjasutanto,  Fabrian  Oktavino. Institut Teknologi  Bandung.  Jl.  Ganesha  10 Bandung 40132, Indonesia ). Http;//Makalah-Algoritma  Semut.htm(  1 September 2014). [4] Halda, Yani Ranius dan Syaputra.
Implementasi  Algoritma  Dijkstra  Untuk Menentukan  Jalur  Terpendek  Rumah  Sakit Di Kota Palembang (Palembang: Gramedia Pustaka Utama,2015),7.
[5] I’ing Mutakhiroh, dkk. Pemanfaatan Metode Heuristik  Dalam  Pencarian  Rute  terpendek Dengan  algoritma  Semut  dan  Algoritma genetika.Vol.7 .No.7.(2007).Hal.33
[6] Jong  Jek  Siang.  Matematika  Diskrit  daan Aplikasinya pada Ilmu Pengetahuan. (Yogyakarta: penerbit ANDI,2009).
[7] Mahmud  Basuki.  2017. ”  Penentuan Rute
Optimum Distribusi Produk Indmira
Berdasarkan Jarak” Universitas  Tridinanti Palembang: Mahmud Basuki. Vol. 5 No. 1. [8] Surachmad Pratama. Perbandingan
Algoritma  Dijkstra  dan  algoritma  Floyd
Warshall Pada Pencarian Rute Parawisata di
Kota Palembang. Vol,2. No,3.(2020)
[9] Saymour
Lipschutz,MaeclarLipson.
Matematika  Diskrit  2  terj.  Tim  Editor
Penerbit  Salemba  Mustika  Edidi  pertama.
(Jakarta:Salemba Teknika, 2002).
[10] Sarwat  Ahmad  .  2018. Fiqih  Jual  Beli.
Jakrta Selatan : Rumah Fiqih Publishing