## PENCARIAN SPBU TERDEKAT DAN PENENTUAN JARAK TERPENDEK MENGGUNAKAN ALGORITMA DIJKSTRA (STUDI KASUS DI KABUPATEN JEMBER)
Windi Eka Yulia R., Dwiretno Istiadi, Abdul Roqib Program Studi Sistem Informasi Universitas Jember e-mail:windi.ilkom@unej.ac.id
Abstrak —Stasiun Pengisian Bahan Bakar (SPBU) untuk umum merupakan prasarana yang disediakan PT Pertamina  untuk  memenuhi  kebutuhan  bahan  bakar.  Prasarana  ini  cukup  penting  di  semua  kota,  salah satunya Jember. Akses informasi letak dan fasilitas SPBU di Kabupaten ini masih sangat sulit didapatkan. Penelitian ini membahas tentang pemetaan lokasi, pencarian lokasi, dan penentuan jalur terpendek untuk mencapai  lokasi  SPBU  tersebut.  Pencarian  SPBU  terdekat  pada  penelitian  ini  menggunakan  algoritma Dijkstra. Hasil pengambilan data didapatkan 33 SPBU yang menjual premium dan bio solar di Kabupaten Jember. Pencarian SPBU terdekat dipengaruhi oleh kriteria, cost, dan reverse _cost. Dimana untuk jalan satu  arah  diberikan  nilai reverse _ cost sebesar  1000000,  sehingga  jalan  ini  tidak  akan  pernah  dipilih. Algoritma  dijkstra  sangat  sesuai  dan  mudah  digunakan  pada  studi  kasus  di  penelitian  ini.  Penerapan algoritma  dijkstra  telah  merekomendasikan  jalur  terpendek  jarak  tempuh  guna  memberikan  efisiensi penggunaan bahan bakar kendaraan bermotor.
Kata Kunci : SPBU, Algoritma Dijkstra dan jalur terpendek
Abstract — Fuel Filling Station (Gas Station) to the public is an infrastructure provided by PT Pertamina. This  infrastructure  is  quite  important  in  all  cities,  one  of  which  is  Jember.  Access  to  information  and facilities layout stations in this district is still very difficult to obtain. This study discusses the mapping of the location, location, and the determination of the shortest path to reach the location of the gas station. Search nearby gas stations in this study using the Djiktra’s algorthm . The results of the  data collection obtained 33 gas stations that sell gasoline and bio- diesel in Jember . T he shortest path location is dependent on criteria , cost, and reverse _cost. To identification of one way by providing high value to reverse _ cost parameter of 1000000 , so this road will never be selected. Dijkstra’s algorithm is very suitable and easy to use on a case study in this research. Implementation of dijkstra’s algorithm has recommended the shortest path in order to provide fuel efficiency of motor vehicles.
Keywords : Gas Station, Djiktsr’s Algorith, and  shortest path

