## Menentukan Rute Kendaran Pengangkut Sampah Kota Yogyakarta dengan Algoritma
Cheapest Insertion Heuristic Modifikasi Route Construction
Hanifah 1 , Dian Eka Wijayanti 2 , Aris Thobirin 3 , Puguh Wahyu Prasetyo 4
1,2,3 Program Studi Matematika; 4 Program Studi Pendidikan Matematika Universitas Ahmad Dahlan, Kampus Terpadu Universitas Ahmad Dahlan, Jl. Lingkar Selatan, Tamanan, Bantul, Daerah Istimewa Yogyakarta, Indonesia 55191, Telp. (0274) 511830.
Korespondensi; Hanifah, Email: hanifah1600015026@webmail.uad.ac.id; Wijayanti, Email: dian@math.uad.ac.id; Aris Thobirin, Email: aris.thobi@math.uad.ac.id; Prasetyo, Email: puguh.prasetyo@pmat.uad.ac.id

## Abstrak
Penelitian  ini  bertujuan  untuk  menemukan  rute  perjalanan  kendaraan  pengangkut  sampah  di  Kota  Yogyakarta. Manfaat  penelitian  ini  yaitu  sebagai  bahan  evaluasi  serta  pertimbangan  dalam  pemilihan  rute  alternatif pengangkutan sampah Kota Yogyakarta. Menggunakan metode dengan perpaduan ilmu matematika secara teori, logika pemikiran, dan ilmu komputasi dengan mengambil lokasi penelitian di Sektor Gunung Ketur yang merupakan bagian dari tanggung jawab Dinas Lingkungan Hidup Kota Yogyakarta. Teori yang digunakan yaitu penggunaan graf berupa graf berbobot dan berarah. Sedangkan algoritma yang digunakan yaitu Cheapest Insertion Heuristic (CIH) yang merupakan bagian dari algoritma Insertion dengan modifikasi Route Construction (RC) yang merupakan salah satu dari metode algoritma Artificial Immune System (AIS). Dengan demikian, penerapan ilmu matematika secara teori  dan  diperkuat  komputasi  dapat  diterapkan  secara  nyata.  Permasalahan  penentuan  jalur  tercepat  maupun efektivitas suatu perjalanan sebenarnya tidak memiliki suatu solusi yang pasti. Tentunya setiap metode memiliki pendekatan masing-masing. Namun, yang perlu diperhatikan adalah kepastian langkah yang digunakan agar langkah tersebut dapat menghasilkan output yang sama meskipun menggunakan metode pendekatan yang berbeda. Hasil yang diperoleh pun sebenarnya tidak sepenuhnya sempurna tetapi hanya menghasilkan beberapa solusi ataupun pilihan yang dapat dijadikan bahan pertimbangan untuk menyelesaikan suatu permasalahan.
Kata Kunci Cheapest Insertion Heuristic; Efektivitas; Route Contructions; Rute; Sektor Gunung Ketur.

## Abstract
This  research  aims  to  find  the  route  of  the  garbage  truck  in  Yogyakarta  City.  The  benefit  of  this  research  is  to produce the evaluation and the consideration of the selection of alternative routes for transporting the waste in Yogyakarta  City.  The  research  has  been  done  by  combining  theoretical  mathematical  science,  logic,  and computational  science  by  focusing  on  solving  the  problem  at  Gunung  Ketur  Sector,  which  is  under  the Environmental  Agency  of  Yogyakarta  City.  The  research  used  the  theory  of  weighted  and  directed  graphs. Furthermore, the researchers used the Cheapest Insertion Heuristic (CIH), which is a part of the Insertion algorithm with a modified Route Construction (RC), which is one of the methods of Artificial Immune System (AIS) algorithm. Therefore,  the  application  of  theoretical  mathematical  science  and  computationally  could  be  applied  in  a  real problem. Indeed, the determination of the fastest and the most effective routes has no concrete solutions. Each method has its own approach. However, it is crucial to consider the certainty of the procedure used to produce the same output even though using different ways. The result obtained is not entirely perfect, but the research outcome has made some solutions or alternatives as considerations to solve a problem.
Keywords Cheapest Insertion Heuristic; Effectiveness; Route Contructions; Route; Sektor Gunung Ketur.

