## Aplikasi Perhitungan Dan Visualisasi Jarak Terpendek Berdasarkan
Data Coordinate Dengan Algoritma Dijkstra Dalam Kasus Pengantaran Barang Di Kawasan Jabodetabek
Elsa Kusuma 1] , Jefri 2] , Halim Agung 3]
Program Studi Teknik Informatika [1], [2], [3] Universitas Bunda Mulia Jakarta, Indonesia
Abstrak —  Penelitian  diangkat  berdasarkan  rute-rute  yang ditempuh  para  pengantar  barang.  Karena  kondisi  jalan  yang macet dan memakan waktu lama, mereka seringkali kebingungan untuk  menentukan  rute  terbaik.  Berdasarkan  variasi  rute  yang ditempuh  dan  jarak  antara  titik  awal  dan  tujuan,  kita  dapat menghitung  dan  menentukan,  jalur  mana  yang  memiliki  jarak terpendek dan terefektif. Dalam penelitian ini, algoritma Dijkstra diterapkan untuk menghitung jarak terpendek dari suatu titik ke titik  lainnya  dalam  area  Jabodetabek,  berdasarkan  banyaknya titik  koordinat  yang  terdapat  dalam database .  Metode Iterative- Enhancement diterapkan  dalam  mengembangkan  sistem  ini. Pengumpulan  data  dilakukan  melalui  observasi  pola  rute  yang sering  dilalui  dan  studi  literatur,  disertai  penelitian  terdahulu tentang implementasi algoritma Dijktra . Sistem dirancang dalam beberapa  tahapan,  yaitu  analisis  kebutuhan  sistem  dan user , perancangan flowchart ,  perancangan DFD ,  perancangan database ,  hingga  perancangan  tampilan  sistem.  Hasil  penelitian akan diwujudkan dalam bentuk sistem perangkat lunak berbasis web dan  mencantumkan  peta  sederhana  sebagai  sarana  untuk membantu para pengantar barang menentukan rute pengantaran yang  lebih  sesuai.  Hasil  penelitian  diperoleh  dari  pengujian dengan dua kondisi (jumlah data) yang berbeda, yakni 2.056 dan 5.186  titik  koordinat.  Pengujian  menunjukkan  perbedaan  jarak terpendek yang signifikan untuk masing-masing kondisi, di mana hasil perhitungan dengan kondisi jumlah data lebih sedikit tidak lebih efektif dibandingkan kondisi jumlah data lebih banyak. Dari pembahasan  dan  pengujian,  disimpulkan  bahwa  algoritma Dijkstra sangat membanu dalam menentukan rute terpendek yang optimal.  Didapati  pula  bahwa  jumlah  data  sangat  berpengaruh terhadap  hasil  perhitungan.  Semakin  banyak  jumlah  titik koordinat  yang  ada  dalam database ,  semakin  optimal  hasil perhitungan  yang  akan  diperoleh.  Sistem  juga  menawarkan kemudahan  bagi  setiap  pengguna  melalui  tampilan  peta  yang tertera sebagai visualisasi rute.
Kata Kunci— Jabodetabek, Dijkstra, Iterative-Enhancement, Titik koordinat, Latitude, Longitude, Euclidean Distance, Jarak terpendek

## I. PENDAHULUAN
Dewasa  ini,  mobilitas  di  jalan  raya  kerap  kali  menjadi kendala  di  kota-kota  besar,  khususnya  Jakarta.  Kemacetan  di jalan  utama  yang  terlalu  padat  menambah  parah  kondisi tersebut. Banyak dari pengendara jalan, akhirnya memilih rute alternatif untuk mencapai destinasinya. Hal ini membuat rute yang ditempuh menjadi beraneka ragam dan perlu untuk diteliti, mana yang paling efektif.
Kasus yang penulis angkat kali ini didasari pada rute-rute yang  ditempuh  para  pengantar  barang.  Dengan  tujuan  untuk tiba  di  destinasi  pengiriman  secepat  mungkin,  banyak  dari mereka yang begitu mengenal kawasan lalu lintas. Pengetahuan mereka  tersebut  dipergunakan  untuk  mempercepat  layanan mereka mengirim barang.
Berdasarkan variasi rute yang ditempuh dan pola cakupan pengantaran  yang  identik,  kita  dapat  menghitung  dan menentukan,  jalur  mana  yang  memiliki  jarak  terpendek  dan lebih efektif. Nantinya, hasil tersebut dapat direkomendasikan kepada para pengantar barang. Kecepatan pengiriman pun akan meningkat  yang  kemudian  akan  berbuah  pada  banyak  hal positif lainnya.
Oleh karena masalah tersebut, penulis ingin membuat penelitian  yang  berjudul  Penentuan  Jarak  Terpendek Berdasarkan  Data  Coordinate  Menggunakan  Algoritma Dijkstra  Dalam  Kasus  Pengantaran  Barang  Se-Jabodetabek. Lintasan terpendek dapat diartikan sebagai bobot minimal dari kombinasi  rute.  Grafis  lintasan  tersebut  yang  akan  dijadikan indikator hasil perhitungan jarak terpendek.

