Ekologia : Jurnal Ilmiah Ilmu Dasar dan Lingkungan Hidup
Volume 19, Nomor 1, April 2019, Hal.39-43
https://journal.unpak.ac.id/index.php/ekologia
e-ISSN: - ; p-ISSN: 1411-9447

## MODEL VEHICLE ROUTING PROBLEM DALAM MENENTUKAN BANYAKNYA RUTE DAN ARMADA PENGANGKUTAN SAMPAH

## DI KOTA BOGOR
Maya Widyastiti 1* , Isti Kamila 2
1 Program Studi Matematika, FMIPA, Universitas Pakuan *Email: maya.widyastiti@unpak.ac.id
diterima: 16 Januari 2019; direvisi:29 Januari 2019; disetujui:24 Februari 2019

## ABSTRAK
Masalah  sampah  adalah  masalah  yang  umum  terjadi  di  perkotaan,  termasuk  Kota  Bogor. Penelitian ini bertujuan untuk menentukan banyaknya rute dan armada pengangkutan sampah di Kota Bogor. Metode yang  digunakan adalah metode Branch and Bound dengan  menggunakan model Vehicle  Routing  Problem .  Hasil  yang  diperoleh  berupa  rute  pengangkutan  sampah sebanyak  69  rute  dan  armada  pengangkut  sampah  yang  dibutuhkan  sebanyak  36  armada pengangkut,  dengan  rincian  Bogor  Tengah  sebanyak  7  rute  dan  armada  pengangkut  sampah sebanyak 4 unit, Bogor Utara sebanyak 13 rute dan armada pengangkut sebanyak 4 unit, Bogor Timur sebanyak 6 rute dan armada pengangkut sebanyak 3 unit, Bogor Barat sebanyak 14 rute dan  armada  pengangkut  sebanyak  7  unit,  Bogor  Selatan  sebanyak  16  rute  dan  armada pengangkut  sebanyak  8  unit,  dan  Tanah  Sareal  sebanyak  12  rute  dan  armada  pengangkut sampah sebanyak 6 unit.

## Kata Kunci : armada pengangkut, rute, sampah, vehicle routing problem

## VEHICLE ROUTING PROBLEM TO DETERMINE THE NUMBER OF ROUTES AND FLEET OF GARBAGE TRANSPORTATION IN BOGOR

## ABSTRACT
Garbage problem is a common problem in urban areas, including in Bogor. This study aims to determine the number of routes and fleet of garbage transportation in Bogor. The method used is the  Branch  and  Bound  method  by  using  the  Vehicle  Routing  Problem  model.  The  results obtained  in  the  form  of  69  garbage  transportation  routes  and  36  garbage  transport  fleets  are needed, with details of Central Bogor as many as 7 routes and 4 garbage transport fleets, North Bogor as many as 13 routes and 4 transport fleet units, East Bogor as much as 6 units 3 units of transport  routes  and  fleets,  14  units  of  West  Bogor  and  7  units  of  transport  fleet,  16  units  of Bogor Selatan and 8 units of transport fleet, and 12 units of Tanah Sareal and 6 units of garbage transport fleet.
Keywords: garbage, route, transport fleet, vehicle routing problem
Maya Widyastiti, dkk: Model Vehicle Routing Problem Dalam Menentukan Banyaknya Rute.....

