Penyelesaian Capacitated Vehicle Routing Problem Menggunakan Pengembangan Algoritma Clarke and Wright Savings

Abstract

Permasalahan penentuan rute distribusi merupakan suatu permasalahan yang harus diperhatikan agar biaya distribusi yang dihasilkan lebih rendah. Permasalahan ini dapat disebut sebagai Vehicle Routing Problem (VRP). Salah satu varian VRP yang populer digunakan adalah Capacitated Vehicle Routing Problem (CVRP) yaitu VRP yang berkaitan dengan kendala kapasitas. CVRP ini dapat diselesaikan menggunakan algoritma Clarke and Wright Savings. Penyelesaian menggunakan algoritma ini didasari pada nilai penghematan dari dua titik pelanggan yang akan dilayani jika keduanya dilayani sekaligus dalam rute yang sama. Namun, algoritma ini hanya memperhatikan nilai penghematan dari kedua titik saja sehingga hasil algoritma hanya berupa kelompok rute dan perlu diperbaiki ulang urutannya menggunakan algoritma lain. Pengembangan dilakukan dengan mengubah cara penentuan rute berdasarkan nilai penghematan dengan menggunakan konsep head dan tail serta menambahkan batasan waktu operasional distribusi. Pengembangan bertujuan agar hasil dari algoritma merupakan sebuah urutan rute yang tidak perlu diperbaiki ulang menggunakan algoritma lain. Algoritma yang telah dikembangkan menghasilkan solusi dengan perbaikan jarak tempuh sebesar 1,8% dan biaya sebesar 0,12% dari algoritma Clarke and Wright Savings. Selain itu, pengembangan algoritma mampu menghasilkan solusi dalam waktu 1 menit dan solusi yang dihasilkan lebih baik dibandingkan solver LINGO dengan waktu komputasi 74 jam.