## II. LANDASAN TEORI
A. Teori Transportasi
Pengertian  transportasi  berasal  dari  kata  Latin,  yaitu transportare ,  di  mana trans diartikan  seberang  atau  sebelah
lain,  dan portare berarti  mengangkut  atau  membawa.  Jadi secara harafiah, transportasi berarti mengangkut atau membawa (sesuatu) ke sebelah lain, dari suatu tempat ke tempat lain. Ini berarti transportasi meruapakan suatu jasa yang diberikan, guna menolong  orang  atau  barang  dalam  hal  pemindahan  posisi. Dapat  ditegaskan  pula  bahwa  transportasi  adalah  jasa  yang dipergunakan  sebagai  alat  untuk  memperoleh  keuntungan- keuntungan  ekonomis  dalam  berbagai  kegiatan  usaha  dan hubungan kemasyarakatan [5] .
B. Latitude dan Longitude
Latitude adalah garis yang melintang di antara kutub utara dan kutub selatan, yang menghubungkan antara sisi timur dan barat  bagian  bumi.  Garis  ini  memiliki  posisi  membentangi bumi, sama halnya seperti garis equator (khatulistiwa), tetapi dengan  kondisi  nilai  tertentu.  Garis  lintang  inilah  yang dijadikan ukuran dalam mengukur sisi utara-selatan koordinat suatu titik di belahan bumi. Sedangkan, longitude adalah garis membujur  yang  menghubungkan  antara  sisi  utara  dan  sisi selatan  bumi  (kutub).  Garis  bujur  ini  digunakan  untuk mengukur sisi barat-timur koordinat suatu titik di belahan bumi. Sama seperti equator pada latitude yang berada di tengah dan memiliki nilai 0 (nol) derajat, pada longitude , garis tengah yang bernilai  0  (nol)  derajat  disebut  garis prime meridian (garis bujur). Sedangkan, garis yang berada paling kiri memiliki nilai -90 derajat, dan yang paling kanan memiliki nilai 90 derajat [12] .

## C. Euclidean Distance
Euclidean Distance adalah  metrik  yang  digunakan  untuk menghitung kesamaan 2 vektor. Fungsi Euclidean menghitung akar  dari  kuadrat  perbedaan  2  vektor. Euclidean space diperkenalkan  oleh  Euclid,  seorang  matematikawan  dari Yunani sekitar tahun 300 B.C.E . untuk mempelajari hubungan antara sudut dan jarak. Euclidean ini biasanya diterapkan pada 1,  2,  dan  3  dimensi [12] .  Adapun  rumus  dari  perhitungan Euclidean Distance dalam ranah 2 dimensi sebagai berikut:
𝐿𝑎𝑡𝑖𝑡𝑢𝑑𝑒1 𝐿𝑎𝑡𝑖𝑡𝑢𝑑𝑒2 𝐿𝑜𝑛𝑔𝑖𝑡𝑢𝑑𝑒1
𝐿𝑜𝑛𝑔𝑖𝑡𝑢𝑑𝑒2
Rumus 2.1 Perhitungan Euclidean Distance [12]
D. Algoritma Algoritma  merupakan  langkah-langkah  logis  penyelesaian masalah yang disusun secara sistematis terhadap permasalahan yang  akan  diselesaikan.  Dalam  bidang  komputer,  algoritma sangat  diperlukan  dalam  menyelesaikan  berbagai  masalah pemrograman,  terutama  dalam  proses  komputasi  numerik. Tanpa  algoritma  yang  dirancang  dengan  baik  maka  proses pemrograman akan menjadi salah, rusak atau lambat dan tidak efisien [6] .
 Algoritma Pencarian Rute Terpendek Secara  umum,  pencarian  jalur  terpendek dibagi  menjadi  dua  metode,  yaitu  metode
konvensional  dan  metode  heuristik.  Metode konvensional  cenderung  mudah  dipahami  dari  pada metode heuristik. Tetapi bila dibandingkan, hasil yang diperoleh  dari  metode  heuristik  lebih  variatif  dan waktu yang diperlukan lebih singkat.
 Algoritma Dijkstra Pencarian rute terpendek termasuk ke dalam materi  teori  graf.  Algoritma  yang  sangat  terkenal untuk  menyelesaikan  persoalan  ini  adalah  algoritma Dijkstra .  Algoritma  ini  ditemukan  oleh  seorang ilmuwan  komputer  berkebangsaan  Belanda  yang bernama  Edsger  Dijkstra.  Algoritma Dijkstra dianggap  cocok  karena  mudah  digunakan  oleh user dalam penggunaannya hanya dengan menentukan titik awal dan titik tujuan [14] .
