Jurnal Sains Riset (JSR) p -ISSN 2088-0952, e -ISSN 2714-531X http://journal.unigha.ac.id/index.php/JSR DOI. 10.47647/jsr.v10i12

## DISTRIBUSI GAS LPG DENGAN MENCARI RUTE TERPENDEK PERBANDINGAN ALGORITMA DIJKSTRA DAN ANT COLONY WILAYAH KABUPATEN PIDIE
Yuswardi 1 , Balia 2
1 Teknik Informatika , Universitas Jabal Ghafur
2 Teknik Informatika , Universitas Jabal Ghafur e-mail: yuswardi@unigha.ac.id

## ABSTRACT
Finding the shortest path is a problem finding a path between two nodes with a minimum amount of weight. In the case of finding the shortest path between two different locations on a map, the node will represent the location on the map and  the weight represents the time it takes to travel between  the  two  locations.  Dijkstra  and  Ant  Colony  algorithms  are  the  most  commonly  used algorithms  in  the  search  for  the  shortest route.  Dijkstra and  Ant  Colony  algorithms  use  greedy principles, which is to find the optimum solution at each step passed, intending to get the optimum solution in the next step that will lead to the best solution at this time to find the shortest route for the  distribution  of  LGP  Gas  3  Kg.  This  problem  gave  rise  to  the  idea  of  creating  a  web-based application,  which can  search  for  the  shortest  route  for LPG  gas  distribution. Where  a  detailed study of the application of Dijkstra and Ant Colony algorithms is to solve the shortest trajectory problem and the software used is Sublime Text as a script editor, PHP as a programming language, and Google Maps to display maps, and Mysql as a database. This system only displays the shortest distance from the Gas Distribution Company (PT /CV) to the existing Gas bases in Pidie Regency to find out the distance from the initial location to the destination location obtained from Google Maps.
Keywords : Dijkstra and Ant Colony Algorithms, Shortest Route Search, LPG Gas Distribution in Pidie Regency.

## ABSTRAK
Pencarian jalur terpendek merupakan suatu permasalahan untuk menemukan sebuah jalur antara dua node dengan jumlah bobot minimal. Pada kasus pencarian jalur terpendek antara dua lokasi yang  berbeda  dalam  sebuah  peta,  node  akan  merepresentasikan  lokasi  pada  peta  dan  bobot merepresentasikan waktu yang dibutuhkan untuk melakukan perjalanan antara dua lokasi tersebut. Algoritma  Dijkstra  dan  Ant  Colony  merupakan  algoritma  yang  paling  sering  digunakan  dalam pencarian rute terpendek. Algoritma Dijkstra dan Ant Colony menggunakan prinsip Greedy, yaitu mencari solusi optimum pada setiap langkah yang dilalui, dengan tujuan untuk mendapatkan solusi optimum pada langkah selanjutnya yang akan mengarah pada solusi terbaik pada saat ini untuk menemukan  rute  terpendek  bagi  pendistribusian  Gas  LGP  3  Kg  tersebut.  Dari  permasalahan tersebut memunculkan gagasan untuk membuat sebuah aplikasi berbasis web, yang didalamnya dapat melakukan pencarian rute terpendek untuk distribusi Gas LPG. Dimana kajian detail tentang aplikasi algoritma dijkstra dan Ant Colony adalah untuk memecahkan masalah lintasan terpendek serta perangkat lunak yang digunakan adalah Sublime Text sebagai text editor script, PHP sebagai bahasa pemrograman, Google Maps untuk menampilkan peta, dan Mysql sebagai database. Sistem
Jurnal Sains Riset (JSR) p -ISSN 2088-0952, e -ISSN 2714-531X http://journal.unigha.ac.id/index.php/JSR DOI. 10.47647/jsr.v10i12
ini hanya menampilkan jarak terpendek dari Perusahaan Distribusi Gas (PT/CV) ke pangkalan- pangkalan Gas yang ada di Kabupaten Pidie untuk mengetahui Jarak dari lokasi awal ke lokasi tujuan diperoleh dari Google Maps.
Kata kunci : Algoritma Dijkstra dan Ant Colony, Pencarian Rute Terpendek, Distribusi Gas LPG di Kabupaten Pidie.