## PENDAHULUAN
Masalah  sampah  adalah  merupakan salah satu tantangan yang sering dihadapi di setiap daerah, termasuk di Kota Bogor. Dari tahun  ke  tahun,  volume  sampah  di  Kota Bogor  kian  meningkat.  Hal  ini  disebabkan oleh bertambahnya jumlah penduduk di Kota Bogor.  Data  yang  diperoleh  dari  Dinas Lingkungan  Hidup  (DLH)  Kota  Bogor menyebutkan bahwa volume sampah di Kota Bogor  mencapai  2900  meter  kubik  dan hanya  2100  meter  kubik  yang  dapat terangkut  ke  Tempat  Pembuangan  Akhir (TPA) Galuga. Proses pengangkutan sampah di  Kota  Bogor  dilakukan  setiap  harinya dengan  2  kali  perjalanan.  Akan tetapi,  DLH Kota  Bogor  memiliki  keterbatasan  dalam proses pengangkutan sampah, seperti keterbatasannya armada pengangkut sampah. Saat ini armada pengangkut sampah di setiap kecamatan  berbeda.  Volume  sampah  di setiap  kecamatan  pun  berbeda.  Oleh  karena itu, penelitian ini bertujuan untuk menentukan  banyaknya  armada  pengangkut sampah agar sampah dapat terangkut dengan baik  dari  setiap  Tempat  Pembuangan Sementara  (TPS)  di  setiap  kecamatan  ke TPA Galuga.
Apriyanti et  al (2018)  telah  melakukan penelitian  menggunakan  Sistem  Informasi Geografis  dalam  proses  pengangkutan sampah.  Hasil  yang  diperoleh  berupa  rute perjalanan sebanyak 88 rute. Pada penelitian ini,  masalah  pengangkutan  sampah  akan diformulasikan  ke  dalam  model Vehicle Routing  Problem dan  selesaikan  dengan metode Branch and Bound . Menurut Toth dan Vigo (2002), Vehicle Routing Problem (VRP) merupakan masalah penentuan  rute  armada  pengangkut  dalam mengantarkan  suatu  produk  dari  depot (tempat produksi) ke pelanggan (konsumen) dengan tujuan meminimumkan jarak tempuh atau  biaya  perjalanan  atau  waktu  tempuh. Pada kasus pengangkutan sampah, beberapa batasan yang harus dipenuhi, antara lain:
1. setiap armada harus memulai perjalanan dari TPA
2. Setiap  TPS  hanya  akan  dikunjungi sebanyak satu kali oleh satu armada
3. Setiap TPS mempunyai volume sampah yang harus diangkut
4. Setiap  armada  memiliki  keterbatasan kapasitas
5. Tidak  terdapat subroute untuk  setiap armada.
Masalah
VRP telah banyak dikembangkan,  antara  lain  oleh  Crevier (2007)  untuk  VRP  banyak  depot,  Kim (2006) menyelesaikan dengan Vehicle Routing Problem with time windows .

## BAHAN DAN METODE Data
Data yang digunakan pada penelitian ini berupa  data  volume  sampah  di  Kota  Bogor yang  diperoeh  dari  DLH  Kota  Bogor, berupa  data  TPS  kontainer,  volume  sampah dan  banyaknya  armada  (truk container ) yang  tersedia  secara  tidak  merata  di  setiap kecamatan.  Adapun  banyaknya  TPS  dan armada  di  setiap  kecamatan  dapat  dilihat pada Tabel 1.
Tabel 1. Banyaknya TPS dan armada pengangkut sampah di setiap kecamatan
Kecamatan Banyaknya TPS Banyaknya armada Bogor Tengah 17 7 Bogor Utara 13 5 Bogor Timur 14 5 Bogor Barat 12 4 Bogor Selatan 16 4 Tanah Sareal 17 6

## Vehicle Routing Problem
Menurut Toth dan Vigo (2002), Vehicle Routing  Problem (VRP)  pertama  kali diperkenalkan  oleh  Dantzig  dan  Ramser pada  tahun  1959.  Masalah  ini  berorientasi pada  masalah  optimasi  kombinatorial,  yaitu optimasi  yang  melibatkan  banyak  variabel. VRP  dapat  dinyatakan  sebagai  suatu  digraf (    ) ,  dengan *          + adalah himpunan  simpul  yang  menunjukkan  lokasi pelanggan  dan *(    )                + yaitu himpunan sisi berarah yang menyatakan  jalan  penghubung  antarlokasi pelanggan.  Gambaran  mengenai  VRP  dapat dilihat pada Gambar 1 dan Gambar 2.
Gambar 1. Input dari sebuah VRP.
Gambar 2. Salah satu solusi yang mungkin terjadi dari Gambar 1