Dijkstra adalah  algoritma  yang  digunakan untuk  mencari  lintasan  terpendek  pada  sebuah  graf berarah.  Contoh  penerapan  algoritma  ini  adalah lintasan  terpendek  yang  menghubungkan  antara  dua kota  berlainan  tertentu.  Kasus  ini  sering  disebut Single-source Single Destination Shortest Path Problems .
Cara  kerja  algoritma Dijkstra memakai stategi greedy , di mana pada setiap langkah dipilih sisi dengan  bobot  terkecil  yang  menghubungkan  sebuah simpul  yang  sudah  terpilih  dengan  simpul  lain  yang belum  terpilih.  Algoritma Dijkstra membutuhkan parameter berupa tempat asal dan tempat tujuan [4] .
Parameter tersebut berisi rute berbentuk sisi ( vertex )  atau vertices dalam  bentuk  jamak  untuk diperbandingkan.  Setiap  sisi  dari  rute  ini  adalah pasang vertices (u,v)  yang  melambangkan  hubungan dari vertex u ke vertex v. Himpunan semua tepi kita sebut  sebagai E .  Bobot  ( weights )  dari  semua  sisi dihitung dengan fungsi :

## 𝑤 ∶ 𝐸 → 0, ∞

## Rumus 2.2 Perhitungan Bobot pada Algoritma
Dijkstra [13]
Jadi,  w(u,v)  adalah  jarak  tak-negatif  dari vertex u  ke vertex v.  Ongkos  ( cost )  dari  sebuah  sisi dapat dianggap sebagai jarak antara dua vertices , yaitu jumlah jarak semua sisi dalam jalur tersebut [9] . Untuk sepasang vertex s  dan  t  dalam  V,  algoritma  ini menghitung  jarak  terpendek  dari  s  ke  t.  Adapun pseudocode penerapannya  dapat  divisualisasikan sebagai berikut :
Gambar 2.1 Pseudocode Algoritma Dijkstra [7] Algoritma Dijkstra diterapkan pada penelitian berjudul Vehicle Routing Problems for City Logistics [2] dengan  hasil  penelitian  bahwa  optimasi rute  kendaraan  berperan  sebagai  kunci  dalam perkembangan  mobilisasi  produk  urban.  Penelitian berjudul  Aplikasi  pgRouting  Untuk  Penentuan  Jalur Optimum Pada Pembuatan Rute Pemadam Kebakaran (Studi Kasus : Kota Semarang) [3] menghasilkan tabel spasial/layer  baru  melalui  beberapa  perintah SQL Query yang  tersimpan  pada  basis  data PostgreSQL . Penelitian  berjudul  Pencarian  Rute  Terpendek Menggunakan  Algoritma  Dijkstra  Pada  Sistem Informasi  Geografis  Pemetaan  Stasiun  Pengisian Bahan  Bakar  Umum[4]  menghasilkan  informasi  dan membantu  pengguna  dalam  melakukan  pencarian lokasi  SPBU  berdasarkan  nama  dan  rute  terpendek antar  lokasi  SPBU  dalam  bentuk  peta  jalan  kota Padang.  Penelitian  berjudul An Application of Dijkstra’s Algorithm to Shortest Route Problem [7] menghasilkan  Rute  terpendek  antar node dalam jaringan  peta  dapat  ditentukan  dari  destinasi  yang diinginkan  dan  melalui  proses back- tracking melewati node-node yang  ada.  Penelitian  berjudul Railway Route Optimization System Using Dijkstra Method [8]  menghasilkan  kesimpulan  rute  terpendek yang diperoleh akan lebih optimal berdasarkan jarak di antara dua stasiun, bukan waktu yang ditempuh dari stasiun  awal  ke  stasiun  akhir.  Penelitian  berjudul Pencarian  Rute  Terpendek  Menggunakan  Algoritma Dijkstra  Pada  SIG  Berbasis Web Untuk  Distribusi Minuman (Studi Kasus PT. Coca Cola Kota Padang) [9]  menghasilkan  informasi  untuk  PT.  Coca  Cola tentang  jalur  mana  yang  bisa  ditempuh  untuk mempercepat proses pendistribusian engan mengikuti jalur  terpendek  yang  dihasilkan.  Penelitian  berjudul Pencarian  SPBU  Terdekat  Dan  Penentuan  Jarak Terpendek  Menggunakan  Algoritma  Dijkstra  (Studi Kasus  di  Kabupaten  Jember)  [10]  menghasilkan perhitungan  jarak  terpendek  dalam  pencarian  SPBU
dipengaruhi oleh nilai kriteria, cost , dan reverse cost . Sedangkan,  nilai  waktu  tempuh  didapat  dari perhitungan  jarak  dibagi  kecepatan.  Penelitian berjudul  Optimalisasi  Algoritma  Dijkstra  Dalam Menghadapi Perbedaan Bobot Jalur Pada Waktu Yang Berbeda  [13  ]menghasilkan  kesimpulan  bahwa keterbatasan algoritma Dijkstra dapat  diatasi  dengan penerapan metode yang diusulkan dalam menghadapi perbedaan bobot jalur yang berbeda-beda.

