## OPTIMASI RUTE TRUK PENGANGKUTAN SAMPAH DI KOTA
SUMBAWA BESAR SHIFT II MENGGUNAKAN GVRP
Koko Hermanto 1 , Eki Ruskartina 2
1 Jurusan Teknik Industri, Universitas Teknologi Sumbawa,  kokoaction88@gmail.com
2 Jurusan Teknik Industri, Universitas Teknologi Sumbawa, ekiruskartina@gmail.com
Abstract. The  problem  of  garbage  in  the  city  of  Sumbawa  Besar  is  a  common  problem  that  often occurs, as well as large cities in Indonesia. To avoid the negative impact of the existence of waste, the waste  problem  needs  to  be  handled  properly  by  improving  quality  and  waste  management,  for example in terms of distribution. Set warehouse, TPS and TPA as vertices, and the connecting paths of these  vertices  are  edgy.  Arrange  the  shortest  route  for  each  fleet  in  the  second  shift  using  the generalized vehicle  routing  problem (GVRP) method.  Then,  using  the  clustered  generalized  vehicle routing problem (CGVRP) method and resolved with the Dijkstra algorithm. Obtained the total route on the second shift 85,569 meters, so that spent fuel RP 69,524, - more optimal than the route that has been used that is along 96,302 meters obtained RP. 78,245, -.
Keywords: garbage, shortest route , GVRV, CGVRP, Djikstra
Abstrak. Persoalan  sampah  di  kota  Sumbawa  Besar  merupakan  masalah  umum  yang  sering  terjadi, Sama  halnya  dengan  kota-kota  besar  yang  ada  di  Indonesia.  Untuk  menghindari  adanya  dampak negatif  dari  keberadaan  sampah  maka  persoalan  sampah  perlu  ditangani  dengan  baik  dengan  cara peningkatan  kualitas  dan  pengelolaan  sampah,  misalnya  dari  segi  pendistribusianya.  Ditetapkan gudang,  TPS  dan  TPA  sebagai  verteks,  serta  jalan  penghubung  vertek-verteks  tersebut  adalah  edge. Menyusun  rute  terpendek  untuk  setiap  armada  pada shift kedua  menggunakan  metode generalized vehicle  routing  problem (GVRP) ,  selanjutnya  menggunakn  metode clustered  generalized  vehicle routing  problem  (CGVRP) dan  diselesaikan  dengan  algoritma  Djikstra.  Diperoleh  total  rute  lima armada pada shift kedua adalah 85.569 meter sehingga menghabiskan bahan bakar Rp 69.524,- lebih optimal dibandingkan rute yang selama ini digunakan yaitu 96.302 meter diperoleh biaya bahan bakar Rp. 78.245,-.
Keywords: Sampah, rute terpendek, GVRV, CGVRP, Algoritma Djikstra

## 1 Pendahuluan
Kota Sumbawa Besar merupakan ibu kota dari kabupaten Sumbawa  yang berada di provinsi Nusa Tenggara Barat. Sesuai dengan slogan dari kota ini yaitu “BESAR” adalah suatu singkatan dari  kata-kata  Bersih,  Elok,  Sehat,  Aman  dan  Rapi.  Untuk  mewujudkan  capaian  dari  slogan tersebut  maka keterlibatan  anatara  kalangan masyarakat dan pemerintah  sangat  diperlukan. Hal kecilnya,  masyarakat  memiliki  kesadaran  untuk  menjaga  kebersihan  lingkungan  sekitar, membuang  sampah  pada  tempatnya.  Sedangkan  untuk  sarana  dan  prasarana  dapat  disediakan oleh  pemerintah  guna  untuk  mengumpulkan  dan  mengangkut  sampah-sampah  dari  masyarakat atau  dari  tempat  pembuangan  sementara  (TPS)  untuk  didistribusikan  ke  Tempat  Pembuangan Akhir (TPA).
Pendistribusian  sampah  adalah  salah  satu  bagian  kegiatan  penting  dilakukan  oleh  instansi pemerintah  dalam  pendistribusian  barang  atau  jasa.  Penentuan  rute  perjalan  dari  kantor  Dinas