## Metode Branch and Bound
Prinsip  dasar  dari  metode  Branch  and Bound adalah memecah daerah fisibel suatu masalah  LP-relaksasi  dengan  membuat subproblem-subproblem.  Ada  dua  konsep dasar  dalam  metode branch  and  bound, yaitu branching dan bounding .
1. Branching Branching adalah  proses  membagi-bagi permasalahan menjadi subproblem- subproblem  yang mungkin  mengarah ke solusi.
2. Bounding Bounding adalah  suatu  proses  untuk mencari/menghitung  batas  atas  (dalam masalah  minimisasi)  dan  batas  bawah (dalam  masalah  maksimisasi)  untuk solusi  optimal  pada  subproblem  yang mengarah ke solusi.
Berikut  ini  adalah  langkah-langkah penyelesaian  suatu  masalah  maksimisasi dengan metode branch and bound . 1. Langkah 0 Didefinisikan sebagai  batas  bawah  dari nilai  fungsi  objektif  (solusi)  ILP  yang optimum. Pada awalnya ditetapkan dan .
2. Langkah 1
Subproblem  LP ( i ) dipilih  sebagai  masalah berikutnya  untuk  dipecahkan.  Subproblem LP ( i ) diselesaikan dan diukur dengan kondisi yang sesuai.
a). Jika  LP ( i ) terukur  dan  solusi  LP  yang ditemukan lebih baik  maka batas bawah z  diperbarui.  Jika  tidak,  bagian  masalah (subproblem)  baru i dipilih  dan  langkah 1 diulangi. Jika semua subproblem telah dipecahkan, maka proses dihentikan.
b). Jika LP ( i ) tidak terukur, proses dilanjutkan ke langkah 2 untuk melakukan pencabangan LP ( i ) . 3. Langkah 2 Dipilih  salah  satu  variabel x j yang  nilai optimumnya adalah x j * yang tidak memenuhi  batasan integer dalam  solusi LP ( i ) .  Bidang  [ x j * ]  ≤ x j ≤  [ x j * ]  +  1 disingkirkan dengan membuat dua subproblem LP, yaitu x j ≤ [ x j * ] dan x j ≥ [ x j * ] + 1, sehingga diperoleh kendala subproblem baru sebagai berikut:
 Subproblem baru 1 : kendala subproblem lama + kendala x j ≤ [ x j * ]  Subproblem baru 2 : kendala subproblem lama + kendala x j ≥ [ x j * ]+1 dengan  [ x j * ]  didefinisikan  sebagai integer terbesar yang kurang dari atau sama dengan
Pelanggan DEPOT RUTE DEPOT
Maya Widyastiti, dkk: Model Vehicle Routing Problem Dalam Menentukan Banyaknya Rute.....
x j * .  Selanjutnya  kembali  ke  langkah  1. (Taha 1996)

## HASIL DAN PEMBAHASAN
Himpunan dan Indeks K = {1,2,…, r }   = himpunan armada, dengan indeks k S = {2,3,…, n }  =  himpunan  TPS,  dengan indeks i, j, l A =  {1,2,…, n }  = himpunan TPA dan TPS, dengan node 1 menyatakan TPA dan dengan indeks i, j, l
Parameter a k = kapasitas angkut maksimal dari armada ke- k q i = banyaknya volume sampah yang ada di TPS ke- i r i =  banyaknya  volume  sampah  yang diangkut di TPS ke- i d ij = jarak TPS ke- i dan TPS ke- j M = konstanta positif u ki =  variabel  tambahan  yang  menyatakan truk k mengunjungi TPS i agar menghindari terjadinya subroute .
N = banyaknya truk yang tersedia