## E. Iterative-Enhancement Model
S oftware-development life-cycle adalah proses terbentuknya sebuah  sistem  informasi  yang  dimulai  dari  konseptual  ke implementasi. Software-development life-cycle digunakan untuk  membantu  mengerti  keseluruhan proses,  membantu untuk  merencanakan  sumber  daya  yang  digunakan,  dan membantu  untuk  mengontrol  jalannya  proses. Software- development life-cyle terbagi  menjadi  lima  sampai  sembilan tahap, minimal  harus  memiliki lima  tahap dan paling banyak adalah sembilan tahap [6] .
Gambar 2.2 Iterative-Enhancement Model [6]
Iterative-enhancement model adalah  model  linier  yang diterapkan  secara  berulang-ulang.  Pada  model  ini,  proses dipecah  menjadi  beberapa  modul  yang  dikembangkan  secara bertahap. Kebutuhan utama yang telah diketahui dapat diproses terlebih dahulu, kebutuhan termasuk perubahan lainnya dapat diproses  setelahnya.  Masing-masing  proses  dapat  dilakukan berulang-ulang hingga mendapatkan hasil yang diinginkan [6] .

## F. Data Flow Diagram (DFD)
Data Flow Diagram digunakan  untuk  menggambarkan suatu fungsi dari suatu sistem informasi. Beberapa simbol yang digunakan dalam Data Flow Diagram dapat dilihat pada Tabel 2.1.

## Tabel 2.1 Simbol DFD [14]
Data Flow Diagram memiliki beberapa tahap dalam pembuatannya.  Tahap  awal  adalah  diagram  konteks  yang menggambarkan keseluruhan sistem secara umum. Selanjutnya adalah diagram level 0 untuk menggambarkan tahapan proses dari diagram konteks. Selanjutnya adalah diagram level 1 untuk menggambarkan  tahapan  proses  dari  diagram level 0  dan seterusnya [14] .
G. Entity Relationship Diagram (ERD) ERD ( Entity Relationship Diagram )  adalah  suatu  model jaringan yang menggunakan susunan data yang disimpan dalam sistem secara  abstrak. Dalam sebuah sistem  informasi entitas adalah  data  yang  mewakili  seseorang,  tempat,  benda,  atau kegiatan  untuk  disimpan  atau  diolah,  sedangkan  karakteristik khusus atau ciri–ciri khusus dalam suatu entitas disebut atribut. Sebuah database dapat  memiliki  lebih  dari  satu  entitas  dan hubungan antar entitas tersebut disebut ERD. [14]
ERD  merupakan  model  yang  menunjukan  relasi  logis  dan interaksi  antar  entitas.  ERD  digunakan  untuk  memodelkan keseluruhan  sistem  dan  dasar  untuk  membuat  struktur  data fisik. Simbol–simbol yang digunakan dalam ERD dapat dilihat pada Tabel 2.2.
Tabel 2.2 Simbol ERD Crow’s Foot [14]
H. Flowchart Flowchart adalah sebuah teknik yang merepresentasikan alir kendali dalam program [6]. Beberapa simbol yang digunakan dalam flowchart dapat dilihat pada Tabel 2.3.
Tabel 2.3 Simbol Flowchart [6]

## III. ANALISIS DAN PERANCANGAN

## A. Analisis Kebutuhan
Berikut  ini  adalah  kebutuhan  fungsional  dan  kebutuhan non-fungsional dari sistem penentuan jarak terpendek ini :

## 1) Kebutuhan fungsional
Kebutuhan  fungsional  yang  ada  dalam  sistem  ini adalah sebagai berikut:
a) Sistem  dapat  menerima  data  masukan  dari user berupa titik awal penerimaan  barang  dan titik destinasi pengiriman barang.
b) Sistem  dapat  mengkonversi  masukan  tersebut menjadi format koordinat
latitude dan longitude .
c) Sistem  dapat  terkoneksi  dengan database penyimpanan histori rute para pengantar barang.
d) Sistem  dapat  mengeksekusi  masukan  dan mengkalkulasi jarak terpendek berdasarkan data coordinate .
e) Sistem  dapat  memberikan  keluaran  berupa  nilai jarak terpendek dari titik awal ke titik akhir dalam satuan kilometer.

