Penerapan Algoritma Cheapest Insertion Heuristic dengan Sweep Clustering pada Capacitated Vehicle Routing Problem

Abstract

Industri pada masa kini berkembang sangat pesat seiring dengan kecanggihan teknologi yang semakin modern. Maka dari itu, persaingan industri juga semakin ketat. Dengan adanya persaingan itulah yang membuat setiap perusahaan harus bisa mengatur perusahaannya, salah satunya dengan proses distribusi dari perusahaan itu. Proses distribusi adalah proses pengiriman barang dari depot ke pelanggan. Penting bagi setiap perusahan karena berkaitan dengan kepuasan pelanggan yang mempengaruhi keuntungan produksi. Konsep distribusi diantaranya jarak, waktu dan harga minimum itu dipengaruhi oleh kapasitas kendaraan yang akan didistribusikan dari depot ke pelanggan, dengan begitu hal tersebut bisa merupakan kasus Capacitated Vehicle Routing Problem. Penelitian ini bertujuan untuk mendapatkan solusi permasalahan Capacitated Vehicle Routing Problem pada pendistribusian produk dengan menerapkan dua jenis algoritma yaitu Cheapest Insertion Heuristic dengan Sweep Clustering dan algoritma Cheapest Insertion Heuristic. Data yang digunakan dalam penelitian ini adalah data distribusi beras. Data ini terdiri atas sebuah depot dan 30 pelanggan. Data yang digunakan terdapat empat kriteria yang meliputi lokasi depot dan pelanggan, jumlah permintaan setiap pelanggan, jarak antar lokasi dan kapasitas kendaraan. Algoritma Cheapest Insertion Heuristic dengan Sweep Clustering menggunakan dua metode yaitu Forward Sweep dan Backward Sweep. Hasil penelitian menunjukkan bahwa dari penerapan kedua algoritma menghasilkan total jarak yang berbeda. Hasil optimal yang di dapatkan terjadi pada algoritma Cheapest Insertion Heuristic dengan Sweep Clustering. Hal ini karena secara umum jarak total minimal paling banyak didapatkan dengan menggunakan algoritma tersebut daripada jarak total minimal dengan menggunakan algoritma Cheapest Insertion Heuristic. Demikian bisa disimpulkan bahwa pada permasalahan Capacitated Vehicle Routing Problem menggunakan algoritma Cheapest Insertion Heuristic dengan Sweep Clustering lebih baik daripada hanya menggunakan algoritma Cheapest Insertion Heuristic.