## JURNAL ILMIAH TEKNIK INDUSTRI
ISSN: 1412-6869  e-ISSN: 2460-4038 Journal homepage: http://journals.ums.ac.id/index.php/jiti/index doi:10.23917/jiti.v18i2.8744
Ekky Armandi 1a , Annie Purwani 1b , Utaminingsih Linarti 1c
Abstract. The increasing population in Yogyakarta City has implications for consumption and solid waste production activities. The waste collection process is the most expensive one in municipal waste management. It is necessary to determine the optimal route for municipal waste collection. In this research, we developed a vehicle routing problem (VRP) with a heterogeneous fleet, multiple trips, intermediate facility, and split delivery to approach the Yogyakarta City waste collection problem. We proposed a hybrid genetic algorithm (GA) to solve the VRP. The result of this study shows that developed VRP can be used to solve the Yogyakarta City waste collection problem.
Keywords: Vehicle Routing Problem, routing problem, city waste collection, Genetic Algorithm
Abstrak. Jumlah  penduduk  Kota  Yogyakarta  yang  terus  bertambah  setiap  tahunnya  berimplikasi  pada  semakin meningkatnya  aktivitas  konsumsi  sekaligus  sampah  yang  dihasilkan.  Proses  pengumpulan  sampah  merupakan kontributor terbesar untuk biaya pengelolaan sampah. Sehingga diperlukan penentuan rute pengangkutan sampah kota yang optimal. Penelitian ini mengembangkan model vehicle routing problem (VRP) untuk persoalan penentuan rute pengangkutan sampah Kota Yogyakarta yang mempertimbangkan batasan heterogeneous fleet, multiple trip, intermediate facility, dan split delivery yang kemudian diselesaikan menggunakan hybrid genetika algoritma (GA). Peneletian ini berhasil mengembangkan model VRP untuk menyelesaikan persoalan penentuan rute pengangkutan sampah Kota Yogyakarta.
Kata Kunci: Vehicle Routing Problem, penentuan rute, pengangkutan sampah kota, Algoritma Genetika

## I. P ENDAHULUAN
Jumlah penduduk Kota Yogyakarta yang terus bertambah  setiap  tahunnya  berimplikasi  pada semakin  meningkatnya  aktivitas  konsumsi sekaligus  sampah  yang  dihasilkan.  Menurut  UU No. 18, tahun 2008 tentang Pengelolaan Sampah, sampah didefinisikan sebagai sisa kegiatan sehari- hari  manusia  dan/atau  proses  alam  yang berbentuk padat.
Pada  tahun  2016,  jumlah  sampah  yang dihasilkan  oleh  Kota  Yogyakarta  rata-rata mencapai 226,2  ton/hari  sedangkan  jumlah  yang terangkut  ke  tempat  pembuangan  akhir  (TPA) rata-rata adalah 176,4 ton/hari atau sekitar 77,98%
dari total sampah yang dihasilkan dalam sehari.
Proses  pengumpulan  sampah  merupakan kontributor  terbesar  untuk  biaya  pengelolaan sampah  (Fitria  dkk . ,  2009).  Dinas  Lingkungan Hidup  (DLH)  Kota  Yogyakarta  merupakan perangkat  daerah  yang  bertugas  salah  satunya dalam  melakukan  kegiatan  teknis  pengelolaan sampah  seperti  penyapuan  jalan,  pengumpulan sampah,  dan  pengangkutan  sampah  dari  tempat pembuangan  sementara  (TPS)  menuju  TPA Piyungan.
TPA  Piyungan  merupakan  salah  satu  TPA terbesar  yang  ada  di  Provinsi  Daerah  Istimewa Yogyakarta  (DIY)  yang  mampu  menampung sampah  dari  Kota  Yogyakarta,  Kabupaten  Bantul, maupun  dari  Kabupaten  Sleman  (Lestari,  2013). DLH  Kota  Yogyakarta  membagi  wilayah  kerjanya menjadi  lima  sektor;  yang  diantaranya  adalah Sektor Malioboro-Kranggan, Sektor Gunung Ketur, Sektor  Ngasem-Gading,  Sektor  Kota  Gede,  dan Sektor  Krasak.  DLH  Kota  Yogyakarta  juga menyediakan fasilitas penampungan sampah yang terdiri  dari  TPS  dengan  volume  rata-rata  relatif kecil dan sedikitnya TPS dengan volume yang lebih besar dari kapasitas kendaraan. Ada sekitar 30 truk dengan  kapasitas  berbeda  yang  ditugaskan  DLH

