## Science  And  Technology

## ANALISA OPTIMASI RUTE TRANSPORTASI ANTAR JEMPUT SISWA MENGGUNAKAN METODE CGVRP DAN ALGORITMA DIJKSTRA DI SDIT SAMAWA CENDEKIA
Koko Hermanto 1 , Tita Dwi Ermayanti 2 , Eki Ruskartina 3
1* Program Studi Teknik Industri, Fakultas Rekayasa Sistem Universitas Teknologi Sumbawa
2,3 Program Studi Teknik Industri, Fakultas Rekayasa Sistem Universitas Teknologi Sumbawa *Corresponding Author email : * 1 koko.hermanto@uts.ac.id, 2 titadwie2397@gmail.com ,  3 eki.ruskartina@uts.ac.id
Abstrak Bus  sekolah  merupakan  salah satu  Alat  transportasi  yg  dipersiapkan  oleh  beberapa Diterima  :
Bulan September 2021 Diterbitkan : Bulan Oktober
2021

## Keyword:
Model CGVRP,
Algoritma Dijkstra, bus sekolah, SDIT Samawa Cendekia
sekolah  sebagai  sarana  antar  jemput  untuk  mempermudah  siswa-siswi  mereka  dalam dalam  kegiatan  bersekolah,  sehingga  dalam  proses  antar  jemput  diperlukan  rute  yang optimal agar dapat menghemat bahan bakar. Tujuan dari penelitian ini untuk menyusun model rute transportasi antar jemput peserta didik dengan model Clustered Generalized Vehicle  Routing  Problem  (CGVRP) selanjutnya  model  tersebut  diselesaikan menggunakan Algoritma Dijkstra serta membandingkan jarak rute real transportasi antar jemput  dengan jarak rute menggunakan model CGVRP dan Algoritma Dijkstra . Model CGVRP menggunakan Algoritma Djikstra  yang diterapkan pada studi kasus antar jemput peserta  didik  di SDIT  Samawa  Cendekia  lebih  hemat  dibandingkan  dengan  jarak  yang digunakan  sebelumnya.  Diketahui  jarak  real  pada  SDIT  Samawa  Cendekia  yaitu 2.627.424 meter dengan biaya Rp. 2.118.384 dalam sebulan. Sedangkan jarak pada rute usulan  didapatkan  2.389.128  meter  dengan  biaya  Rp.  1.926.757  dalam  sebulan.  Maka diperoleh selisih jarak dari rute real dan rute usulan yaitu 238.296 meter dengan selisih biaya Rp. 191.604 dalam sebulan .

## PENDAHULUAN
Bus  sekolah  merupakan  salah  satu  Alat transportasi  yg dipersiapkan oleh beberapa sekolah sebagai  sarana  antar  jemput  untuk  mempermudah siswa-siswi  mereka  dalam  proses  mengajar  (untuk mempermudah siswa-siswi dalam kegiatan bersekolah/belajar). Sehingga dalam hal ini sekolah ingin  mengefisienkan  waktu  serta  biaya  yang  akan di  keluarkan  agar  nantinya  bus  sekolah  ini  dapat beroperasi secara optimal. Pengemudi bus merupakan salah satu alasan utama agar rancangan ini dapat terwujud, mengingat biasanya pengemudi bus hanya mengantar siswa-siswi dengan rute yang menurutnya  lebih  cepat  tanpa  perhitungan  atau hanya  menggunakan  insting  pribadinya.  Untuk  itu, harus dilakukan perhitungan yg tepat dalam memilih jalur agar mengatahui apakah jalur yang biasanya di tempuh  oleh  pengemudi  bus  sudah  efektif  atau belum, sehingga dapat mempurmudah dan meminimalisir waktu tempuh serta biaya yang akan dikeluarkan
Sering  dijumpai  dalam  kehidupan  sehari- hari,  salah  satunya  dibidang  transportasi  mengenai masalah  rute  terpendek.  Masalah  ini  menjadi masalah  yang  penting  karena  berkaitan  dengan biaya  yang  akan  dikeluarkan  serta  waktu  yang dibutuhkan dalam setiap prosesnya.
Metode CGVRP dan  algoritma  Dijkstra merupakan  metode  yang  akan  digunakan  dalam menentukan  rute  terpendek  pada  penelitian  ini. Metode CGVRP merupakan  pengembangan  dari metode VRP dan GVRP dimana vertek - vertek dari VRP dipartisi  menjadi  sejumlah  rangkaian vertek - vertek yang  disebut Cluster kemudian  ditentukan rute  yang  optimal  dari  depot  ke  sejumlah Cluster yang telah ditetapkan yang meliputi tepat satu vertek dari  setiap Cluster dan  kendaraan  yang  digunakan untuk pendistribusian lebih dari satu kendaraan yang identik  dan  kapasitasnya  terbatas.  Metode  ini biasanya digunakan untuk meminimalisasikan biaya dan kendaraan dalam proses pendistribusian.
Algoritma  Dijkstra  merupakan  sebuah algoritma  digunakan  untuk  memecahkan  masalah pencarian rute terpendek dengan menghitung bobot terkecil dari setiap vertek . Setiap bobot dari vertek yang  belum  dipilih  akan  dianalisis,  lalu  dipilih vertek dengan bobot yang paling kecil. Apabila ada bobot yang lebih kecil melalui vertek tertentu, maka rute akan berubah mengikuti bobot yang lebih kecil tersebut,  artinya  rute  lintasan  akan  berubah. Algoritma  Dijkstra  akan  berhenti  ketika  semua vertek sudah terlewati.
Sehingga  dari  latar  belakang  tersebut metode ini membantu SDIT mengoptimal pelayanan transportasi  antar  jemput  dengan  perhitungan  yang hampir pasti  karena di SDIT sendiri untuk penetuan