## 2) Kebutuhan non fungsional
Kebutuhan  non-fungsional  yang  ada  dalam  sistem penentuan jarak terpendek ini adalah sebagai berikut :
a) Beberapa perangkat lunak yang dibutuhkan untuk pengembangan sistem penentuan jarak terpendek ini adalah Sistem Operasi, minimal Windows XP atau  versi  di  atasnya, web browser ,  dan MongoDB.
b) Untuk dapat menjalankan sistem penentuan jarak terpendek ini dengan baik, dibutukan spesifikasi minimal  perangkat  keras  adalah Processor Intel Pentium IV,  RAM  2GB,  dan  Ruang harddisk kosong 1GB.
c) Adapun analisis kebutuhan user adalah User yang memiliki  kemampuan  untuk  mengoperasikan komputer  dan  memahami  sistem  operasi
Windows ,    Sistem  dapat  memberikan  notifikasi kepada
user
saat terjadi kesalahan pemasukan data atau ketidaklengkapan data, dalam  kasus  lain,  sistem  dapat  memberikan notifikasi kepada user pula jika basis data belum terintegrasi  dengan  sistem  yang  menyebabkan kegagalan sistem.

## B. Metodologi Pengembangan Sistem
Tahapan  yang  penulis  lakukan  dengan  metodologi pengembangan sistem iterative-enhancement , yaitu:
 Analysis
Pada tahap ini, penulis melakukan studi kepustakaan yang bersumber dari buku, jurnal, skripsi dan internet. Lalu memutuskan  untuk  membuat  sistem  penentuan  jarak terpendek berdasarkan data coordinate dengan menerapkan fungsi Euclidean Distance
dan mengimplementasikan  algoritma Dijkstra .  Lalu  penulis juga melakukan analisis dan perencanaan terhadap sistem yang  dikembangkan.  Kegiatan  analisa  dan  perencanaan yang  dilakukan  antara  lain,  analisis  kebutuhan fungsional  sistem,  analisis  kebutuhan  non-fungsional sistem, dan analisis kebutuhan user .
 Design
Pada  tahap  ini,  dilakukan  desain  terhadap  sistem penentuan  jarak  terpendek  yang  akan  dikembangkan, antara lain desain alur kerja sistem dengan menggunakan flowchart dan  desain  fungsionalitas  sistem  dengan menggunakan Data Flow Diagram.
 Code
Pada tahap ini, penulis membangun sistem yang telah dirancang  dengan  menggunakan  bahasa  pemrograman Javascript.
 Testing
Pada  tahap  ini  dilakukan  uji  coba  sistem  yang  telah dibuat  untuk  melihat  masih  ada  kesalahan  atau  tidak. Penulis  melakukan  pengecekan  proses  perhitungan  jarak dan penentuan rute dari data coordinate berupa   graf yang  dapat  dilihat  oleh  mata  manusia.  Penulis  juga membandingkan  optimasi output berupa  jarak  terpendek yang dihasilkan.
 Delivery of Increment
Pada tahap ini penulis menerima kritik dan saran dari para  dosen  mengenai  mengenai  sistem  yang  dibuat.  Jika sistem disetujui, maka sistem akan dirilis. Tetapi, jika  masih  ada  bagian  dari  sistem  yang  belum  disetujui, maka  penulis  akan  mengulang  kembali  proses
pengembangan aplikasi ke increment yang selanjutnya.

## C. Perancangan Proses
1) Alur Penentuan Jarak Terpendek
Proses perhitungan dan penentuan jarak dimulai dari  penerimaan  masukan  berupa  titik pick-up dan delivery dari user . Kemudian, sistem lanjut ke proses pencarian  titik  terdekat  dan  perhitungan  jarak  antar titik, hingga sampai ke titik destinasi ( delivery ). Alur proses  digambarkan  dalam  bentuk flowchart pada gambar 3.1, sebagai berikut :
Gambar 3.1 Flowchart Proses Penentuan Jarak Terpendek
Sedangkan,  proses  perhitungan  dengan algoritma Dijkstra digambarkan  pada  gambar  3.2, sebagai berikut :