## Optimasi Rute Pengangkutan Sampah Kota Yogyakarta Menggunakan Hybrid Genetic Algorithm
1 Program Studi Teknik Industri, Fakultas Teknologi Industri, Universitas Ahmad Dahlan, Jl. Prof. DR. Soepomo Sh No.80, Warungboto, Kec. Umbulharjo, Kota Yogyakarta, Daerah Istimewa Yogyakarta 55164.
a email: ekkyarmandi@gmail.com
b email: annie.purwani@ie.uad.ac.id c email: utaminingsih.linarti@ie.uad.ac.id
Diajukan: 30-08-2019 Diperbaiki: 07-12-2019
Disetujui: 10-12-2019
untuk melakukan pengumpulan dan pengangkutan  sampah  Kota  Yogyakarta  setiap harinya.
Setiap  kendaraan  yang  ditugaskan  untuk melakukan  pengumpulan  dan  pengangkutan sampah berangkat dari depot yang sama menuju titik-titik  TPS  untuk  melakukan  pengangkutan sampah  hingga  memenuhi  kapasitas  kendaraan yang  kemudian  muatannya  dikosongkan  terlebih dahulu  pada  TPA  sebelum  kembali  ke  depot maupun  sebelum  kembali  melakukan  pelayanan pengangkutan sampah pada titik TPS yang belum terlayani selama tidak melebihi batas waktu yang telah ditentukan.
Persoalan
penentuan rute sejumlah kendaraan  yang  berangkat  dari  depot  dalam memenuhi  permintaan  sejumlah  titik  layanan dengan  tidak  melanggar  batasan  operasional tertentu dikenal sebagai Vehicle Routing Problem (VRP) (Wibisono, 2018). Model dasar VRP memiliki asumsi bahwa kendaraan yang ditugaskan adalah homogen  dan  titik  layanan  hanya  boleh  dilayani tepat satu kali dalam satu rute pelayanan dengan fungsi  tujuan  meminimumkan  jarak  tertempuh yang  diasosiasikan  dengan  biaya  (Golden  dkk . , 1984).
Penelitian  terdahulu  yang  menggunakan model  VRP  dasar  dilakukan  oleh  Indrawati  dkk .
(2016) pada persoalan penentuan rute pengangkutan  sampah  Kota  Palembang  yang diselesaikan menggunakan metode saving matrix . Sedangkan penelitian yang dilakukan Pakusadewa dkk . (2017) menggunakan model VRP dasar pada penentuan  rute  pengangkutan  sampah  Kota Denpasar  yang  diselesaikan  menggunakan Genetic  Algorithm yang  dihibridasi  dengan algoritma Simulated Annealing (GA-SA). Model  VRP  dasar  terlalu  sederhana  untuk persoalan penentuan rute pengangkutan sampah Kota  Yogyakarta.  Model  VRP  dasar  tidak mempertimbangkan adanya
TPA sebagai intermediate facility , kendaraan dengan kapasitas berbeda,  kondisi  yang  memungkinkan  suatu kendaran  untuk  melayani  lebih  dari  satu  rute dalam  satu  periode  perencanaan  penugasan kendaraan,  maupun  kondisi  dimana  titik  layanan memungkinkan untuk dilayani lebih dari satu kali.
Penugasan  kendaraan  dalam  melakukan pengangkutan sampah dari depot menuju TPS ke TPA dan kembali ke TPS maupun kembali ke depot
adalah  persoalan  penentuan  rute  yang mempertimbangkan adanya
TPA sebagai intermediate facility . Menurut  Angelelli  dan  Speranza  (2002), intermediate  facility adalah  fasilitas  yang  harus dikunjungi  oleh  suatu  kendaraan  untuk memperbarui  kapasitas  kendaraan    setiap  kali kendaraan akan memulai rute baru.
Fitria  dkk . (2009)  mengembangkan  model VRP  yang  mempertimbangkan  keberadaan intermediate  facility dan batasan yang memungkinkan  kendaraan  melakukan  pelayanan untuk  lebih  dari  satu  rute  yang  disebut  sebagai Vehicle Routing Problem with Multiple Trips and Intermediate  Facility (VRPMTIF)  yang  digunakan pada  penentuan  rute  pengumpulan  dan pengangkutan  sampah  Kota  Bandung  dengan fungsi  tujuan  meminimumkan  jumlah  kendaraan yang  digunakan  dan  total  waktu  penyelesaian yang ditempuh oleh kendaraan yang diselesaikan menggunakan algoritma sequential insertion . Menurut  Arvianto  dkk . (2014),  batasan multiple trips adalah batasan yang memungkinkan suatu kendaran untuk melayani lebih dari satu rute dalam  satu  periode  perencanaan  penugasan kendaraan.
Model  VRP  dasar  maupun  model  VRPMTIF yang  dikembangkan  oleh  Fitria  dkk . (2009) menganggap  bahwa  seluruh  kendaraan  yang digunakan adalah homogen dan tidak mempertimbangkan titik
layanan yang memungkinkan untuk dilayani lebih dari satu kali. Model VRP yang mempertimbangkan adanya kendaraan  dengan  kapasitas  berbeda  disebut sebagai Heterogeneous  Fleet  Vehicle  Routing Problem (HFVRP) umumnya dengan fungsi tujuan meminimumkan  total  jarak  tertempuh  oleh kendaraan (Prins, 2002).
Menurut  Ray  dkk . (2012),  batasan  VRP  yang memungkinkan suatu titik layanan untuk dilayani lebih  dari  satu  kali  jika  kendaraan  pertama  tidak mampu memenuhi permintaan pada titik layanan tersebut disebut dengan split delivery . VRP dikategorikan sebagai masalah kombinatorial  dan  diklasifikasi  sebagai  NP-Hard ( non deterministic polynomial time ) ketika jumlah titik  kunjungan  dan  batasan  VRP  semakin bertambah  yang  berarti  semakin  meningkat jumlah  solusinya,  VRP  semakin  dituntut  untuk dapat  diselesaikan  dalam  waktu  komputasi  yang
lebih singkat (Golden dkk . , 1984).
Metode  eksak  seperti  penelitian  yang dilakukan oleh Fukasawa dkk . (2006) dalam Prins (2009) hanya sanggup menyelesaikan VRP dengan 100  titik  layanan.  Oleh  sebab  itu  dibutuhkan metode  heuristik  (seperti  pada  penelitian  yang dilakukan oleh Priyandari (2008), Fitria dkk . (2009), Eminugroho dan Dwi (2013), Arvianto dkk . (2014), Arinalhaq dkk . (2013), dan  Indrawati dkk . (2016)) maupun  metaheuristik  (seperti  pada  penelitian yang  dilakukan  oleh  Bell  dan  McMullen  (2004), Prins    (2009),  Baker  dan  Ayechew  (2003),  Cheng dan Yu (2013), dan Nugraha dan Mahmudy (2015)) untuk  menyelesaikan  VRP  dengan  waktu komputasi  yang  lebih  singkat  dan  menghasilkan solusi yang paling mendekati optimal.
Penelitian  yang  dilakukan  oleh  Baker  dan Ayechew  (2003)  mengembangkan  GA  untuk menyelesaikan  VRP  dasar,  Prins    (2009) mengembangkan  dua memetic  algorithm (MA) yang merupakan GA yang dihibridasi dengan local search untuk menyelesaikan HVRP. Liu dkk . (2009) mengembangkan  GA  untuk  menyelesaikan Fleet Size and Mix Vehicle Routing Problem (FSMVRP), dan  Cheng  dan  Yu  (2013)  mengembangkan  GA untuk  menyelesaikan  VRP with  Time  Windows (VRPTW).
Jika penelitian yang dilakukan oleh  Fitria dkk . (2009)  dan  Indrawati  dkk . (2016)  menggunakan algoritma sequential  insertion ,  dan  Pakusadewa dkk . (2017)  menggunakan  GA-SA  untuk menyelesaikan  VRP  pada  persoalan  penentuan rute  pengumpulan  dan  pengangkutan  sampah kota. Maka penelitian ini kemudian menggunakan GA  yang  dikombinasikan  dengan  algoritma  LS pada tahap evaluasi yang disebut sebagai Hybrid GA  untuk  menyelesaikan  VRP  yang  telah dikembangkan  pada  persoalan  penentuan  rute pengumpulan  dan  pengangkutan  sampah  Kota Yogyakarta.  Penelitian  ini  dilakukan  pada  sektor Krasak  yang  merupakan  salah  satu  wilayah  kerja DLH Kota Yogyakarta. Adapun batasan VRP yang dipertimbangkan  dalam  penelitian  ini  adalah sebagai  berikut:  (a)  jenis  kendaraan  yang digunakan  memiliki  kapasitas  yang  berbeda ( heterogeneous  fleet ),  (b)  adanya  TPA  sebagai intermediate  facility atau  titik  yang  harus dikunjungi oleh kendaraan sebelum memulai rute baru  maupun  sebelum  kembali,  (c)  kondisi  yang memungkinkan suatu kendaraan untuk
menciptakan rute perjalanan baru ( Multiple Trips ), dan  (d)  kondisi  yang  memungkinkan  suatu  titik layanan  untuk  dapat  dilayani  lebih  dari  satu  kali atau oleh kendaraan berikutnya ( Split Delivery ).