## I. PENDAHULUAN
Kabupaten  Jember    merupakan  salah  satu kabupaten  yang  berada  di  Jawa  Timur  yang memiliki peningkatan perkembangan pembangunan  yang  sangat  pesat  [1].  Salah satunya  adalah  pembangunan  infrastruktur stasiun  pengisian  bahan  bakar  umum  (SPBU). Peran  dari  SPBU  tersebut  tidak  kalah  penting fungsinya  seperti  infrastruktur  penting  lainnya yang  ada  di  Kabupaten  Jember.  Keberadaan SPBU  sangat  penting  karena  dapat  melayani masyarakat  dalam  memenuhi  kebutuhan  bahan bakar kendaraan bermotor.
Kabupaten  Jember    merupakan  salah  satu destinasi kota yang banyak objek wisatanya [2], sehingga  tidak  sedikit  para  wisatawan  dari luar
kota berdatangan dengan tujuan berwisata. Kota Jember juga merupakan akses utama jalur mudik karena Kabupaten Jember  merupakan salah satu pusat regional di kawasan tapal kuda, sehingga banyak  pengendara  kendaraan  bermotor  yang dari  luar  kota  bepergian  ke  kota  Jember  baik untuk  berkunjung  ataupun  berwisata.  Di  luar kota pengendara biasanya tidak begitu mengetahui  letak  SPBU,  sehingga  mereka kesulitan dalam menentukan harus ke mana dan melewati  jalur  mana  yang  lebih  dekat  untuk menuju SPBU.
Pada  [2]  dijelaskan  bahwa  sistem  informasi geografis  berbasis  web  dapat  mempermudah pengguna  mengakses  informasi  lokasi  SPBU dimana  saja  dan  kapan  saja  serta  dapat membantu  pengguna  dalam  menentukan  letak
SPBU baru yang strategis . Rute terpendek juga pernah  menjadi  konsen  penelitian  Sofyan Arifianto [4] . Pada  penelitian  ini  diaplikasikan penentuan  rute  terpendek  pada  jaringan  multi moda transportasi umum menggunakan algoritma  dijkstra.  Algoritma  dijkstra  dianggap cocok karena mudah digunakan oleh user dalam penggunaannya hanya dengan menentukan titik awal dan titik tujuan.
Berdasarkan  referensi  penelitian  yang  telah ada  dapat  diketahui  bahwa  algoritma  dijkstra sesuai  untuk  pencarian  jarak  terpendek.  Pada penelitian ini, akan diterapkan algoritma dijkstra untuk mencarian SPBU terdekat dan penentuan jarak terpendek di Kabupaten Jember . Hasil dari penelitian  ini  diharapkan  dapat  memberikan informasi  letak  SPBU  dan  merekomendasikan jalur terpendek jarak tempuh guna memberikan efisiensi  penggunaan  bahan  bakar  kendaraan bermotor.

## II. TINJAUAN PUSTAKA
Jalur Terpendek ( Shortest Path Problem ) Proses  penghitungan  rute  terpendek  adalah proses  mencari  jarak  terpendek  atau  biaya terkecil suatu rute dari node awal ke node tujuan dalam sebuah jaringan. Pada proses penghitungan  rute  terpendek  terdapat  dua macam proses yaitu proses pemberian label dan proses  pemeriksaan  node.  Metode  pemberian label  adalah  metode  untuk  memberikan identifikasi  pada  setiap  node  dalam  jaringan. Pada sebagian besar algoritma penghitungan rute terpendek,  terdapat  3  label  informasi  yang dikelola  untuk  setiap  node  i  pada  proses pemberian  label  yaitu:  label  jarak  d(i), parent node p(I), dan status node S(i) [5]. Algoritma  yang  dapat  digunakan  untuk mencari  jalur  terpendek  telah  banyak  diteliti. Beberapa algoritma yang dapat digunakan untuk menyelesaikan penentuan jalur terpendek adalah dijkstra’s algorithm, bell bellman- ford’s algorithm, a* search algorithm, dan floyd–warshall algorithm [6].

## Algoritma Dijkstra
Algoritma  dijkstra  merupakan  salah  satu bentuk algoritma greedy. Algoritma ini termasuk algoritma pencarian graf yang digunakan untuk menyelesaikan  masalah  lintasan  terpendek dengan satu sumber pada sebuah graf yang tidak memiliki cost sisi  negatif,  dan  menghasilkan
sebuah pohon lintasan terpendek. Algoritma ini sering digunakan pada routing [5].
Algoritma  dijkstra  menggunakan adjacent list untuk  merepresentasikan  sebuah  jaringan. Secara  garis  besar  algortima  dijkstra  membagi semua node menjadi dua, kemudian dimasukkan ke  dalam  tabel  yang  berbeda,  yaitu  tabel permanen  dan  tabel  temporal.  Tabel  permanen berisi  node  awal  dan node-node  yang  telah melalui  proses  pemeriksaan  dan  labelnya  telah diubah  dari  temporal  menjadi  permanen.  Tabel temporal  berisi node-node yang  berhubungan dengan node pada tabel permanen.