## Pendahuluan
Dalam  kehidupan  ini  permasalahan pencarian jalur terpendek merupakan sebuah kajian  yang  banyak  dibahas.  Hal  ini  akan sangat  berguna  untuk  diimplementasikan pada  beberapa  kasus  yang  membutuhkan tingkat  efisiensi  waktu  tinggi  seperti pengiriman  barang,  pencarian  lokasi,  dan sebagainya.  Dengan  memperoleh  jalur terpendek  antara  dua  lokasi,  maka  tingkat efisiensi  waktu  yang  dibutuhkan  untuk melakukan  perjalanan  antara  dua  lokasi tersebut akan semakin baik.
Pada  kasus  pencarian  jalur  terpendek antara dua lokasi yang berbeda dalam sebuah peta,  node  akan  merepresentasikan  lokasi pada  peta  dan  bobot  merepresentasikan waktu  yang  dibutuhkan  untuk  melakukan perjalanan antara dua lokasi tersebut.
Algoritma  Dijkstra  dan  Ant  Colony merupakan  algoritma  yang  paling  sering digunakan  dalam  pencarian  rute  terpendek, sederhana penggunaannya dengan menggunakan simpul-simpul sederhana pada jaringan  jalan  yang  tidak  rumit.  Dalam mencari  solusi,  algoritma  Dijkstra  dan  Ant Colony  menggunakan  prinsip  Greedy,  yaitu mencari solusi optimum pada setiap langkah yang dilalui, dengan tujuan untuk mendapatkan  solusi  optimum  pada  langkah selanjutnya yang akan mengarah pada solusi terbaik.  Oleh  karena  itu  penerapan  Sistem Informasi  Geografis  untuk  menemukan  rute terpendek  menggunakan  algoritma  Dijkstra dan  Ant  Colony  merupakan  solusi  terbaik saat  ini  untuk  menemukan  rute  terpendek bagi pendistribusian Gas LGP 3 Kg tersebut di  sektor  peta  wilayah  dalam  Kabupaten Pidie.
Untuk  itu,  kita  harus  mengetahui proses penerapan algoritma Dijkstra dan Ant Colony  dalam  melakukan  pencarian  rute
terpendek  untuk  pendistribusian  Gas  LPG dan  bagaimana  cara  membangun  aplikasi pencarian rute terpendek distribusi Gas LPG di  dalam  Wilayah  Kabupaten  Pidie  berbasis Website.  Adapun  tujuan  penelitian  karya ilmiah  ini  adalah  memahami  penerapan metode  Dijkstra  dan  Ant  Colony  pada pencarian rute terpendek pendistribusian Gas LPG serta membangun sebuah aplikasi yang bisa  menentukan  rute  terpendek  lokasi pangkalan  gas  LPG  di  dalam  Wilayah Kabupaten Pidie.
Dalam ilmu komputer, untuk menentukan jalur terpendek diperlukan suatu algoritma.  Algoritma  yang  bisa  digunakan untuk  menentukan  jalur  terpendek  adalah algoritma  Dijkstra  dan  Ant  Colony.  Dari permasalahan tersebut maka diperlukan suatu penelitian  untuk  menganalisa  karakteristik maupun penerapan kedua algoritma tersebut. Ada empat langkah yang perlu dilakukan algoritma Dijkstra sebelum melakukan pada pencarian jarak terpendek:
S Menentukan  kumpulan  vertices pada graph dimana lokasi awal dan lokasi akhir ditemukan
V– S  Kumpulan dari vertices pada graph dimana shortest path dari satu start ke vertices belum diketahui
D Array berisi perkiraan jarak terpendek dari start kesetiap vertices
T Nilai total dari jarak ditempuh
Cara kerja algoritma Dijkstra sebagai berikut:
a. Isi S sebagai start (Lokasi awal).
b. Jika, lokasi ≠ lokasi maka isi V-S dengan lokasi  yang  terhubung  dengan  lokasi awal.
Jurnal Sains Riset (JSR) p -ISSN 2088-0952, e -ISSN 2714-531X http://journal.unigha.ac.id/index.php/JSR DOI. 10.47647/jsr.v10i12
c. Isi  D  dengan  urutan  lokasi  yang terhubung  dengan  lokasi  awal  yang berdasarkan  jarak  terpendek  dari  lokasi awal.
d. Isi  T  dengan  jarak  yang  ditempuh  dan selalu  bertambah  bila  ada  jarak  yang baru.
e. Apabila lokasi awal = lokasi akhir berarti proses  pencarian  akan  selesai,  tetapi apabila  lokasi  awal  ≠  lokasi  akhir lanjutan langkah ke 2.