## II. M ETODE P ENELITIAN

## Karakteristik Sistem
Penelitian  ini  dilakukan  pada  Sektor  Krasak yang merupakan salah satu wilayah kerja DLH Kota Yogyakarta dengan titik TPS terbanyak dibanding sektor yang lainnya. Ada 27 titik TPS (Tabel 1) yang tersebar dan ada 10 kendaraan dengan kapasitas berbeda  yang  ditugaskan  pada  Sektor  Krasak, diantaranya adalah 2 truk kompaktor ( compactor ) dan  8  truk  bak  ( dump  truck )  masing-masing dengan kapasitas 10m 3 dan 6m 3 . Penugasan  kendaraan  dalam  melakukan pengumpulan dan pengangkutan sampah dimulai sejak jam 06:00 pagi hingga jam 13:00 siang atau sama dengan 7 jam kerja (420 menit). Setiap hari, kendaraan  pengangkut  sampah  ditugaskan mengunjungi titik-titik TPS untuk mengumpulkan dan  mengangkut  sampah  menuju  TPA  Piyungan. Setiap kendaraan akan berangkat dari kantor DLH dan  akan  berakhir  di  kantor  DLH.  Sampah  yang diangkut  tidak  boleh  melebihi  kapasitas kendaraan.  Kendaraan  dengan  bak  yang  penuh akan  dikosongkan  pada  TPA  Piyungan  sebelum kembali  mengunjungi  titik-titik  TPS  yang  belum terangkut.  Titik  TPS  yang  tidak  terangkut sepenuhnya  boleh  dilayani  oleh  kendaraan lainnya. Total waktu penyelesaian kendaraan tidak boleh  melebihi  batas  waktu  penyelesaian  yang telah  ditentukan.  Kondisi  yang  menghambat perjalanan truk diabaikan.

## Pengembangan Model
Model  VRP  yang  digunakan  pada  penelitian ini  mengacu  pada  model  VRPMTIF  yang  telah dikembangkan  oleh  Fitria  dkk . (2009)  dengan menambahkan batasan model Heterogenous fleet oleh Jiang dkk . (2014) dan Split Delivery oleh Izar (2018) dengan fungsi tujuan meminimumkan total jarak  tertempuh  dan  total  waktu  penyelesaian kendaraan.
Batasan model yang dipertimbangkan dalam mendekati  persoalan  pada  penelitian  ini  adalah sebagai berikut:
1. Heterogeneous Fleet , dimana kendaraan yang digunakan  memiliki  kapasitas  yang  berbeda
dan tidak mempertimbangkan biaya tetap dan biaya variabel.
2. Intermediate Facility , dimana setiap kendaraan akan  mengosongkan  muatanya  pada  TPA sebelum memulai perjalanan baru selama tidak melebihi batas waktu penyelesaian yang telah ditentukan.
3. Multiple  Trips ,  dimana  setiap  kendaraan memungkinkan untuk melayani lebih dari satu rute  dalam  satu  periode  perencanaan penugasan kendaraan.
4. Split  Delivery ,  dimana  suatu  titik  layanan memungkinkan  untuk  dilayani  lebih  dari  satu kali  jika  kendaraan  pertama  tidak  mampu memenuhi permintaan pada titik layanan.