## Pendahuluan
Perkembangan  ilmu  pengetahuan  abad 21  dan era  revolusi  industri  4.0  merupakan  suatu hal  baru yang mempengaruhi segala aspek kehidupan. Hal tersebut terlihat dari perkembangan teknologi yang semakin canggih untuk memudahkan segala macam pekerjaan manusia yang masih bersifat manual
karena keterbatasan kemampuan dalam mengerjakan beberapa hal dalam waktu bersamaan. Sementara itu  tuntutan  zaman  semakin  hari  semakin  menginginkan  adanya  perubahan  baru  supaya  pekerjaan dilakukan  dengan  cepat  dan  akurat.  Akan  tetapi,  perkembangan  ilmu  pengetahuan  dan  teknologi berbanding  terbalik  dengan  dampak  yang  dihasilkan.  Salah  satunya  turut  serta  mempengaruhi  pola pikir bahkan tingkah laku manusia dalam bersosialisasi, berinteraksi, simpati, empati, dan sikap terhadap kepedulian  lingkungan.  Kurangnya  sikap  peduli  lingkungan  terlihat  ditemukannya  sampah  yang mencemari lingkungan sehingga menimbulkan dampak negatif bagi kehidupan.
Rian Anggara Putra dalam [1] menyebutkan pengelolaan sampah di Indonesia sudah diatur dalam Undang-undang  (UU)  Nomor  18  tahun  2008  tentang  Pengelolaan  Sampah  dan  dilengkapi  dengan Peraturan Pemerintah (PP) Nomor 81 Tahun 2012 tentang Pengelolaan Sampah Rumah Tangga dan Jenis Sampah Rumah Tangga. Perwujudan dari UU dan PP tersebut yaitu dengan dibangunnya sarana prasarana seperti Tempat Pembuangan Sementara (TPS) yang meliputi landasan kontainer, depo sampah, bak sampah dan diakhiri dengan adanya Tempat Pembuangan Akhir (TPA). Tentu saja sarana prasarana tersebut didukung dengan adanya Sumber Daya Manusia (SDM) sebagai tenaga utama dan dilengkapi dengan  kendaraan  penunjang.  Akan  tetapi,  semua  tidak  akan  berjalan  dengan  maksimal  jika  tidak dilaksanakan  dan  didukung  dengan  baik  oleh  masyarakat.  Terbukti  sampah  menjadi  salah  satu permasalahan  di  kota-kota  besar  tak  terkecuali  Daerah  Istimewa  Yogyakarta  (DIY)  yang  tak  jarang dapat mengakibatkan permasalahan baru.
Data tahun 2019 menyebutkan bahwa DIY menghasilkan 644,69 ton sampah pertahun dan tertangani 583.80 ton sampah per tahun [2]. DIY merupakan salah satu provinsi di Pulau Jawa yang terdiri dari empat  kabupaten  dan  satu  kota  madya.  Dari  lima  daerah  tersebut,  daerah  yang  paling  banyak menghasilkan sampah yaitu Yogyakarta sebagai kota madya. Sementara itu, DIY memiliki Peraturan Daerah  (Perda)  yang  mengatur  pengelolaan  sampah  yaitu  Perda  DIY  No.  3  Tahun  2013  tentang Pengelolaan Sampah Rumah Tangga dan Sampah Sejenis Sampah Rumah Tangga. Sedangkan menurut Peraturan  Daerah  Kota  Yogyakarta  No.18  Tahun  2002  tentang  Pengelolaan  Sampah,  menyebutkan pengelolaan sampah menjadi tanggung jawab bersama antara Pemerintah Daerah (DLH setempat) dan masyarakat.
Pada saat ini, DLH Kota Yogyakarta membagi sistem penanganan sampah menjadi 5 sektor/wilayah, yaitu  Sektor  Gunung  Ketur,  Sektor  Ngasem-Gading,  Sektor  Krasak,  Sektor  Kotagede,  dan  Sektor Malioboro-Kranggan. Untuk Sektor Malioboro-Kranggan, DLH Kota Yogyakarta melibatkan pihak ketiga dikarenakan keterbatasan SDM. Sektor yang menarik untuk dilakukan penelitian yaitu Sektor Gunung Ketur yang terdiri atas 18 titik TPS. Sementara rute kendaraan pengangkut sampah di Sektor Gunung Ketur kurang efektif karena rute yang digunakan masih bersifat umum yang artinya rute digunakan untuk meyelesaikan semua  sektor dan tidak hanya terfokus pada satu sektor saja. Oleh karena itu, kendaraan pengangkut sampah yang digunakan akan membentuk suatu rute baru untuk menyelesaikan proses pengangkutan sampah tersebut. Tidak jarang adanya penambahan rute tersebut menyebabkan semakin jauh jarak tempuh dari rute yang sudah ditentukan sebelumnya serta tidak memaksimalkan muatan pada kendaraan yang ada. Sedangkan untuk menentukan suatu rute perjalanan yang efektif tentunya dengan memperhatikan jarak tempuh minimum sehingga mempersingkat  waktu perjalanan. Selain itu tentu saja tetap memperhatikan kapasitas muatan kendaraan yang digunakan dalam proses pengangkutan.
Ilmu  matematika  khususnya  bidang  teori  graf  mampu  merepresentasikan  kasus  penentuan  rute kendaraan pengangkutan sampah dalam menentukan efektivitas rute suatu perjalanan. Pada penelitian ini, akan dianalisis metode yang dapat diterapkan untuk menyelesaikan efektivitas rute pengangkutan sampah  dengan Cheapest  Insertion  Heuristic  (CIH).  CIH  merupakan  bagian  dari  algoritma  insertion dimana  pada  setiap  penyisipan  rute  baru  ke  dalam  subtour  mempunyai  bobot  paling  minimal. Penyisipan tersebut bertujuan untuk meminimalkan jarak tempuh dan waktu perjalanan yang dilalui kendaraan. Pada penelitian ini, peneliti memadukan dengan modifikasi Route Construction (RC) dimana peneliti mempertimbangkan titik TPS terjauh dan titik TPS terdekat berdasarkan titik TPS yang telah ditentukan oleh DLH Kota Yogyakarta. Dengan adanya modifikasi tersebut, peneliti akan menganalisis efektivitas rute kendaraan pengangkutan sampah yang telah ditentukan DLH Kota Yogyakarta.
Oleh  karena  itu,  penelitian  ini  difokuskan  terhadap  bagaimana  memahami  penerapan  teori  graf untuk menentukan efektivitas jalur tempuh kendaraan pengangkut sampah Sektor Gunung Ketur. Selain itu mampu memahami hasil penghitungan menggunakan algoritma Cheapest Insertion Heuristic (CIH)
dengan modifikasi Route Construction (RC) berdasarkan pemilihan TPS yang paling jauh dan TPS yang paling dekat untuk pengangkutan sampah Kota Yogyakarta.