## III. METODOLOGI ATAU TEORI
Penelitian  ini  dimulai  dari  pengumpulan data  dan  pemetaan  lokasi  SPBU  di  Kabupaten Jember . Data lain yang dibutuhkan adalah data jalan, persimpagan, dan info jalur satu arah. Data tersebut  akan  digunakan  untuk  penggambaran peta  lokasi  SPBU.  Pencarian  data  yang dibutuhkan  sebagian  besar  adalah  data  spatial, sehingga dibutuhkan GPS, metode tracking, dan wawancara  kepada  pemilik/karyawan  SPBU. Data jalan di Indonesia yang didapat dari google dapat dilihat pada gambar 1. Data tersebut akan dilakukan proses intersection dengan data batas wilayah Kabupaten Jember yang ada di gambar 2. Hasil intersection dari kedua data adalah data jalan  yang  ada  di  Kabupaten  Jember,  dapat dilihat pada gambar 3.
Gambar 1. Data jalan di Indonesia
Gambar 2. Batas wilayah Kabupaten Jember
Gambar 3. Data jalan di Kabupaten Jember
Data  spatial  yang  didapat  akan  digunakan untuk proses intersection dengan data jalan yang ada  di  Indonesia.  Hasil  proses  tersebut  akan didapat data jalan yang ada di Kabupaten Jember saja. Data atribut yang berupa nilai kriteria, cost, dan  reverse  _cost  akan  digunakan  dalam perhitugan algoritma Dijkstra untuk mendapatkan  jalur  terpendek.  Detail  proses penentuan jalur terpendek menuju lokasi SPBU menggunakan  algoritma  dijkstra    dapat  dilihat pada gambar 4.
Gambar 4. Diagram penentuan jalur terpendek SPBU

## IV. HASIL DAN PEMBAHASAN
Pencarian  SPBU  terdekat  pada  penelitian ini  dimulai  dengan  menghitung  jarak  user  ke masing-masing SPBU. Perhitungan jarak dilakukan  oleh  sistem  dengan  memilih  posisi user  pada  peta.  Perhitungan  jarak  ini  akan menghasilkan  rekomendasi  SPBU  terdekat  dari posisi  user.  Proses  ini  membutuhkan  beberapa parameter, yaitu parameter geometry awal dalam hal  ini  adalah  posisi  user  dan  geometry  akhir dalam  hal  ini  adalah  posisi  SPBU  terdekat. Parameter tersebut akan dihitung untuk mendapatkan perbandingan jarak dengan menggunakan  rumus Haversine formula  pada persamaan 1.
...(1)
Perhitungan SPBU terdekat pada penelitian ini  dapat  diberikan  1  contoh  kasus  detail. Langkah  pertama  adalah  penentuan  posisi  user dan  posisi  SPBU  terdekat  yang  dapat  dilihat pada gambar 5.
Gambar 5. Posisi user dan SPBU terdekat
Langkah  kedua  posisi geometry user  dan SPBU dibandingkan unntuk mendapat jaraknya. Hasil perbandingan jarak dapat dilihat pada tabel 1.  Dari  hasil  perbandingan  tersebut  akan dilakukan perhitungan jalur terpendek.
Perhitungan ini dilakukan  dengan  meenghitung panjang  pada  masing-masing  jalan.  Pada penelitian  ini,  setiap  persimpangan  jalan  yang ada  adalah vertex .  Parameter  yang  harus diperhatikan  adalah  jenis  kendaraan  apa  yang digunakan  oleh  user  dan  arah  jalur  pada  jalan tersebut.  Jenis  kendaraan  diperlukan  untuk mencari  jalan  terdekat  yang  sesuai  dengan kendaraan  user.  Beberapa  jalan  hanya  bisa dilalui  oleh  sepeda  motor,  sehingga  jalan tersebut  tidak  akan  dipilih  ketika  user menggunakan mobil.
Langkah  berikutnya  adalah  perhitungan jalur terpendek dengan menggunakan algoritma Dijkstra  .  Perhitungan  ini  dapat  dilakukan dengan  representasi graph .  Jalan  antara  user dengan  SPBU  digambarkan  dengan edge , sedangkan setiap persimpangan
akan
digambarkan dengan vertex .
Tabel 1. Hasil perbandingan jarak geometry
Notasi graph hasil  representasi  pencarian  jalur terpendek SPBU dapat dilihat pada gambar 6.
Gambar 6. Notasi graph pencarian jalur terdekat
Penentuan  jalur  terpendek  pada  gambar  6 dengan menggunakan algoritma Dijkstra menghasilkan rute terpendek A  B  F  I  J. Perhitungan penyelesaiannya dapat dilihat pada tabel 2.
Tabel 2. Hasil perhitungan algoritma Dijkstra
Hasil  perhitungan  dari  algoritma  dijkstra telah  diimplementasikan  kedalam  sistem  pada penelitian  ini.  Hasil  yang  ditampilkan  sistem dengan  contoh  kasus  ini  telah  sesuai  dengan perhitungan manual algoritma dijkstra.
Perhitungan  dari  sistem  dapat  dilihat  pada gambar 7.
Gambar 7. Hasil perhitungan pada sistem
Untuk  menguji  ketepatan  perhitungan  dan implementasi  algoritma  dijkstra  ,  penentuan jalur terpendek juga dihitung dengan menggunakan software lain yaitu QuantumGIS . Hal  ini  dilakukan  untuk  melihat  apakah  jalur yang  dihasilkan  sudah  benar.  Dari  hasil perbandingan didapatkan hasil bahwa jalur yang telah  diperoleh  sama  dengan  perhitungan QuantumGIS .