## Model Matematis
Sesuai  karakteristik  sistem  penentuan  rute pengangkutan  sampah  Kota  Yogyakarta,  maka model matematis yang ditentukan pada penelitian
ini adalah sebagai berikut. Himpunan Indeks 𝑉 = himpunan titik layanan 𝐾 = himpunan kendaraan
𝐿 = himpunan rute
Parameter
𝑉 = depot 𝑉 = intermediate facility 𝑑 = permintaan pada titik 𝑖 ( 𝑖 ∈ 𝑉 ) 𝑡 = waktu tempuh (menit)
𝑐 = jarak tempuh (meter)
𝑝 = waktu loading (m3/menit) 𝑞 = waktu unloading (m3/menit)
𝑚 = jumlah kendaraan (unit) 𝑛 = jumlah titik layanan (unit) ( 𝑛 ∈ 𝑉 ) 𝑄 = kapasitas kendaraan 𝑘 (m3) ( 𝑘 ∈ 𝐾 ) 𝑇 = maksimal waktu penyelesaian (menit) Variabel Keputusan
𝑆 = waktu pelayanan oleh kendaraan 𝑘 pada rute 𝑙 (menit) ( 𝑙 ∈ 𝐿, 𝑘 ∈ 𝐾 ) 𝐶𝑇 =  waktu  penyelesaian  oleh  kendaraan 𝑘 (menit)
𝑋 =  bernilai  1  jika  kendaraan 𝑘 melakukan perjalanan dari titik 𝑖 ke titik 𝑗 pada rute 𝑙 , bernilai  0  jika  sebaliknya  (( 𝑖, 𝑗) ∈ 𝑉, 𝑘 ∈ 𝐾, 𝑙 ∈ 𝐿 ) 𝑌 = bernilai 1 jika ada permintaan pada titik 𝑖 yang  terangkut  oleh  kendaraan 𝑘 pada rute 𝑙 , bernilai 0 jika sebaliknya ( 𝑖 ∈ 𝑉, 𝑘 ∈ 𝐾, 𝑙 ∈ 𝐿 )