## Unisda Journal of Mathematics and Computer Science
Lingkungan  Hidup  kabupaten  Sumbawa  atau  gudang dump  truk pendistribusian  sampah  dari tiap-tiap  TPS  ke  TPA  sangat  rumit  sehinga  harus  harus diperhatikan sehingga  proses pengangkutan  dapat  dilakukan  dengan  secara  tepat  sesuai  dengan  banyaknya  unit  kendaraan pengangkut sampah yang nantinya dapat menghempat biaya bahan bakar.
Persoalan  rute  terpendek  adalah  suatu  jaringan  yang  menentukan  rute  perjalanan  di  mana seseorang dalam menentukan rute perjalanan ingin menentukan rute terpendek antara dua objek atau lebih berdasarkan rute alternatif yang tersedia yang biasanya terdiri dari satu atau beberapa objek  tujuan.  Masalah  ini  umumnya dapat  diilustrasikan  atau  dimodelkan  dalam  bentuk graph guna  memodelkan  persoalan  yang  diamati  sehingga  dapat  mempermudah  dalam  penyelesaian masalah tersebut. Masalahnya adalah menentukan cara mengunjungi setiap objek pada graph dari objek  awal  ke  objek  akhir  dengan  bobot  yang  minimum,  dalam  penelitian  ini  bobot  yang dimaksud  adalah  jarak  dari  masing-masing  objek  dan  objeknya  didefinisikan  sebagai  TPS sampah  diasumsikan  sebagai  vertek  yang  saling  terhubung.  Metode  yang  digunakan  untuk menentukan  rute  terpendek  pada  penelitian  ini  adalah  menggunakan  metode GVRP dan algoritma  Djikstra,  di  mana  dengan  menggunakan  metode GVRP setiap  TPS  dikelompokkan berdasarkan  kelurahan  dengan  tetap  memperhatikan  kapasitas dump  truk selanjutnya  denga menggunakan  Algoritma  Djikstra  ditentukan  rute  terpendek  setiap  TPS  didalam  kelompok tersebut. Tujuan dari penelitian adalah dapat menjadi bahan pertibangan bagi Dinas Lingkkungan Hidup  di  Kabupaten  Sumbawa  atau  instansi  terkait  dalam  hal  menentukan  rute  terpendek pendistribusian barang atau jasa.

## 2 Tinjauan Pustaka

## 2.1 Teori Graph
Susanna [10] melaskan definisi graph dan graph berarah sebagai berikkut: Definisi 1. Graph G merupakan pasangan (V,A) di mana V himpunan berhingga dengan yang anggotanya disebut titik (vertek) dan himpunan berhingga A yang anggotanya disebut sisi (edge).  Secara  matematis  ditulis  G  =  (V,A),  di  mana  V merupakan  himpunan  vertek  dan  A adalah himpunan edge.
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.

## 2.2 Generalized Vehicle Routing Problem (GVRP)
Definisi  3. [7] GVRP adalah  masalah  mencari  rute  terpendek  yang  direpresentasikan  dengan sebuah  graph  berarah  G  =  (V,A)  dengan  V= *            + sebagai  himpunan  vertex  dan A= *(    )|               + himpunan  edge.  Nilai bernilai  tidak  negatif  untuk  setiap  edge (    ) ,  himpunan  vertek  dibagi  menjadi  k+1  himpunan  bagian  tak  kosong  saling  esklusif, yang disebut dengan kelompok
( dan untuk
semua *           + dan ) .

## Unisda Journal of Mathematics and Computer Science
Setiap rute kendaraan mengunjungi tepat satu vertek dari sejumlah kelompok dan memenuhi kendala kapasitas . Contoh skema ilustrasi GVRP dan koleksi rute  yang  layak ditunjukkan pada Gambar 1 berikut.
Gambar 1. Contoh Solusi Layak GVRP
Gambar 1  mejelaskan solusi layak GVRP dari suatu masalah pendistribusian barang yang dilakukan  oleh  dua  kendaraan  distribusi  yang  identik  dengan  kapasitas  kendaraan . Kendaraan  pertama  pendistribusian  dimulai  dari  gudang menuju  vertek dengan permintannya dan vertek mewakili kelompok dengan jumlah permintaan kemudian  kendaraan  pertama  menuju  vertek dengan  permintaannya dan  vertek mewakili  kelompok dengan  jumlah  permintaan selanjutnya  kendaraan  pertama tersebut kembali lagi ke gudang.
Sedangkan  kendaraan  kedua  pendistribusian  dimulai  dari  gudang menuju  vertek dengan permintannya dan vertek mewakili kelompok dengan jumlah permintaan kemudian kendaraan kedua menuju vertek dengan permintaannya
dan vertek mewakili  kelompok dengan  jumlah  permintaan ,  kemudian  menuju  vertek dengan permintaannya dan vertek mewakili kelompok dengan jumlah permintaan selanjutnya kendaraan  tersebut kembali ke gudang.
2.3 Clustered Generalized Vehicle Routing Problem (CGVRP)
Tujuan CGVRP adalah untuk menentukan koleksi biaya minimum dari m tur kendaraan yang berawal dan berakhir di gudang sehingga vertek dari tiap graph dikunjungi tepat satu kali dengan