## Metode
Penulis
menggunakan beberapa metode  penelitian  untuk  mengarahkan penelitian  (perancangan)  ini  agar  tujuan peneliti yang telah ditentukan dapat tercapai. Beberapa metode penelitian yang digunakan penulis sebagai berikut:
1. Library Research
Merupakan  cara  pengumpulan  data dengan  mempelajari  literatur,  paket modul dan panduan, buku-buku pedoman, buku-buku perpustakaan, jurnal  dan  segala  kepustakaan  lainnya yang dianggap perlu dan mendukung.
2. Observasi Yaitu  metode  untuk  mendapatkan  data dengan melakukan pengamatan langsung dan pencatatan secara sistematis terhadap gejala  atau  fenomena  yang  terkait  tanpa mengajukan pertanyaan.
3. Interview (Wawancara) Metode  ini  dilakukan  dengan  cara mengajukan pertanyaan-pertanyaan yang mendukung permasalahan.
Diagram Alur Kerja Penelitian

## Gambar 1. Diagram Alur Kerja Penelitian

## Hasil dan Pembahasan
Halaman Home Pada user interface ditampilkan desain grafis  antarmuka.  Adapun  form  tampilan dalam  aplikasi  ini,  antara  lain  tampilan halaman  Home,  halaman  Hitung  Jarak, halaman login, dan halaman operator.
Gambar 2 : Tampilan Halaman Index

## Halaman Hitung Jarak
Gambar 3: Tampilan Halaman Hitung Jarak
Djikstra
A Mengidentifikasi Masalah Teori dan Tinjauan Pustaka Menentukan Lokasi Penelitian MULAI Memfokuskan Tujuan Penelitian A Implementasi Sistem Kesimpulan Penelitian Uji Coba Sistem SELESAI Perancangan Sistem
Jurnal Sains Riset (JSR) p -ISSN 2088-0952, e -ISSN 2714-531X http://journal.unigha.ac.id/index.php/JSR DOI. 10.47647/jsr.v10i12
Gambar 4: Tampilan Halaman Hitung Jarak

## Ant Colony
Tampilan halaman hitung jarak dimana pada halaman  ini  semua  nya  memiliki  hak  yang sama  yaitu  mencari  rute  lokasi  tujuan,  baik itu admin atau user .  Gambar  3  adalah tampilan halaman pencarian djikstra dimana pengguna  hanya  perlu  memilih  lokasi  asal dan  tujuan  yang  terdapat  pada  form pencarian, kemudian sistem akan menampilkan rute tercepat. Gambar 4 adalah tampilan  pencarian  rute  dengan ant  colony, pada  halaman  ini  pengguna  harus  memilh lokasi  yang  ingin  dituju  serta  menandai lokasi  tersebut  pada  peta,  maksimal  lokasi yang bisa ditandai untuk satu kali pencarian adalah 10 (sepuluh) lokasi. Setelah menandai maka system akan mencari serta menampilkan  rute  tercepat  berdasarkan algoritma ant colony.