## ISSN
: 2301-7988
Gambar 3.2 Flowchart Proses Perhitungan Jarak Terpendek
Secara deskriptif, algoritma  ini terdiri dari beberapa langkah. Langkah-langkah algoritma Dijkstra dapat dipaparkan sebagai berikut:
a) Tentukan  titik  mana  yang  akan  menjadi  node  awal, lalu  beri  bobot  jarak  pada  node  pertama  ke  node terdekat  satu  per  satu, Dijkstra akan  melakukan pengembangan  pencarian  dari  satu  titik  ke  titik  lain dan ke titik selanjutnya tahap demi tahap.
b) Beri  nilai  bobot  (jarak)  untuk  setiap  titik  ke  titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (belum terisi).
c) Set semua node yang belum dilalui dan set node awal sebagai “Node keberangkatan”.
d) Dari  node  keberangkatan,  pertimbangkan  node tetangga yang belum dilalui dan hitung jaraknya dari titik  keberangkatan.  Jika  jarak  ini  lebih  kecil  dari jarak  sebelumnya  (yang  telah  terhitung  nilainya) hapus data lama, simpan ulang data jarak dengan jarak yang baru.
e) Saat  kita  selesai  mempertimbangkan  setiap  jarak terhadap node tetangga, tandai node yang telah dilalui sebagai  “Node  dilewati”.  Node  yang  dilewati  tidak akan  pernah  di  cek  kembali,  jarak  yang  disimpan adalah  jarak  terakhir  dan  yang  paling  minimal bobotnya.
f) Set “Node belum dilewati” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan ulangi langkah 5 hingga node tujuan tercapai.

## 3) DFD
a) Diagram Konteks
Diagram  konteks  pada  sistem  penentuan jarak  terpendek  yang  dibuat  dapat  dilihat pada gambar 3.3.
Gambar 3.3 Diagram Konteks Sistem Penentuan Jarak Terpendek
Pada  Gambar  3.3,  ditunjukkan  bahwa terdapat 1  entitas di luar sistem,  yaitu user . User dapat memberi masukan kepada sistem berupa  titik  koordinat pick- up  (awal)  dan delivery (destinasi). Sistem dapat menghasilkan keluaran berupa total kilometer  jarak  terpendek  dan  titik-titik terkait yang menunjukkan rutenya.
b) Diagram Level 0 Diagram Level 0 pada sistem penentuan jarak terpendek  yang  dibuat  dapat  dilihat  pada Gambar 3.4.
Gambar 3.4 Diagram Level 0 Sistem Penentuan Jarak Terpendek
Pada  Gambar  3.4,  ditunjukkan  bahwa terdapat  2  entitas  di  luar  sistem,  yaitu user
dan database .  Sebelum  proses  perhitungan jarak  dan  pencarian  titik, user memberi masukan  kepada  sistem  berupa  titik koordinat pick- up  (awal)  dan delivery (destinasi).  Kemudian,  sistem  yang  telah terkoneksi  dengan database ,  mencari  data koordinat  terdekat  menggunakan  algoritma Dijkstra . Hasilnya, database mengembalikan data-data  koordinat  terdekat  disertai  posisi titiknya.  Setelah  mencapai  titik delivery , sistem  menampilkan  visualisasi  jarak terdekat dalam bentuk rangkaian titik kepada user .

## D. Perancangan Basis Data
1) ERD
ERD pada sistem penentuan jarak terpendek ini terdiri dari satu entitas. Admin sebagai pembuat dan perubah data  koordinat,  serta CoordinateData yang  memuat semua  elemen  yang  berkaitan  dengan  perhitungan koordinat.  Adapun  ERD  dapat  dilihat  pada  Gambar 3.5, sebagai berikut :
Gambar 3.5 ERD Sistem Penentuan Jarak Terpendek
2) Kamus Data Kamus  data  berisi  daftar  tabel,  atribut,  tipe,  dan keterangan  dari  atribut  yang  akan  menjadi  indikator perhitungan jarak terpendek pada sistem ini. Adapun kamus  data  pada  sistem  ini  dapat  dilihat  pada  Tabel 3.1, sebagai berikut :
Tabel 3.1 Kamus Data Tabel DataCoordinate
Tabel 3.2 Kamus Data Tabel Admin

## IV. HASIL PENELITIAN
A. Halaman Sistem
1) Halaman Login
Gambar 4.1 Halaman Login
Sesuai  hasil  perancangan,  tertera  area input email
(adminID) dan password untuk  masuk  ke  sistem.
Tersedia  pula  opsi sign up untuk  mendaftarkan  ID
baru.
2) Halaman Home
Gambar 4.2 Halaman Home
Halaman  ini  pun  sesuai  dengan  perancangan  yang menampilkan  adminID  dan  menjadi  halaman  utama setelah proses login berhasil.
3) Halaman Input Titik Awal dan Akhir
Gambar 4.3 Halaman Input Titik Awal dan Akhir
Sesuai  perancangan,  halaman  ini  berperan  bagi user untuk memberi masukan berupa titik awal dan tujuan. Setelah  titik  di input, tombol find ditekan  dan  proses perhitungan jarak terpendek dimulai.