## Science  And  Technology
rutenya  masih  menggunakan  perkiraan.  Dengan pengoptimalan rute tersebut sekolah dapat meminimalkan biaya serta waktu kerja lebih efektif.

## LANDASAN TEORI

## a) Teori Graph
Definisi graph dapat dijelaskan sebagai berikut: Definisi 1. Graph 𝐺 didefinisikan sebagai pasangan himpunan ( 𝑉 , 𝐸 ) ditulis dengan notasi 𝐺 =( 𝑉 , 𝐸 ), yang dalam hal ini 𝑉 adalah himpunan tidak-kosong dari vertek dan 𝐸 adalah  himpunan  sisi  edge  yang menghubungkan sepasang vertek . Definisi  2. Graph berbobot merupakan graph yang masing-masing  edge  memiliki  bobot  real  positif.
Jumlah  bobot  dari  semua  edge  adalah  bobot  total graph.  Jika  G  adalah  graph  berbobot  dan  e  adalah edge G, maka w (e) menunjukkan bobot e dan w (G) menunjukkan total bobot G.
Definisi  3 Graph  Berarah  merupakan  graph yang  edge-edgenya  diberikan  orientasi  arah dan panah. Sehingga (vj,vk) ≠ (vk,vj). Definisi  4 Graph  Isomorfik  merupakan  Dua  buah Graph  yang  sama  tetapi  secara  geometri  berbeda disebut  Graph  yang  saling  isomorfik.  Dua  buah Graph, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi  satu-satu  antara  simpul-simpul keduanya  dan  antara  sisi-sisi  keduaya  sedemikian sehingga hubungan kebersisian tetap terjaga .

## b) CGVRP
Tujuan CGVRP adalah  untuk  menentukan  koleksi biaya minimum dari m tur kendaraan yang berawal dan berakhir di depot sehingga vertek dari tiap graph dikunjungi  tepat  satu  kali  dengan  melakukan  jalur Halmiton  pada  tiap vertek ,  serta  muatan  masing- masing kendaraan tidak melebihi kapasitas Q .
Dengan mengikuti perluasan yang sama pada GTSP ( General traveling salesman problem ), maka varian dari GVRP didefinisikan  sebagai  masalah  umum Cluster rute  kendaraan  atau clustered  generalized vehicle  routing  problem yang  dinotasikan  sebagai CGVRP , dimana semua vertek setiap Cluster harus dikunjungi  secara  berurutan  dalam  rute  kendaraan. Ilustrasi CGVRP dan solusi  layak yang  merupakan lanjutan dari masalah GVRP , yang dapat dilihat pada Gambar 1.
q 1=12

## c) Algoritma dijkstra
Algoritma Dijkstra adalah algoritma pencarian graph  yang  memecahkan  masalah  jalur  terpendek yang bersumber dari satu vertek untuk sebuah grafik dengan bobot vertek tidak boleh negatif.
Algoritma  Dijkstra  diterapkan  untuk  mencari lintasan terpendek pada graph berarah. Algoritma ini menggunakan  prinsip  greedy.  Prinsip  greedy  pada algoritma  dijkstra  menyatakan  bahwa  pada  setiap langkah  kita  memilih  sisi  yang  berbobot  minimum dan memasukannya dalam himpunan solusi[Andayani].
Prinsip  algoritma  Dijkstra  dalam  menentukan rute  terpendek  dari  suatu  masalah  jaringan  yang dimodelkan  dalam  graph  adalah  pada  waktu penentuan  rute  alternatif  yang  kemungkinan menjadi solusi, setiap bobot dari vertek yang belum dipilih  akan  dianalisis,  lalu  dipilih  vertek  dengan bobot  yang  paling  kecil.  Apabila  ada  bobot  yang lebih  kecil  melalui  vertek  tertentu,  maka  rute  akan berubah mengikuti bobot  yang lebih kecil tersebut, artinya  rute  lintasan  akan  berubah.  Algoritma Dijkstra  akan  berhenti  ketika  semua  vertek  sudah terlewati