## Unisda Journal of Mathematics and Computer Science
melakukan  jalur  Halmiton  pada  tiap  vertek,  serta  muatan  masing-masing  kendaraan  tidak melebihi  kapasitas Q [2].  Ilustrasi CGVRP dan  solusi  layak  yang  merupakan  lanjutan  dari masalah GVRP pada Gambar 1 sebelumnya disajikan dalam Gambar 2.

## Gambar 2 Contoh Solusi Layak CGVRP
Gambar  2  mejelaskan  solusi  layak CGVRP dari  suatu  masalah  pendistribusian  barang  yang dilakukan  oleh  dua  kendaraan  distribusi  yang  identik  dengan  kapasitas  kendaraan . Kendaraan  pertama  pendistribusian  dimulai  dari  gudang menuju  vertek dengan
permintannya
kemudian  menuju  vertek dengan  permintaan selanjutnya menuju vertek dengan permintaan merupakan vertek-vertek yang ada di kelompok dengan  jumlah  permintaan
.  Kemudian  kendaraan  pertama  menuju  vertek dengan permintaannya
kemudian  menuju  vertek dengan  permintaan merupakan vertek-vertek  yang  berada  di  kelompok dengan  jumlah  permintaan selanjutnya kendaraan  pertama  tersebut  kembali  lagi  ke  gudang.  Begitu  juga  dengan  pendistribusian kendaraan  kedua.  Jadi  rute  optimal  dari  pendistribusian  tersebut  adalah  jumlahan  seluruh  jarak edge-edge yang dilalui dua kendaraan pendistribusian tersebut.

## 2.4 Algoritma  Dijkstra
Algoritma Dijkstra merupakan  sebuah algoritma digunakan untuk menentukan rute terpendek pada  graph  berarah  atau  graph  tak  berarah  yang  memiliki  bobot  tanpa  mengenumerasi  secara eksplinsit semua rute alternatif yang mungkin menjadi solusi rute optimal [6].

## Unisda Journal of Mathematics and Computer Science Jurusan Matematika, UNISDA, Lamongan
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 [2].

## 3 Metodologi Penelitian
Metode yang digunakan untuk menyusun penelitian ini adalah sebagai berikut:
1) Lokasi Penelitian
Penelitian dilakukan pada area pelayanan pengambilan sampah yang dilakukan oleh Dinas Lingkungan Hidup kabupaten Sumbawa.
2) Sampel Data Jumlah  armada,  kapasitas dump  truk ,  volume  sampah  di  TPS,  lokasi  TPS,  lokasi  TPA, jarak dari TPA ke setiap TPS  dan jarak TPS kesetiap TPS.
3) Prosedur Penelitian
a. Pengkajian  metode GVRP , CGVRP ,  dan  algoritma  Djikstra  untuk  menentukan  rute terpendek pengambilan sampah
b. Pengumpulan data yang dibutuhkan pada poin 2.
c. Pemodelan metode GVRP , CGVRP , dan algoritma Djikstra
 Menentukan jarak antar  TPA ke TPS, gudang ke TPS, gudang ke TPA dan  antar TPS
 Mendefinisikan kelompok setiap TPS yaitu pengelompokan berdasarkan kelurahan dengan  tetap  memperhatikan  kapasitas dump  truk untuk  menyusun  model GVRP dan CGVRP .
 Menggunakan  algoritma  Djikstra  mencari  jarak  terpendek  antara  tiap-tiap  TPS yang telah disusn model GVP dan CGVRP .
 Pembentukan rute berdasarkan urutan TPS
 Membandingkan  rute  yang  didapat  dengan  rute  yang  selama  ini  dilakuan  oleh Dinas Lingkungan Hidup.

## 4 Hasil dan Pembahasan
Pendistribusian sampah oleh Dinas Lingkungan Hidup di setiap TPS di kota Sumbawa Besar menggunakan  dua shift yaitu shift pertama  dilakukan  pada  pukul  07.00-08.30  dan shift kedua pada pukul 09.00-10.30 dengan total jarak tempuh pada shift kedua yaitu 96.302 meter diperoleh biaya bahan bakar Rp.  78.245. Berikut akan dijelaskan shift kedua. Kendaraan  yang digunakan adalah dump truck dengan kapasitas 2 , sebanyak 5 dump truk .
Pada  penelitian  ini  untuk  mengukur  jarak  setiap  TPS terdapat  beberapa  ansumsi  yaitu dump truk yang  digunakan  untuk  mengangkut  sampah  selalu  dalam  kondisi  baik,  kemacetan  di  rute distribusi sampah diabaikan sehingga ruas tiap jalan selalu dapat dilewati, jarak dari TPS ke- i ke TPS ke- j sama dengan jarak TPS ke- j ke ke- i serta volume sampah ditiap TPS selalu tetap. Jarak

