## Implementasi Capacitated Vehicle Routing Problem with Time Windows dengan Pendekatan Algoritma Sweep untuk Distribusi Pengangkutan Sampah
Dedi Sa'dudin Taptajani 1
Jurnal Kalibrasi Sekolah Tinggi Teknologi Garut Jl. Mayor Syamsu No. 1 Jayaraga Garut 44151 Indonesia Email : jurnal@itg.ac.id
1 deditaptajani@itg.ac.id
Abstrak – Vehicle Routing Problem (VRP) merupakan suatu permasalahan yang berkaitan dengan bagaimana menentukan rute yang dianggap optimal dan melibatkan lebih dari satu alat angkut demi memperhatikan beberapa kendala dalam melayani sejumlah tempat layanan sesuai dengan permintaan.  Salah  satu  varian dari VRP adalah capacitated  vehicle  routing  problem  with  time window (CVRPTW) varian ini menambahkan kendala kapasitas alat angkut sebagai salah satu pertimbangan didalam mengangkut ke masing masing tujuan dan kemudian memberikan jendela waktu  didalam  proses  pengangkutannya.  Tujuan  dari  penulisan  ini  adalah  menjelaskan pembentukan  model  dari  CVRPTW  untuk  permasalahan  rute  pengangkutan  sampah  dari  tiap rumah  Sampai  Ke Tempat Pembuangan Akhir,  dengan  pertimbangan  waktu yang  tersedia  dan kapasitas  angkut  alat  angkut  yang  tersedia,  Sedangkan  Penyelesaiannya  yaitu  dengan menggunakan pendekatan algoritma sweep. Algoritma Ini merupakan algoritma yang terdiri dari dua  tahap,  pada  tahapan  pertama  yaitu  clustering  dari  masing  masing  rumah  dan  tahap selanjurtnya  yaitu  membentuk  rute  pengiriman  untuk  masing-masing  cluster  dengan  metode Nearest  Neighbour,  kemudian  dilanjutkan  dengan  menentukan  kapasitas  alat  angkut  terhadap waktu  yang  diperlukan  untuk  menentukan  kapan  sampah  ini  akan  di  angkut  ke  tempat pembuangan  akhir.  Studi  ini  sangat  penting  dilakukan  dalam  rangka  menerapkan  dasar  untuk memahami  kemungkinan meningkatkan  tingkat layanan  pada  proses pengangkutan sampah  di tingkat desa.
Kata Kunci – Algoritma; Nearest Neighbour; Pengangkutan Sampah; Vehicle Routing Problem.