## Fungsi Tujuan
Fungsi  tujuan  dari  model  VRP  yang dikembangkan  pada  penelitian  ini  adalah multi objective function yang bertujuan meminimumkan total  jarak  tertempuh  ( total  cost ,  TC)  dan  total penyelesaian  waktu  perjalanan  ( total  completion time , TCT), sehingga perlunya membentuk jumlah tertimbang  ( weight  sum )  pada  fungsi  tujuan seperti persamaan (1).
min 𝑓(𝜃) = 𝜔 𝑇𝐶(𝜃) + 𝜔 𝑇𝐶𝑇(𝜃) …(1)
Dimana 𝜃 adalah  solusi,  sedangkan 𝜔 dan 𝜔 adalah bobot untuk masing-masing fungsi tujuan 𝑇𝐶 persamaan (2) dan 𝑇𝐶𝑇 persamaan (3).
𝑇𝐶 = 𝑐 𝑋 ∈ ∈ ∈ … (2)
Tabel 1. Data titik TPS Sektor Krasak
No. Lokasi TPS Volume (m 3 ) Kode TPS 1 DLH Kota Yogyakarta - Depot 2 TPS Herman Yohanes 2 T1 3 Perikanan Sagan 1 T2 4 TPS Wardani 1 T3 5 Barat Jembatan Layang 1 T4 6 TPS Atmosukarto 2 T5 7 Jl. Krasak Barat 3 T6 8 Jl. Kusbini 9 T7 9 TPS Kusbini I 2 T8 10 Jl. Ungaran 2 T9 11 Jl. I Nyoman Oka 3 T10 12 Jl. Patimura 1 T11 13 TPS Johar Muhadi 2 T12 14 TPS Hadi Darsono 2 T13 15 TPS Urip Sumoharjo 2 T14 16 TPS Munggur 3 T15 17 Belakang Duta Foto 2 T16 18 TPS SD Klitren 1 T17 19 TPS Kowilhan 2 T18 20 TPS Tribrata 3 T19 21 TPS Kusbini II 1 T20 22 Jl. Balapan 6 T21 23 TPS SMA 3 3 T22 24 TPS Telkom 1 T23 25 Komplek Pamungkas 3 T24 26 Jl. Merbabu (RRI Jogja) 15 T25 27 TPS Sagan 32 D1 28 TPS Pengok (Rel Kereta) 32 D2 29 TPA Piyungan - TPA
𝑇𝐶𝑇 = 𝐶𝑇
∈
… (3)
Persamaan  (1)  merupakan  total  jarak tertempuh oleh kendaraan dengan bobot 𝜔 yang dijumlahkan  dengan  total  penyelesaian  waktu perjalanan  dengan  bobot 𝜔 ; dimana  total penyelesaian waktu
perjalanan adalah penjumlahan  dari  total  waktu  perjalanan persamaan  (4)  dan  total  waktu  pelayanan persamaan (5) yang dihitung berdasarkan jumlah terangkut dan waktu pelayanan untuk loading dan unloading muatan.
𝑆 = (𝑝 + 𝑞) 𝑑 𝑌 ∈ … (4)
𝐶𝑇 = 𝑡 ∈ 𝑋 + 𝑆 ∈ ∈ , ∀𝑘 ∈ 𝐾 … (5)
Batasan Model
𝑋 ∈ ≥ 𝑌
∈ , ∀𝑗 ∈ 𝑉
∈ … (6)
𝑋 ∈ − 𝑌 ∈ = 0, ∀𝑘 ∈ 𝐾
… (7)
𝑋 ∈
= 1, 𝑋 ∈ = 1, ∀𝑘 ∈ 𝐾 … (8)
𝑑 ∈ 𝑌 ≤ 𝑄 , ∀𝑘 ∈ 𝐾 … (9)
𝑋 , , ∈ = 1, ∀𝑘 ∈ 𝐾 … (10) 𝑋 , , ∈ = 1, ∀𝑘 ∈ 𝐾 … (11)
𝑋 = 𝑋 , ∀𝑖 ∈ 𝑉, ∀𝑘 ∈ 𝐾 … (12)
𝑋 ∈ = 𝑋 ∈ , ∀𝑒 ∈ 𝑉 , ∀𝑘 ∈ 𝐾; 𝑖, 𝑗 ≠ 𝑒 … (13) 𝐶𝑇 ≤ 𝑇 … (14) 𝑑 ∈ 𝑌 ≥ 0, ∀𝑖 ∈ 𝑉, ∀𝑘 ∈ 𝐾 … (15) 𝑋 ∈ {0,1}, ∀𝑖𝑗 ∈ 𝑉, ∀𝑘 ∈ 𝐾 … (16)
𝑌 ∈ {0,1}, ∀𝑖𝑗 ∈ 𝑉, ∀𝑘 ∈ 𝐾 … (17)
Batasan  (6)  menjamin  bahwa  titik 𝑖 paling tidak  dilayani  sebanyak  1  kali  selama  rute perjalanan.  Batasan  (7)  menjamin  bahwa kendaraan akan meninggalkan titik layanan yang telah dilayani. Batasan (8) menjamin bahwa setiap rute  kendaraan  berawal  dan  berakhir  di  depot. Batasan  (9)  menjamin  bahwa  muatan  rute kendaraan 𝑘 tidak  melebihi  kapasitas  kendaraan 𝑄𝑘 .  Batasan  (10)  menjamin  bahwa  setiap kendaraan  melakukan  unloading  muatan  pada intermediate  facility .  Batasan  (11)  mengijinkan kendaraan  memulai  rute  baru  dari intermediate facility selama  batas  waktu  masih  mencukupi. Batasan  (12)  dan  (13)  memungkinkan  suatu  titik layanan 𝑖 untuk dikunjungi lebih dari satu kali oleh kendaraan  dengan  rute  berbeda.  Batasan  (14) menjamin bahwa waktu penyelesaian kendaraan 𝑘 tidak melebihi batas waktu maksimal 𝑇 . Batasan (15)  menjamin  bahwa  muatan  kendaraan 𝑘 tidak negatif. Batasan (16) dan (17) merupakan variabel keputusan bilangan biner.

## Hybrid Genetika Algoritma (GA)
GA  adalah  algoritma  yang  berbasis  inspirasi alam. Pada prinsipnya, GA menirukan teori evolusi Charles  Darwin  yang  berupaya  menghasilkan generasi  (solusi)  terbaik  dalam  populasi  secara alami melalui seleksi alam.
Hybrid GA yang digunakan pada penelitian ini menggunakan  teknik split (Baker  &  Ayechew, 2003) pada tahap evaluasi VRP dan algoritma local search setelah  tahap  evaluasi  (Moscato  &  Cotta, 2003).  Sedangkan  pada  tahapan  lainnya  seperti seleksi, crossover ,  dan  mutasi  menggunakan teknik  yang  disebut  dengan Roulette  Wheel’s Selection (RWS), Multiplepoint  Crossover ,  dan Scramble  Mutation ;  dengan  parameter  GA  yang digunakan adalah 100 populasi dan 25.000 iterasi.
Istilah  kromosom  atau  individu  dalam  GA adalah  representasi  solusi  dari  persoalan  yang akan  diselesaikan.  Umumnya  kromosom  atau individu GA pada VRP ditampilkan dalam bentuk giant tour atau non-binary representation . Proses Hybrid GA berlangsung secara iteratif dimana setiap iterasi menghasilkan generasi baru yang akan menggantikan generasi terdahulu yang dianggap  sebagai  generasi  atau  solusi  dengan kualitas  ( fitness )  buruk.  Adapun  diagram  alir
tahapan GA pada penelitian ini dapat dilihat pada Gambar 1 (Sharma & Mehta, 2013).
Berdasarkan  Gambar  1,  tahapan Hybrid GA dimulai dengan pembangkitan inisialisasi populasi, yaitu  pembangkitan  sejumlah  solusi  secara  acak yang disebut dengan kromosom yang merupakan representasi dari persoalan yang akan diselesaikan.
Tahap berikutnya adalah evaluasi setiap solusi awal yang telah dibangkitkan menggunakan teknik Split untuk menentukan nilai fitness atau kualitas masing-masing  solusi.  Demi  menghasilkan  solusi yang lebih baik, penelitian ini mengembangkan GA dengan  menambahkan  algoritma local  search setelah setiap tahap evaluasi.
Sesuai dengan nama algoritma tersebut, local search dapat  berarti  algoritma  yang  berupaya mencari ( search ) atau memperbaiki sub-rute ( local ) untuk solusi yang telah diperoleh.
Tahap  berikutnya  dilanjutkan  pada  tahap seleksi  individu  atau  tahap  untuk  menentukan parents menggunakan  teknik Roulette  Wheel’s Selection (RWS).  Kromosom  di  dalam  populasi akan diurutkan berdasarkan nilai fitness terburuk. Dua  kromosom  akan  dipilih  secara  acak  dan kromosom dengan nilai fitness besar (buruk) akan
memiliki persentase terpilih lebih besar.
Parents yang  telah  ditentukan  akan dikawinkan  silang  dengan  teknik multiple  point crossover .  Dua  titik  dari parent pertama  akan ditukarkan  dengan  bagian parent kedua,  hasil crossover disebut sebagai child . Jika child adalah hasil dari pertukaran bagian dua  kromosom  yang  disebut parents .  Tahap mutasi adalah penukaran bagian kromosom yang dilakukan secara individual, yaitu setiap child yang telah  dihasilkan  dari crossover akan  dimutasi dengan teknik scramble mutation . Hasil dari mutasi menghasilkan individu baru yang disebut  sebagai offsprings . Offsprings yang telah  ditentukan  kemudian  dievaluasi  kembali menggunakan teknik split dan diperbaiki dengan algoritma local search . Tahap  berikutnya  adalah  memperbarui generasi  atau  populasi  ( elitism )  dengan  cara mengganti  kromosom  yang  memiliki  kualitas terburuk didalam populasi dengan offspring s yang memiliki kualitas fitness lebih baik. Sebab GA berlangsung secara iteratif, proses GA akan berhenti jika iterasi pada GA memenuhi kondisi berhenti ( terminating condition ) dan solusi yang  ditentukan  setelah  GA  berakhir  adalah kromosom atau solusi dengan nilai fitness terbaik.