## 4) Halaman Hasil
Gambar 4.4 Halaman Hasil
Pada  halaman  ini  berdasarkan  perancangan, ditampilkan informasi titik koordinat awal, akhir, dan hasil perhitungan jarak terpendeknya. Peta sederhana menampilkan  gambaran  rute  yang  harus  ditempuh. Simbol  berwarna  merah  menunjukkan  titik  awal, sedangkan  simbol  berwarna  biru  menunjukkan  titik tujuan.
B. Implementasi Algoritma Dijkstra
C. Hasil Pengujian
Pengujian hasil penelitian ini dibagi ke dalam dua kondisi,
yaitu :
1. Kondisi  pertama,  jumlah  titik  koordinat  di database sebanyak 2.056 titik.
2. Kondisi  kedua,  jumlah  titik  koordinat  di database sebanyak 5.186 titik.
Hal  ini  dilakukan  untuk  menguji  keterkaitan  antara jumlah data koordinat dengan jarak terpendek yang diperoleh. Pengujian  dilakukan  sebanyak  50  (lima  puluh)  kali  untuk masing-masing  kondisi.  Hasil  pengujian  dengan  kondisi pertama dapat dilihat pada Tabel 4.1.
Tabel 4.1 Hasil Pengujian Kondisi Pertama
function djikstraSolve(graph, s) { var solutions = {}; solutions[s] = []; solutions[s].dist = 0;
while (true) { var parent = null, nearest = null, dist = Infinity;
//for each existing solution for (var n in solutions) { if (!solutions[n]) continue var ndist = solutions[n].dist; var adj = graph[n]; //for each of its adjacent nodes... for (var a in adj) { //without a solution already... if (solutions[a]) continue; //choose nearest node with lowest *total* cost var d = adj[a] + ndist; if (d < dist) { //reference parent parent = solutions[n]; nearest = a; dist = d;
} } }
//no more solutions if (dist === Infinity) { break; }
//extend parent's solution path solutions[nearest] = parent.concat(nearest); //extend parent's cost
solutions[nearest].dist = dist; }
return solutions; }
Hasil pengujian dengan kondisi kedua dapat dilhat pada Tabel 4.2. Tabel 4.2 Hasil Pengujian Kondisi Kedua
Dari  hasil  pengujian  dua  kondisi  di  atas,  tampak  perbedaan signifikan dari data jarak terpendek kondisi pertama dan kedua. Hasil  pada  kondisi  kedua,  di  mana  data  koordinat  yang tersimpan  lebih  banyak,  lebih  kecil  nilainya  dibandingkan kondisi pertama, di mana data koordinat lebih sedikit. Ada pula beberapa hasil perhitungan yang tidak berubah nilainya, seperti pada pengujian nomor 4, 8, 14, 15, dan lainnya. Perbandingan jarak  terpendek  antara  dua  kondisi  di  atas  dapat  dilihat  pada Tabel 4.3.
Tabel 4.3 Perbandingan Jarak Terpendek Antar Kondisi
E-ISSN  : 2581-0588
Hasil perbandingan menunjukkan sebagian besar hasil perhitungan  pada  kondisi  kedua  lebih  kecil  nilainya dibandingkan kondisi pertama. Semakin banyak data yang ada dalam database , semakin baik hasil perhitungan dan jarak yang diperoleh  menjadi  lebih  singkat.  Dengan  begitu,  kami menyimpulkan bahwa jumlah data akan mempengaruhi kualitas hasil perhitungan sistem.

## V. PENUTUP
A. Kesimpulan
Berdasarkan latar belakang serta pembahasan-pembahasan pada bab sebelumnya, dapat disimpulkan bahwa :
 Implementasi  algoritma Dijkstra dalam  sistem  ini sangat  membantu  untuk  menemukan  rute  terpendek yang optimal.
 Banyaknya  data  yang  tersimpan  dalam database sangat mempengaruhi kualitas hasil. Semakin banyak data  koordinat  yang  ada,  hasil  perhitungan  jarak terpendek yang diperoleh sistem semakin baik.
 Sistem menawarkan
kemudahan dalam
memvisualisasikan  peta  bagi  setiap  pengguna sehingga mudah untuk dimanfaatkan.

## B. Saran
Saran  untuk  penelitian  selanjutnya,  dapat  dicoba  untuk melakukan  penghitungan  estimasi  waktu  tempuh  atau  lama perjalanan dengan :
 Mempertimbangkan  beberapa  faktor  lain,  contohnya tingkat  kemacetan  yang  dapat  terjadi  akibat  volume kendaraan,  ataupun  jumlah traffic light sepanjang perjalanan  yang  mungkin  mempengaruhi  waktu tempuh perjalanan.
 Adanya penambahan beberapa variabel, misalnya arah dan  bobot  jalan  berdasarkan  aturan  lalu  lintas  agar fungsi  penentuan  rute  ini  memberikan  manfaat  yang lebih nyata.