## I. PENDAHULUAN
Perkembangan teknologi e-commers memaksa keadaan lingkungan harus bisa beradaptasi dengan cepat pada kebiasaan saat ini, dimana banyak orang melakukan aktifitas belanja online dengan aplikasi yang nantinya berkibat  kepada  menumpuknya  sampah  rumah  tangga  akibat  penggunaan packaging  plastic yang mengharuskan penggunaan itu untuk meminimalisir terjadinya kerusakan barang pada saat pengiriman, namun ternyata itu menimbulkan effect yang sangat buruk terhadap adanya penumpukan sampah yang terjadi di msing masing daerah. Untuk menanggulangi sampah tersebut maka perlu dilakukan proses pengangkutan sampah yang dilakukan oleh masyarakat setempat guna menjadikan lingkungan yang sehat dan bersih, dalam proses pengangkutan  sampah  yang  dilakukan  perlu  adanya  tahapan  atau  cara  yang  husus  agar  pada  saat  proses pengangkutan sampah bisa terorganisir dengan baik, mengingat tidak adanya petugas khusus yang dilakukan di masing masing daerah dalam proses pengangkutan sampah [1],[2].
Penggunaan media grobak berkapasitas 0,8 m³ diharapkan mampu menyisir sampah yang ada di lingkungan masyarakat  secara  optimal.  Hanya  saja  proses  pengangkutan  sampah  dilakukan  secara  swadaya  oleh masyarakat yang berkaitan dengan penjadwalan di lingkungan.
varian VRP dengan tambahan time windows lebih dikenal dengan Capacitated Vehicle Routing Problem with Time Windows (CVRPTW) [3]. Time windows sendiri bisa diartikan sebagai batasan dari waktu operasional pekerjaan,  atau  batasan  waktu  suatu  kendaraan  bisa  mngirimkan  sampah.  Model  ini  diharapkan  mampu menyelesaikan  masalah  yang  terjadi  saat  ini,  dimana  penumpukan  sampah  di  masing  masing  rumah  tidak memperhatikan  Beberapa  penelitian  terkait  algoritma  yang  digunakan  untuk  menyelesaikan  permasalahan CVRPTW [4].
Belum  adanya  penentuan  rute  perjalanan  membuat  sulit  aparatur  desa  didalam  melaksanakan  tugas membersihkan sampah, apabila ada satu atau dua alat angkut yang harus diperbaiki maka timbunan sampah yang tidak terangkut akan makin menumpuk. Maka penentuan rute pengangkutan sampah dari rumah warga menuju  TPS  harus  diperhatikan  supaya  proses  pengangkutan  sampah  menjadi  lebih  optimal  karena berhubungan dengan efisiensi jarak dan biaya. Oleh karena itu, efisiensi sub-sistem ini diharapkan menjadkan proses pengangkutan sampah dari Rumah menuju TPS dapat menghemat jarak, waktu dan biya pengangkutan [5]. Aparatur desa sudah memiliki rute sendiri dalam proses pengangkutan sampah tetapi tidak menggunakan metode  khusus  dalam  penggunan  rekayasa  penentuan  rute  sehingga  rute  yang  digunakan  tidak mempertimbangkan  jarak  yang  ditempuh, kemudian untuk  setiap rute  menjadi tidak  seimbang  karena rute pengangkutan yang digunakan masyarakat tidak memperhatikan utilitas kapasitas kendaraan, sehingga beban sampah  yang  diangkut  masing-masing  kendaraan  di  setiap  rute  tidak  merata,  untuk  menentukan  rute pengangkutan sampah serta menjadwalkan sejumlah kendaraan yang terbatas dari tiap-tiap rumah menuju TPS dengan menentukan rute yang harus dilalui berdasarkan kepada volume kapasitas alat angkut [6],[7].
Proses  pengangkutan  sampah  di  Daerah  yaitu  mulai  dari  Rumah  sampai  berakhir  di  Tepat  Pembuangan Sementara  (TPS)  yang  baik  sesuai  dengan  apa  yang  kita  harapkan,  atau  pendistribusian  yang  optimal merupakan langkah untuk mempercepat sampainya sampah ke tempat pembuangan akhir [8]. Sehingga pada proses pengambilan sampah ke tiap rumah, masing-masing alat angkut membawa sampah dengan kapasitas yang optimal, tanpa ada kendaraan yang kosong, ketika kendaraan sampai di Tepat Pembuangan Akhir (TPA), pentingnya  proses  pengambilan  sampah  yang  optimal  merupakan  salah  satu  cara  yang  baik  di  dalam pendistribusian sampah, sehingga pada saat kendaraan mengirim sampah itu harus  mempertimbangkan rute terpendek pada jalur pengangkutan sampah, sehingga diharapkan mampu mengoptimmalkan kendaraan yang ada [9],[10].
Untuk  mencapai  pemakaian  sarana  transportasi  atau  kendaraan  yang  ideal,  dan  pola  pengangkutan  yang optimal,  maka  diperlukan  suatu  model,  yang  dapat  menggambarkan  berbagai  masalah  dalam  bidang pengangkutan,  Selain itu  juga,  diperlukan suatu  metode  sebagai  pemecahan masalah  untuk  menyelesaikan kasus tersebut [11].  Dengan permodelan   tersebut, akan memudahkan pencarian solusi untuk menemukan rute paling pendek pada sejumlah kendaraan dengan biaya yang minimal, sehingga tidak ada kendaraan yang mengeluarkan  biaya  tinggi  karena  terlalu  banyak  mengirimkan  sampah  atau  terlalu  jauh  ketika  proses pengiriman sampah dilakukan [12].