## III. H ASIL DAN P EMBAHASAN
Hybrid GA diimplementasi kedalam perangkat  lunak  Matlab  R2018a  dan    dijalankan sebanyak  10  kali  pada  komputer  dengan spesifikasi Windows 10 (64-bit) Processor Intel(R)
Core(TM) i5-8250 @1,6Ghz dan RAM 4GB. Berdasarkan hasil penyelesaian menggunakan Hybrid GA  yang  dibandingkan dengan  algoritma Particle  Swarm  Optimization (PSO),  nilai  fungsi  tujuan  paling  minimum didapatkan ketika Hybrid GA dijalankan ke-3 dan ke-4 dengan nilai fungsi tujuan yang sama, yaitu sebesar 307.176 dengan waktu komputasi 129,18 detik  (2,15  menit)  dan  135,19  detik  (2,25  menit), dengan  rata-rata  waktu  komputasi  155,86  detik (2,60 menit).
Sedangkan  nilai  fungsi  tujuan  paling minimum yang diperoleh menggunakan PSO yang dijalankan  sebanyak  10  kali  adalah  ketika  PSO dijalankan ke-7, dengan nilai fungsi tujuan sebesar 315.611  dengan  waktu  komputasi  1.240,22  detik (20,67  menit),  dan  rata-rata  waktu  komputasi
Selesai Ya Tidak Seleksi Parents Crossover untuk
menghasilkan Children Mutasi untuk menghasilkan Offspring Menghitung nilai fitness Offspring (evaluasi) Memperbarui generasi ( elitism) Mulai Pembangkitan Inisial Populasi Menghitung Nilai fitness Individu (evaluasi) Memenuhi Kondisi Berhenti? Memperbaiki solusi dengan
Local Search (LS)
Memperbaiki solusi dengan Local Search (LS)
Gambar 1. Diagram Alir Tahapan Hybrid GA
302,44  detik  (23,85  menit).  Adapun  parameter yang  digunakan  dalam  menjalankan  PSO  adalah dengan 100 partikel dan 25.000 iterasi.
Tabel 2. Hasil Penyelesaian Menggunakan Hybrid GA
dan PSO Dijalankan ke- Hybrid GA PSO Nilai Fungsi Tujuan Waktu Komputasi (detik) Nilai Fungsi Tujuan Waktu Komputasi (detik) 1 307.237 163,35 318.120 1.536,80 2 307.196 136,80 319.711 1.756,40 3 307.176 129,18 316.526 1.646,90 4 307.176 135,19 315.721 1.355,30 5 309.474 145,28 318.170 1.626,90 6 307.790 202,83 317.847 1.348,41 7 308.015 148,22 315.611 1.240,22 8 308.132 201,92 317.953 1.314,69 9 307.734 144,33 317.720 1.319,96 10 307.686 151,50 320.315 1.163,20
Berdasarkan  solusi  yang  didapatkan  pada Tabel 2, Gambar 2 dan 3 menunjukkan grafik nilai fungsi  tujuan  dan  nilai  rata-rata  fungsi  tujuan ketika  GA  dijalankan  ke-3  dan  ke-4.  Sedangkan Gambar 4 menunjukkan grafik nilai fungsi tujuan dan  nilai  rata-rata  fungsi  tujuan  ketika  PSO dijalankan ke-7.
Pada  Gambar  2  dapat  dilihat  bahwa  nilai fungsi  tujuan  yang  diperoleh  mencapai  kondisi steady state ketika memasuki iterasi ke 15.000 dan seterusnya. Sedangkan nilai rata-rata fungsi tujuan dari  100  populasi  mencapai  kondisi  konvergen ketika memasuki iterasi ke 20.000 dan seterusnya.
Gambar 2. Grafik Nilai Fungsi Tujuan Vs. Nilai Rata-rata Fungsi Tujuan GA ketika dijalankan ke-3
Sedangkan  Gambar  3  menunjukkan  bahwa kondisi steady state dalam proses pencarian nilai
fungsi tujuan baru terjadi ketika mendekati iterasi ke 25.000 dengan nilai rata-rata fungsi tujuan dari 100  populasi  belum  sempat  mencapai  kondisi konvergen.
Gambar 3. Grafik Nilai Fungsi Tujuan Vs. Nilai Rata-rata Fungsi Tujuan GA ketika dijalankan ke-4
Gambar  4  menunjukkan  bahwa  pencarian nilai  fungsi  tujuan  paling  minimum  ketika  PSO dijalankan  ke-7  mengalami  kondisi steady  state untuk  perolehan  nilai  fungsi  tujuan  terbaik  yang terjadi setelah memasuki iterasi ke 10.000 hingga seterusnya. Sedangkan nilai rata-rata fungsi tujuan dari  100  partikel  yang  digunakan,  menunjukkan bahwa nilai fungsi tujuan dari setiap partikel terus berubah  setiap  iterasinya  sehingga  tidak menunjukkan tanda-tanda konvergensi.
Gambar 4. Grafik Nilai Fungsi Tujuan Vs. Nilai Rata-rata Fungsi Tujuan PSO dijalankan ke-7
Tabel  3  berikut  adalah  rekapitulasi  solusi penentuan
rute
penugasan
kendaraan pengangkutan  sampah  Kota  Yogyakarta  pada
Sektor Krasak.
Berdasarkan hasil rekapitulasi penentuan rute penugasan  kendaraan  pengangkutan  sampah Kota  Yogyakarta  khususnya  pada  Sektor  Krasak seperti yang dapat dilihat pada Tabel 3, total jarak tertempuh dari seluruh kendaraan adalah 611.910 meter  (611,91  Km)  dengan  total  waktu penyelesaian  kendaraan  paling  maksimal  adalah 302  menit,  jumlah  perjalanan  yang  diciptakan adalah 31 trip, dan total sampah terangkut adalah 138m 3 atau  setara  dengan  volume  sampah  yang harus  terangkut  dari  Sektor  Krasak.  Sedangkan jumlah  jarak  tertempuh  paling  jauh  dan  waktu penyelesaian  paling  lama  ditempuh  oleh kendaraan  5  dengan  jarak  tertempuh  adalah 85.450 meter (85,45 km) dan waktu penyelesaian adalah 298 menit.