## Unisda Journal of Mathematics and Computer Science
setiap  TPS  ditentukan  menggunakan google  earth dengan  tetap  memperhatikan  jarak  yang sebenarnya  di  lapangan    yang  diperoleh    secara  manual  menggunakan speedometer sepeda motor. Jarak setiap TPS pada shift kedua disajikan pada Tabel 1 berikut.

## Tabel 1. Jarak setiap TPS
Selanjutnya  setiap  TPS  dikelompokan  berdasarkan  kelurahan  masing-masing  dengan  tetap memperhatikan  kapasitas dump  truk yaitu  total  volume  sampah  pengelompokan  TPS  tidak melebihi kapasitas dump truk bila melebihi kapasitas dump truk maka dibentuk kelompok baru. Volume sampah dan pengelompokan setiap TPS disajikan pada Tabel 2 berikut.
Tabel. 2. volume sampah dan pengelompokan setiap TPS
No. Kelurahan Persediaan Sampah TPS Persediaan Sampah 1. Pungka ( ) 0,4  parate (6) 0,2  pungka (7) 0,2 2. Pekat ( ) 0,4  Jalan kh. Dewantara (19) 0,2  gurami (21) 0,2 3. Bugis 1 ( ) 1,98  jalan diponegoro (13) 0,66  jalan setia budi (14) 0,66  jalan kamboja (10) 0,66 4. Bugis ( ) 1,98  jalan akeang (15) 0,66  jalan mawar (11) 0,66  jalan melati (12) 0,66 5. Lempeh ( ) 0,49  Jalan garuda (1) 0,49 6. Seketeng ( ) 0,86  jalan kepiting (5) 0.3  stadion pragas (8) 0.3 7. Uma Sima ( ) 0,95  jalan mangga (23) 0,12
0' 1 3 2 4 8 5 7 6 9 10 11 12 14 13 15 16 17 18 19 20 21 22 24 23 25 v 10 v 2 v 4 v 5 v 7 v 8 v 11 v 12 v’ 4 K=5 dan Q=2 q1=0,4 q2=0,4 q4=1,98 q4'=1,98 q5=0,49 q8=0,95 q12=0,92 q7=0,86 q11=0,87  jalan kebayan (25) 0,12  jalan tongkol (20) 0,12  jalan Durian (22) 0,12  jalan osap sio (24) 0,12 8. Karag Dima ( ) 0,87  Kompi (4) 0,17  BTN Kompi (3) 0,17  Pertamina (2) 0,17 9. Desa Kerato ( ) 0,92  jalan kemuning (9) 0,15  taman kerato (16) 0,15  Sering (17) 0,15  Kerato Pojok (18) 0,15 T o t a l 8,87
Berdasarkan  Tabel  2  dengan  menggunakan  graph  dapat  diilustrasikan  lokasi  dan pengelompokan TPS seperti Gamabar 3 berikut.