## II. METODOLOGI PENELITIAN
Untuk  menentukan rute  pengangkutan  sampah  dari masing masing  rumah  ke  tempat  pembuangan  sampah sementara ini dilakukan dengan cara mengambil sampah didatangi ke ujuan atau rumah warga. masing masing menggunakan  gerobak  sampah  yang  sudah  disediakan  pihak  desa,  kemudian  menentukan  urutan  rute pengangkutan  sampah  yang  akan  dilalui  serta  menentukan  jumlah  alat  angkut  berdasarkan  kapasitas  alat angkutyang ada ( gerobak sampah), dengan adanya skema ini diharapkan mampu memperoleh  rute terpendek dari titik titik sampah yang dilalui yaitu rumah warga yang akan membuang sampah, dengan memperhatikan kapasitas sampah yang maksimal sehingga akan menghemat waktu, biaya, dan jarak, berikut alur penentuan pemecahan masalah pengangkutan sampah dengan pendekatan metode alghoritma sweep sebagai alternatif penentuan rute dan meminimukan jarak atau waktu dan alat angkut dengan pertimbangan kendala-kendala yang ada saat ini.

## Gambar 1: Flow Chart penyelesaian pengangkutan sampah untuk kasus CVRPTW
Pada Model CVRPTW ini akan dilakukan clustering setiap Rumah Warga yang ada pada wilayah yang akan diteliti serta dilalui oleh sejumlah alat angkut yang dilakukan secara bersamaan. dengan mempertimbangkan sejumlah alat angkut yang akan melakukan pengangkutan secara bersamaan. Data-data yang dibutuhkan pada penelitian  ini  adalah  data  jalur  pengiriman  sampah  mulai  dari  RUMAH  WARGA  ke  TPS,  Kapasitas Alat angkut, jumlah alat angkut dan jenis alat angkut yang dipakai untuk mengangkut Sampah. dilakukan Grouping / clustering pada setiap Rumah yang ada pada wilayah yang akan diteliti serta dilalui oleh sejumlah alat angkut yang  dilakukan  secara  bersamaan.  dengan  mempertimbangkan  kapasitas  angkut  pada  masing  masing kendaraaan [13],[14]. Data-data yang dibutuhkan pada penelitian ini adalah data titik titik POOL, rumah dan TPS dalam bentuk gambar atau peta sehingga nantinya akan diubah menjadi titik kordinat kartesius dengan bantuan software geogebra, selanjutnya adalah jumlah kapasitas angkut pada masing masing angkutan untuk mengetahui batasan dari proses pengelompokan. Kemudian dilakukan penentuan rute kendaraan yang akan dilalui  sesuai  dengan  urutan  yang  sudah  diperhitungkan  dengan  pendekatan  Nearest  Neighbour,  data  yang diperlukan pada tahapan routing ini adalah matrix jarak antar Rumah, jarak antara rumah ke TPS, serta rumah mana  saja  yang  akan  dilalui  berdasarkan  pengelompokan  sebelumnya.  Proses  ini  diharapkan  mampu memberikan solusi optimal pada saat melakukan pendistribusian bahan baku kulit tersebut.  pengolahan data ini untuk memecahkan permasalahan kasus dari model CVRPTW dengan menggunakan Algoritma sweep, metode ini sangat sederhana sehingga mudah untuk diimplementasikan dalam penentuan rute kendaraan.