## METODE PENELITIAN
Analisis  terhadap  hasil  pengolahan  data  untuk mengoptimasikan  rute  tranportasi  antar  jemput siswa  dengan  metode Clustered  Generalized Vehicle Routing  Problem (CGVRP) , maka perlu di lakukan sebagai berikut :
2. Membuat  Model CGVRP dari  rute  real  yang digunakan pengemudi.
3. Membuat  model CGVRP dan  Algoritma Dijkstra  untuk  rute  usulan  dengan  melakukan hal sebagai berikut:
a) Menentukan  jarak  antar  sekolah  ke terminal dan antar terminal
b) Mendefinisikan  kelompok  setiap  terminal yaitu pengelompokan berdasarkan kelurahan  dengan  tetap  memperhatikan kapasitas  dari  mobil  penjemputan  untuk menyusun model CGVRP .
c) Menggunakan  algoritma  Dijkstra  mencari jarak  terpendek  antara  tiap-tiap  terminal yang telah disusun model CGVRP .
d) Pembentukan  rute  berdasarkan  urutan terminal.
e) Membandingkan rute yang didapat dengan rute  yang  selama  ini  dilakukan  oleh Pengemudi.

## HASIL DAN PEMBAHASAN
Antar  jemput  peserta  didik  oleh  SDIT Samawa  Cendikia  dari  rumah  ke  sekolah  dan sebaliknya menggunakan 4 kendaraan dengan total jarak tempuh mobil yaitu 54.738 meter, dengan total
K = 2  dan  Q = 25 2 d 2 = 5 3 d 3 = 4 q  =9 2 1 4 d 1 = 3 d   = 5 4 V 1 5 d 5 = 4 V 0 V 2 0 V 5 q 3 =5 q 0=0 11 q 4 =11 d 11 = 7 q 5 = 7 6 d 6 = 5 V 3 10 d 10 = 3 7 d 7 = 2 9 d 9 = 4 8 d 8 = 2

## Science  And  Technology
biaya  Rp.44.133-,.  Sehingga  total  jarak  dalam sebulan  yaitu  2.627.424  meter  dengan  total  biaya yang dikeluarkan yaitu Rp. 2.118.384,-. Kendaraan tersebut  memiliki  kapasitas  masing-masing  15 orang.
Berdasarkan Tabel 2 dapat diilustrasikan lokasi dan  pengelompokan  terminal  seperti  Gambar berikut:
Pada  penelitian  ini  untuk  mengukur  jarak setiap  terminal  terdapat  beberapa  ansumsi  yaitu kendaraan  yang  digunakan  selalu  dalam  kondisi baik,  kemacetan  di  rute  antar  jemput  diabaikan sehingga ruas tiap jalan selalu dapat dilewati, jarak dari terminal ke- i ke terminal ke- j sama dengan jarak terminal ke- j ke terminal ke- i . Jarak setiap terminal ditentukan menggunakan google earth dengan tetap memperhatikan  jarak  yang  sebenarnya  di  lapangan yang  diperoleh  secara  manual  menggunakan speedometer sepeda  motor.  Jarak  antar  terminal dapat dilihat sebagai berikut:
Selanjutnya          setiap terminal dikelompokan  berdasarkan  kelurahan  masing- masing dengan tetap memperhatikan kapasitas kendaraan  yaitu  total  siswa  yangg  dijemput tidak  melebihi  kapasitas  kendaraan  bila melebihi  kapasitas  kendaraan  maka  dibentuk kelompok baru. jumlah siswa dan pengelompokan  setiap  terminal  disajikan  pada
Tabel
V7
Ditetapkan Siswa di Terminal di kelompok V 1 dan V 4 dijemput  oleh  mobil  pertama,  siswa  di Terminal  di  kelompok V 5 V 3 dan V 8 dijemput  oleh mobil kedua, siswa di kelompok V 9 dan V 6 dijemput oleh mobil ketiga dan siswa di kelompok V 2 , V 7 dan V 10 dijemput oleh mobil keempat. Selanjutnya untuk setiap  kendaraan  ditentukan vertek terpendek  dari masing-masing Cluster ang  dilalui  sebagai vertek awal  yang  dikunjungi.  Maka  untuk  kendaraan  1 ditentukan vertek terpendeknya dari Cluster V 1 dan V 4 ,  pada  kendaraan  2  ditentukan vertek terpendeknya  dari V 5 V 3 dan  V 8., kendaraan  3  akan ditentukan vertek terpendeknya dari V 9 dan  V 6 dan kendarran  4  akan  ditentukan vertek terpendeknya dari V 2 , V 7 dan V 10 . Dari vertek awal  tersebut  akan dikunjungi  seriap  vertek  yang  ada  pada Cluster tersebut. Setelah semua vertek dari Cluster tersebut telah  dikunjungi  maka  dilanjukan  ke Cluster berikutnya.  Dan  setelah  semua Cluster dikunjungi maka  kendaraan  kembali  ke  sekolah.  Untuk menghitung  vertek  mana  yang  akan  dikunjungi terlebih dahulu  maka kita menggunakan Algoritma Dijkstra sehingga didapatkan hasil seperti berikut
V7
Dari Gambar 3 dan Tabel 1 dapat dilihat solusi usulan  rute  antar  jemput  peserta  didik  di  SDIT Samawa  Cendekia.  Diperoleh  total  rute  sepanjang 49.787  meter.  Bahan  bakar  yang  digunakan  oleh mobil  pengantaraan  adalah  bensin  dengan  harga perliternyaRp.6.450 dan satu liter dapat menempuh jarak 8.000 meter, sehingga biaya bahan bakar untuk pengantaran  siswa  adalah  Rp.  40.141,-.  Dimana dalam  sehari  terdapat  2  kali  perjalanan  sehingga sehari  menempuh  jarak 2 𝜒 49.787 𝑚𝑒𝑡𝑒𝑟 =
K= 4 Q=15 16 V9 15 18 V1 21 17 V6 22 14 20 1 6 26 13 7 9 8 12 0 V4 2 10 5 25 4 V3 3 11 V5 V2 24 V10 V8 K = 4Q=15 16 q9 =7 q6 =8 15 V9 18 V1 22 17 V6 21 14 20 1 6 26 q1  =12 13 7 9 q4 =3 8 12 0 q7 =10 V4 2 10 25 q3 =2 V3 23 q 2 =3 4 3 q8=5 5 11 24 V5 V2 V8 q5 =8 q10 =2 V10