## Gambar 3. Pengelompokan TPS
Ditetapkan  sampah  di  TPS  di  kelompok , dan diangkut  oleh dump  truk pertama, sampah di TPS kelompok diangkut oleh dump truk kedua, sampah di kelompok diangkut oleh dump  truk ketiga,    sampah  di  kelompok dan  kelompok diangkut  oleh dump  truk keempat, sampah di kelompok dan kelompok diangkut oleh dump truk kelima. Selajutnya dengan  menggunakan  metode  Djikstra  akan  disusun  model GVRP yaitu  menentukan  dua  TPS yang jaraknya paling mimimal dengan gudang selanjutnya vertek tersebut dihubungkan dengan edge kasus  untuk  kendaraan dump  truk ditugaskan  pada  satu  kelompok.  Sedangkan  jika dump truk mengunjungi  lebih  dari  satu  kelompok  maka  akan  dipilih  dua  TPS  dari  kelompok  yang berbeda  yang  jaraknya  paling  minimal  selanjutnya  TPS  yang  terpilih  tersebut  dihubungkan dengan edge jika terdiri dari dua kelompok, sedangkan yang lebih dari dua kelompok ditentukan satu  TPS  dari  kelompok  yang  lain  yang  jaraknya  paling  minimal  dari  TPS  yang  ditentukan
0' 1 3 2 4 8 5 7 6 9 10 11 12 14 13 15 16 17 18 19 20 21 22 24 23 25 v 10 v 2 v 4 v 5 v 7 v 8 v 11 v 12 v’ 4 K=5 dan Q=2 q10=0,4 q7=0,86 q4=1,98 q2=0,4 q4'=1,98 q12=0,92 q8=0,95 q11=0,87 q5=0,49 0' 1 3 2 4 8 5 7 6 9 10 11 12 14 13 15 16 17 18 19 20 21 22 24 23 25 v 10 v 2 v 4 v 5 v 7 v 8 v 11 v 12 v’ 4 K=5 dan Q=2 q10=0,4 q7=0,86 q2=0,4 q4'=1,98 q4=1,98 q5=0,49 q11=0,87 q8=0,95 q12=0,92
sebelumnya.   Sehingga dari Gambar 3 dapat disusun solusi model GVRP seperti pada Gambar 4 berikut.
Gambar 4. Model GVRP shift kedua
Setelah  diperoleh  model GVRP seperti  pada  Gambar  4  selanjutnya  dengan  menggunakan metode Djikstra akan ditentukan model CGVRP , yaitu menentukan rute terpendek setiap TPS di dalam kelompok masing-masing. Model CGVRP disajikan pada Gambar 5 berikut.
Gambar 5. Model CGVRP shift kedua
Dari Gambar 5 dapat lihat solusi usulan rute pendistribusian sampah pada shift kedua di kota Sumbawa  Besar.  Diperoleh  total  rute  pendistribusian  sampah  dari  tiap-tiap  TPS  di shift kedua sepanjang  85.569  meter.  Bahan  bakar  yang  digunakan  oleh dump  truck adalah  solar  dengan harga  perliternya  Rp.  6.500,-  dan  satu  liter  dapat  menempuh  jarak  8000  meter,  sehingga  biaya bahan bakar untuk pendistribusian sampah pada shift kedua adalah Rp 69.524,- .

## Unisda Journal of Mathematics and Computer Science

## 5 Kesimpulan
Berdasarkan  hasil  yang  diperoleh  dengan  menggunakan  metode GVRP dan  metode Djikstra  diperoleh  total  rute  pendistribusian  sampah  pada shift kedua  yaitu  sepanjang  85.569 meter  sehingga  menghabiskan  bahan  bakar  Rp  69.524,-  sedangkan  total  rute  yang  selama  ini digunakan  oleh  Dinas  Lingkungan  Hidup  yaitu  sepanjang  96.302  meter  diperoleh  biaya  bahan bakar Rp. 78.245,- sehingga dengan menggunakan metode GVPR dan Djikstra  lebih optimal.

## 6 Ucapan Terimakasih
Pada kesempatan ini tim peneliti menyampaikan terima kasih kepada Ditlitabmas Dirjen Dikti Kementerian Pendidikan dan Kebudayaan yang telah sepenuhnya mendanai penelitian ini. Semoga penelitian ini dapat bermanfaat.

## 7 Daftar Pustaka
[1]  Dantzig, G.,  dan Ramser, J. The truck dispatching problem. Management Science,(1959), 6:80–91.
[2]  Fauzi, Imron 2011, Penggunaan Algoritma Dijkstra Dalam Pencarian Rute Tercepat Dan Rute Terpendek (Studi Kasus Pada Jalan Raya antara Wilayah Blok M dan Kota) .
[3]  Gendreau, Michel. Dkk. 2010. A Tabu Search Heuristic for the Vehicle Routing Problem . Jstor.  Management Science, Vol. 40, No. 10 (Oct., 1994), pp. 1276-1290.
[4]  Ghiani, G., dan Improta, G. An efficient transformation of the generalized vehicle routing problem , Eur. J. Oper. Res. 122 (2000) 11–17.
[5] Laporte, G., dan Palekar, U. Some applications of the clustered traveling salesman problem , J. Oper. Res. Soc. 53 (2002) 972–976.
[6]  Marsudi. 2016. Teori Graf . Malang: University of Brawijaya Press.
[7]  P. C. Pop. 2007. New Integer Programming Formulations of the Generalized Travelling Salesman Problem. American Journal of Applied Sciences 4 (11): 932-937, 2007, ISSN 1546-9239
[8]  ______. 2012. Generalized Network Design Problems Modeling and Optimization . Boston: de Gruyter.
[9]  ______., Kara, Imdat., dan A., H., Marc. 2011. New mathematical models of the generalized vehicle routing problem and extensions . :Elsevier. Applied Mathematical Modelling 36(2012) 97–107
[10] Susanna S. 2012 . Discrete Mathematics with Application, 4 th Edition . Boston, Amerika Serikat: DePaul  University.