## Landasan Teori
Graf  G  adalah  pasangan  himpunan  (  V,E  ) dengan  V  adalah  himpunan  tak kosong  berhingga  dari elemen yang  disebut titik  ( vertex) dan E adalah himpunan berhingga (boleh kosong) dari pasangan titik dalam V × V yang disebut sisi ( edge) [3]. Berdasarkan keterhubungan arah orientasi pada sisinya, ada dua jenis graf, yaitu graf tak berarah dan graf berarah [4]. Graf tak berarah yaitu graf yang sisinya tidak  mempunyai  orientasi  arah,  untuk  urutan  pasangan  titik  yang  dihubungkan  oleh  sisi  tidak diperhatikan. Jadi (𝑣 𝑖 , 𝑣 𝑗 = 𝑣 𝑗 , 𝑣 𝑖 ) .
Gambar 1. Contoh Graf Tak Berarah.
Graf tak berarah yaitu graf yang sisinya tidak mempunyai orientasi arah, untuk urutan pasangan titik yang dihubungkan oleh sisi tidak diperhatikan. Jadi (𝑣 𝑖 , 𝑣 𝑗 ≠ 𝑣 𝑗 , 𝑣 𝑖 ) .

## Gambar 2. Contoh Graf Berarah.
Khasanah dan Fitriani dalam [5] mengemukakan bahwa graf berbobot ( weighted graph) adalah graf yang setiap sisinya ditandai dengan bilangan bulat positif (bobot).
Marsudi dalam [3] menyatakan matriks ketetanggaan ( adjacency) dari suatu graf 𝐺 = (𝑉, 𝐸) adalah graf  berlabel  dengan 𝑉 = {  1𝑣 1 , 𝑣 2 , 𝑣 3 , . . . , 𝑣 𝑛 }. Matriks  ketetanggaan  dari 𝐺 adalah  matriks  bujur sangkar orde −𝑛 , 𝐴 =   𝑎 𝑖𝑗 dengan:
𝐴 = { 1 𝑗𝑖𝑘𝑎   𝑣 𝑖 𝑏𝑒𝑟𝑡𝑒𝑡𝑎𝑛𝑔𝑔𝑎 𝑑𝑒𝑛𝑔𝑎𝑛 𝑣 𝑗 0 𝑗𝑖𝑘𝑎 𝑣 𝑖 𝑡𝑖𝑑𝑎𝑘 𝑏𝑒𝑟𝑡𝑒𝑡𝑎𝑛𝑔𝑔𝑎 𝑑𝑒𝑛𝑔𝑎𝑛 𝑣 𝑗
Vehicle Routing Problem atau disingkat VRP didefinisikan sebagai sebuah perjalanan untuk mencari efisiensi  pengunaan  sejumlah  kendaraan  ( vehicle)  yang  harus  melakukan  perjalanan  baik  untuk mengantar  dan/atau  menjemput  orang  atau  barang.  Dengan  kata  lain,  VRP  merupakan  suatu permasalahan distribusi untuk mencari serangkaian rute untuk sejumlah kendaraan dengan kapasitas tertentu dari satu depot atau lebih untuk melayani konsumen. Biasanya setiap titik tujuan atau titik pemberhentian hanya  dilayani  satu  kali  saja dengan  mempertimbangkan  kapasitas  kendaraan  sekali angkut dengan tujuan meminimalkan biaya yang diperlukan dan berkaitan erat dengan meminimalkan jarak tempuh.
Menurut  Toth  dan  Virgo  dalam  [6]  VRP  memiliki  tujuan  seperti  meminimalkan  jarak  dan  biaya tetap yang berhubungan dengan penggunaan kendaraan, meminimalkan banyaknya kendaraan yang digunakan,  dan  juga  dapat  meminimalkan  pelayanan  yang  kurang  memuaskan  terhadap  konsumen, seperti keterlambatan pengiriman dan lain sebagainya. Salah satu kendala yang dapat mempengaruhi munculnya variasi VRP yaitu terletak pada kapasitas kendaraan atau sering disebut dengan Capacitated Vehicle Routing Problem (CVRP).
Algoritma Cheapest  Insertion  Heuristic  atau  disingkat  dengan  Algoritma  CIH  adalah  algoritma insertion  dimana  pada  setiap  penambahan  tempat  baru  (titik  baru)  yang  akan  disisipkan  ke  dalam subtour mempunyai bobot penyisipan paling minimal. Bobot penyisipan tersebut diperoleh dari jumlah titik  TPS  yang  dimiliki,  kapasitas  muatan  di  kendaraan  maupun  di  titik  TPS,  rute  serta  trip  yang dibentuk. Algoritma ini memberikan rute perjalanan yang berbeda tergantung dari urutan penyisipan kota-kota pada subtour yang bersangkutan [7].
Penyelesaian masalah penentuan rute efektif suatu perjalanan guna optimalisasi waktu menggunakan algoritma  CIH  ini  ada  beberapa  tahapan  dalam  penggunaannya.  Berikut  adalah  tahapan  dalam penggunaan algoritma CIH [7]:
1. Perjalanan dimulai dari titik kunjungan pertama yang terhubung dengan titik kunjungan terakhir.
2. Dibuat sebuah hubungan sirkuit antara kedua  titiik  tersebut. Misalkan sirkuit yang dibuat  adalah (1,3)   → (3,2)   → (2,1) maka dapat digambar sebagai berikut:
Gambar 4. Ilustrasi Rute.
3. Ganti salah satu arah hubungan (sisi) dari dua titik dengan kombinasi dua busur, yaitu sisi ( 𝑖, 𝑗 ) dengan sisi ( 𝑖, 𝑘 ) dan sisi ( 𝑘, 𝑗 ) , dengan k diambil dari daerah yang belum masuk subtour dan dengan menambahkan jarak terkecil. Jarak diperoleh dari 𝑐 𝑖𝑘 +   𝑐 𝑘𝑗 −   𝑐 𝑖𝑗 , dengan  𝑐 𝑖𝑘 adalah jarak dari titik 𝑖 ke titik 𝑘 ,
 𝑐 𝑘𝑗 adalah jarak dari titik 𝑘 ke titik 𝑗 ,  𝑐 𝑖𝑗 adalah jarak dari titik 𝑖 ke titik 𝑗 .
4. Ulangi tahapan nomor 3 hingga seluruh titik berhasil dikunjungi dan masuk dalam rute.
5. Hentikan proses jika semua titik berhasil dikunjungi dan membuat suatu rute.
Algoritma CIH sendiri telah banyak diterapkan dalam menyelesaikan permasalahan khususnya dalam bidang distribusi barang, seperti yang disampaikan dalam [8] bahwa algoritma CIH diterapkan dalam rang optimasi distribusi produk dengan berbantuan atau berbasis website. Di lain pihak, [9] menerapkan algoritma  CIH  dalam  rangka  menyelesaikan Travelling  Salesman  Problem  (TSP).  Lebih  lanjut,  [10] menggunakan  algoritma  CIH  untuk  menyelesaikan  permasalahan  tentang  bagaimana  menyisipkan pelanggan dalam rute distribusi suatu produk berdasarkan kriterianya. Sementara itu Paul dan Harvey Deitel  dalam  [11]  menyebutkan  bahwa  RC  merupakan  suatu  teknik  pengurutan  dengan  cara membandingkan dan mengurutkan dua data pertama pada array berikutnya untuk memastikan apakah array  sudah  berada  di  tempat  yang  semestinya.  Dengan  kata  lain,  algoritma  ini  digunakan  untuk mengurutkan suatu array data yang belum terurut agar menjadi  array data yang terurut dan sesuai dengan  yang  diinginkan.  Algoritma  ini  cocok  digunakan  untuk  mengurutkan  angka  yang  memiliki jumlah elemen sedikit. Teori lain yang dikemukakan oleh Dasgupta dan Nino dalam [12] bahwa RC merupakan salah satu metode algoritma Artificial Immune System (AIS) yang merupakan bagian dari algoritma genetika. Hingga saat ini, algoritma AIS banyak digunakan untuk menyelesaikan berbagai permasalahan  seperti  optimasi,  klasifikasi, clustering,  deteksi  anomali,  machine  learning,  adaptive control, dan associative memories. Secara umum, langkah-langkah yang digunakan dalam modifikasi RC adalah sebagai berikut:
1. Siapkan rute  acak yang akan digunakan untuk mengidentifikasi penyelesaian permasalahan letak titik bagi seluruh titik yang sebelumnya tidak masuk ke rute.
2. Buat tabel yang berisi data untuk melakukan perhitungan posisi titik terbaik.
3. Hasil akhir yang akan diperoleh yaitu terbentuknya sebuah rute pada tahap RC sehingga jika rute yang dihasilkan melebihi kapasitas kendaraan maka akan dilakukan ejection pool sebelum akhirnya dilanjutkan ke tahap local search. Hal ini dilakukan dengan catatan apabila rute-rute yang dihasilkan memiliki kapasitas seditit, maka pada saat ejection pool dapat digabung sengan syarat tidak melebihi kapasitas yang tersedia.

## Metode Penelitian
Penelitian  ini  dikembangkan  dengan  metode  studi  kasus  yang  bertujuan  untuk  menentukan  rute kendaraan  pengangkut  sampah  di  Sektor  Gunung  Ketur  Kota  Yogyakarta  dengan  menggunakan algoritma  CIH  dengan  memodifikasi route  construction.  Pencarian  rute  tersebut  dilakukan  untuk mendapatkan rute yang efektif dengan kriteria: meminimumkan total jarak, total waktu perjalanan, dan meminimalkan jumlah kendaraan yang digunakan untuk mengangkut sampah di Sektor Gunung Ketur Kota Yogyakarta. Data yang digunakan dalam penelitian ini diperoleh melalui wawancara dan survei sehingga diperoleh data berupa kapasitas kendaraan, data volume sampah per hari dan per sektor, rute  kendaraan  pengangkut  sampah,  jarak  tempuh  perjalanan,  dan  waktu  tempuh  kendaraan pengangkutan sampah Sektor Gunung Ketur Kota Yogyakarta. Penelitian ini termasuk penelitian yang melibatkan Vehicle  Routing  Problem  (VRP).  Dengan  memadukan  antara  penggunakaan  maka selanjutnya  akan  dibuat  suatu  logika  pemikiran  serta  pemodelan  yang  memanfaatkan  bahasa pemrograman Python untuk menganalisis pencarian rute yang efektif. Pemilihan bahasa pemrograman Python dilakukan dengan mempertimbangkan beberapa hal seperti penggunaan bahasa pemrograman yang lebih sederhana dibanding bahasa pemrograman yang lain, dan merupakan open source software, serta mendukung Internet of Things (IoT).
Gambar 5. Flowchart Logika Pemikiran.

## Hasil dan Pembahasan
Menurut  data  perencanaan  kinerja  tahun  2019  dari  Bidang  Pengelolaan  Persampahan,  DLH  Kota Yogyakarta memiliki Sumber Daya Manusia (SDM) yang terdiri dari 190 Pegawai Negeri Sipil (PNS), 19 Tenaga Bantuan (Naban), dan 231 tenaga teknis. Sementara untuk jumlah bangunan dan kendaraan yang dimiliki disajikan dalam Tabel 1 dan Tabel 2 sebagai berikut:
Tabel 1. Data Bangunan Milik DLH Kota Yogyakarta.
No Jenis TPS Jumlah 1. TPS 74 2. Landasan Kontainer 18 3. Depo 11 4. Bak Kontainer 28 5. Bak JR 2 6. Bak Sampah Induk 1 7. Kantor Sektor 8
Tabel 2. Data Kendaraan Milik DLH Kota Yogyakarta.
No Jenis TPS Jumlah 1. Dump Truck Sampah 31 2. Amrol Truck Sampah 6 3. Compactor Sampah 3 4. Road Sweeper 2 5. Mobil Pick Up 5 6. Motor Roda 3 30 7. Gerobak Sampah 54
Berdasarkan  pengumpulan  data  dengan  menggunakan  metode  wawancara  diperoleh  hasil  yang berbeda.  Dalam  kesehariannya  hanya  29 dump  truck,  5  compactor  truck,  dan  3  pick  up  yang digunakan. Sedangkan jumlah amrol truck yang digunakan sesuai dengan data kinerja tahun 2019. Akan tetapi, terdapat perbedaan jumlah bangunan milik DLH Kota Yogyakarta jika dilihat dari data perencanaan kinerja tahun 2019 dari Bidang Pengelolaan Persampahan dengan data yang diperoleh secara langsung dari penentuan rute yang sudah ditentukan.
Data utama yang digunakan dalam penelitian ini adalah data volume sampah per hari per sektor Kota Yogyakarta, dan data rute kendaraan yang digunakan DLH Kota Yogyakarta pada tahun 2019. Data  yang  diperoleh  kemudian  akan  digunakan  untuk  menentukan  jarak  antar  lokasi.  Lokasi  yang digunakan yaitu pangkalan truk Kota Yogyakarta selaku depot, TPS, dan TPA yang diterletak di Desa Ngablak, Sitimulyo, Kecamatan Piyungan, Kabupaten Bantul. Berikut disajikan peta lokasi depo/landasan kontainer Kota Yogyakarta:
Gambar  6.  Peta  Lokasi  DEPO  atau  Landasan  Kontainer  Kota.  (Sumber:  Bidang  Pengelolaan  Persampahan  DLH  Kota Yogyakarta)
Sebelum dilakukan pengujian menggunakan bahasa pemrograman, tentu terlebih dahulu dirancang suatu  logika  pemikiran penentuan  rute  kendaraan  yang  akan digunakan.  Hal  ini  penting  dilakukan agar  program  dapat  bekerja  sesuai  pemikiran  manusia.  Logika-logika  tersebut  diterjemahkan  dalam bahasa  pemrograman  supaya  dapat  diterima,  dimengerti,  dan  direpresentasikan  ke  dalam  mesin komputer yang akan dibuat seperti halnya alur sebuah cerita. Alur cerita tersebut seperti bagaimana awal  masalah  itu  terjadi,  bagaimana  cara  untuk  mengatasinya,  dan  hasil  apa  yang  didapat  saat menyelesaikan masalah tersebut.
Merepresentasikan  sebuah  graf  diperlukan  suatu  titik  dan  sisi  dari  data  titik  letak  TPS  yang digunakan.  Data  tersebut  digunakan  sebagai  titik  acuan  untuk  membentuk  rute  sebagai  sisi  yang menghubungkan  antar  titik.  Dalam  graf  ini,  rute  pengangkutan  sampah  dimulai  dari  DLH  Kota Yogyakarta, kemudian sejumlah TPS Sektor Gunung Ketur, dilanjutkan menuju TPA Piyungan untuk membuang sampah, dan berakhir di DLH Kota Yogyakarta sebagai titik akhir atau titik berhenti.
Pendefinisian penulisan tempat atau lokasi TPS yang digunakan dalam penelitian ini yaitu Sektor Gunung Ketur, maka diberikan notasi sebagai berikut:
Tabel 3. Penotasian TPS di Sektor Gunung Ketur.
Notasi Nama Lokasi Volume (m 3 ) 0 Dinas Lingkungan Hidup Kota Yogyakarta 0 1 TPS Jl. Hayam Wuruk 3,5 2 TPS Jl. Lempuyangan (Barat) 1 3 TPS Jl. Lempuyangan (Timur) 1,5 4 TPS Jl. Bausasran (Barat) 3 5 TPS Jl. Bausasran (Timur) 2 6 TPS Jl. Mangunsarkoro 6 7 TPS Jl. Cantel 1 1 8 TPS Jl. Cantel 2 1 9 TPS Jl. Cantel Baru 1 10 TPS Kowilhan 2 11 TPS Jl. Kusumanegara (UST) 5 12 TPS Jl. Juminahan (Rusunawa) 3 13 TPS Dinas Sosial Karangwaru 4,5 14 TPS Dinas Sosial Karangkajen 3 15 TPS Jl. Gajah 2 16 TPS Jl. Pramuka 4 17 TPS Asrama Brimob 2 18 TPS LP Wirogunan 2 19 TPA Piyungan 0
Data  tempat  atau  lokasi  yang  berada  di  Sektor  Gunung  Ketur disajikan  melalui  sebuah  matriks. Matriks tersebut memberikan gambaran mengenai besarnya jarak tempuh dari satu TPS menuju TPS lain. Jarak tempuh yang dihasilkan dan disajikan dalam bentuk matriks tersebut selanjutnya digunakan sebagai salah satu komponen pelengkap penyusunan algoritma penyelesaian. Selain itu, data tempat atau lokasi TPS Sektor Gunung Ketur dapat direpresentasikan pula melalui gambar graf sebagai berikut:
Gambar 7. Graf Rute Sektor Gunung Ketur.
Pada penelitian ini kendaraan yang digunakan yaitu dump truck milik DLH Kota Yogyakarta berjenis Isuzu dengan kapasitas 5-6 𝑚 3 . Selain itu, diasumsikan kendaraan pengangkut selalu dalam keadaan baik, arus kendaraan lancer, dan jumlah volume sampah tidak mengalami kenaikan secara signifikan. Penentuan jarak pada penelitian ini menggunakan google maps. Pemilihan rute dititik beratkan pada jarak terdekat pada titik keberangkatan terakhir kendaraan dan beban yang ada pada masing-masing TPS. Jika pada suatu percobaan terdapat titik dengan jarak terdekat namun beban yang tersedia pada titik tersebut tidak mampu di angkut oleh kendaraan, maka secara otomatis akan dicari titik terdekat lainnya dengan mempertimbangkan ka-pasitas sisa ruang yang ada pada kendaraan pengangkut tersebut.
Adapun komponen jarak didapat dari perhitungan jumlah jarak pada masing-masing rute perjalanan yang terbentuk dari jarak TPS satu ke TPS yang lain. Pada beberapa output jika ditemukan adanya beberapa hal yang sama baik dalam kapasitas beban terangkut serta jarak, maka langkah selanjutnya keputusan  akan  diambil  berdasarkan  waktu  tempuh.  Perhitungan  waktu  tempuh  ini  didapatkan  dari jumlah jarak pada setiap rute perjalanan dibagi dengan kecepatan kendaraan pengangkut sampah yang digunakan yaitu 35 km/jam kemudian dikalikan dengan 60 yang merupakan satuan jumlah jam dalam menit.  Satuan  jarak  yang  digunakan  yaitu  km,  satuan  beban  yang  digunakan  yaitu  m 3 dan  satuan waktu yang digunakan yaitu menit.
Berikut merupakan langkah yang digunakan dalam pemanfaatan bahasa pemrograman Python: 1. Membuat dan menyusun suatu fungsi untuk membuang kemungkinan mengunjungi jalur yang sama. Dengan kata lain, setiap titik TPS hanya berlaku maksimal satu kali kunjungan.
2. Membuat suatu fungsi untuk  membaca node dengan mengubah fungsi berbasis bilangan tertentu yang sudah disesuaikan menjadi kemungkinan jalur.
3. Membuat suatu fungsi untuk menentukan semua jalur yang mungkin terjadi. Pada tahap ini akan disajikan maksimal jalur yang mungkin terbentuk.
4. Membuat  suatu  fungsi  untuk  menghitung  berat  angkut  kendaraan,  jarak  tempuh  kendaraan,  dan waktu tempuh.
5. Input data berupa jarak dari masing-masing titik TPS dan beban yang terdapat pada masing-masing titik TPS. Data tersebut diinput secara manual dalam bentuk matriks.
6. Membuat suatu fungsi untuk mempertimbangkan syarat dalam mere-presentasikan permasalahan ke dalam algoritma yang digunakan.
7. Membuat suatu fungsi untuk membaca rute pilihan yang sudah terbentuk. Tahap ini dibuat untuk menyempurnakan langkah awal yaitu langkah nomor satu sekaligus menginformasikan titik mana saja yang sudah dikunjungi.
8. Pada tahap terakhir, dibuat suatu fungsi untuk menolak jalannya program yang sudah disusun jika kemungkinan jalur yang diinginkan terlalu sedikit.
Pada saat melakukan operasi hitung dengan menjalankan algoritma yang sudah terbentuk, peneliti melakukan beberapa literasi untuk memperoleh hasil berupa kunjungan pada semua titik TPS. Pada
literasi tersebut tentu saja menghasilkan beberapa array output yang jumlahnya tidak sedikit. Hal itu terjadi  karena  ketika  sudah  diplih  rute  yang  akan  digunakan  maka  setelahnya  akan  dilakukan  run kembali hingga semua titik TPS berhasil dikunjungi dan program berhenti berjalan.
Dari hasil penghitungan pada masing-masing titik antara titik awal depo dengan titik akhir maka diperoleh hasil berupa rute kendaraan pengangkut sampah yaitu sebagai berikut:

## Tabel 4. Hasil Uji Menggunakan Algoritma CIH dengan Modifikasi RC
Berat (m 3 ) Jarak (Km) Waktu (Menit) Rute Penggunaan Kapasitas Kendaraan (%) 6 68,4 117,2571 0 – 6 – 19 100 % 6 27,6 47,3142 19 - 3 - 13 – 19 100 % 6 25,9 44,4 19 – 7 – 8 – 16 – 19 100 % 6 25,4 43,5428 19 - 5 - 15 - 17 – 19 100 % 5,5 27,0 46,2857 19 – 18 – 1 – 19 91, 67  % 6 26,1 44,7428 19 - 9 - 11 – 19 100 % 6 26,2003 44,9142 19 – 12 – 4 – 19 100 % 6 29,2997 50,2285 19 - 2 - 10 - 14 – 19 100 % 0 9,5 16,285 19 – 0 0 %

## Kesimpulan dan Saran
Berdasarkan hasil penelitian dan penghitungan komputasi menggunakan bahasa pemrograman Python maka dapat ditarik kesimpulan rraf yang dihasilkan dalam representasi rute jalur dan tata letak TPS milik Dinas Lingkungan Hidup (DLH) Kota Yogyakarta yaitu graf berarah dengan label bilangan positif berupa waktu tempuh dan jarak dari satu TPS ke TPS lain. Dalam representasi tersebut, terdapat 28 titik dan 27 sisi. Representasi graf tersebut tentunya dapat diaplikasikan untuk menyederhanakan jarak dan  waktu  dalam  menentukan  efektifitas  suatu  perjalanan  kendaraan  pengangkut  sampah  Kota Yogyakarta.  Hasil  penghitungan  menggunakan  algoritma Cheapest  Insertion  Heuristic  (CIH)  dengan modifikasi Route Construction (RC) berdasarkan pemilihan TPS yang paling jauh dan TPS yang paling dekat untuk pengangkutan sampah Kota Yogyakarta diperoleh sebagai berikut:
a. DLH Kota Yogyakarta - TPS Jl. Mangunsarkoro - TPS Piyungan.
b. TPA Piyungan - TPS Jl. Lempuyangan (Timur) - TPS Dinas Sosial Karangwaru - TPA Piyungan.
c. TPA Piyungan - TPS Jl. Cantel 1 - TPS Jl. Cantel 2 - TPS Jl. Pramuka - TPA Piyungan.
d. TPA Piyungan - TPS Jl. Bausasran (Timur) - TPS Jl. Gajah - TPS Asrama Brimob - TPA Piyungan.
e. TPA Piyungan - TPS LP Wirogunan - TPS Jl. Hayam Wuruk -TPA Piyungan.
f. TPA Piyungan - TPS Jl. Cantel Baru - TPS Jl. Kusumanegara (UST) - TPA Piyungan.
g. TPA Piyungan - TPS Jl. Juminahan (Rusunawa) -TPS Jl. Bausasran (Barat) - TPA Piyungan.
h. TPA Piyungan - TPS Jl. Lempuyangan (Barat) - TPS Kowilhan - TPS Dinas Sosial Karangkajen - TPA Piyungan.
i. TPA Piyungan - DLH Kota Yogyakarta.
Pada penelitian selanjutnya dengan tema yang sama diharapkan dapat menggunakan metode lain untuk  menentukan  titik  dalam  satu  rute,  memperluas  komponen-komponen  yang  digunakan  seperti biaya,  dan  dilakukan  penyempurnaan  dan  perbaikan  secara  komputasi  baik  menggunakan  bahasa pemrograman yang sama maupun berbeda sehingga dapat menghasilkan simulasi efektivitas rute dan dapat menghasilkan simulasi graf sesuai dengan letak sebenarnya sesuai dengan yang diharapkan.

## Ucapan Terimakasih
Penulis mengucapkan terimakasih kepada Bappeda Kota Yogyakarta atas bantuan serta ijin serta data yang diberikan sehingga penelitian ini dapat dilaksanakan dengan lancar. Peneliti juga mengucapkan terimakasih kepada Fakultas Sains dan Teknologi Terapan dan Fakultas Keguruan dan Ilmu Pendidikan atas segala dukungan dalam yang bersifat administratif dalam penelitian ini.

## Referensi
[1] R. A. Putra, “Efektivitas Metode Sequential Insertion dan Metode Nearest Neighbor dalam Penentuan Rute Kendaraan Pengangkut Sampah di Kota Yogyakarta,” Universitas Negeri Yogyakarta, 2014.
[2] Badan Perencanaan Pembangunan
Daerah DIY, “Pengelolaan Sampah,” Report , 2020.
http://bappeda.jogjaprov.go.id/dataku/data_dasar/index/208-pengelolaan-sampah?id_skpd=25.
[3] Marsudi, Teori Graf . Malang: Universitas Brawijaya Press, 2016.
[4] T. Harju, Graph Theory . Turku: Mathematics Department, University of Turku, 2012.
[5] U. Khasanah and H. Fitriyani, Matematika Diskret . Yogyakarta: JPMIPA FKIP Universitas Ahmad Dahlan, 2012.
[6] D. Vigo and P. Toth, Vehicle Routing . 2014.
[7] A. Priyanto, “Algoritma Cheapest Insertion Heuristic Untuk Menyelesaikan Asymmetric Traveling Salesman Problem,” Universitas Negeri Yogyakarta, 2009.
[8] K. Meliantari, D. Putra Githa, and N. K. Ayu Wirdiani, “Optimasi Distribusi Produk Menggunakan Metode Cheapest Insertion  Heuristic  Berbasis  Web,” J.  Ilm.  Merpati  (Menara  Penelit.  Akad.  Teknol.  Informasi) ,  2018,  doi: 10.24843/jim.2018.v06.i03.p07.
[9] R. G. Utomo, D. S. Maylawati, and C. N. Alam, Implementasi Algoritma Cheapest Insertion Heuristic (CIH) dalam Penyelesaian Travelling Salesman Problem (TSP),” J. Online Inform. , 2018, doi: 10.15575/join.v3i1.218.
[10] M. Alssager, Z. A. Othman, and M. Ayob, “Cheapest insertion constructive heuristic based on two combination seed customer  criterion  for  the  capacitated  vehicle  routing  problem,” Int.  J.  Adv.  Sci.  Eng.  Inf.  Technol. ,  2017,  doi: 10.18517/ijaseit.7.1.1792.
[11] P. Deitel and H. Deitel, “Intro to Python for Computer Science and Data Science: Learning to Program with Ai, Big Data and the Cloud,” Pearson , 2019.
[12] D. Dasgupta, Artificial Immune Systems : A Bibliography,”2007.

## THIS PAGE INTENTIONALLY LEFT BLANK