## Science  And  Technology
99.574 𝑚𝑒𝑡𝑒𝑟 maka biaya yang dikeluarkan dalam sehari  yaitu 2 𝜒 𝑅𝑝 .  40.141  = 𝑅𝑝 .  80.282 ,-. Dimana  Sekolah  aktif  selama  24  hari  dalam  satu bulan  maka  total  jarak  yang  ditempuh  yaitu  jarak 24 𝜒 99.574 𝑚𝑒𝑡𝑒𝑟 =  2.389.128 𝑚𝑒𝑡𝑒𝑟 dan biaya yang dikeluarkan  sebesar 24 𝜒 𝑅𝑝 . 80.282 = 𝑅𝑝 . 1.926.757 ,-.

## PENUTUP

## Kesimpulan
Proses antar jemput yang dilakukan dengan metode CGVRP dan Algoritma Dijkstra menghasilkan  rute  yang  mampu  mengoptimalkan jarak  dari  sekolah  ke  terminal-terminal  yang  telah ditentukan. Metode CGVRP menggunakan Algoritma  Dijkstra  yang  diterapkan  pada  studi kasus  antar  jemput  peserta  didik  di  SDIT  Samawa Cendekia  lebih  hemat  dibandingkan  dengan  jarak yang  digunakan  sebelumnya.  Total jarak  pada  rute SDIT  Samawa  Cendekia  yaitu  2.627.424meter dengan  biaya  Rp.  2.118.384  dalam  sebulan. Sedangkan   jarak   pada   rute   usulan   didapatkan 2.389.128 meter dengan biaya Rp. 1.926.757dalam sebulan. Sehingga didapatkan selisih jarak dari rute
real  dan  rute  usulan  yaitu  238.296  meter  dengan selisih biaya Rp. 191.604 dalam sebulan.

## REFERENSI
Andayani,  Sri.2014.  Penentuan  Rute  Terpendek Pengambilan  Sampah  di  Kota  Merauke Menggunakan  Algoritma  Dijkstra .  Jurnal
Semantik :164-170. Hermanto, Koko.2015. Model Matematika Generalized  Vehicle  Routing  Problem  Dan Ekstensinya  Studi  Kasus:  Pendistribusian Kertas  Karton.  Tesis.  Universitas  Gajdah Mada.
Hermanto, Koko dan Eki Ruskartina.2017. “Optimasi Rute Truk Pengangkutan Sampah
Di Kota Sumbawa Besar Shift II MenggunakanGVRP ”. Jurnal UJMC .4(2):15-23 Jek  Siang,  Jong.2014. Riset  Operasi  Pada PendekatanAlgoritmis”.
Yogyakarta.Penerbit Andi.