## V. KESIMPULAN
Kesimpulan  dari  penelitian  ini  dapat  dibagi menjadi beberapa yaitu :
1. Hasil  pengambilan  data  pemetaan  SPBU  di Kabupaten  Jember    didapatkan  33  SPBU dimana  semua  SPBU  menjual  bahan  bakar premium  dan  bio  solar.  Dari  33  SPBU tersebut  19  menjual  pertamax,  7  menjual pertamax dex, dan 6 menjual keduanya.
2. Hasil  perhitungan  jarak  terpendek  dalam pencarian  SPBU  dipengaruhi  oleh  nilai kriteria,  cost,  dan reverse _cost.  Sedangan nilai waktu tempuh didapat dari perhitungan jarak dibagi dengan kecepatan.
3. Identifikasi jalan satu arah dilakukan dengan memberikan  nilai reverse _ cost sebesar
1000000.  Nilai  ini  diberikan  agar  pada  saat perhitungan, jalan ini mempunyai nilai yang tinggi  dibandingkan  jalan  lain.  Sehingga jalan ini tidak akan pernah dipilih.
4. Penentuan  jalan  yang  diambil  oleh  sistem juga  ditentukan  oleh  jenis  kendaraan  yang digunakan oleh user. Pada penelitian ini yang diambil adalah mobil dan sepeda motor.

## DAFTAR PUSTAKA
[1] Arifin,  Edy  Burhan.  2006.  Pertumbuhan Kota  Jember  dan  Munculnya  Budaya Pandhalungan. Jakarta : Konferensi Nasional Sejarah VIII. [2] Gusmao,  Antonio,  dkk.  2013. Sistem Informasi  Geografis  Pariwisata  Berbasis Web  Dan  Pencarian  Jalur  Terpendek Dengan Algoritma Dijkstra. Jurnal EECCIS Vol. 7, No. 2. [3] Darmawan, Artha Eka, dkk. Tanpa Tahun. Sistem Informasi Geografis Stasiun Pengisian  Bahan  Bakar  Umum  Di  Kota Batam. Jurnal Fakultas Teknik Universitas Maritim Raja Ali Haji (UMRAH).
[4] Arifianto,  Sofyan.  2012.  Sistem  Aplikasi Penentuan  Rute  Terpendek  Pada  Jaringan Multi Moda
Transportasi Umum
Menggunakan  Algoritma  Dijkstra.  Tesis.
Program  Studi  Magister  Sistem  Informasi Universitas Diponegoro Semarang. [5] Purwananto, Yudhi, dkk. 2005. Implementasi  Dan  Analisis  Algoritma Pencarian  Rute  Terpendek  Di  Kota Surabaya. Jurnal Penelitian dan
Pengembangan TELEKOMUNIKASI. Vol.
10, No. 2.
[6] Sanan, dkk. 2013. Shortest Path Algorithm. International  Journal  of  Application  or Innovation in Engineering & Management (IJAIEM). Volume 2, Issue 7.

## Biodata Penulis
Windi Eka Yulia Retnani, S.Kom.,MT ., Staff Pengajar  di  Universitas  Jember.  Lahir  di Nganjuk pada tanggal 5 Maret 1984. Pendidikan S1  di  jurusan  Ilmu  Komputer  Universitas Brawijaya.  Pendidikan  S2  di  jurusan  Rekayasa Perangkat Lunak Institut Teknologi Bandung.