## III. HASIL DAN PEMBAHASAN
Dari  612  Tempat  atau  rumah  yang  membuang  sampah  (RUMAH  WARGA),  Satu  Tempat  Pembangan Sementara (TPS)  dengan pendekatan algoritma sweep maka dihasilkan 4 rute pengiriman sampah, kemudian terdapat 4 pool dimana ini mengacu kepada jumlah RW yang ada di Daerah,  612 rumah warga yang tiap hari membuang sampah dan 1 TPS didalam proses pengiriman sampah, dimana semuanya tersebar di beberapa titik yang  ada  Daerah.  Proses  pertama  yang dilakukan  sebelum  menentukan  rute  perjalanan  adalah  menentukan lokasi depot pada pemetaan dengan bantuan map lalu kemudian diubah menjadi koordinat kartesius dengan bantua  software  geogebra  yang  selanjutnya  akan  diubah  menjadi  koordinat  polar.  Ada  beberapa  tahapan perhitungan  sebelum  kepada  penentuan  Rute  berdasarkan  pendekatan  Algoritma  sweep,  yaitu  tahapan Grouping / clustering  dari setiap rumah, berikut Tabel hasil perhitungan yang dilakukan antara lain :
Tabel 1: Hasil grouping / clustering
No kelompok 1 kelompok 2 kelompok 3 kelompok 4 1 Q P G1 D 2 R C1 L N1 3 I N W O1 4 S M1 F U 5 Q1 J1 I1 P1 6 H M E K1 7 J E1 F1 L1 8 H1 K D 9 T O B1 10 Z A1 V 11 G
Setelah  didapatkan  hasil  pengelompokan  berdasarkan  urutan  dari  proses  grouping  dengan  pertimbangan kapasitas angkut, maka perhitungan selanjutnya adalah menentukan jarak terpendek dari rumah  ke TPS  dan jarak masing masing Rumah, selanjutnya adalah pembentukan rute dari masing masing cluster   yang   telah diperoleh   pada   tahapan sebelumnya dan akan diselesaikan dengan menggunakan metode Nearest Neighbour sehingga dapat diperoleh urutan rute perjalanan dari masing-masing  cluster, yaitu menentukan  satu titik yang akan menjadi titik awal perjalanan dimana dalam penelitian  ini sudah ditentukan bahwa titik awal perjalanan dimulai dari Pool / garasi alat angkut sampah (KANTOR RW) kemudian dilanjutkan ke Rumah, pilih titik Rumah yang akan dikunjungi selanjutnya yaitu Rumah terdekat dengan melihat  jarak paling minimum  dengan titik yang sudah terpilih sebelumnya, kemudian lakukan langkah seperti sebelumnya sampai semua titik pada cluster dikunjungi
Vol. 19; No. 1; 2021; Hal 1-6
Rute 1
Rute 2
Rute 3 Rute 4
Gambar 2: Rute Pengiriman Sampah di Daerah
empat rute inilah yang diharapkan menjadi solusi optimal pada pendistribusian sampah di kota garut. Karena kita ketahui selama ini pola pendistribusian sampah di Daerah belum pernah ditentukan rute perjalanannya, dengan  menggunakan  pendekatan  suatu  metode.  Adapun  proses  pengiriman  sampah  itu  dilaksanakan  atas dasar pengetahuan si pengantar.

## IV. KESIMPULAN
Dari hasil perhitungan total jarak pada rute 1 sebesar ± 2,8 km, rute 2 sebesar ± 3,1 km, rute 3 sebesar ± 1,1 km, rute  sebesar ± 1,42 km dengan  menggunakan  8 unit alat angkut  diharapkan mampu mengoptimasi jarak dari  kondisi  semula  yang  semberawut  tida  memiliki    pola  kebijakan  rute  yang  harus  dilalui,  dan  sekarang setelah  dilakukan  penelitian  diharapkan  akan  menjadi  lebih  optimal  baik  dari  sisi  jarak,  waktu,  dan pengangkutan.