## Perbandingan Jalur Terpendek
Dalam  pengujian  perbandingan  jalur terpendek  yang  dihasilkan  oleh  kedua algoritma,  penulis  menguji  kedua  algoritma dengan  data  masukkan  yang  sama  dan dilakukan  pengujian  sebanyak  11  (sebelas) kali.  Langkah-langkah  pengujian  untuk setiap algoritma yaitu dengan cara memasukkan  data  lokasi  gudang  dan  lokasi pangkalan pada pencarian djikstra , sedangkan  memilih  lokasi  pada  maps berdasarkan lokasi yang sama dengan lokasi pencarian djikstra . Pada algoritma ant colony nilai  parameter  jumlah  semut  dan  siklus maksimum  bernilai  50  dan  50.    Setelah memasukkan  data  dan  melakukan  proses pencarian dengan masing-masing algoritma,
maka akan muncul hasil dari proses tersebut seperti pada gambar 22.
Sebelum  kita  membandingkan  jarak antara  algoritma djiktra dengan ant  colony pada pencarian rute terpendek, sebaiknya kita mengetahui nama dan alamat tiap-tiap lokasi yang digunakan pada aplikasi E-Gas. Berikut adalah  data  lokasi  yang  digunakan  pada pencarian  rute  terpendek  ini  berjumlah  11 titik  lokasi  pangkalan  gas  yang  ada  pada wilayah  Kabupaten  Pidie  dan  3  lokasi pangkalan  serta  1  lokasi  SPBE  (Stasiun Pengisian Bulk Elpiji) di kabupaten Pidie dan Pidie  Jaya.  Adapun  berikut  daftar  sampel lokasi  yang  digunakan  pada  aplikasi  E-Gas adalah sebagai berikut:
Tabel 1. Lokasi Pangkalan Gas No Nama Pangkalan Lokasi Pangkalan 1 Maar Perkasa Jl.  Profesor Abdul Majid Ibrahim, Lampeudeu Baroh, Pidie, Kabupaten Pidie,  Aceh  24112, Indonesia 2 UD. Jasa Keluarga Lorong Mushalla, Kramat  Luar,  Kota Sigli, Kabupaten Pidie,  Aceh  24114, Indonesia 3 BKPS Jl.  Sigli  -  Kembang Tanjong, Blang Paseh, Kota  Sigli,  Kabupaten Pidie,  Aceh  24113, Indonesia 4 M Ali Jl.  Sigli  -  Kembang Tanjong, Sukon, Simpang Tiga, Kabupaten Pidie, Aceh 24181, Indonesia 5 Rahma Yanti Jl.  Sigli  -  Kembang Tanjong, Pante, Simpang Tiga, Kabupaten Pidie, Aceh 24181, Indonesia
Jurnal Sains Riset (JSR) p -ISSN 2088-0952, e -ISSN 2714-531X http://journal.unigha.ac.id/index.php/JSR DOI. 10.47647/jsr.v10i12
6 Suci Hati Jl.  Sigli  -  Kembang Tanjong, Simpang Tiga, Kabupaten Pidie, Aceh 24181, Indonesia 7 Mariah Jl.  Sigli  -  Kembang Tanjong, Simpang Tiga, Kabupaten Pidie, Aceh 24181, Indonesia 8 Efendi Jl. Kp. Blang Meunasah Juerong, Simpang Tiga, Kabupaten Pidie, Aceh 24181, Indonesia 9 Jufri Jl. Kp. Blang - Lampoih Saka Meunasah Juerong, Simpang Tiga, Kabupaten Pidie, Aceh 24181, Indonesia 10  Rakan LPG  Jl.  Sigli  -  Kembang Tanjong, Kulam Baro, Simpang Tiga, Kabupaten Pidie, Aceh 24181, Indonesia 11  Maimun Blang Leuen, Simpang Tiga, Kabupaten Pidie, Aceh 24181, Indonesia Adapun setiap pangkalan diatas memiliki  agen  yang  menyalurkan  gas  LPG dari SPBE ke gudang, kemudia pihak gudang menyalurkan  ke  seiap  pangkalan  yang  ada dibawahnya melalui agen.
Tabel 2. Lokasi Gudang Gas No  Nama Gudang
Lokasi Gudang 1 CV.Muhammad Noernikkmat Jl.  Kp.  Blang  - Lampoih Saka Meunasah Juerong, Simpang Tiga,
Kabupaten  Pidie, Aceh 24181 2 PT. Indung Tulot Energy Garot Cut, Indrajaya, Kabupaten  Pidie, Aceh 24182, Indonesia 3 PT. Maar Perkasa Jaya Gas Jl. Pesantren Kuta Krueng Ulee  gle,  Pidie Jaya, Muko Kuthang,  Aceh, Kabupaten  Pidie Jaya, Aceh 24152 4 SPPBE Rahmat Seulawah Jantan Hagu, Panteraja,
Kabupaten Pidie Jaya, Aceh
Berdasarkan data lokasi pangkalan dan gudang  diatas  maka  kita  akan  menghitung jarak  dari  gudang  ke  setiap  pangkalan  yang dibawahinya.  PT.  Indung  Tulot  Energy membawahi memiliki 4 pangkalan dibawahnya yaitu Efendi, Suci Hati, UD. Jasa Keluarga dan BKPS. CV.Muhammad Nuernikmat membawahi 6 pangkalan dibawahnya yaitu Jufri, M Ali, Rakan LPG, Maimun, Rahma Yanti dan Mariah.
Sedangkan PT. Maar Perkasa Jaya Gas hanya membawahi  1  pangkalan  di  wilayah  sigli yaitu  Maar  Perkasa.  Untuk  SPBE  mereka melakukan penyaluran ke setiap gudang yang ada  di  wilayah  kabupaten  Pidie  dan  Pidie Jaya. Berikut adalah hasil pencarian rute dari gudang ke pangkalan.
Tabel 3. Hasil Perbandingan Pencarian Rute
Terpendek No Lokasi Hasil Perhitungan Algoritma Asal Tujuan Djikstr a Ant Colony 1 PT. Indung Tulot Energy Efendi 17 mins 25.38 Mins 2 Suci Hati 23 mins 33.63 Mins 3 UD. Jasa Keluarga 18 mins 28.56 Mins 4 BKPS 20 mins 29.70 Mins 5 Jufri 1 mins 1 Mins
Jurnal Sains Riset (JSR) p -ISSN 2088-0952, e -ISSN 2714-531X http://journal.unigha.ac.id/index.php/JSR DOI. 10.47647/jsr.v10i12
6 CV.Muha mmad Nuernikm at M Ali 9 mins 13.17 Mins 7 Rakan LPG 9 mins 12.36 Mins 8 Maimun 11 mins 15.23 Mins 9 Rahma Yanti 6 mins 8.53 Mins 10 Mariah 7 mins 10.86 Mins 11 PT. Maar Perkasa Jaya Gas Maar Perkasa 71 mins 104.72 Mins Total waktu 192 282.14 Total jarak 90.14
Berdasarkan  tabel  3.  maka  dapat disimpulkan bahwa pencarian dengan menggunakan  algoritma djikstra lebih cepat dibandingkan  dengan  algoritma ant  colony , dimana  jarak  keduanya  secara  keseluruhan 90.14  mins,  dimana  pencarian  dengan djikstra  hanya  memerlukan  waktu  192 mins sedangkan ant  colony memerlukan  waktu 282.14  mins.  Namun  tingkat  keakuratan lokasi setelah melakukan pencarian algoritma ant colony lebih akurat dibandingkan djikstra. Berdasrkan  hasil  ini maka penulis memutuskan bahwa penerapan algoritma ant  colony untuk  pencarian  rute terpendek  pada  aplikasi  E-Gas  lebih  tepat dibandingkan  dengan  penerapan  algoritma djikstra .