## IV. S IMPULAN
Penelitian  ini  berhasil  mengembangkan model  VRP  untuk  menyelesaikan  persoalan penentuan  rute  pengangkutan  sampah  Kota Yogyakarta  dengan  mempertimbangkan  batasan seperti heterogeneous  fleet , multiple  trip , intermediate facility dan split delivery . Sedangkan metode  GA  yang  digunakan  pada  penelitian  ini berhasil  menyelesaikan  VRP  dengan  titik
kunjungan yang banyak dan dengan batasan yang lebih  kompleks.  GA  yang  dikembangkan  dengan algoritma Local  Search (LS)  pada  penelitian  ini lebih  efektif  dan  lebih  efisien  dibanding  dengan algortima  PSO  dari  segi  pencarian  nilai  fungsi tujuan paling minimum dan waktu komputasi.

## R EFERENCES
Angelelli, E., Speranza, M.G. (2002). The periodic vehicle routing  problem  with  intermediate  facilities. European Journal of Operational Research, 137 (2), 233–247.
Arinalhaq, F., Imran, A., Fitria, L. (2013). Penentuan Rute
Kendaraan Pengangkutan Sampah Dengan Menggunakan  Metode  Nearest  Neighbour. Jurnal Online Institut Teknologi Nasional, 1 (1).
Arvianto,  A.,  Setiawan,  A.H.,  Saptadi,  S.  (2014).  Model Vehicle Routing Problem dengan Karakteristik Rute Majemuk, Multiple Time Windows, Multiple Products dan  Heterogeneous  Fleet  untuk  Depot  Tunggal. Jurnal Teknik Industri, 16 (2), 83–94.
Baker, B.M., Ayechew, M.A. (2003). A genetic algorithm for  the  vehicle  routing  problem. Computers  & Operations Research, 30 (5), 787–800. Bell, J.E., McMullen, P.R. (2004). Ant colony optimization techniques  for  the  vehicle  routing  problem. Advanced Engineering Informatics, 18 (1), 41–48.
Tabel 3. Rekapitulasi Penentuan Rute Penugasan Kendaraan untuk Pengumpulan dan Pengangkutan Sampah Kota
Yogyakarta di Sektor Krasak No.  Kendaraan Jenis Kendaraan Rute Total Trip Kendaraan Total Jarak Tertempuh (meter) Total Waktu Penyelesaian (menit) Total Volume Terangkut (m³) 1 AB 8396 UA Compactor Depot-T17-T7-TPA-T9-T25- TPA-Depot 3 60.110 277 20 2 AB 8127 UA Compactor Depot-T21-T16-T14-TPA-T10- T11-T25-TPA-Depot 3 58.830 283 20 3 AB 8336 UA Dump Truck Depot-T15-T19-TPA-T6-T24- TPA-Depot 3 58.300 233 12 4 AB 8163 UA Dump Truck Depot-D2-T20-T8-T4-TPA- T10-T22-T23-T5-TPA-Depot 3 58.190 226 12 5 AB 8247 UA Dump Truck Depot-D2-TPA-D1-TPA-T18- TPA-Depot 4 85.450 302 14 6 AB 8133 UA Dump Truck  Depot-D2-TPA-D1-TPA-Depot 3 57.950 223 12 7 AB 8020 IA Dump Truck  Depot-D2-TPA-D1-TPA-Depot 3 57.950 223 12 8 AB 8049 UA Dump Truck  Depot-D2-TPA-D1-TPA-Depot 3 57.950 223 12 9 AB 8300 UA Dump Truck  Depot-D2-TPA-D1-TPA-Depot 3 57.950 223 12 10 AB 8246 UA Dump Truck Depot-T1-T2-D1-TPA-T5-T12- T13-T3-TPA-Depot 3 59.230 229 12 Total 31 611.910 2.442 138
Cheng,  A.,  Yu,  D.  (2013). Genetic algorithm for vehicle routing  problem .  In  ICTE  2013:  Safety,  Speediness, Intelligence,  Low-Carbon,  Innovation  (pp.  2876– 2881).
Eminugroho,  R.S.,  Dwi,  L.  (2013).  Optimasi  Sistem Pengangkutan Sampah di Kota Yogyakarta dengan Model  Vehicle  Routing  Problem  Menggunakan Algoritma Sequential Insertion. Jurnal SAINTEK,  19 , 31–40.
Fitria,  L.,  Susanty,  S.,  Suprayogi,  S.  (2009).  Penentuan Rute Truk Pengumpulan dan Pengangkutan Sampah di Bandung. Jurnal Teknik Industri, 11 (1), 51–60.
Fukasawa,  R.,  Longo,  H.,  Lysgaard,  J.,  de  Aragão,  M.P., Reis,  M.,  Uchoa,  E.,  Werneck,  R.  F.  (2006).  Robust branch-and-cut-and-price  for  the  capacitated vehicle routing problem. Mathematical Programming, 106 (3), 491–511.
Golden, B., Assad, A., Levy, L., Gheysens, F. (1984). The fleet  size  and  mix  vehicle  routing  problem. Computers & Operations Research, 11 (1), 49–66. Republik  Indonesia.  (2008). Undang-Undang  No.  18 Tahun  2008  tentang  Pengelolaan  Sampah .  Jakarta: Sekretariat Negara.
Indrawati, Eliyati, N., Lukowi, A. (2016). Penentuan Rute Optimal  pada  Pengangkutan  Sampah  di  Kota Palembang  dengan  Menggunakan  Metode  Saving Matrix. Jurnal Penelitian Sains, 18 (3).
Izar,  S.  (2018).  Model  Multi  Depot  Vehicle  Routing Problem dengan Split Delivery dan Time Windows.
Jiang,  J.,  Ng,  K.M.,  Poh,  K.L.,  Teo,  K.M.  (2014).  Vehicle routing  problem  with  a  heterogeneous  fleet  and time windows. Expert Systems with Applications, 41
(8), 3748–3760.
Lestari,  H.P.  (2013).  Penerapan  algoritma  koloni  semut untuk  optimisasi  rute  distribusi  pengangkutan sampah di kota Yogyakarta. Jurnal Sains Dasar, 2 (1). Liu,  S.,  Huang,  W.,  Ma,  H.  (2009).  An  effective  genetic algorithm for the fleet size and mix vehicle routing problems. Transportation Research Part E: Logistics and Transportation Review, 45 (3), 434–445. Moscato,  P.,  Cotta,  C.  (2003). A  gentle  introduction  to memetic algorithms . In Handbook of metaheuristics (pp. 105–144). Springer.
Nugraha,  D.C.A.,  Mahmudy,  W.F.  (2015). Optimasi Vehicle Routing Problem with Time Windows Pada Distribusi  Katering  Menggunakan  Algoritma Genetika . Prosiding SESINDO 2015. Pakusadewa,  P.G.,  Dewi,  C.,  Wihandika,  R.C.  (2017). Penerapan  Hibridisasi  Algoritme  Genetika  dan Simulated  Annealing  untuk  Optimasi  Vehicle Routing Problem pada Kasus Pengangkutan Sampah Kota  Denpasar. Jurnal  Pengembangan  Teknologi
Informasi  Dan  Ilmu  Komputer E-ISSN,  2548 (February), 964X.
Prins,  C.  (2002).  Efficient  heuristics  for  the heterogeneous  fleet  multitrip  VRP  with  application to  a  large-scale  real  case. Journal  of  Mathematical Modelling and Algorithms, 1 (2), 135–150. Prins,  C.  (2009).  Two  memetic  algorithms  for heterogeneous  fleet  vehicle  routing  problems. Engineering Applications of Artificial Intelligence, 22 (6), 916–928.
Priyandari,  Y.  (2008).  Alogaritma  Sequential  Insertion untuk  Memecahkan  Vehicle  Routing  Problem dengan  Multiple  Trips,  Time  Window  dan Simultaneous Pickup Delivery. Performa, 7 (1), 88–96. Ray, S., Soeanu, A., Debbabi, M., Boukhtouta, A., Berger,
J. (2012). Modeling multi-depot split-delivery vehicle routing  problem .  The  Proceedings  of  the  IEEE- Cenference on Computation Engineering in System Applications.
Sharma,  A.,  Mehta,  A.  (2013).  Review  paper  of  various selection methods in genetic algorithm. International  Journal  of  Advanced  Research  in Computer Science and Software Engineering, 3 (7), 1476–1479.
Wibisono, E. (2018). Logika Logistik: Teknik dan Metode Pemrograman dalam Problem-problem Pengaturan Rute . Surabaya: Graha Ilmu.