## Variabel Keputusan
{
{

## Fungsi Tujuan
Fungsi tujuan pada penelitian ini adalah meminimumkan banyaknya rute yang akan dilalui oleh armada ke- k.

## ∑

## Kendala
Kendala yang harus dipenuhi antara lain.
1. Tidak semua armada keluar dari TPA
∑
2. Tidak  ada  agen  yang  dilayani  oleh kendaraan yang tidak dijalankan,
3. Setiap  TPS  akan  dikunjungi  hanya  satu kali oleh satu armada
∑ ∑
∑ ∑
4. Setiap truk akan meninggalkan TPS suatu TPS untuk mengunjungi TPS lainnya

## ∑ ∑
5. Setiap  truk  hanya  mampu  mengangkut sampah sesuai dengan kapasitas dari truk tersebut.
∑ ∑
6. Tidak  terjadinya  subroute  untuk  setiap truk
7. Variabel keputusan x ijk merupakan variabel keputusan yang bernilai 0 atau 1,
*   +
8. Variabel keputusan z k merupakan variabel keputusan yang bernilai 0 atau 1,
*   +

## Pembahasan
Berdasarkan formulasi matematika yang  telah  dibentuk,  kemudian  dicari  solusi berupa  banyaknya  rute  dan  banyaknya armada  dengan  menggunakan  perangkat lunak  LINGO  11.0.  Hasil  yang  diperoleh
Ekologia : Jurnal Ilmiah Ilmu Dasar dan Lingkungan Hidup
berupa banyaknya rute pengangkutan sebanyak  69  rute  dan  banyaknya  armada yang  dibutuhkan  sebanyak  36  unit.  Rincian dari  hasil  yang  diperoleh  untuk  setiap kecamatan dapat dilihat pada Tabel 2.
Tabel 2. Hasil yang diperoleh Kecamatan Banyaknya Rute Banyaknya Armada Bogor Tengah 7 4 Bogor Utara 13 7 Bogor Timur 6 3 Bogor Barat 14 7 Bogor Selatan 16 8 Tanah Sareal 13 7 Total 69 36
Berdasarkan Tabel 1 dan Tabel 2, dapat dilihat  bahwa  banyaknya  armada  di  di Bogor  Barat,  Bogor  Selatan  dan  Tanah Sareal  mengalami  kekurangan  armada berturut-turut  sebanyak  3  unit,  4  unit  dan  1 unit.  Hal  ini  menunjukkan  bahwa  di  3 kecamatan tersebut memiliki peluang penumpukan  sampah  karena  kurangnya ketersediaan  armada.  Sedangkan  untuk Bogor  Tengah,  Bogor  Utara  dan  Bogor Timur mengalami kelebihan armada masing-masing sebanyak 3 unit, 2 unit dan 2 unit.  Hal  ini  dapat  menunjukkan  bahwa DLH  Kota  Bogor  dapat  meningkatkan kinerjanya  dalam  mengangkut  sampah karena  di  3  kecamatan  ini  ketersediaan armada telah tercukupi.

## KESIMPULAN
Berdasarkan  hasil  penelitian  yang  telah dilakukan  dapat  ditarik  kesimpulan  : Banyaknya  rute  yang  dihasilkan  adalah sebanyak  69  rute,  dengan  rincian  Bogor Tengah  sebanyak  7  rute,  Bogor  Utara sebanyak  13  rute,  Bogor  Timur  sebanyak  6 rute,  Bogor  Barat  sebanyak  14  rute,  Bogor Selatan  sebanyak  16  rute,  dan  Tanah  Sareal sebanyak  13  rute.  Banyaknya  armada  yang dibutuhkan adalah 36 armada dengan rincian
Bogor  Tengah  sebanyak  4  armada,  Bogor Utara  sebanyak  7  armada,  Bogor  Timur sebanyak 3 armada, Bogor Barat sebanyak 7 armada,  Bogor  Selatan  sebanyak  8  armada, dan  Tanah  Sareal  sebanyak  7  armada. Terjadi kekurangan armada untuk kecamatan  Bogor  Barat  sebanyak  3  unit, Bogor  Selatan  sebanyak  4  unit  dan  Tanah Sareal sebanyak 1 unit.

## UCAPAN TERIMA KASIH
Penelitian  ini  didanai  oleh  dana  Yayasan
Pakuan
Siliwangi Nomor 20/LPPM-
KPDP/XI/2018.  Ucapan  terima  kasih  ini  juga ditujukan  kepada  semua  pihak  yang  terkait sehingga  penelitian  ini  dapat  terlaksana  dengan baik.

## DAFTAR PUSTAKA
Apriyanti,  D.,  Kresnawati,  D.  K.  & Diniyah,  W.  F.  (2018).  Pemanfaatan Sistem  Informasi  Geografis  Untuk Analisis  Rute  Armada  Pengangkutan Sampah  Di  Kota  Bogor. Proceeding
National
Seminar of Geomatics Geospatial Information  Agency. Bogor, Indonesia.
Crevier  B,  Cordeau  JF,  Laporte  G.  (2007).
The multi-depot vehicle routing problem with inter-depot routes. European Journal of Operational Research. 176(2): 756-773.
Kim  BI,  Kim  S,  Sahoo  S.  (2006).  Waste collection vehicle routing problem with time windows. Computer &  Operations Research. 33(12): 3624-3642.
Taha HA. (1996). Pengantar Riset Operasi . Daniel  Wirajaya,  penerjemah.  Jakarta: Binarupa  Aksara.  Terjemahan  dari: Operations Research .
Toth  P,  Vigo  D.  (2002).  An  overview  of vehicle  routing  problems.  Di  dalam Toth  P, et  al., editor. The  Vehicle Routing  Problem. Philadelphia:  Siam; hlm. 1-26.
Winston WL. (2004). Operations Research Applications and Algorithms . Ed ke-4. New York: Duxbury.