## Simpulan dan Saran Kesimpulan
Aplikasi  pencarian  rute  terpendek distribusi gas LPG atau disingkat dengan E- Gas  ini  dibangun  dengan  menggunakan Bahasa pemograman web, serta menggunakan google maps API sebagai peta yang digunakan untuk pencarian rute secara online.  Aplikasi  E-Gas  ini  menerapkan  dua metode pencarian rute yaitu, Djikstra dan Ant Colony,  adapun  hasil  nya  adalah  sebagai berikut:
1. Hasil  pencarian  djikstra  lebih  cepat dibandingkan dengan ant colony namun, rute ataupun posisi pangkalan mengalami pergeseran  dari  lokasi  semula  dan  ini
terjadi  pada  beberapa  titik  ketika melakukan pencarian.
2. Hasil  pencarian  ant  colony  lebih  lambat namun,  tingkat  keakuratan  posisi  lebih akurat  dan  tidak  terjadi  pergeseran sebagai  mana  terjadi  pada  algoritma djikstra.  Pada  pencarian  ant  colony apabila lokasi yang dicari jauh dari jalan maka baru akan terjadi pergeseran posisi agar lebih dekat ke jalan.
3. Pencarian  djikstra  hanaya  bisaa  mencari 1 rute tujuan, sedangkan pada pencarian ant  colony  bisa  melakukan  hingga  10 lokasi  tujuan  yang  berbeda  dalam  1 proses pencarian.