## DAFTAR PUSTAKA
[1] A. Sedeño-Noda and A. Raith, “A Dijkstra-like method computing all  extreme  supported  non-dominated  solutions  of  the  biobjective shortest  path  problem”  Comput.  Oper.  Res.,  vol.  57,  2015. DOI : 10.1016/j.cor.2014.11.010. [2] Cattaruzza, Diego, dkk. 2017. Vehicle  Routing Problems for City Logistics. DOI : 10.1007/s13676-014-0074-0
[3] Farah, Nasytha Nur, Andri Suprayogi, dan Moehammad Awaluddin.
2014.  Aplikasi  Pgrouting  Untuk  Penentuan  Jalur  Optimum  Pada Pembuatan  Rute  Pemadam  Kebakaran  (Studi  Kasus  :  Kota Semarang). Jurnal Geodesi Undip Volume 3, Nomor 1, Tahun 2014, hal. 182-197. ISSN : 2337-845X.
[4] Junanda,  Berry,  Denny  Kurniadi,  dan  Yasdinul  Huda.  2016. Pencarian Rute Terpendek Menggunakan Algoritma Dijkstra Pada Sistem  Informasi  Geografis  Pemetaan  Stasiun  Pengisian  Bahan Bakar Umum. Jurnal Vokasional Teknik Elektronika & Informatika Vol. 4, No. 1, Maret 2015, hal. 89-93. ISSN : 2302-3295.
[5] Miro,  Fidel.  (2012).  Pengantar  Sistem  Transportasi.  Erlangga, Jakarta. ISBN : 9789790993112.
[6] Munir,  Rinaldi  dan  Leony  Lidya.  2016.  Algoritma  dan Pemrograman  Dalam  Bahasa  Pascal,  C,  dan  C++  Edisi  Keenam. Jakarta : Informatika.  ISBN : 602-1514-91-7
[7]
Ojekudo,  Nathaniel  Akpofure  dan  Nsikan  Paul  Akpan.  2017.  An Application  of  Dijkstra’s  Algorithm  To  Shortest  Route  Problem. IOSR Journal of Mathematics (IOSR-JM) Volume 13, Issue 3 Ver. 1, hal. 20-32.  DOI : 10.9770/5728-1303012032
[8] Pandey,  Pramod  dan  Sunanda  Dixit.  2014.  Railway  Route Optimization System Using Dijkstra Method. International Journal on Recent and Innovation Trends in Computing and Communication (IJRITCC) Volume : 2 Issue : 3, hal. 435-440. ISSN : 2321-8169.
[9] Primadasa,  Yogi.  2015.  Pencarian  Rute  Terpendek  Menggunakan Algoritma  Dijkstra  Pada  SIG  Berbasis  Web  Untuk  Distribusi Minuman  (Studi  Kasus  PT.  Coca  Cola  Kota  Padang).  Jurnal KomTekInfo Fakultas Ilmu Komputer, Volume 2, No. 2, Des 2015, hal. 47-54.  ISSN : 2356-0010.
[10] R.,  Windi  Eka  Yulia,  Dwiretno  Istiadi,  dan  Abdul  Roqib.  2015. Pencarian SPBU Terdekat Menggunakan Algoritma Dijkstra (Studi Kasus di Kabupaten Jember). Jurnal Nasional Teknik Elektro Vol : 4, Jember.  ISNN : 2302-2949.
[11] Risald, Suyoto, dan Antonio E. Mirino. 2017. Best Routes Selection Using  Dijkstra  and  Floyd-Warshall  Algorithm.  DOI  : 10.1109/ICTS.2017.8265662.
[12] Setiawan,  Kiki,  dkk.  2018.  Menghitung  Rute  Terpendek Menggunakan  Algoritma  A*  Dengan  Fungsi  Euclidean  Distance. Seminar  Nasional  Teknologi  Informasi  dan  Komunikasi  2018 (SENTIKA 2018), Yogyakarta. ISSN : 2089-9815.
[13] Setiyadi, Isnaeni, Teguh Bharata Adji dan Noor Akhmad Setiawan. 2015.  Optimalisasi  Algoritma  Dijkstra  Dalam  Menghadapi Perbedaan  Bobot  Jalur  Pada  Waktu  Yang  Berbeda.  Seminar Teknologi  Informasi  dan  Multimedia,  STMIK  AMIKOM Yogyakarta, hal. 31-36.  ISSN : 2302-3805
[14] Siang, Jong Jek. 2014. Riset Operasi dalam Pendekatan Algoritmis Edisi 2. Jakarta : Andi Publisher.  ISBN : 9789792943542.
[15] Wu,  Yu,  dkk.  2017.  Path  Planning  for  Carrier  Aircraft  Based  On Geometry and Dijkstra’s Algorithm. DOI : 10.1109/CCSSE.2017.8087906