## DAFTAR PUSTAKA
[1] T. A. M. Toffolo, T. Vidal, and T. Wauters, “Heuristics for vehicle routing problems: Sequence or set optimization?,” Comput. Oper. Res. , 2019, doi: 10.1016/j.cor.2018.12.023.
[2] N.  Gamayanti,  A.  Alkafi,  and  R.  Mangatas,  “Optimisasi  Multi  Depot  Vehicle  Routing  Problem  ( MDVRP ) dengan Variabel Travel Time Menggunakan Algoritma Particle Swarm Optimization,” JAVA J. Electr. Electron. Eng. , 2015.
[3] Lukmandono, M. Basuki, M. J. Hidayat, and F. B. Aji, “Application of Saving Matrix Methods and Cross Entropy for Capacitated Vehicle Routing Problem (CVRP) Resolving,” 2019, doi: 10.1088/1757- 899X/462/1/012025.
[4] F. Arnold and K. Sörensen, “Knowledge-guided local search for the vehicle routing problem,” Comput. Oper. Res. , 2019, doi: 10.1016/j.cor.2019.01.002.
[5] S. H. Huang and P. C. Lin, “Vehicle routing-scheduling for municipal waste collection system under the  ‘Keep  Trash  off  the  Ground’  policy,” Omega  (United  Kingdom) ,  2015,  doi: 10.1016/j.omega.2015.02.004.
[6] F. Stavropoulou, P. P. Repoussis, and C. D. Tarantilis, “The Vehicle Routing Problem with Profits and consistency constraints,” Eur. J. Oper. Res. , 2019, doi: 10.1016/j.ejor.2018.09.046.
[7] R. Pérez-Rodríguez and A. Hernández-Aguirre, “A hybrid estimation of distribution algorithm for the vehicle routing problem with time windows,” Comput. Ind. Eng. , 2019, doi: 10.1016/j.cie.2019.02.017.
[8] S.  T.  Bae,  H.  S.  Hwang,  G.  S.  Cho,  and  M.  J.  Goan,  “Integrated  GA-VRP  solver  for  multi-depot system,” Comput. Ind. Eng. , 2007, doi: 10.1016/j.cie.2007.06.014.
[9] L. Wen and R. Eglese, “Minimum cost VRP with time-dependent speed data and congestion charge,” Comput. Oper. Res. , 2015, doi: 10.1016/j.cor.2014.10.007.
[10]  M. Casazza, A. Ceselli, and R. Wolfler Calvo, “A branch and price approach for the Split Pickup and Split Delivery VRP,” Electron. Notes Discret. Math. , 2018, doi: 10.1016/j.endm.2018.07.025.
[11]  V.  Baradaran,  A.  Shafaei,  and  A.  H.  Hosseinian,  “Stochastic  vehicle  routing  problem  with heterogeneous vehicles and multiple prioritized time windows: Mathematical modeling and solution approach,” Comput. Ind. Eng. , 2019, doi: 10.1016/j.cie.2019.03.047.
[12]  Y. H. Huang, C. A. Blazquez, S. H. Huang, G. Paredes-Belmar, and G. Latorre-Nuñez, “Solving the Feeder  Vehicle  Routing  Problem  using  ant  colony  optimization,” Comput.  Ind.  Eng. ,  2019,  doi: 10.1016/j.cie.2018.10.037.
[13]  R. J. Kuo, B. S. Wibowo, and F. E. Zulvia, “Application of a fuzzy ant colony system to solve the dynamic  vehicle  routing  problem  with  uncertain  service  time,” Appl.  Math.  Model. ,  2016,  doi: 10.1016/j.apm.2016.06.025.
[14]  B.  Sawik,  J.  Faulin,  and  E.  Pérez-Bernabeu,  “A  Multicriteria Analysis  for  the  Green VRP: A  Case Discussion for the Distribution Problem of a Spanish Retailer,” 2017, doi: 10.1016/j.trpro.2017.03.037.