## Saran-Saran
1. Untuk mengembangkan sistem selanjutnya  disarankan  untuk  meliputi wilayah  yang  lebih  luas,  agar  lebih banyak masyarakat yang bisa merasakan manfaat dari aplikasi E-Gas ini.
2. Untuk  pengembngan  system  selanjutnya diharapkan untuk dapat dijadikan sebuah aplikasi berbasis Android ataupun IOS.

## Daftar Pustaka
Sunardi,  A.  Yudhana,  and  A.  A.  Kadim, “Implementasi  Algoritma  Dijkstra
Dalam Penentuan Jalur dan Pemesanan Online Transportasi Umum  Berbasis  Android,”  Semin. Nas. Teknlogi Infromasi dan Komun., pp. 1–7, 2017. N.  Azizah  and  D.  Mahendra,  “Geolocation dengan Metode Djikstra untuk Menentukan  Jalur  Terpendek  Lokasi Peribadatan,” J. Sist. Inf. Bisnis, vol. 02, pp. 96–103, 2017. A.  Ratnasari,  F.  Ardiani,  and  F.  Nurvita, “Penentuan  Jarak  Terpendek  dan Jarak Terpendek Alternatif Menggunakan  Algoritma  Dijkstra Serta  Estimasi  Waktu  Tempuh,” Semin.  Nas.  Teknol.  Inf.  Komun.
Terap., pp. 29–34, 2013.
Jurnal Sains Riset (JSR) p -ISSN 2088-0952, e -ISSN 2714-531X http://journal.unigha.ac.id/index.php/JSR DOI. 10.47647/jsr.v10i12
S.  Andayani  and  E.  W.  Perwitasari, “Penentuan Rute Terpendek Pengambilan sampah di Kota Merauke  Menggunakan  Algoritma
Dijkstra,”  Semin.  Nas.  Teknol.  Inf.
Komun.  Terap.  2014,  vol.,  no.,  pp. 164–170, 2014. Gusmão,  S.  H.  Pramono,  and  Sunaryo, “Sistem Informasi Geografis Pariwisata Berbasis Web Dan Pencarian  Jalur  Terpendek  Dengan Algoritma Dijkstra,” J. EECCIS, vol. 7, no. 2, pp. 125–130, 2013. RIDWAN ACHMAD. 2015. PERBANDINGAN  ALGORITMA DIJKSTRA  DAN  ALGORITMA ANT COLONY

## OPTIMATION
DALAM TRAVELLING SALESMAN PROBLEM (TSP) PADA KOTA SEMARANG
Aprilia,  Kusumah  Angga  Rani.  2017.
IMPLEMENTASI  GOOGLE  MAP API  PADA  APLIKASI  PENENTU RUTE  TERPENDEK  LAYANAN ANTAR KONSUMEN PADA RESTORAN WARALABA.
Zakaria,  Dwiki.  2020.  Sistem  Informasi
Penjualan  Handphone  Berbasis  Web Pada Tiara Cell Panekan. Ginting, Elizaandayni. 2013. Pengembangan Sistem  Informasi  Penjualan  Benih Padi Pada Balai Pengkajian Teknologi Pertanian. Permana,  Bayu.  2018.  Perancangan  Sistem Informasi Penjualan Handphone Berbasis Web.
Nurlaela  E.  2011.  Keamanan  Pangan  dan perilaku penjamah  makanan  di instansi  gizi  rumah  sait.  Media  Gizi Masyarakat Indonesia.